BookmarkSubscribeRSS Feed
deleted_user
Not applicable
Hi, thought I'd get the ball rolling...

I have a question regarding Proc LP. I have solved a very simple problem (choosing best 11 variables out of about 500 subject to about half a dozen constraints) for the optimal solution. But I am interested in seeing the other feasible solutions that are close in value to the optimal one. I'm by no means an OR/Proc LP expert but a while ago had a read of documentation and couldn't see how to do it. Any takers on this one...?

Thanks, John
3 REPLIES 3
Matthew_Galati
SAS Employee
Are you solving an LP or an MILP?
deleted_user
Not applicable
It is an MILP problem I think - my variables are of the "_binary_" constraint type in that they take the values of either 1 (selected) or 0 (not selected).

Is that clear?

Thanks, John
Matthew_Galati
SAS Employee
There is no option to get "alternative" or "suboptimal" solutions. We (R&D) have discussed this as a possible option in a future release (of OPTMILP). In case you do not know, we have a new suite of solvers that replace most of the functionality of PROC LP: OPTLP for LPs and OPTMILP for MILPs. Also, performance has been greatly improved.

Although we do not provide alternative solutions, there is a way you can "simulate this" which is not too difficult since your problem is binary. Solve the problem, getting a solution x*, let S0 = {j in 1..n: x* = 0} and S1 = {j in 1..n: x* = 1}, and add the following constraint to cut off the given solution:

sum {j in S0} x + sum {j in S1} (1 - x) >= 1

The idea is that this constraint forces some variable to take a different value than its current value (at least one 0 must become a 1, or at least one 1 must become a 0). Solve again. If the problem is infeasible, the original problem has a unique feasible solution. Otherwise, you get an alternative feasible solution, which might or might not have the same objective value as x*. Continue adding cuts and re-solving until the resulting problem is infeasible or the desired number of solutions have been obtained.

This can be done using the macro language and manipulating the input data sets for PROC LP. Also, it would be much easier using OPTMODEL.

sas-innovate-2024.png

Don't miss out on SAS Innovate - Register now for the FREE Livestream!

Can't make it to Vegas? No problem! Watch our general sessions LIVE or on-demand starting April 17th. Hear from SAS execs, best-selling author Adam Grant, Hot Ones host Sean Evans, top tech journalist Kara Swisher, AI expert Cassie Kozyrkov, and the mind-blowing dance crew iLuminate! Plus, get access to over 20 breakout sessions.

 

Register now!

Multiple Linear Regression in SAS

Learn how to run multiple linear regression models with and without interactions, presented by SAS user Alex Chaplin.

Find more tutorials on the SAS Users YouTube channel.

Discussion stats
  • 3 replies
  • 1024 views
  • 0 likes
  • 2 in conversation