Gurobi's solution is infeasible, while IIS says the solution is feasible (matlab)

[Daan]

Hello,

I am trying to solve a MIP problem with the use of Model predictive control and some boolean variables. However, the model becomes infeasible while running it in Matlab. But, when I compute the Irreducible Inconsistent subsystem it tells me that the model IS feasible.

I've calculated the IIS by using gurobi.bat with the lp and mps files (attached). 

Using gurobit.bat find_infeasibilty.py mip1.lp told me that the model is feasible.

However, using the mps file: gurobi.bat find_infeasbility.py INFEASIBLE_06-12_13.07 

the following results appeared:

Gurobi 7.0.2 (win64, Python) logging started 06/12/17 13:09:15

Read MPS format model from file INFEASIBLE_06-12_13.07.mps

Reading time = 0.00 seconds

matlab: 51 rows, 35 columns, 117 nonzeros

Optimize a model with 51 rows, 35 columns and 117 nonzeros

Variable types: 15 continuous, 20 integer (5 binary)

Coefficient statistics:

  Matrix range     [1e+00, 3e+03]

  Objective range  [1e-03, 2e-02]

  Bounds range     [1e+00, 1e+04]

  RHS range        [1e+00, 8e+03]

Presolve removed 47 rows and 33 columns

Presolve time: 0.00s

Explored 0 nodes (0 simplex iterations) in 0.00 seconds

Thread count was 1 (of 2 available processors)

Solution count 0

Pool objective bound 1e+100

Model is infeasible

Best objective -, best bound -, gap -

Computing Irreducible Inconsistent Subsystem (IIS)...

      Constraints           Bounds       Runtime

     Min       Max       Min      Max

------------------------------------------------

        0       51         0       40         0s

       10       10         1        1         0s

IIS computed: 10 constraints, 1 bounds

IIS runtime: 0.02 seconds

And this infeasible.ilp file:

\ Model matlab_copy

\ LP format - for model browsing. Use MPS format to capture full model detail.

Minimize

 

Subject To

 R1: C5 = 7672.717008629721

 R2: C10 = 1

 R3: C15 = 0

 R6: C1 - 1.1 C11 = 0

 R7: C2 - 1.1 C12 = 0

 R10: 2700 C1 + C5 - C6 = 368.7365039979017

 R11: 2700 C2 + C6 - C7 = 606.9631510035821

 R18: - C15 + C16 <= 1

 R38: 2 C10 - 2 C11 - C15 <= 0

 R39: 2 C11 - 2 C12 - C16 <= 0

Bounds

 C1 free

 C2 free

 C5 free

 C6 free

 -infinity <= C7 <= 12558

 C15 free

 C16 free

Binaries

 C10 C11 C12

Generals

 C15 C16

End

I can't figure out which constraints result in the infeasibility...

[Daniel Espinoza]

Hi Daan,

If you remove the bounds on C7 and minimize C7 in your ILP you will see that the optimal value is 12637, way above the 12558 bound in the ILP.

I hope this helps,

Best,

Daniel

[Daan]

Hi Daniel,

Thank you for your quick response. If I remove the bounds on C7, i am still getting infeasibility errors:

Gurobi 7.0.2 (win64, Python) logging started 06/12/17 13:52:04

Read MPS format model from file INFEASIBLE_06-12_13.51.mps

Reading time = 0.00 seconds

matlab: 51 rows, 30 columns, 117 nonzeros

Optimize a model with 51 rows, 30 columns and 117 nonzeros

Variable types: 10 continuous, 20 integer (5 binary)

Coefficient statistics:

  Matrix range     [1e+00, 5e+03]

  Objective range  [1e-03, 2e-02]

  Bounds range     [1e+00, 1e+00]

  RHS range        [1e+00, 5e+03]

Presolve removed 5 rows and 6 columns

Presolve time: 0.00s

Explored 0 nodes (0 simplex iterations) in 0.00 seconds

Thread count was 1 (of 2 available processors)

Solution count 0

Pool objective bound 1e+100

Model is infeasible

Best objective -, best bound -, gap -

Computing Irreducible Inconsistent Subsystem (IIS)...

      Constraints           Bounds       Runtime

     Min       Max       Min      Max

------------------------------------------------

        0       51         0       30         0s

        5        5         5        5         0s

IIS computed: 5 constraints, 5 bounds

IIS runtime: 0.01 seconds

AND

\ Model matlab_copy

\ LP format - for model browsing. Use MPS format to capture full model detail.

Minimize

 

Subject To

 R1: C5 = 5053.71836993729

 R10: - 5400 C1 + C5 - C6 = 1784.401045021623

 R11: - 5400 C2 + C6 - C7 = 1772.180044307078

 R12: - 5400 C3 + C7 - C8 = 1759.959043592532

 R13: - 5400 C4 + C8 - C9 = 1747.738042877986

Bounds

 C5 free

 C6 free

 C7 free

 C8 free

End

Op maandag 12 juni 2017 13:43:33 UTC+2 schreef Daniel Espinoza:

[Daniel Espinoza]

Hi Daan,

I meant removing the bound from the IIS and optimize the resulting problem. A problem may have multiple IIS, so removing one may not make the problem feasible.

Best

Daniel

[Daan]

Hi Daniel,

I see what you mean. However, I have found something that had to be changed. The model is still not feasbile but I am getting a different IIS now...

\ Model matlab_copy

\ LP format - for model browsing. Use MPS format to capture full model detail.

Minimize

 

Subject To

 R1: C5 = 1742.47015902558

 R10: - 5400 C1 + C5 - C6 = 407.1978220948048

 R11: - 5400 C2 + C6 - C7 = 427.5072450789882

 R12: - 5400 C3 + C7 - C8 = 447.8166680631712

 R13: - 5400 C4 + C8 - C9 = 463.7720736530131

Bounds

 C5 free

 C6 free

 C7 free

 C8 free

End

I have found one solution and that is by dividing the RHS by 100. In this way the model is feasible, but obviously does not give me the right solutions. So I am kinda lost right now.

Op maandag 12 juni 2017 15:48:10 UTC+2 schreef Daniel Espinoza:

[Michael Winkler]

As Daniel pointed out there might be several IIS in your model. E.g., for your last one if you plug in R1 in R10, then add the new R10 to R11 and ... new R12 to R13 you get:

- 5400 C4 - 5400 C3 - 5400 C2 - 5400 C1 - C9 = 3.8236498644

Since all these variable above  are >= 0, this problem is infeasible.

Best,
Michael