CODEWITHSUNDEEP
pythonlinear-programminggurobi
Mojtaba Sardar
Mojtaba Sardar

Reputation: 57

How to find all possible optimum solutions in LP with GUROBI

I have solved an LP model with GUROBI and I know that the model has an infinite number of optimum solutions. As you can see below, the objective function and constr 1 has the same slop and constr 1 is binding. The GUROBI only show one optimum solution, but how can I find all possible solutions (or the range)? How can I find the number of optimum solutions in more complex LP models?

Maximize
   <gurobi.LinExpr: -1.0 x1 + 2.0 x2>
Subject To
   non negative x1 : <gurobi.LinExpr: x1> >= 0.0
   non negative x2 : <gurobi.LinExpr: x2> >= 0.0
   constr 1 : <gurobi.LinExpr: -1.0 x1 + 2.0 x2> <= 4.0
   constr 2 : <gurobi.LinExpr: x1 + x2> <= 5.0
   constr 3 : <gurobi.LinExpr: x1 + -1.0 x2> <= 3.0

Upvotes: 0

Views: 1353

Answers (1)

Erwin Kalvelagen
Erwin Kalvelagen

Reputation: 16782

All optimal LP solutions is a difficult concept. There are likely infinitely many of them. Gurobi has tools to enumerate all optimal integer solutions (solution pool), but that is not applicable in a pure LP. So the short answer is no.

It is possible to enumerate all optimal bases, but it requires some work (basically encode the basis using binary variables: a variable or constraint is basic or non-basic). See this link. This approach can be implemented by adding additional constraints, or more efficiently by using the aforementioned solution pool. Although conceptually interesting, it is noted that this approach is not practical for large problems.

Upvotes: 0

Related Questions