Warm tip: This article is reproduced from serverfault.com, please click

optimization-为什么MIP对此问题的最佳绑定是无限的?

(optimization - Why is MIP best bound infinite for this problem?)

发布于 2020-12-14 13:48:43

我有以下MIP问题。上开往pre_6_0因为它是从计算不应该是无限的inp1inp2inp3,和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
Questioner
Samvid Mistry
Viewed
0
abc 2020-12-14 22:19:43

MIP的最佳界限是无限的,因为不存在可行的整数解。
实际上,你的ILP中的所有变量都被限制为通用整数值(“通用”部分)。

这里有一个使用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)