solver.com

For an explanation of these types of problems, please see Mixed-Integer and Constraint Programming.

Branch and Bound

The standard Microsoft Excel Solver uses a basic implementation of the Branch and Bound method to solve MIP problems.  Its speed limitations make it suitable only for problems with a small number (perhaps 10 or 20) integer variables.

The Premium Solver and Premium Solver Platform use an extended Branch and Bound method that supports the alldifferent constraint as a native type, as well as reduced cost fixing for integer variables.  It also uses more sophisticated rules for choosing the next node to explore and the next variable to branch upon, based upon pseudocosts which are estimates of the change in the objective that will result from branching on a given variable.

The Large-Scale GRG Solver, Large-Scale SQP Solver, KNITRO Solver, MOSEK Solver, and LGO Global Solver make use of the Premium Solver Platform's Branch and Bound method to handle integer variables and the alldifferent constraint.

The Large-Scale LP Solver an integrated Branch and Bound plus Cut Generation strategy, often called Branch and Cut.  It supports the alldifferent constraint by generating an equivalent matrix of 0-1 variables and incorporating these into the problem.  Its Branch and Bound method uses pseudocosts, degradation factors and strong branching, and it implements a number of cuts.

The XPRESS Solver Engine uses an integrated and highly tuned Branch and Cut strategy.  It uses a variety of node selection and branch variable selection strategies, including pseudocosts, degradation factors and strong branching, and offers many user options for controlling the search strategy.  Like the Large-Scale LP Solver, it supports the alldifferent constraint by generating an equivalent matrix of 0-1 variables and incorporating these into the problem.

Strong Branching

Strong Branching is a method used to estimate the impact of branching on each integer variable on the objective function (its pseudocost), by performing a few iterations of the Dual Simplex method. Such pseudocosts are used to guide the choice of the next subproblem to explore, and the next integer variable to branch upon, throughout the Branch and Bound process.

The Large-Scale LP Solver and the XPRESS Solver Engine use Strong Branching techniques in their own Branch and Bound methods.

Preprocessing and Probing

Preprocessing and probing strategies exploit the special properties of 0-1 or binary integer variables.  For example, they use the constrained settings of certain 0-1 variables to determine settings for other 0-1 variables, without solving an optimization subproblem.

The standard Microsoft Excel Solver and the Premium Solver do not employ any such strategies.  The Premium Solver Platform uses several Preprocessing and Probing methods including feasibility testing, optimality fixing, bounds improvement and variable reordering for Branch and Bound.

The Large-Scale LP Solver, Large-Scale SQP Solver, and MOSEK Solver make full use of the Premium Solver Platform's Preprocessing and Probing methods.

The XPRESS Solver Engine uses a variety of Preprocessing and Probing strategies including most of the logical preprocessing methods of the Premium Solver Platform, reduced cost fixing, and probing at the top node.

Cut Generation

Cut Generation involves the automatic generation of additional constraints, or "cuts," that reduce the size of the feasible region for the optimization subproblems that must be solved, without eliminating any potential integer solutions.

The LP/Quadratic Solver in the Premium Solver Platform can generate both Gomory Cuts and Lifted Cover Inequalities at the root node, using a "Cut and Branch" framework.  The Large-Scale SQP Solver and the MOSEK Solver can generate Lifted Cover Inequalities at the root node.

The Large-Scale LP Solver uses a wide range of Cut Generation methods.  It can generate Lift and Cover, Rounding, Knapsack, Gomory, Clique and "Odd Hole" cuts in several passes at any node in the Branch and Bound tree.

The XPRESS Solver Engine employs sophisticated Cut Generation methods in an integrated Branch and Cut framework.  It can generate both Gomory Cuts and Lifted Cover Inequalities at any node.  User options make it possible to control cut frequency and the depth of nodes eligible for cut generation.

Integer Heuristics

Heuristics are "rules of thumb" that may often, but not always, succeed in achieving a given result.  the Evolutionary Solver and the LP/Quadratic Solver in the Premium Solver Platform, and the Large-Scale SQP Solver and MOSEK Solver each use heuristics to attempt to find an integer feasible solution, or "incumbent," early in the Branch and Bound search.  Such an incumbent can be used to prune the search tree and save time later in the search.

The XPRESS Solver Engine makes sophisticated use of integer heuristics.  User options make it possible to control the type and frequency of application of these heuristic rules.

Nontraditional Methods

The Evolutionary Solver built into the Premium Solver Platform and the OptQuest Solver use "nontraditional methods" to handle integer variables and the alldifferent constraint.  In both of these solvers, integer variables and permutations are represented directly, and candidate solutions are generated that always satisfy integer and alldifferent constraints.  The Evolutionary Solver uses several different integer- and permutation-preserving mutation and crossover operators to generate new candidate solutions.

Next:  Smooth Nonlinear Optimization

Back to Technology Summary