MIP: Relaxing the 'infeasible bound', the 'feasible' solution meets the 'infeasible' bound

Answered

Haleh Sadat Ale Ahmad

• October 29, 2020 12:09

Hello,

 

I have an MIP, where Z and X are a binary variables, among others. When I set the binary variable as 1, the problem becomes infeasible. Then I relax this constraint and in the optimal solution the variable is 1. I have run this problem with more than 1000 instances and I have encountered this issue only a few times. As an example, I have:

Z[9,3].lb = 1

This problem is infeasible. When I remove this constraint, the problem becomes feasible and in the optimal solution, I have Z[9,3] = 1. I cannot figure out what the issue is.

I am using gurobipy 9.0.3. I have the lp and mps of both problems here. Any help is much appreciated.

0

• 

  Jaromił Najman

  Gurobi Staff

  • October 29, 2020 15:21
  • Edited

  Hi Haleh,

  It seems like many of the coefficients in your model suffer from round off errors, e.g., the coefficient -2.8563150000000004e+01 should very likely be set to -2.856315e+01. These innocent looking small round off errors may cause a lot of trouble during the solution process as they are far below the feasibility tolerance of the solver but still may have influence on the solution process. Another such coefficient is, e.g., -5.5607999999999993e+02 which should rather be -5.5608e+02.
  
  In contrast, if we export your MPS file to an LP file, these round off errors are just cut off during the writing of the LP file and the problem you describe does not occur for your models in LP file format. So, except if these values are really desired, we strongly recommend to always clean up round off errors caused by floating point operations or data generation methods.
  
  For more information, I recommend the excellent article by Ed Klotz on Numerical Instability in Linear and Integer Programs.

  Best regards,
  Jaromił

  1

Please sign in to leave a comment.