I am solving a classical network flow problem with CPLEX (using Java). It contains the constraint Ax=b (A being the node-arc incidence matrix, x the decision variable for link flows, and b the given right hand sides). I am interested in the shadow prizes of in-/decreasing b in one dimension.
In a non degenerate problem the shadow prices are given by the dual variables on the constraint Ax=b. However, my problem is degenerate. Thus one optimal solution can be expressed by several combinations of basis and non-basis variables. Each of theses combinations should have different dual variables.
At least one of theses duals should give me a the shadow price of increasing b, another dual will provide the shadow price of decreasing b. (According to W.Powell (1989): "A review of sensitivity results for linear networks and a new approximation to reduce the effects of degeneracy")
My question is: After solving the LP with CPLEX and obtaining a first set of duals, how do I get CPLEX to perform a swap of basis and non-basis variables, so that I can obtain another set of duals?
The whole discussion below refers to the dual problem.
Non-basic variables with zero reduced cost can enter the basis at positive level and form alternative optimal solutions. Thus, if the optimal objective value of the problem is z* and c'x is the associated objective function, you can add the constraint
c'x = z*, change the objective function to be a different one, let simplex perform one iteration, and iterate. Each iteration after the second one should (i) generate a new optimal solution or (ii) generate an optimal solution already generated, in which case we can change the objective function and iterate.
This technique is described here, with a reference to the C API functions:
For linear programs reduced costs of zero for nonbasic variables indicate an alternate optimal basis exists. Furthermore, you can use the routines CPXgetgrad and CPXgetx to determine whether the associated pivot is degenerate (in which case the solution values remain unchanged but the basis changes) or not (in which case both the solution values and the basis change). Note that reduced costs on slack variables are the negative of the associated dual variables. In addition, the routine CPXaddrows provides a simple way to enumerate alternate optimal solutions. Suppose the optimal objective value of the original problem is z*, and that c'x is the associated objective function. Use CPXaddrows to add the following constraint:
c'x = z*
Change the objective function to some other objective; set a simplex iteration limit of 1 (one) (or solution limit of 1 in the case of a MIP); then repeatedly optimize the problem. Each feasible solution to this modified problem is an optimal solution to the original problem. This procedure will provide some, but not necessarily all, alternate optimal solutions to the original problem. Note that this method of adding a constraint will also work on a continuous model with a quadratic objective, whereas the method of fixing nonbasic variables with zero reduced costs does not readily extend to nonlinear objectives. Since CPLEX solves convex quadratic programs, the constraint on the quadratic objective must be an inequality rather than an equality, as described in the case of the linear objective above. Since only nonbasic variables with reduced costs of 0 (zero) can change when the application moves from one alternate optimal solution to another, you can also enumerate alternate optimal solutions by using the routines CPXgetdj and CPXgetpi to identify the nonbasic structural variables and slacks with nonzero reduced costs. Then, fix these structural variables to their current values using CPXchgbds, and fix the slack variables with CPXchgsense. Set the simplex iteration limit to 1 (one); change the objective as before; and you can enumerate some, but not all, alternate optimal solutions.
Another way, very similar, is to add a small random vector to the relevant objective function coefficients (i.e., "perturb" the objective), resolve the problem and verify that the new vertex is not the same as the old vertex and that it gives the same objective function value as the old vertex (if not, perturb again and repeat). This technique is described nicely in this post by Paul Rubin.
For MIP problems CPLEX provides a solution pool that keeps a certain number of solutions already found, and the function populate, which searches for more solutions. This post (again by Paul Rubin) explains how this works under the Java API.
Update
A follow up on the comment below:
The objective function value will remain the same, as we add the constraint that the objective should equal its optimal value (c'x = z*). When I say "generate a new optimal solution" above, I refer to a new set of optimal dual values, i.e., a different optimal dual basis. The primal solution will remain the same (provided the primal problem is degenerate and there are not multiple optimal solutions for the primal).
The fact that all duals are equal to zero sounds like an implementation issue. Did you check that the resulting LP is feasible and that a finite optimal solution is returned? Also, I am not sure I understand the first part of the above statement (after changing ... variables). Changing the (dual) basis is by definition a reevaluation of the dual variables. When a problem is primal degenerate, (which is the current case), there are multiple dual optimal solutions, therefore a change of basis in the dual space results in the same optimal solution value and in the same primal basis (unless the problem has both primal and dual degeneracy).
This is true, but in this case we need to solve the problem 2 * n times, where n is the size of b: we need to substitute each component of b with b - 1 and b + 1 at a time are resolve.
I am not aware of any method that can do what you are looking for without resolving.. I found a relevant post by Tobias Achterberg, the main developer of CPLEX, who essentially describes the same method. Also, this paper recovers an optimal primal solution from an optimal dual solution, via resolving the LP again. It might be possible without resolving if you exploit the network flow structure of your problem, but this will require building a customized algorithm for that specific problem. I had done something similar for a lot sizing formulation some years ago, and it does require a bit of effort.
I hope this helps!