Originally posted by: alexy_yeti

Hi
I have a question regarding LP
i solve a LP and get optimal solutions via getValues()..
is there any function to call and get another optimal solution basis(if there is)?

if there is no function what is your suggestion to get another optimal solution basis
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

In theory you could do the following:
1. Query the reduced costs and fix every variable to its current solution value that has a non-zero reduced cost value. Of course, such a variable would either be at its lower or at its upper bound.
2. Query the dual solution and convert every constraint that has a non-zero dual value into an equation.

This process means to fix the problem to the optimal face of the polyhedron. Now, you can just install arbitrary objective functions (for example, random coefficients) and reoptimize to sample the vertices of the optimal face.

In practice, you would just apply this strategy, but the big question is what "non-zero" in the two steps above means. Typically you would define a threshold value up to which you declare a reduced cost or dual value to be "zero". If you choose this threshold too small, then you fix too much and will miss optimal vertices. If you choose the threshold too large, then you fix not enough and risk to leave the optimal face, i.e., to produce non-optimal solutions.

My experience is that you should apply a very strict threshold for the duals; something like 1e-9. For the reduced costs you can apply a larger threshold, for example 1e-6.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: alexy_yeti

Thanks Dear Tobias for your time and proposed solution
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: andrea.bustillos

I'm getting a similar problem. And tried your proposed solution. But I have a fe issues:

1) By the definition of reduced cost, I understand that a variable has a non-zero reduced cost only if it's zero. If a variable is positve then its reduced cost should be zero, but for my particualr problem (maximization problem with linear equations as restrictions) I'm getting postive reduced costs to positive valued variables.

2) Because my problem is in the form

max c'x

subject to

AX=b

I just skipped the second step you proposed.

 

By changing my objective function to a specific secondary objective I have (maximization of the values of some variables) I finally obtain the solution I was looking for, but the dual cost of my restrictions have changed. To contrast, I've alredy tried another method to fix my search to the facet where multiple solutions are (adding the objective function with its optimal valua as a solution and changing the objective function), and in this case, the dual costs remained the same. What did I did wrong? 

#CPLEXOptimizers
#DecisionOptimization

Regarding the first point, if you specify a finite upper bound for a variable (as a bound, not as a constraint), and the variable attains that bound in the optimal solution, its reduced cost with equal what would have been the dual price (typically nonzero) of that bound had the bound been written as a constraint.

As for the change in dual solution, a problem with multiple optimal solutions to the primal could possibly have multiple optimal solutions to the dual. (Multiple dual solutions occur when the primal solution -- or in this case, perhaps one of the primal solutions -- is degenerate.) I'm not sure that's what is happening in your case, but it is a possibility.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: andrea.bustillos

Thank you for your quick reply, and sorry for the confusion. The problem I'm solving is 

Maximize

1000 x1 + 500 x2 - 500 x5 - 250 x6 

Subject To

 c1: x1 + x2 - x3 - x4  = 0
 c2: - x3 + x5  = 0
 c3: - x4 + x6  = 0

With these Bounds

 0 <= x1 <= 10
 0 <= x2 <= 15
 0 <= x5 <= 15
 0 <= x6 <= 5

When I modify it using the steps in this thread I get the next auxiliar problem

 

Maximize

x1 + x2 

Subject To

 c1: x1 + x2 - x3 - x4  = 0
 c2: - x3 + x5  = 0
 c3: - x4 + x6  = 0
 c4: 1000 x1 + 500 x2 - 500 x5 - 250 x6  = 6250

With these Bounds

 0 <= x1 <= 10
 0 <= x2 <= 15
 0 <= x5 <= 15
 0 <= x6 <= 5

And I obtain the solution I was looking for. But for the second problem the duals are different. I've noticed that if I modify the coeficients in the objective function, the results of the dual variables change, which makes sense. Yet I would like that my final solution results in the same duality solution. Is this possible?

Another question is: if the optimal solution of the auxiliar problem is an optimal solution of the original problem, how does the aditional constraint affects the duality of my problem?

And finally, how do I determine if my one of my primal solutions is degenerate? For example, to the original problem I have the next relation of basic variables and their values

[AtUpper, AtLower, Basic, Basic, Basic, AtUpper]
[10.0, 0.0, 5.0, 5.0, 5.0, 5.0]

And I can see that the corresponding basic variables don't have a zero value. Can this be?

 

#CPLEXOptimizers
#DecisionOptimization

First, using the technique from this thread for finding alternate optimal solutions to the primal problem, the dual solution pretty much has to change. You added a new constraint, so the dual solution's dimension increased by one.

Now suppose that the original primal problem is (P), with dual (D), and that you get an optimal solution x* to (P) and a dual solution y*. If x' is an alternative optimal solution to (P), y* is still an optimal solution to (D). It will not be an optimal solution to the modified problem (P') that let you find x', but it remains an optimal solution to the original problem (P). Does that satisfy your needs?

I do not understand your last question. The solution you listed is not degenerate. Did you have some reason to expect it to be? Bear in mind that there is no connection between having a degenerate primal solution and having multiple primal solutions. (Multiple primal solutions corresponds to a degenerate dual solution.)

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: andrea.bustillos

Ok, thank you for your response ,Paul. I think this information is enough to solve my problem.

#CPLEXOptimizers
#DecisionOptimization