Manual Control of Presolve

INDEX PREVIOUS NEXT

The first control function provided by the advanced presolve interface is CPXpresolve, which manually invokes presolve on the supplied problem. Once this routine is called on a problem, the problem has a presolved problem associated with it. Subsequent calls to optimization routines (CPXprimopt, CPXdualopt, CPXbaropt, CPXmipopt) will use this presolved problem without repeating the presolve, provided no operation that discards the presolved problem is performed in the interim. The presolved problem is automatically discarded if a problem modification is performed that is incompatible with the setting of CPX_PARAM_REDUCE (further information is provided in Modifying a Problem).

By using the parameter CPX_PARAM_REDUCE to restrict the types of presolve reductions, CPLEX can make use of the optimal basis of the presolved problem. If you set CPX_PARAM_REDUCE to restrict presolve reductions, then make problem modifications that don't invalidate those reductions, CPLEX will automatically use the optimal basis to the presolved problem. On the other hand, if the nature of the problem modifications is such that you cannot set CPX_PARAM_REDUCE, you can still perform an advanced start by making the modifications, calling CPXpresolve to create the new presolved problem, then calling CPXcopystart, passing the original model and any combination of primal and dual solutions. With nondefault settings of CPX_PARAM_REDUCE, CPLEX will crush the solutions and use them to construct a starting basis for the presolved model. If you are continuing with primal simplex, only providing a primal starting vector will usually perform better.

We should point out a few of the subtleties associated with using CPXcopystart to start an optimization from an advanced, presolved solution. This routine only creates a presolved solution vector if the presolved problem is already present (either because the user called CPXpresolve or because the user turned off some presolve reductions through CPX_PARAM_REDUCE and then solved a problem). The earlier sequence would not have started from an advanced solution if CPXcopystart had been called before CPXpresolve. Another important detail about CPXcopystart is that it crushes primal and/or dual solutions, not bases. It then uses the crushed solutions to choose a starting basis. If you have a basis, you need to compute optimal primal and dual solutions (using CPXcopybase and then CPXprimopt), extract them, and then call CPXcopystart with them to use the corresponding advanced solution. In general, starting with both a primal and dual solution is preferable to starting with one or the other. One other thing to note about CPXcopystart is that the primal and dual slack (slack and dj) arguments are optional. The routine will compute slack values if none are provided.

Recall that you can set the parameter CPX_PARAM_ADVIND to 2 in order to use advanced starting information together with presolve. At this setting, CPLEX will use starting information provided to it with CPXcopystart or CPXcopybase when it solves an LP with the primal or dual simplex optimizer in the following way. If no presolved model is available, presolve is invoked. Then the starting information is crushed and installed in the presolved model. Finally, the presolved model is solved from the advanced (crushed) starting point.

Another situation where a user might want to use CPXpresolve is to work directly on the presolved problem. By calling CPXgetredlp immediately after CPXpresolve, the user can obtain a pointer to the presolved problem. For an example of how this might be used, the user could call routines CPXcrushx and CPXcrushpi to presolve primal and dual solution vectors, call CPXgetredlp to get access to the presolved problem, then use CPXcopystart to copy the presolved solutions into the presolved problem, then optimize the problem, and finally call routines CPXuncrushx and CPXuncrushpi--CPXqpuncrushpi for QPs--to unpresolve solutions from the presolved problem, creating solutions for the original problem.

The routine CPXgetredlp provides the user access to internal CPLEX data structures. The presolved problem must not be modified by the user. If the user wishes to manipulate the reduced problem, the user should make a copy of it (using CPXcloneprob) and manipulate the copy instead.

The advanced presolve interface provides another call that is useful when working directly with the presolved problem (either through CPXgetredlp or through the advanced MIP callbacks). The call to CPXcrushform translates a linear expression in the original problem into a linear expression in the presolved problem. The most likely use of this routine is to add user cuts to the presolved problem during a mixed integer optimization. The advanced presolve interface also provides the reverse operation. The CPXuncrushform routine translates a linear expression in the presolved problem into a linear expression in the original problem.

A limited presolve analysis is performed by CPXbasicpresolve and by the Concert Technology method IloCplex::basicPresolve. This function detects which rows are redundant and computes strengthened bounds on the variables. This information can be used to derive some types of cuts that will tighten the formulation, to aid in formulation by pointing out redundancies, and to provide upper bounds for variables. CPXbasicpresolve does not create a presolved problem.

The interface allows the user to manually free the memory associated with the presolved problem using routine CPXfreepresolve. The next optimization call (or call to CPXpresolve) recreates the presolved problem.