Special Types of Problem

Topics covered in this chapter:

Nonlinear objectives

Xpress NonLinear works with nonlinear constraints. If a nonlinear objective is required (except for the special case of a quadratic objective — see below) then the objective should be provided using a constraint in the problem. For example, to optimize f(x) where f is a nonlinear function and x is a set of one or more variables, create the constraint

f(x) - X = 0

where X is a new variable, and then optimize X.

In general, X should be made a free variable, so that the problem does not converge prematurely on the basis of an unchanging objective function. It is generally important that the objective is not artificially constrained (for example, by bounding X) because this can distort the solution process. Also, as such an objective transfer row is not a real constraint, no error vectors should be added (row can be enforced); feasibility should be provided by the transfer variable X being free.

Convex Quadratic Programming

Convex quadratic programming (QP) is a special case of nonlinear programming where the constraints are linear but the objective is quadratic (that is, it contains only terms which are constant, variables multiplied by a constant, or products of two variables multiplied by a constant) and convex (convexity is checked by the Xpress Optimizer). It is possible to solve convex quadratic problems using SLP, but it is not usually the best way. The reason is that the solution to a convex QP problem is typically not at a vertex. In SLP a non-vertex solution is achieved by applying step bounds to create additional constraints which surround the solution point, so that ultimately the solution has been obtained within suitable tolerances. Because of the nature of the problem, successive solutions will often swing from one step bound to the other; in such circumstances, the step bounds are reduced on each SLP iteration but it will still take a long time before convergence. In addition, unless the linear approximation is adequately constrained, it will be unbounded because the linear approximation will not recognize the change in direction of the relationship with the derivative as the variable passes through a stationary point. The easiest way to ensure that the linear problem is constrained is to provide realistic upper and lower bounds on all variables.

In Xpress NonLinear, convex quadratic problems can be solved using the quadratic optimizer within the Xpress optimizer package. For pure QP (or MIQP) problems, therefore, SLP is not required. However, the SLP algorithm can be used together with QP to solve problems with a quadratic objective and also nonlinear constraints. The constraints are handled using the normal SLP techniques; the objective is handled by the QP optimizer. If the objective is not convex (not semi-definite), the QP optimizer may not give a solution (with default settings, it will produce an error message); SLP will find a solution but — as always — it may be a local optimum.

If a QP problem is to be solved, then the quadratic component should be input in the normal way (using QMATRIX or QUADOBJ in MPS file format, or the library functions XPRSloadqp or XPRSloadmiqp). Xpress NonLinear will then automatically use the QP optimizer. If the problem is to be solved using the SLP routines throughout, then the objective should be provided via a constraint as described in the previous section.

This applies to quadratically constrained (QCQP and MIQCQP) problems as well.

For a description on when it's more beneficial to use the XPRS library to solve QP or QCQP problems, please see Selecting the right algorithm for a nonlinear problem - when to use the XPRS library instead of XSLP.

Mixed Integer Nonlinear Programming

Mixed Integer Non-Linear Programming (MINLP) is the application of mixed integer techniques to the solution of problems including non-linear relationships. Xpress NonLinear offers a set of components to implement MINLP using Mixed Integer Successive Linear Programming (MISLP).

Mixed Integer SLP

The mixed integer successive linear programming (MISLP) solver is a generalization of the traditional branch and bound procedure to nonlinear programming. The MIP engine is used to control the branch-and-bound algorithm, with each node being evaluated using SLP. MIP then compares the SLP solutions at each node to decide which node to explore next, and to decide when an integer feasible and ultimately optimal solution have been obtained.

MISLP, also known as SLP within MIP, offers nonlinear specific root heuristics controlled by control XSLP_HEURSTRATEGY.

Other generic heuristics are controlled by the respective XPRS heuristics controls.

The branch and bound tree exploration is executed in parallel. Use the XPRS control MIPTHREADS to limit the number of threads used.

Normally, the relaxed problem is solved first, using XSLPnlpoptimize with the -l flag to ignore the integer elements of the problem. It is also possible to call the XSLPnlpoptimize routine with the -g flag and allow it to do the initial SLP optimization as well. In either case, ensure that the control parameter XSLP_OBJSENSE is set to +1 (minimization) or -1 (maximization) before calling XSLPnlpoptimize.

The actual algorithm employed is controlled by a number of control parameters, as well as offering the possibility of direct user interaction through call-backs at key points in the solution process.

Heuristics for Mixed Integer SLP

For hard MINLP problems, or where a solution must quickly be generated, the root heuristics of MISLP can be executed as stand alone methods. These approaches can be used by changing the value of the control parameter XSLP_MIPALGORITHM.

there are two MISLP heuristics:

1. MIP within SLP. In this, each SLP iteration is optimized using MIP to obtain an integer optimal solution to the linear approximation of the original problem. SLP then compares this MIP solution to the MIP solution of the previous SLP iteration and determines convergence based on the differences between the successive MIP solutions.
2. SLP then MIP. In this, SLP is used to find a converged solution to the relaxed problem. The resulting linearization is then fixed (i.e. the base point and the partial derivatives do not change) and MIP is run to find an integer optimum. SLP is then run again to find a converged solution to the original problem with these integer settings.

The approach described in (1) seems potentially dangerous, in that changes in the integer variables could have disproportionate effects on the solution and on the values of the SLP variables. There are also question-marks over the use of step-bounding to control convergence, particularly if any of the integer variables are also SLP variables.

The approach described in (2) has the big advantage that MIP is working on a linear problem and so can take advantage of all of the special attributes of such a problem. This means that the solution time is likely to be much faster than the alternatives. However, if the real problem is significantly non-linear, the integer solution to the initial SLP solution may not be a good integer solution to the original problem and so a false optimum may occur.

Fixing or relaxing the values of the SLP variables

The solution process may involve step-bounding to obtain the converged solution. Some MIP solution strategies may want to fix the values of some of the SLP variables before moving on to the MIP part of the process, or they may want to allow the child nodes more freedom than would be allowed by the final settings of the step bounds. Control parameters XSLP_MIPALGORITHM, XSLP_MIPFIXSTEPBOUNDS and XSLP_MIPRELAXSTEPBOUNDS can be used to free, or fix to zero, various categories of step bounds, thus effectively freeing the SLP variables or fixing them to their values in the initial solution.

At each node, step bounds may again be fixed to zero or relaxed or left in the same state as in the solution to the parent node.

XSLP_MIPALGORITHM uses bits 2-3 (for the root node) and 4-5 (for other nodes) to determine which step bounds are fixed to zero (thus fixing the values of the corresponding variables) or freed (thus allowing the variables to change, possibly beyond the point they were restricted to in the parent node).
Set bit 2 (4) of XSLP_MIPALGORITHM to implement relaxation of defined categories of step bounds as determined by XSLP_MIPRELAXSTEPBOUNDS at the root node (at each node).
Set bit 3 (5) of XSLP_MIPALGORITHM to implement fixing of defined categories of step bounds as determined by XSLP_MIPFIXSTEPBOUNDS at the root node (at each node).

Alternatively, specific actions on setting bounds can be carried out by the user callback defined by XSLPsetcbprenode.

The default setting of XSLP_MIPALGORITHM is 17 which relaxes step bounds at all nodes except the root node. The step bounds from the initial SLP optimization are retained for the root node.

XSLP_MIPRELAXSTEPBOUNDS and XSLP_MIPFIXSTEPBOUNDS are bitmaps which determine which categories of SLP variables are processed.

Bit 1

Process SLP variables which do not appear in coefficients but which do have coefficients (constant or variable) in the original problem.

Bit 2

Process SLP variables which have coefficients (constant or variable) in the original problem.

Bit 3

Process SLP variables which appear in coefficients but which do not have coefficients (constant or variable) in the original problem.

Bit 4

Process SLP variables which appear in coefficients.

In most cases, the default settings (XSLP_MIPFIXSTEPBOUNDS=0, XSLP_MIPRELAXSTEPBOUNDS=15) are appropriate.

Iterating at each node

Any number of SLP iterations can be carried out at each node. The maximum number is set by control parameter XSLP_MIPITERLIMIT and is activated by XSLP_MIPALGORITHM. The significant values for XSLP_MIPITERLIMIT are:

0

Perform an LP optimization with the current linearization. This means that, subject to the step bounds, the SLP variables can take on other values, but the coefficients are not updated.

1

As for 0, but the model is updated after each iteration, so that each node starts with a new linearization based on the solution of its parent.

n>1

Perform up to n SLP iterations, but stop when a termination criterion is satisfied. If no other criteria are set, the SLP will terminate on XSLP_ITERLIMIT or XSLP_MIPITERLIMIT iterations, or when the SLP converges.

After the last MIP node has been evaluated and the MIP procedure has terminated, the final solution can be re-optimized using SLP to obtain a converged solution. This is only necessary if the individual nodes are being terminated on a criterion other than SLP convergence.

Termination criteria at each node

Because the intention at each node is to get a reasonably good estimate for the SLP objective function rather than to obtain a fully converged solution (which is only required at the optimum), it may be possible to set looser but practical termination criteria. The following are provided:

Testing for movement of the objective function
This functions in a similar way to the extended convergence criteria for ordinary SLP convergence, but does not require the SLP variables to have converged in any way. The test is applied once step bounding has been applied (or XSLP_SBSTART SLP iterations have taken place if step bounding is not being used). The node will be terminated at the current iteration if the range of the objective function values over the last XSLP_MIPOCOUNT SLP iterations is within XSLP_MIPOTOL_A or within XSLP_MIPOTOL_R * OBJ where OBJ is the average value of the objective function over those iterations.

Related control parameters:

XSLP_MIPOTOL_A	Absolute tolerance
XSLP_MIPOTOL_R	Relative tolerance
XSLP_MIPOCOUNT	Number of SLP iterations over which the movement is measured

Testing the objective function against a cutoff
If the objective function is worse by a defined amount than the best integer solution obtained so far, then the SLP will be terminated (and the node will be cut off). The node will be cut off at the current SLP iteration if the objective function for the last XSLP_MIPCUTOFFCOUNT SLP iterations are all worse than the best obtained so far, and the difference is greater than XSLP_MIPCUTOFF_A and XSLP_MIPCUTOFF_R * OBJ where OBJ is the best integer solution obtained so far.

Related control parameters:

XSLP_MIPCUTOFF_A	Absolute amount by which the objective function is worse
XSLP_MIPCUTOFF_R	Relative amount by which the objective function is worse
XSLP_MIPCUTOFFCOUNT	Number of SLP iterations checked
XSLP_MIPCUTOFFLIMIT	Number of SLP iterations before which the cutoff takes effect

Callbacks

User callbacks are provided as follows:

XSLPsetcbintsol(XSLPprob Prob,
                int (*UserFunc)(XSLPprob myProb, void *myObject),
                void *Object);

UserFunc is called when an integer solution has been obtained. The return value is ignored.

XSLPsetcboptnode(XSLPprob Prob,
                 int (*UserFunc)(XSLPprob myProb, void *myObject, int *feas),
                 void *Object);

UserFunc is called when an optimal solution is obtained at a node.
If the feasibility flag *feas is set nonzero or if the function returns a nonzero value, then further processing of the node will be terminated (it is declared infeasible).

XSLPsetcbprenode(XSLPprob Prob,
                 int (*UserFunc)(XSLPprob myProb, void *myObject, int *feas),
                 void *Object);

UserFunc is called at the beginning of each node after the SLP problem has been set up but before any SLP iterations have taken place.
If the feasibility flag *feas is set nonzero or if the function returns a nonzero value, then the node will be declared infeasible and cut off. In particular, the SLP optimization at the node will not be performed.

XSLPsetcbslpnode(XSLPprob Prob,
                 int (*UserFunc)(XSLPprob myProb, void *myObject, int *feas),
                 void *Object);

UserFunc is called after each SLP iteration at each node, after the SLP iteration, and after the convergence and termination criteria have been tested.
If the feasibility flag *feas is set nonzero or if the function returns a nonzero value, then the node will be declared infeasible and cut off.

Integer and semi-continuous delta variables

Functions implementing piecewise linear expressions often lead to local stalling due to the partial derivatives not capturing the true nature of the behaviour of the function. Such functions are often implemented as user functions or expressions using the abs function. To provide Xpress with a better way of evaluating such expressions, it is possible to mark variables (typically the key dependencies of the expression) as having a semi-continuous delta variable with a minimum perturbation size associated, which means the value of any expression that involves this variable is expected to meaningfully change if the variable's value in the current solution is changed by at least the semi-continuous bound of the delta. If a minimum meaningful perturbation is not known, the variable's delta may be set up to being of type explore, when SLP will trial several values up to the provided maximum in case zero partials are detected. Using exploration deltas may significantly increase the number of times the formulas the variable is used in are evaluated.

It is important to note that the value with a semi-continuous delta will still be allowed to take any value and make arbitrary steps between iterations, the extra information of the delta variable is solely used as a means of better evaluating the effect of change per variable.

User functions that can only be evaluated at given values (e.g. lookup tables or simulations over integer input) may be modelled with variables with an integer delta variable. If a variable's delta variable is flagged as being integer, with a step value of 'delta', then assuming the variable has an initial value of 'x0', the possible values of the variable are 'x0 + i * delta' where 'i' is an integer number. If no initial value is provided, the lower bound (or zero if no lower bound) is used to start the possible values from.

Variables with a semi-continuous delta are not expected to make the problem harder, in fact, the extra information usually aids the solve noticeably.

A model with variables with integer deltas is considered to be hard. An integer delta is expected to be used to model the domain of user functions, and should not be used to otherwise model integrality of the original variable. Variables with an integer delta used in constraints tend to make the problem difficult to solve unless their use is balanced by the presence of infeasibility breaker variables (penalty slacks).

To change the type of a delta variable, use 'XSLPchgdeltatype' in the API and the 'setdeltatype' method in Mosel.

If variables with integer deltas are present in the problem, then SLP will run a number of heuristics as part of the solve, please refer to XSLP_GRIDHEURSELECT.