Originally posted by: Falcon_G

Hi everybody

Let P be the primal problem which is degenerate.

Let D be the dual of P which has multiple solution.

Let stay in the space of D variables. I solve D to optimality and I know the optimal of P which I can obtain from the reduced cost of constraints in D.

Now, I do not want to change the solution of P but I want to change my objective function such that it gives me another solution of D with the same solution to P (another optimal of D).

as solution to P are reduced costs of the constraints in D, is there anyway in CPLEX helping me to fix those reduced costs (euivalently  fix solution to P).

Any constructive comment is appreciated.

regards

If you just want another optimal solution to the dual (D), and you solved (D) directly, I suggest getting the objective sensitivity information (IloCplex.getObjSA method in the Java API). If (D) has multiple optima, at least one of the objective coefficients will have a lower or upper limit equal to its current value in the sensitivity output. Nudge the coefficient slightly past that limit, reoptimize (D) and you should get another solution that is optimal in the original (D). (I suggest confirming that its value in the original dual objective is a match, just in case you nudged it a bit too far.)

Paul

Originally posted by: Falcon_G

Dear Paul, Thanks for your comment.

Well, I remember  1-2 years ago (you may also remember), in one of the discussions on Benders, it was said that when doing magnanti-wang method using the relative interior point, one only needs to fix some of the reduced costs and re-optimize the same model (with the objexpr=optimal added) with the new objective to move over the optimality face.

I never understood how this can be done directly. The forum seems to have been migrated and it is not easy to find that conversation now.

Sadly, I can barely remember one to two days ago, let alone years ago. :-) The forum migration has caused more than a few headaches, for the IBM staff as well as for us users.

Sorry, without the specifics in front of me, I can't really grasp what's going on or what you're trying to do.

Originally posted by: TobiasAchterberg

If you have explicitly formulated the dual, then it this not too hard to do.

Let us first consider the case in which you want to get alternative optimal solutions to a primal LP that has multiple optimal solutions, just to avoid the confusion that comes from dualization. Let (x,s) be an optimal solution and (y,r) the associated dual/reduced cost vector. Now, the optimal face of this primal LP can be obtained by fixing all variables with non-zero reduced costs r_j to their current value x_j (which is either the lower or upper bound) and by changing the sense of all constraints with non-zero dual y_i to equality (i.e., fixing the slack variable of the constraint to 0). Now, you can select an arbitrary objective function in this restricted primal problem, reoptimize, and you will get some other optimal solution to the original primal LP. This is because only those variables and slacks with zero reduced costs remain in the problem, hence there will be no more change to the original objective function.

Now apply the same to the dual model. Say (y,r) is an optimal solution of the dual, and (x,s) is the dual's dual solution, i.e., the solution and slack vector of the primal. Now, in order to stay on the optimal face of the dual, you need to fix the dual variables y_i that correspond to a non-zero s_i, and you have to turn the dual inequalities j with x_j non-zero into equations. Then, change the dual objective function (i.e., the primal right hand side vector and the primal bounds of the variables) and reoptimize.

Tobias