为什么 MIP 对这个问题最好是无限的？

Question

我有以下 MIP 问题。 pre_6_0 的上限不应是无限的，因为它是根据 inp1、inp2、inp3 和 inp4 计算得出的，所有这些都在两边都有界.

Maximize
 obj: pre_6_0
Subject To
 c1:  inp0 >= -84
 c2:  inp0 <= 174
 c3:  inp1 >= -128
 c4:  inp1 <= 128
 c5:  inp2 >= -128
 c6:  inp2 <= 128
 c7:  inp3 >= -128
 c8:  inp3 <= 128
 c9:  inp4 >= -128
 c10: inp4 <= 128
 c11: pre_6_0 + 0.03125 inp1 - 0.0078125 inp2 - 0.00390625 inp3
      + 0.00390625 inp4  = -2.5
 c12: - 0.0078125 inp0 + pre_6_1  = -2.5
 c13: - 0.00390625 inp0 - 0.01171875 inp3 + pre_6_2  = 6.5
 c14: - 0.0078125 inp0 + pre_6_3  = -1.5
 c15: - 0.00390625 inp0 - 0.0078125 inp3 + pre_6_4  = 6.5
Bounds
      pre_6_0 Free
      inp0 Free
      inp1 Free
      inp2 Free
      inp3 Free
      inp4 Free
      pre_6_1 Free
      pre_6_2 Free
      pre_6_3 Free
      pre_6_4 Free
Generals
 pre_6_0  inp0  inp1  inp2  inp3  inp4  pre_6_1  pre_6_2  pre_6_3  pre_6_4

Answer 1

MIP 最佳边界是无限的，因为不存在可行的整数解。
事实上，您的 ILP 中的所有变量都被限制为一般整数值（Generals 部分）。

这里有一个使用GLPK求解ILP的例子

15 rows, 10 columns, 25 non-zeros
10 integer variables, none of which are binary 

...    

Solving LP relaxation...
GLPK Simplex Optimizer, v4.65
5 rows, 10 columns, 15 non-zeros
      0: obj =  -8.000000000e+00 inf =   1.631e+01 (5)
      5: obj =  -3.750000000e-01 inf =   0.000e+00 (0)
*     8: obj =   3.000000000e+00 inf =   0.000e+00 (0)
OPTIMAL LP SOLUTION FOUND

Integer optimization begins...
Long-step dual simplex will be used
+     8: mip =     not found yet <=              +inf        (1; 0)
+     8: mip =     not found yet <=     tree is empty        (0; 3)
PROBLEM HAS NO INTEGER FEASIBLE SOLUTION
Time used:   0.0 secs
Memory used: 0.1 Mb (63069 bytes)

为什么 MIP 对这个问题最好是无限的？

Why is MIP best bound infinite for this problem?

optimization

linear-programming

cplex