topic Re: Proc LP question - quot;nearquot; optimal solutions? in Mathematical Optimization, Discrete-Event Simulation, and OR

Proc LP question - "near" optimal solutions?

deleted_user — Tue, 27 Feb 2007 16:29:03 GMT

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

Re: Proc LP question - quot;nearquot; optimal solutions?

Matthew_Galati — Wed, 28 Feb 2007 14:49:58 GMT

Are you solving an LP or an MILP?

Re: Proc LP question - "near" optimal solutions?

deleted_user — Fri, 02 Mar 2007 13:47:57 GMT

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

Re: Proc LP question - quot;nearquot; optimal solutions?

Matthew_Galati — Wed, 07 Mar 2007 00:36:54 GMT

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.