Performance Issues
Choice of Algorithm
The Xpress‑Optimizer is essentially "three solvers in one", offering users a choice of methods to be used for solving LP and QP problems: the primal and dual simplex algorithms and the Newton barrier interior point algorithm. The best algorithm to use for optimization in a given situation is problem-specific. As a general rule, the dual simplex is usually much faster than the primal simplex if the model is not infeasible or near-infeasibility. If the problem is likely to be infeasible, then the primal simplex is probably the best choice as it makes determining the cause of the infeasibility simpler. Interior point methods such as the Newton barrier algorithm perform better on certain classes of problems, although, for a problem matrix A, if ATA is dense then the barrier will be slow.
As a default, the Xpress‑Optimizer employs the dual simplex method for solving LP problems and the barrier method for solving QP problems. For most users this will be sufficient and they need not consider changing it. If a problem seems to be taking an unusually long time to solve, however, it may be worth experimenting with the different algorithms. These may be called by specifying flags to the optimization routines, XPRSmaxim (MAXIM) and XPRSminim (MINIM). The default algorithm used is determined by the value of the control parameter, DEFAULTALG.
In the following few sections, performance issues relating to these methods and to the search for integer solutions will be discussed in more detail.
Simplex Performance
The Simplex Method
The region defined by a set of linear constraints is a polyhedron, known as the feasible region. Points with the same linear objective function value, known as a level set, form a hyperplane. It follows that an optimal value of the objective function will occur only on the boundary of the feasible region and one will always occur at one of the vertices of the polyhedron. In some cases, when the level sets of the objective function are parallel to part of the polyhedron's boundary, the optimal solution will not be unique, consisting rather of a line, plane or hyperplane of solutions. However, in this case also, the optimal solution value may be found by considering only the vertices of the feasible region, although there will obviously be a continuum of decision variable values which will produce this optimum.
In general, vertices occur at points where as many constraints and variable bounds as there are variables in the problem intersect. Simplex methods usually only consider solutions at vertices, or bases (known as basic solutions) and proceed or iterate from one vertex to another until an optimal solution has been found, or the problem proves to be infeasible or unbounded. The number of iterations required increases with model size, usually slightly faster than the number of constraints.
The primal and dual simplex methods differ in which vertices they consider and how they iterate. The dual is the default for LP problems, but may be explicitly invoked using the d flag with either XPRSmaxim (MAXIM) or XPRSminim (MINIM).
Inversion
During optimization using the simplex method, every so often the Optimizer will go through a process known as inversion, with frequency determined by the controls INVERTFREQ and INVERTMIN. This will attempt to find a more compact representation of the current solution and check its accuracy. However, it is possible that the Optimizer may be unable to find a new representation of the current solution. This may be due to accuracy problems or an unstable initial condition produced by the crash or XPRSreadbasis (READBASIS). In such a situation, a number of the vectors will be rejected from the basis and replaced by unit vectors corresponding to slack or artificial variables. Following inversion, the Optimizer subsequently tries to adjust the current solution to find a more stable one before continuing with the algorithm.
Partial Pricing vs. Devex Pricing
The primal simplex Optimizer uses a mixture of partial pricing and Paul Harris" Devex pricing as determined by the control PRICINGALG. Typically, partial pricing results in a greater number of fast iterations whereas Devex pricing results in fewer, slow iterations. Which is better is highly problem-dependent. When set to 0, the Optimizer will start by using partial pricing and automatically determine when to switch to Devex pricing. To prevent the Optimizer from switching to Devex pricing, the user can set PRICINGALG to -1. To force the Optimizer to switch to Devex pricing the PRICINGALG control can be set to 1.
Output
Whilst searching for an optimal LP solution, the Console Optimizer writes an iteration log to the screen. The same information may be obtained by library users with the XPRSsetlogfile or XPRSsetcblplog functions. This log is produced every LPLOG iterations. If this is positive, a summary output is produced, whereas a more detailed log is produced if it is negative. When set to 0, a log is displayed only when the solution terminates.
Barrier Performance
The Newton Barrier Method
In contrast to the simplex method, the Newton barrier is an interior point method for solving LP and QP problems. As the name suggests, such a method involves iteratively moving from one point to the next within the interior of the feasible region. Approaching the boundary of the region is penalized, so iterates of this method cannot leave the region. However, since optimal solutions of LP problems lie on the boundary of the feasible region, this penalty must be dynamically decreased as the algorithm proceeds in order to allow iterates to converge to the optimal solution.
Interior point methods typically yield a solution lying strictly in the interior of the feasible region and so can be only an approximation to the true optimal vertex solution. It is therefore the required proximity to the optimal solution which determines the number of iterations required, rather than the number of decision variables. Unlike the simplex method, therefore, the barrier often completes in a similar number of iterations regardless of the problem size.
The barrier solver can be invoked on a problem by using the b flag with either XPRSmaxim (MAXIM) or XPRSminim (MINIM). This is used by default for QP problems, whose quadratic objective functions result in optimal solutions that generically lie on a face of the polyhedral feasible region, rather than at a vertex.
Controlling Barrier Performance
The Newton barrier method is influenced by a number of controls which can be altered if the solution search seems slow, or if numerical problems result. Ensuring that the CACHESIZE is set correctly can have a significant effect on the performance, and must be set manually on non-Intel and non-AMD platforms. Similarly, altering the ordering algorithm for the Cholesky factorization using BARORDER can affect performance. Setting this to 2 often produces better results, although the ordering itself can be significantly slower. Other controls such as DENSECOLLIMIT can be set manually to good effect. For example, numerical problems where dense columns are detected in the tree search can be eliminated by disabling the dense column handling. This is achieved by setting DENSECOLLIMIT to a larger number. In this case the optimization speed may be degraded, but numerical behavior is usually better.
Crossover
Typically the barrier algorithm terminates when it is within a given tolerance of the optimal solution. Since this solution will lie on the boundary of the feasible region, the Optimizer may perform a crossover at this stage, enabling the optimization to be completed using the simplex method and thus yielding a 'true' optimum. If a basic optimal solution is required, then this procedure must be activated before optimization starts. The CROSSOVER control governs this, set to 1 by default for LP problems. If CROSSOVER is set to 0, no crossover will be attempted and the solution provided will be that determined purely by the barrier method.
Convergence
The optimization is normally terminated when the primal and dual solutions are feasible and the relative duality gap is less than BARGAPSTOP, or in other words:
|
 BARGAPSTOP |
For example, BARGAPSTOP = 1.0 E-8 means that eight significant figures will be correct in the optimal objective value. The BARPRIMALSTOP and BARDUALSTOP parameters give the termination criteria for the primal and dual feasibilities. In general it should not be necessary to change the BARGAPSTOP, BARPRIMALSTOP and BARDUALSTOP controls, but if a crossover is employed and the simplex algorithm takes many iterations to get from the crossover basis to an optimal basis, then reducing these controls (e.g. by a factor of 10 to 100) may be worthwhile.
The Newton barrier algorithm computes a search direction at each iteration and takes a step in this direction. If this step size is less than BARSTEPSTOP then the algorithm terminates. If convergence is very slow then it may be better to terminate prematurely by setting a higher value for BARSTEPSTOP and hence invoking the simplex method at an earlier stage.
Output
As with the simplex method, the Console Optimizer can display an iteration log. Similarly, library users may obtain the same information by employing XPRSsetlogfile or XPRSsetcbbarlog. In both cases, this is dependent on the value of the BAROUTPUT control.
Integer Programming - The Global Search
The Branch and Bound Process
The Xpress‑Optimizer uses the Branch and Bound technique to solve mixed integer programming (MIP) problems. A brief overview of this is given here to aid the user in guiding the search for integer solutions. The three major concepts involved are separation, relaxation and fathoming.
The relaxation applied to each integer programming problem is that of dropping the integrality constraints. The relaxed problem is a linear programming problem and can be solved, resulting in one of the following outcomes:
- The LP is infeasible so the MIP problem must also be infeasible;
- The LP has a feasible solution, but some of the integrality constraints are not satisfied - the MIP has not yet been solved;
- The LP has a feasible solution and all the integrality constraints are satisfied so the MIP has also been solved;
- The LP is unbounded.
The final outcome (d) is a tricky case. It can only occur at the very first relaxation, in which case the model is not well posed. It will therefore be assumed that the LP is not unbounded.
Outcomes (a) and (c) are said to "fathom" the particular MIP, since no further work on it is necessary. For case (b) more work is required, since one of the unsatisfied integrality constraints must be selected and the concept of separation applied. Suppose, for example, that the optimal LP value of an integer variable x is 1.34, violating integrality. It follows that in any solution to the original problem either x <= 1.0 or x >= 2.0. If the two resulting IP problems are solved, integer values of x are guaranteed not to be missed, so the problem is separated into two sub-problems.
If both of these sub-problems can be solved and the better of the two is chosen, then the MIP is solved. Exactly the same relaxation strategy is used to solve each of the sub-problems and consequently this is a recursive solution technique.
This can be depicted as a tree-searching algorithm with a certain degree of arbitrariness. Each node of the tree is a MIP sub-problem. That MIP is then relaxed and the LP relaxation can be solved. If the relaxation is not fathomed, then the MIP must be further separated into two more sub-problems, each having the same constraints as the node MIP, plus one further constraint each. Each node is therefore either fathomed or has two descendants.
At some point in exploring the tree an integer solution may be found, providing a bound on the solution to the problem. Clearly the LP relaxation of a MIP will have no worse an optimal objective function value than that of the MIP. The value of the best MIP node found can then act as a cutoff for outstanding nodes. If the value of the LP relaxation is no better than the cutoff, then any MIP descendant of the node cannot be better than the MIP solution value which has been found. Again the node can be fathomed and need be considered no further.
The concept of a cutoff value can be applied even when no integer solution has been found if it is known, or it may be assumed from the outset that the optimal solution must be better than some value. If the relaxation is worse than this cutoff, then the node may be abandoned. There is a danger, however, that all integer feasible solutions, including the optimal one, may be missed if an overly optimistic cutoff value is chosen.
The cutoff concept can be more powerful if a solution within a certain tolerance of the integer optimum is sought. If an integer solution is found, this may be accepted if there is no other solution more than, say, 100 better than it. The cutoff can then be set to be 100 better than the solution that has just been found.
If the problem contains sets then the nodes of the Branch and Bound tree are separated by branching on the sets this is done by choosing a position in the set and setting all members of the set to 0 either above or below the chosen point. Each member of the set has a reference row entry and the sets are ordered by these reference row entries. The optimizer used the reference row entries to decide on the branching position and so it is important to choose the reference row entries which reflect the cost of setting the set member to 0. In some cases it maybe better to model the problem with binary variables instead of sets. This is especially the case if the sets are small.
Node and Variable Selection
The branch and bound technique leaves many choices open to the user. However, in practice the success of the technique is highly dependent upon two choices.
- At any given stage there will generally be several outstanding nodes which have not been fathomed. The choice of which to solve first is known as the node selection problem;
- Having chosen a node to tackle, deciding which variable to separate upon is known as the variable selection problem.
The Optimizer incorporates a default strategy for both choices which has been found to work adequately on most problems. Several controls are provided to tailor the search strategy to a particular problem. Since the Optimizer makes its variable selection when the LP relaxation has been solved, rather than when it has selected the node, the variable selection problem will be discussed first.
Variable Selection for Branching
Each global entry has a priority for branching, either the default value of 500 or one set by the user in the directives file. A low priority value means that the variable is more likely to be selected for branching. Up and down pseudo costs for each global entity can be specified, which are estimates of the per unit degradation of forcing the entity away from its LP value.
The Optimizer selects the branching entity from among those entities of the most important priority class which remain unsatisfied. Of these, it takes the one with the highest estimated cost of being satisfied (degradation).
A rather crude estimate of the best integer solution derivable from the node is made by summing the individual entities" estimates. If these estimates are consistently biased in some problem class, it may be worthwhile to specify pseudo costs different from the default of 0.1. This can be achieved using the XPRSreaddirs (READDIRS) command.
Node Selection
Each active node has an LP relaxation value and an estimated degradation to an integer solution. The controls NODESELECTION, BACKTRACK, VARSELECTION and BREADTHFIRST determine the way the next node is selected.
The value of NODESELECTION defines the candidate set for node selection, i.e. the set of nodes from which one will be chosen, while the value of BACKTRACK defines the criterion used in selection of a node from the candidate set. If NODESELECTION is 1 (the usual default) then the two descendent nodes form the candidate set, but if both have been fathomed then all active nodes form the candidate set. If NODESELECTION is 2, all nodes are always included in the candidate set resulting in a best, or breadth first, search. If NODESELECTION is 3, a depth-first search is performed. If NODESELECTION is 4, all nodes are considered for selection in priority order for the first BREADTHFIRST nodes, after which the usual default behavior is resumed.
For deciding between the nodes in the candidate set, the value of BACKTRACK determines the selection criterion. If BACKTRACK is 1 and MIPTARGET has not been set (either directly by the user or by the search previously finding an integer solution), then the node with the best estimate is chosen. If BACKTRACK is 1 and MIPTARGET has been set, then the Forrest-Hirst-Tomlin Criterion is used. For minimization problems, this chooses the node with the highest value of:
| (MIPTARGET - objective - deg)/deg |
where deg is the estimated degradation. The value of VARSELECTION influences deg. If VARSELECTION is 1 (the default) then deg is assumed to come from the better of the two possible branching directions for each unsatisfied entity.
Various other ways of calculating deg can be actioned by setting VARSELECTION. The table below shows the possible values where upj and downj are the estimated up and down degradations of branching on global entity j.
| VARSELECTION | Estimated Degradation (deg) | |
|---|---|---|
| 1 |  j min(upj,downj) |
|
| 2 | j (upj + downj) |
|
| 3 | j (2.0·min(upj,downj) + max(upj,downj)) |
|
| 4 | j max(upj,downj) |
|
| 5 | j downj |
|
| 6 | j upj |
If BACKTRACK is 2, the node with the smallest estimated solution is always chosen. If BACKTRACK is 3 the node with the smallest bound is always chosen.
Adjusting the Cutoff Value
Since the parameters MIPRELCUTOFF and MIPADDCUTOFF have nonzero default values we must consider carefully the effect of setting MIPADDCUTOFF at different places in the set of commands to the Optimizer. If MIPADDCUTOFF is set prior to XPRSmaxim (MAXIM) or XPRSminim (MINIM) then its value may be altered by the optimization process. At the end of the LP optimization step, MIPADDCUTOFF is set to:
| max (MIPADDCUTOFF, 0.01·MIPRELCUTOFF·LP_value) |
where LP_value is the optimal value found by the LP Optimizer. When this formula is not required and a known value is to be specified for MIPADDCUTOFF, then MIPADDCUTOFF must be set after the LP Optimizer has been run. If a value is specified for MIPRELCUTOFF it must be specified before the LP Optimizer is run.
Integer Preprocessing
If MIPPRESOLVE has been set to a nonzero value before solving a MIP problem, integer preprocessing will be performed at each node of the branch and bound tree search (including the top node). This incorporates reduced cost fixing, binary variable fixing and probing at the top node. If a variable is fixed at a node, it remains fixed at all its child nodes, but it is not deleted from the matrix (unlike the variables fixed by presolve). The integer preprocessing is not influenced by the linear (l) flag in XPRSmaxim (MAXIM) and XPRSminim (MINIM).
MIPPRESOLVE is a bitmap whose values are acted on as follows:
| Bit | Value | Action |
|---|---|---|
| 0 | 1 | reduced cost fixing; |
| 1 | 2 | variable fixing; |
| 2 | 4 | probing at root node. |
So a value of 1+2=3 for MIPPRESOLVE causes reduced cost fixing and variable fixing.
If you have any comments or suggestions about these pages, please send mail to docs@dashoptimization.com.