SAS Optimization, and SAS Simulation Studio

turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

Find a Community

Topic Options

- RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Bookmark
- Subscribe
- Printer Friendly Page

- Mark as New
- Bookmark
- Subscribe
- RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

02-27-2007 11:29 AM

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

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

- Mark as New
- Bookmark
- Subscribe
- RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to deleted_user

02-28-2007 09:49 AM

Are you solving an LP or an MILP?

- Mark as New
- Bookmark
- Subscribe
- RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to Matthew_Galati_SAS

03-02-2007 08:47 AM

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

Is that clear?

Thanks, John

- Mark as New
- Bookmark
- Subscribe
- RSS Feed
- Permalink
- Email to a Friend
- Report Inappropriate Content

Posted in reply to deleted_user

03-06-2007 07:36 PM

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.

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*

sum {j in S0} x

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.