Skip to main content

Obtaining 0-1 Integer Solutions with Linear Programming solvers

Ongoing
Prabhu Manyem
  • Gurobi-versary
  • First Comment
  • First Question

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

Comments

3 comments

Date Votes
  • Official comment
    Simranjit Kaur
    • Gurobi Staff
    This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support.
  • Maliheh Aramon
    • Gurobi Staff

    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
    Edited
    • Gurobi-versary
    • First Comment
    • First Question

    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

Post is closed for comments.

Didn't find what you were looking for?

New post