含逻辑函数与互斥约束的MIP/MIQP求解器选型咨询

待求解的优化问题 #

Maximize: F1(I1) + F2(I2) + F3(I3)

Subject to:
   I1 ∈ [min1, max1] ∪ {0}
   I2 ∈ [min2, max2] ∪ {0}
   I3 ∈ [min3, max3] ∪ {0}
   
   I1 + I2 + I3 ≤ Constant

   Exclusive condition: When I1 > 0 then I2 = 0, and when I2 > 0 then I1 = 0.
   *注：可能存在任意数量的此类互斥条件*

Where:
   F1(x) = {
      0.15x  if x ∈ [min1, min1 + 100]
      0.1x   if x ∈ [min1 + 101, min1 + 200]
      0.05x  if x ∈ [min1 + 201, max1]
   }
   *注：其他函数F2、F3的分段范围与系数为任意给定值*

核心困惑 #

处理互斥约束与分段线性目标函数时遇到困难，怀疑该问题超出MIP/MQP范畴，询问是否存在可处理此类场景的求解器。

解决方案与求解器推荐 #

你的问题并未超出MIP范畴，可以通过引入0-1整数变量将所有约束和目标函数转化为标准MIP形式：

1. 处理变量的“非零即区间”约束 #

对每个变量Ii，引入0-1变量yi：

• 当yi=1时，Ii ∈ [mini, maxi]
• 当yi=0时，Ii=0
  对应的约束为：

mini * yi ≤ Ii ≤ maxi * yi

2. 处理互斥约束 #

以I1和I2互斥为例，引入的0-1变量y1、y2需满足：

y1 + y2 ≤ 1

任意数量的互斥组都可以用类似方式建模，比如若I1、I2、I3三者互斥，则约束为y1 + y2 + y3 ≤ 1。

3. 处理分段线性目标函数 #

分段线性函数可以通过引入额外的0-1变量和连续变量拆解为线性约束。以F1(x)为例：

• 设x的三个分段区间对应的权重分别为w1=0.15、w2=0.1、w3=0.05，区间长度分别为L1=100、L2=100、L3=max1 - (min1+200)
• 引入连续变量x1、x2、x3，分别对应x在三个区间的取值，同时引入0-1变量z1、z2、z3表示x处于哪个区间：

  x = x1 + x2 + x3
  0 ≤ x1 ≤ L1 * z1
  0 ≤ x2 ≤ L2 * z2
  0 ≤ x3 ≤ L3 * z3
  z1 + z2 + z3 = y1  # 仅当y1=1（即x≠0）时，有一个zi=1
  z1, z2, z3 ∈ {0,1}
  

  目标函数中F1(x)的部分转化为：

  0.15x1 + 0.1x2 + 0.05x3
  

4. 适用的求解器 #

• 商业求解器：Gurobi、CPLEX、Xpress，这类求解器对大规模MIP问题的求解效率极高，支持上述所有约束形式。
• 开源求解器：Cbc（Coin-or分支定界求解器）、SCIP，其中SCIP的求解能力接近商业求解器，适合学术或非商业场景使用。

所有上述求解器都能直接处理转化后的MIP模型，无需额外定制开发。

内容的提问来源于stack exchange，提问作者Daniel