Obtaining 01 Integer Solutions with Linear Programming solvers
OngoingI am trying to obtain 01 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, ValidInequalities.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 nonintegral values for integer variables?https://support.gurobi.com/hc/enus/articles/360012237872WhydoesGurobisometimesreturnnonintegralvaluesforintegervariables  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.

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 
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 postprocessing?
Thanks.
0
Please sign in to leave a comment.
Comments
2 comments