topic Re: Find all Optimal solutions to the following LP in Mathematical Optimization, Discrete-Event Simulation, and OR

Find all Optimal solutions to the following LP

nep0827 — Fri, 26 Apr 2019 00:16:19 GMT

max z = 3x[1] + 3x[2]

s.t. x[1] + x[2] <=1;

All x[i] =>0

What would the general code be?

Re: Find all Optimal solutions to the following LP

PGStats — Fri, 26 Apr 2019 03:19:15 GMT

Welcome to the SAS Forum!

Finding ONE optimal solution can be done with proc optmodel (part of SAS/OR, which requires a separate licence) using the SOLVE WITH LP statement, see example here. Adding some other constraint (such as x[1] and x[2] integers) would be required to make the set of ALL optimal solutions finite, in which case you would use SOLVE WITH CLP to find all solutions.

Posting your questions to the OR Community would reach experts in those procs.

Re: Find all Optimal solutions to the following LP

Ksharp — Fri, 26 Apr 2019 13:57:54 GMT

Yeah. Post it at OR forum. @RobPratt is there .

proc optmodel;
var x1>=0 ,x2>=0;
max z=3*x1+3*x2;
con a:x1+x2<=1;
solve  with lp;
print x1 x2;
quit;

Re: Find all Optimal solutions to the following LP

RobPratt — Fri, 26 Apr 2019 14:50:09 GMT

In SAS Optimization 8.4 to be released soon, you can also find all optimal solutions with the MILP solver, which allows both integer and non-integer variables. For that purpose, two solutions are considered distinct if they differ for some integer variable.

Re: Find all Optimal solutions to the following LP

RobPratt — Fri, 26 Apr 2019 14:54:01 GMT

@Ksharp's code looks good for finding one optimal solution. For LP, the number of optimal solutions can be 0, 1, or infinite. In your example, the entire line segment from (x1,x2) = (1,0) to (0,1) is optimal. The LP solver returns only one of these solutions.