带时序条件约束的线性规划线性化及求解器咨询

约束线性化方法 #

这类条件约束可以通过引入二元0-1变量转化为线性约束，具体步骤如下：

针对每个变量Xi，定义二元变量Yi（仅取0或1）：

• Yi=1 对应 sum(X₁,...,Xᵢ₋₁) > some_value 的情况
• Yi=0 对应 sum(X₁,...,Xᵢ₋₁) ≤ some_value 的情况

添加以下三组线性约束：

1. 绑定sum与Yi的逻辑关系（确保Yi=0时sum不超过some_value）：

   sum(X₁,...,Xᵢ₋₁) ≤ some_value + M*(1-Yi)
   

   其中M是一个足够大的正数（需大于sum(X₁,...,Xᵢ₋₁)的最大可能值，避免约束无效）。当Yi=0时，约束强制sum≤some_value；Yi=1时，约束因M足够大自动满足。

2. 反向绑定逻辑（确保sum>some_value时Yi必须为1）：

   sum(X₁,...,Xᵢ₋₁) ≥ some_value + ε - M*(1-Yi)
   

   其中ε是极小的正数（用于处理严格大于的数值问题）。当Yi=1时，约束等价于sum≥some_value+ε，即sum>some_value；Yi=0时，约束因M足够大自动满足。

3. 关联Xi的上限与Yi：

   Xi ≤ max_value_1*Yi + max_value_2*(1-Yi)
   

   该约束直接实现：Yi=1时Xi≤max_value_1，Yi=0时Xi≤max_value_2。

求解器支持情况 #

转化后的模型属于混合整数线性规划（MILP），主流求解器均支持这类问题：

• ortools的CP-SAT求解器或MILP模块可以直接处理，只需将Xi定义为连续变量，Yi定义为0-1整数变量，再添加上述线性约束即可。
• 其他如Gurobi、CPLEX、CBC等求解器也原生支持MILP问题的求解。

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