Handling Infeasibilities

Topics covered in this chapter:

By default, Xpress-SLP will include penalty error vectors in the augmented SLP structure. This feature adds explicit positive and negative slack vectors to all constraints (or, optionally, just to equality constraints) which include nonlinear coefficients. In many cases, this is itself enough to retain feasibility. There is also an opportunity to add penalty error vectors to all constraints, but this is not normally required. For more details on these penalty error vectors, see the section Penalty Infeasibility Breakers in XSLP.

During cascading (see next section), Xpress-SLP will ensure that the value of a cascaded variable is never set outside its lower and upper bounds (if these have been specified).

Managing Infeasibility with Xpress-SLP

There are two sources of infeasibility when XSLP is used

1. Infeasibility introduced by the error of the approximation, most noticeable when significant steps are made in the linearization.
2. Infeasibility introduced by the activation of penalty breakers, where it was not otherwise possible to make a meaningful step in the linearization.

The infeasibility induced by the former diminishes as the solution converges, provided mild assumptions regarding the continuity of the functions describing the model are satisfied. The focus of any analysis of infeasibility in XSLP must therefore most often be on the penalty breakers (also called error vectors). For some problems, Xpress-SLP may terminate with a solution which is not sufficiently feasible for use in a desired application. The first controls to use to try to resolve such an issue are

SLPECFTOL_A

The absolute linearization feasibility tolerance is compared for each constraint in the original, nonlinear problem to its violation by the current solution.

SLPECFTOL_R

The relative linearization feasibility tolerance is compared for each constraint in the original, nonlinear problem to its violation by the current solution, relative to the maximum absolute value of the positive and negative contributions to the constraint.

Penalty Infeasibility Breakers in XSLP

Convergence will automatically address any errors introduced by movement within the linearization. When only small movements occur in the solution, then for differentiable functions the drift resulting from motion on the linearization is also limited. However, it is not always possible to stay within the linearization and still make an improving step. XSLP is often able to resolve such situations automatically by the introduction of penalty infeasibility breakers. These allow the solver to violate the linearized constraints by a small amount. Such variables are associated with large cost penalties in the linearized problems, which prevents the solution process from straying too far from the approximated feasible region. Note that if penalty breakers are required, the solution process may be very sensitive to the choice of cost penalties placed on the breakers. In most cases, XSLP's constraint analysis will automatically identify appropriate penalties as needed for each row, but for some problems additional tuning might be required. Xpress-SLP will attempt to force all penalty breakers to zero in the limit by associating a substantial cost with them in the objective function. Such costs will be increased repeatedly should the penalty breaker remain non-zero over a period of time. The current penalty cost for all such variables is available as SLPCURRENTERRORCOST. The control SLPERRORCOST determines the initial value for this cost, while the SLPERRORCOSTFACTOR controls the factor by which it increases if active error vectors remain. The maximum value of the penalty is determined by the control SLPERRORMAXCOST. If the maximum error cost is reached, it is unlikely that XSLP will converge. It is possible in this situation to terminate the solve, by setting bit 11 of SLPALGORITHM. Some problems may be sensitive to the initial value of SLPERRORCOST. If this value is too small relative to the original objective in the model, feasibility will not be sufficiently strongly encouraged during the solution process. This can cause SLP to explore highly infeasible solutions in the early stages, since the original objective will dominate any consideration of feasibility. It is even possible in this case for unboundedness of the linearizations to occur, although SLP is capable of automatic recovery from such a situation. When the initial penalty cost is too high, the penalty term will dominate the objective. This in turn may lead to initially low quality solutions being explored, with the attendant possibility of numerical errors accumulating. The control SLPOBJTOPENALTYCOST guides the process which selects an automatic value for SLPERRORCOST, but determining such a value analytically can be difficult. For some difficult problems, there may be significant benefits to selecting the value directly. Often for infeasible problems, the contribution of the individual constraints to the overall infeasibility is non-uniform. XSLP can automatically associate a weight with each row based upon the magnitude of the terms in the constraint. It is both possible to refine these weights, or alternatively to allow XSLP to update them dynamically. The latter case is called escalation, and is controlled by bit 8 of SLPALGORITHM. Devising appropriate weights manually can be difficult, and in most cases it is preferable to leave the identification of these values to Xpress-SLP. However, if it is necessary to do so, the output of XSLP may provide hints as to appropriate values if detailed logging is enabled. This can be turned on with NLPLOG. The most important points in such output are the active error vectors at each iteration, where the most attractive constraints to modify are those which occur regularly in the log in association with non-zero error vectors.

Infeasibility Analysis in the Xpress Optimizer

For problems that are solved using the Xpress Optimizer, that is LP, convex QP and QCQP and their MIP counterparts, as well as general, potentially non-convex, MINLPs that are solved to global optimality, there is normally no difficulty with establishing feasibility. Given that all of these solve to global optimality, any infeasibility is generally a proof of global infeasibility (up to tolerances), unlike SLP and Knitro, which cannot distinguish between global infeasibility and converging against a (locally) infeasible solution. When the Xpress Optimizer declares a problem to be infeasible, the tools provided with the Xpress Optimizer console can be used to analyse the infeasibility, and hence to subsequently alter the model to overcome it. One important step in this respect is the ability to retrieve an irreducible infeasible set (IIS) (using the iis command). An IIS is a statement of a particular conflict in the model between a set of constraints and bounds, which make the problem certainly infeasible. An IIS is irreducible in the sense that if any constraint or bound of the IIS were removed from the subproblem represented by the IIS, the resulting (relaxed) subproblem would be feasible. The Xpress Optimizer also contains a tool to identify the minimum weighted violations of constraints or bounds that would make the problem feasible (called repairinfeas). Both iis and repairinfeas can be applied to any LP, convex QP, or convex QCQP problem, as well as to their mixed integer counterparts. They can also be applied to nonlinear and mixed integer nonlinear problems using FICO Xpress Global. Please refer to the Xpress Optimizer and Mosel reference manuals for more information.

Managing Infeasibility with Xpress Knitro

Xpress Knitro has three major controls which govern feasibility.

KNITRO_PARAM_FEASTOL

This is the relative feasibility tolerance applied to a problem.

KNITRO_PARAM_FEASTOLABS

This is the corresponding absolute feasibility tolerance.

KNITRO_PARAM_INFEASTOL

This is the tolerance for declaring a problem infeasible.

The feasibility emphasis control, KNITRO_PARAM_BAR_FEASIBLE, can be set for models on which Knitro has encountered difficulties in finding a feasible solution. If it is set to get or get_stay, particular emphasis will be placed upon obtaining feasibility, rather than balancing progress toward feasibility and optimality as is the default. If one of the built-in interior point methods is used, as determined by KNITRO_PARAM_ALGORITHM, the feasibility emphasis control can force the iterates to strictly satisfy inequalities. It does not, however, require Knitro to satisfy all equality constraints at intermediate iterates. The migration between a pure search for feasibility, and a balanced approach to feasibility and optimality, may be further fine tuned by using the KNITRO_PARAM_BAR_SWITCHRULE control. Should a model still fail to converge to a feasible solution, the KNITRO_PARAM_BAR_PENCONS control may be used to instruct Knitro to introduce penalty breakers of its own. This option has similar behaviour to the corresponding option in XSLP.