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

Why is MIP best bound infinite for this problem?

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

I have the following MIP problem. Upper bound for pre_6_0 should not be infinite because it is calculated from inp1, inp2, inp3, and inp4, all of which are bounded on both sides.

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
1
abc 2020-12-14 22:19:43

The MIP best bound is infinite because no feasible integer solution exists.
Indeed, all the variables in your ILP have been restricted to general integer values (Generals section).

Here an example by using GLPK to solve the 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)