Originally posted by: SystemAdmin

Hello everybody,

I am raising this question because I did not find any helpful text in manual (perhaps someone did).
I am trying to find a way in concert to access the slack variables and also the reduced costs of the slack variables. In other words I need to get dual information about the constraints.

Any comment is highly appreciated.

regards,
Shahin
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Olivier Binckly

in the documentation, search for :

getReducedCost
getReducedCosts
getSlack
getSlacks
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> Shahin G wrote:
> I am trying to find a way in concert to access the slack variables and also the reduced costs of the slack variables. In other words I need to get dual information about the constraints.

In a callback or after solving? After solving (as noted in someone else's reply) you can get slacks values and reduced costs of primal variables (not including the slacks). You can also get the dual values. In a control callback, you can get slack values, but I don't think the dual information is available in a callback (not positive about that).

You can get pointers to the slack variables themselves using a model iterator, but I don't think you can do anything with them other than print their names (which coincide with the names of the constraints in which they appear).

/Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

---In a callback or after solving? After solving (as noted in someone else's reply) you can get slacks values and reduced costs of primal variables (not including the slacks).
It is a post-optimization manipulation.
That is exactly the point. Let me put it this way: you know a constraint is slack in the optimality; what will you do if you want to set the dual value to zero?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> Shahin G wrote:
> Let me put it this way: you know a constraint is slack in the optimality; what will you do if you want to set the dual value to zero?

I don't understand the question. If a constraint is nonbinding in the optimal solution, its dual value will automatically be zero unless the primal solution is degenerate, in which case the dual may have multiple optima. If you have a degenerate primal solution and you want to get a nonzero dual value for a specific constraint, and if the dual value retrieved from CPLEX happens to be zero, you can perturb the RHS slightly to break up the degeneracy and reoptimize the primal ... but that may cause some other nonbinding constraint to get a zero dual value.

If for some specific purpose you need nonzero dual values for all nonbinding constraints (and the primal solution is degenerate), you can use perturbations to get multiple dual solutions and then form a convex combination of them. Assuming each nonbinding constraint has a nonzero dual in at least one of the dual solutions, the convex combination will do what you want. It will not be an extreme point of the dual feasible region, but it will be a valid dual solution (and hence a valid subgradient).

/Paul
Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thanks Paul, you always have useful comments.
Actually the point is that I have tens of thousands of variables and a model which is finally solved to optimality.
for the same reason as you mentioned I have degeneracy multiple optimality in primal. I need to stay on the face of optimality and choose the one I like (moving over the face). I need to do it as efficient as possible because it is very expensive. I can use the reduced costs to fix some of the variables but there are thousands more which can be fixed is I can access the dual variable corresponding to a constraint which is not binding. then if it is not binding I can fix it.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> Shahin G wrote:
> Thanks Paul, you always have useful comments.

Maybe not so useful this time, as I garbled what I wrote before. A nonbinding constraint has to have a zero dual value, period. A binding constraint will have a nonzero dual value except when the primal solution is degenerate -- which is not what I wrote before, and probably not what you were interested in either.

> Actually the point is that I have tens of thousands of variables and a model which is finally solved to optimality.
> for the same reason as you mentioned I have degeneracy multiple optimality in primal. I need to stay on the face of optimality and choose the one I like (moving over the face).

I assume then that what you have is multiple optimality in the primal and degeneracy in the dual, which makes sense given your original question.

What is your criterion for "the one I like"? How do you choose among the competing optima? (This isn't a multicriterion problem, is it?)

> I need to do it as efficient as possible because it is very expensive. I can use the reduced costs to fix some of the variables but there are thousands more which can be fixed is I can access the dual variable corresponding to a constraint which is not binding. then if it is not binding I can fix it.

I got lost here. Are you talking about fixing some nonbasic primal variables at zero?

If the dual is degenerate, some binding primal constraints may have zero duals (but all nonbinding primal constraints must have zero duals). So you cannot tell which primal constraints are binding by looking at the duals, but you can tell by looking at their slack values. CPLEX provides the slack values via getSlack/getSlacks; it just doesn't provide the slack variables themselves.

/Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Hi Paul,

thanks for your comment and sorry for my late reply-- I was away for a while.

No the problem is not multi-criteria optimization. it is just a dual of a degenerated problem which is not facing multiple optimality.

The main idea of this question was : if we solve an LP to optimality with the given property of multiple optimality and you want to stay on the face of optimality while changing the objective how can you fix as many variables and constraints as possible using CPLEX utilities to minimize the total computational efforts needed to re-optimize the new model.
1) variables can be fixed by reduced cost
2) active inequalities can be fixed by converting to inequalities
These two do not seem to be enough for characterizing the optimality face.
and I would like to also fix some thing related to the non-binding constraints.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

The theory is pretty simple: in order to stay on the optimal face, you just need to fix all variables with non-zero reduced cost to their current value, and you need to convert all inequalities with non-zero dual value into equations. Then, you have exactly modeled the optimal face of your polyhedron. Nothing more, nothing less.

In practice, however, the situation might be a bit more challenging due to numerics. For example, it could very well happen that a reduced cost value that CPLEX returns is 1e-10, even though in exact arithmetics the true value would be zero. The same is true for duals, and in my experience, the numerics for the dual values are even more troublesome than the ones for the reduced costs.

As you can see, you need to define some thresholds, and they incur a trade-off. You need to fix all variables with reduced costs smaller than some "djeps", and all constraints with duals smaller than "pieps" (each in absolute terms). If you increase the epsilon thresholds than you are fixing more with the risk of losing optimal vertices (i.e., you are then optimizing only over some face of the true optimal face). If you decrease the epsilon thresholds you are fixing less variables with the risk of leaving the optimal face in the subsequent optimization.

If you want to be exact, there is no way around using an exact simplex algorithm like qsOptEx. This will give you exact values for the reduced costs and duals. Of course, you need to use the gmp library to represent these values.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thanks a lot for your comments.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Hi Tobias,

I knew the theory behind.
The problem is that even by doing what you mentioned we still might end up with singular basis.
I have all the folowing settings:

cplex.setParam(IloCplex::EpRHS, 1e-03  );
cplex.setParam(IloCplex::NumericalEmphasis, 1  );
cplex.setParam(IloCplex::EpMrk, 0.5  );

but still get singular basis.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Which basis is singular? The one after the initial optimization, or the one after having fixed some variables and constraints and reoptimized?

In any case, I don't think that the singularity is related to the variable and constraint fixings. My guess is that your model has intrinsic numerical issues like a mix of very large and very small coefficients.
If the singularity arises for the reoptimization, you could try to resolve the model that was fixed to the optimal face from scratch by setting the "AdvInd" parameter (is this the name in Concert?) to 0. Solving from scratch has the advantage that CPLEX will basically start with a slack basis (that has no numerical issues) and therefore has higher chances to end up with a sparse basis (a basis with many slacks) than when starting from an advanced start basis.
If you change a lot of objective coefficients, reoptimizing from scratch may also be faster than starting from the previous solution that is potentially pretty bad for your new objective function.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thanks for comments.
In fact it happens in both cases. original and re-optimziations.
I have huge right hand sides with binary A matix. I think as is there any additional features which must be turned on?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I guess that since your right hand sides are huge, the bounds of the variables are huge as well (or infinite?).
Is it possible to rescale the variables? For example, express the variables in terms of million dollars instead of cents? If this is still meaningful in your model, such a scaling would decrease the right hand sides and bounds and might help CPLEX with the numerics. CPLEX internally scales the user data as well, but using your domain knowledge you may be able to do something smarter.

Tobias
#CPLEXOptimizers
#DecisionOptimization