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

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:

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:

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.