Obtaining 0-1 Integer Solutions with Linear Programming solvers

Ongoing

Prabhu Manyem

• June 27, 2022 07:10

I am trying to obtain 0-1 Integer solutions using Linear Programming.. I am testing whether the Valid Inequalities (extra constraints which I added to the model) indeed return fully Integer solutions when I solve the Linear Relaxation... (In GUROBI command line in Linux, I run the model file with the .lp extension, Valid-Inequalities.lp)

For some instances with multiple optimal solutions, GLPK 5.0 returned integer solutions, whereas GUROBI returned fractional solutions with the SAME objective function value.. How can I obtain fully Integer solutions with GUROBI by solving the Linear Program (Linear Relaxation)?

(Yes, I have read Greg Glockner's post -- Why does Gurobi sometimes return non-integral values for integer variables?https://support.gurobi.com/hc/en-us/articles/360012237872-Why-does-Gurobi-sometimes-return-non-integral-values-for-integer-variables  -- However, his answer appears to be for Integer Prog. solvers, NOT Linear Prog. solvers.)

I use Gurobi Optimizer version 9.5.1 build v9.5.1rc2 (linux64).

Thank you.

0

• 

  Maliheh Aramon

  Gurobi Staff

  • June 28, 2022 23:55

  Hi Prabhu, 

  When solving an LP, Gurobi terminates as soon as finding one proven optimal solution. Running the Gurobi Optimizer using different parameters such as Seed and/or Method might result in different optimal solutions in case there are multiple optimal solutions. However, there is no guarantee on which solution will be found. If you would like for some of the decision variables to take integral values, there is no way to enforce this on the LP relaxation of the model. You need to define them as integer (binary) variables. Gurobi will then solve a MIP instead of an LP. This would increase the runtime but will ensure the integrality of variables you would like them to be integral.

   Best regards,

  Maliheh

   

  0
• 

  Prabhu Manyem

  • June 29, 2022 01:47
  • Edited

  

  

  

  Maliheh,  Thank you... However, my goal (or hope) is to obtain optimal Integer solutions using Linear Programming... Or by solving at most a polynomial number of Linear Programs... for example, by adding additional constraints (Valid Inequalities) to the model.

  Is it possible to get an optimal Integer solution by some kind of post-processing?

  Thanks.

  0

Please sign in to leave a comment.