Trying to obtain dual variables and reduced costs after solving a MIP

Answer

The CPXsolution, CPXgetpi, CPXgetdj, IloCplex::getDuals, IloCplex::getReducedCosts,IloCplex.getDuals and IloCplex.getReducedCosts routines all require a factorized basis associated with the solution values. When the CPLEX finishes solving a MIP, no such factorization exists. If you are only interested in variable values, call routines to just obtain those values (that is, CPXgetmipx, CPXgetmipslack, IloCplex::getValues, IloCplex::getSlacks, IloCplex.getValues, or IloCplex.getSlacks) rather than routines like CPXsolution. If you require dual variables and reduced costs, then use the CPXchgprobtype, IloCplex::solveFixed or IloCplex.solveFixed routine to change the problem type to fixed. The resulting linear program has all integer variables fixed at their values in the best integer solution. After fixing the problem, call CPXlpopt() to solve this LP if using the C API; the solveFixed routines in the C++ and Java API will solve the fixed LP without any additional function call. After solving this LP, you can call the appropriate function to obtain the dual values and reduced costs.

Since the CPLEX interactive optimizer calls these same functions, it will behave the same way. With this in mind, use the "change problem" command to fix the problem if you need to display dual variables and reduced costs. Then, solve the fixed problem; you can then display the dual variables and reduced costs. Click here if you need more information on obtaining dual variable and reduced cost values when using interactive CPLEX.

CPLEX also supports discrete modeling objects in addition to integer variables, including special ordered sets (SOSs) and indicator constraints. In addition, CPLEX's object oriented APIs support logical constraints and piecewise linear functions that, when translated to the model CPLEX actually solves, involve multiple internal constraints and variables. The presence of any of these discrete extensions in your model might complicate the interpretation of the fixed problem. In general, since dual variables and reduced costs provide information about incremental changes to the model, they probably will not be meaningful for such discrete objects. However, here is some additional information regarding these extensions and their dual variables or reduced costs in the fixed problem.

• For special ordered sets, CPLEX simply fixes the variables at their values associated with the incumbent solution. SOSs do not create any constraint, so an SOS does not generate a dual variable. The SOS has no individual reduced cost, but reduced costs are available for the individual variables in the SOS.


• Indicator constraints consist of a binary indicator variable whose value in a solution determines whether an associated linear constraint is active. For the fixed model, CPLEX includes the linear constraints implied to be active by the solution values of the indicator variables. In contrast, CPLEX excludes any linear constraints in indicator constraints not enforced by the indicator variable values. Since the fixed model might not include all of the linear constraints associated with indicator constraints, the indicator constraints in the original model and the associated dual variables in the fixed model do not have a one to one correspondence. Therefore, one must examine the indicator variable values to identify the dual variable associated with the indicator constraint. CPLEX does not currently list the indicator constraint names in the fixed model.


• Users of the object oriented APIs might use discrete modeling extensions such as IloPiecewiseLinear, IloMax and IloAbs that internally create multiple internal variables and constraints. While these multiple variables and constraints exist in the fixed model resulting from a call to the solveFixed() method of the IloCplex class, their values in the resulting optimal solution are not accessible through the object oriented APIs.

Note also that if the MIP has continuous variables, the objective of the fixed model can differ from objective value reported when the incumbent solution was first found. This can happen because CPLEX has many different procedures to derive integer feasible solutions. Some of them provide an optimal basis to a node LP that will also be optimal for the fixed problem, but others do not. In the latter case, changes to the continuous variables in the fixed model might yield an improvement in the objective.

Finally, note that since duality theory for MIPs is not nearly as developed as for LPs, no dual model for the MIP is available. Hence, one cannot obtain the dual variables for the MIP CPLEX solves by creating a dual model and solving it. That said, some results on the dual of a MIP have been development, but, as of this writing, they remain primarily of theoretical interest. For example, click here for a paper on Integer Programming Duality.