Search code examples
optimizationlinear-programmingcplex

Why is MIP best bound infinite for this problem?


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

Solution

  • 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)