How to get alternative solutions to a linear programming problem using linprog?

Hi,

I am trying to solve a linear programming problem using linprog with no inequalities and an equalities matrix that is 4633-by-10683 in size. As far as I understand, that means there is no unique solution for this problem and I want to be able to arrive at some of the alternative solutions other than the one that running linprog yields. One trick I can think of is to change some of the lower & upper boundary values on the design variables in order to change the solution. I am wondering if there are other ways (maybe changing an internal parameter of the solver function?) to try in order to get at alternative solutions over successive runs of linprog.

Many thanks,

Al

[Breschine]

I would like to know the answer to this as well. It is possible for alternative solutions to exist---this can happen when the level sets of the objective function are parallel to one of the boundaries of the feasible region (one of the constraint lines).

[Torsten]

"linprog" will compute at most one solution for a given problem. You are right: there might exist other solutions with the same value of the objective function. But as there is no such thing as in initial guess given by the user in "linprog" from which the solver starts, my guess is that the solution procedure is deterministic and leads to one fixed result that won't change if you make successive runs with the same input.

A simple problem with more than one solution is e.g.

max: x1 + x2
s.c.
x1 + x2 <= 1
x1, x2 >= 0

But in the degenerate case (i.e. a case where more than one solution exists), you might get different answers for different algorithms:

• 'dual-simplex-highs' (default)
• 'dual-simplex-legacy'
• 'interior-point'
• 'interior-point-legacy'

[Breschine]

Thanks, that makes sense.

Answer 1

[Rakesh Kumar]

Why do you think there won't be a unique solution? When you have a linear objective (bounded) and constraints are linear (and bounded) you get a unique solution. At the solution constraints may be dependent but the solver should be able to take care of that.

Hth, Rakesh

[Torsten]

max: x1 + x2
s.c.
x1 + x2 <= 1
x1, x2 >= 0

?

[Breschine]

I belive the example

max: 18x1 + 6x2 
s.t.
3x1 + x2 <= 120
x1 + 2x2 <= 160
x1 <= 35
x1, x2 >= 0

has multiple alternative solutions also. This is because the leading edge created by the first constraint is parallel to the level sets of the objective function. Therefore the intersection of the constraint with the largest level set is a line segment, not a point. Matlab will return one point from this line segment. The easiest way to see for either system is to solve the problem graphically by plotting the feasible region and level sets.