[Previous chapter] [Next chapter]

Special Types of Problem


Nonlinear objectives

Xpress-SLP 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.

Quadratic Programming

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). It is possible to solve quadratic problems using SLP, but it is not usually the best way. The reason is that the solution to a 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 is 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-SLP, 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. There is an overhead in using the QP optimizer because it cannot make use of the basis from the previous solution. However, this is usually more than offset by the saving in SLP iterations. If the objective is not semi-definite, the QP optimizer may not give a solution; 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 XPRSloadqglobal). Xpress-SLP 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.

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-SLP offers a set of components to implement MINLP using Mixed Integer Successive Linear Programming (MISLP).

Approaches to MISLP

Essentially, there are three ways to approach MISLP:

  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 within MIP. In this, MIP 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.
  3. 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 (3) 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.

Xpress-SLP normally uses the approach outlined in (2). Other approaches can be used by changing the value of the control parameter XSLP_MIPALGORITHM. 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.

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

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.


[Next] [Index]
If you have any comments or suggestions about these pages, please send mail to docs@dashoptimization.com.