1

我正在尝试使用 Linux 中的 CBC 求解器解决 LP 问题。

当我尝试解决它时，模型被确定为线性不可行但找到了解决方案，所以我不明白为什么会这样。

这是求解器输出：

Welcome to the CBC MILP Solver 
Version: 2.10.5 
Build Date: Oct 15 2020 

command line - cbc tt2.lp solve printing csv solu sol.txt (default strategy 1)
Presolve determined that the problem was infeasible with tolerance of 1e-08
Analysis indicates model infeasible or unbounded
Perturbing problem by 0.001% of 6368.0221 - largest nonzero change 9.6555471e-05 ( 8.8302642e-05%) - largest zero change 6.095558e-05
0  Obj 0 Primal inf 1303.3614 (30) Dual inf 6484.7494 (8)
0  Obj 0 Primal inf 1303.3614 (30) Dual inf 1.437715e+13 (28)
36  Obj -16980 Primal inf 105.38866 (21) Dual inf 7.2658581e+12 (14) w.o. free dual inf (13)
58  Obj -16046.434 Primal inf 0.28949488 (2)
Primal infeasible - objective value -16046.434
PrimalInfeasible objective -16046.43383 - 58 iterations time 0.002

Result - Linear relaxation infeasible

Enumerated nodes:           0
Total iterations:           0
Time (CPU seconds):         0.01
Time (Wallclock Seconds):   0.02

Option for printingOptions changed from normal to csv
Total time (CPU seconds):       0.01   (Wallclock seconds):       0.03

我关闭了预处理以查看它是否进行了任何更改，但没有。

Welcome to the CBC MILP Solver 
Version: 2.10.5 
Build Date: Oct 15 2020 

command line - cbc tt2.lp preprocess off passp 0 solve printing csv solu sol.txt (default strategy 1)
Option for preprocess changed from sos to off
passPresolve was changed from 5 to 0
Perturbing problem by 0.001% of 6368.0221 - largest nonzero change 9.6555471e-05 ( 8.8302642e-05%) - largest zero change 6.095558e-05
0  Obj 0 Primal inf 1303.3614 (30) Dual inf 6484.7494 (8)
0  Obj 0 Primal inf 1303.3614 (30) Dual inf 1.437715e+13 (28)
36  Obj -16980 Primal inf 105.38866 (21) Dual inf 7.2658581e+12 (14) w.o. free dual inf (13)
58  Obj -16046.434 Primal inf 0.28949488 (2)
Primal infeasible - objective value -16046.434
PrimalInfeasible objective -16046.43383 - 58 iterations time 0.002

Result - Linear relaxation infeasible

Enumerated nodes:           0
Total iterations:           0
Time (CPU seconds):         0.00
Time (Wallclock Seconds):   0.02

Option for printingOptions changed from normal to csv
Total time (CPU seconds):       0.00   (Wallclock seconds):       0.03

所以问题是LP问题的线性松弛是不可行的，但我不知道这意味着什么或如何解决它。

这是 LP 文件，以防万一。

Minimize
    1.0 cv_1_1 - 1.0 w_1_1 + 2.0 cv_2_1 - 2.0 w_2_1 + 4.0 cv_1_2 - 4.0 w_1_2 + 8.0 cv_2_2 - 8.0 w_2_2 + 9.0 cv_1_3 - 9.0 w_1_3 + 18.0 cv_2_3 - 18.0 w_2_3 + 16.0 cv_1_4 - 16.0 w_1_4 + 32.0 cv_2_4 - 32.0 w_2_4 + 1 dmv_2_1 + 1 dmv_2_2

Subject To

    \Manipulated variables: initial value
    R0: mv_1_0 = 150
    R1: mv_2_0 = 150

    \States: initial value
    R2: x_1_0 = 0.03534155
    R3: x_2_0 = 0.07947994
    R4: x_3_0 = -0.00548606
    R5: x_4_0 = -0.28400902

    \Manipulated variables: change variables
    R6: dmv_1_1 - mv_1_1 + mv_1_0 = 0
    R7: dmv_1_2 - mv_1_2 + mv_1_1 = 0
    R8: dmv_1_3 - mv_1_3 + mv_1_2 = 0
    R9: dmv_1_4 - mv_1_4 + mv_1_3 = 0
    R10: dmv_2_1 - mv_2_1 + mv_2_0 = 0
    R11: dmv_2_2 - mv_2_2 + mv_2_1 = 0
    R12: dmv_2_3 - mv_2_3 + mv_2_2 = 0
    R13: dmv_2_4 - mv_2_4 + mv_2_3 = 0

    \Controlled variables: upper and lower bounds
    R14: cv_1_1 >= 45
    R15: cv_1_1 <= 65
    R16: cv_1_2 >= 45
    R17: cv_1_2 <= 65
    R18: cv_1_3 >= 45
    R19: cv_1_3 <= 65
    R20: cv_1_4 >= 45
    R21: cv_1_4 <= 65
    R22: cv_2_1 >= 5
    R23: cv_2_1 <= 11
    R24: cv_2_2 >= 5
    R25: cv_2_2 <= 11
    R26: cv_2_3 >= 5
    R27: cv_2_3 <= 11
    R28: cv_2_4 >= 5
    R29: cv_2_4 <= 11

    \Manipulated variables: ratio change allowed
    R30: dmv_1_1 <= 1
    R31: dmv_1_1 >= -1
    R32: dmv_1_2 <= 1
    R33: dmv_1_2 >= -1
    R34: dmv_1_3 <= 0.0
    R35: dmv_1_3 >= -0.0
    R36: dmv_1_4 <= 0.0
    R37: dmv_1_4 >= -0.0
    R38: dmv_2_1 <= 1
    R39: dmv_2_1 >= -1
    R40: dmv_2_2 <= 1
    R41: dmv_2_2 >= -1
    R42: dmv_2_3 <= 0.0
    R43: dmv_2_3 >= -0.0
    R44: dmv_2_4 <= 0.0
    R45: dmv_2_4 >= -0.0

    \Manipulated variables: upper and lower bounds
    R46: mv_1_1 >= 140
    R47: mv_1_1 <= 170
    R48: mv_1_2 >= 140
    R49: mv_1_2 <= 170
    R50: mv_1_3 >= 140
    R51: mv_1_3 <= 170
    R52: mv_1_4 >= 140
    R53: mv_1_4 <= 170
    R54: mv_2_1 >= 130
    R55: mv_2_1 <= 150
    R56: mv_2_2 >= 130
    R57: mv_2_2 <= 150
    R58: mv_2_3 >= 130
    R59: mv_2_3 <= 150
    R60: mv_2_4 >= 130
    R61: mv_2_4 <= 150

    \W: reference trajectories for controlled variables
    R62: w_1_1 = 10.0
    R63: w_1_2 = 40.0
    R64: w_1_3 = 90.0
    R65: w_1_4 = 160.0
    R66: w_2_1 = 20.0
    R67: w_2_2 = 80.0
    R68: w_2_3 = 180.0
    R69: w_2_4 = 320.0

    \Model
    \X(t+1) - Gx(t) - Hmv(t) = 0
    \cv(t) - Cx(t) = 0

    R70: x_1_2 - 1.001 x_1_1 + 0.0001777 x_2_1 + 0.02923 x_3_1 + 0.001065 x_4_1 - 5.049e-06 mv_1_1 + 8.92e-06 mv_2_1 = 0
    R71: x_2_2 - 0.001961 x_1_1 - 0.9536 x_2_1 - 0.009859 x_3_1 + 0.08002 x_4_1 - 9.27e-06 mv_1_1 + 0.0001443 mv_2_1 = 0
    R72: x_3_2 - 0.02647 x_1_1 + 0.006174 x_2_1 - 0.9386 x_3_1 + 0.07591 x_4_1 - 5.375e-05 mv_1_1 + 0.000216 mv_2_1 = 0
    R73: x_4_2 + 0.001008 x_1_1 - 0.2273 x_2_1 - 0.04935 x_3_1 - 0.6928 x_4_1 - 0.000377 mv_1_1 + 0.001151 mv_2_1 = 0
    R74: cv_1_1 - 1408.0 x_1_1 + 10.67 x_2_1 + 19.4 x_3_1 - 0.6612 x_4_1 = 0
    R75: cv_2_1 - 4.282 x_1_1 - 77.07 x_2_1 - 0.1379 x_3_1 + 2.884 x_4_1 = 0
    R76: x_1_3 - 1.001 x_1_2 + 0.0001777 x_2_2 + 0.02923 x_3_2 + 0.001065 x_4_2 - 5.049e-06 mv_1_2 + 8.92e-06 mv_2_2 = 0
    R77: x_2_3 - 0.001961 x_1_2 - 0.9536 x_2_2 - 0.009859 x_3_2 + 0.08002 x_4_2 - 9.27e-06 mv_1_2 + 0.0001443 mv_2_2 = 0
    R78: x_3_3 - 0.02647 x_1_2 + 0.006174 x_2_2 - 0.9386 x_3_2 + 0.07591 x_4_2 - 5.375e-05 mv_1_2 + 0.000216 mv_2_2 = 0
    R79: x_4_3 + 0.001008 x_1_2 - 0.2273 x_2_2 - 0.04935 x_3_2 - 0.6928 x_4_2 - 0.000377 mv_1_2 + 0.001151 mv_2_2 = 0
    R80: cv_1_2 - 1408.0 x_1_2 + 10.67 x_2_2 + 19.4 x_3_2 - 0.6612 x_4_2 = 0
    R81: cv_2_2 - 4.282 x_1_2 - 77.07 x_2_2 - 0.1379 x_3_2 + 2.884 x_4_2 = 0
    R82: x_1_4 - 1.001 x_1_3 + 0.0001777 x_2_3 + 0.02923 x_3_3 + 0.001065 x_4_3 - 5.049e-06 mv_1_3 + 8.92e-06 mv_2_3 = 0
    R83: x_2_4 - 0.001961 x_1_3 - 0.9536 x_2_3 - 0.009859 x_3_3 + 0.08002 x_4_3 - 9.27e-06 mv_1_3 + 0.0001443 mv_2_3 = 0
    R84: x_3_4 - 0.02647 x_1_3 + 0.006174 x_2_3 - 0.9386 x_3_3 + 0.07591 x_4_3 - 5.375e-05 mv_1_3 + 0.000216 mv_2_3 = 0
    R85: x_4_4 + 0.001008 x_1_3 - 0.2273 x_2_3 - 0.04935 x_3_3 - 0.6928 x_4_3 - 0.000377 mv_1_3 + 0.001151 mv_2_3 = 0
    R86: cv_1_3 - 1408.0 x_1_3 + 10.67 x_2_3 + 19.4 x_3_3 - 0.6612 x_4_3 = 0
    R87: cv_2_3 - 4.282 x_1_3 - 77.07 x_2_3 - 0.1379 x_3_3 + 2.884 x_4_3 = 0
    R88: x_1_5 - 1.001 x_1_4 + 0.0001777 x_2_4 + 0.02923 x_3_4 + 0.001065 x_4_4 - 5.049e-06 mv_1_4 + 8.92e-06 mv_2_4 = 0
    R89: x_2_5 - 0.001961 x_1_4 - 0.9536 x_2_4 - 0.009859 x_3_4 + 0.08002 x_4_4 - 9.27e-06 mv_1_4 + 0.0001443 mv_2_4 = 0
    R90: x_3_5 - 0.02647 x_1_4 + 0.006174 x_2_4 - 0.9386 x_3_4 + 0.07591 x_4_4 - 5.375e-05 mv_1_4 + 0.000216 mv_2_4 = 0
    R91: x_4_5 + 0.001008 x_1_4 - 0.2273 x_2_4 - 0.04935 x_3_4 - 0.6928 x_4_4 - 0.000377 mv_1_4 + 0.001151 mv_2_4 = 0
    R92: cv_1_4 - 1408.0 x_1_4 + 10.67 x_2_4 + 19.4 x_3_4 - 0.6612 x_4_4 = 0
    R93: cv_2_4 - 4.282 x_1_4 - 77.07 x_2_4 - 0.1379 x_3_4 + 2.884 x_4_4 = 0

Bounds
    \States: upper and lower bounds
    x_1_1 free
    x_1_2 free
    x_1_3 free
    x_1_4 free
    x_1_5 free
    x_2_1 free
    x_2_2 free
    x_2_3 free
    x_2_4 free
    x_2_5 free
    x_3_1 free
    x_3_2 free
    x_3_3 free
    x_3_4 free
    x_3_5 free
    x_4_1 free
    x_4_2 free
    x_4_3 free
    x_4_4 free
    x_4_5 free

 End
4

1 回答 1

0

免责声明：我有点鄙视那些基于 txt 的序列化格式，这意味着我不是专家，因为我不经常使用它们。

我猜：

  • 变量默认为非负数
    • 下限：0.0
    • 上限：正无穷大

这是各种求解器中非常常见的设计决策，关于 LP 文件，我想这也可能是真的（？）。

（快速浏览 Gurobi、CPLEX、FICO 商业求解器让我觉得所有这些都应用了这个逻辑 -> CoinOR Clp/Cbc 可能也是如此）

答： 让我们使用其他求解器并运行您的文件：

  • 不可行
  • 说：R4: x_3_0 = -0.00548606不行（可能还有其他不可行的来源）

B： 您的 lp 文件包含：

Bounds
    \States: upper and lower bounds
    x_1_1 free
    ...
  • 自由变量是 [-infinity, +infinity] 变量 -> 不是非负数
  • 正如我们上面猜测的那样，在这里明确地看到这些在某种程度上表明潜在的默认值

C：

  • x_3_0没有出现在 free-vars 中
  • x_3_0大概在[0, +infinity)
    • 明显不兼容R4: x_3_0 = -0.00548606
      • 这是一个如此简单的演绎，预求解认识到
于 2022-02-10T09:07:53.643 回答