Frontline Systems, Excel Solver, optimization software, Solver Excel, simulation software
Solver.com
From Frontline Systems, developers of the Excel Solver.

Solver tutorials

Learn to use optimization for resource allocation, and Monte Carlo simulation for risk analysis of your model.


 

Solver Platform SDK - Faster Solution of Mixed-Integer Problems

Faster Solution of Mixed-Integer Problems

The Solver Platform SDK excels at solving integer linear programming problems, with 0-1 or binary integer variables, general integer variables, and integer variables in "alldifferent" groups.  It employs powerful Cut Generation methods, for faster solution of LP/MIP problems, in an overall Branch and Cut framework. 

It uses Strong Branching to guide the choice of the next subproblem to explore, and the next integer variable to branch upon.  It automatically generates a wide range of cuts -- new constraints that 'cut off' portions of the feasible region of LP subproblems without eliminating any possible integer solutions. 

Among others, Probing Cuts determine the values of some binary integer variables based on the settings of others, and Lift and Cover Cuts, Clique Cuts, and new Flow Cover and Mixed Integer Rounding cuts are often effective in speeding up the Branch and Bound search.  And it uses a Rounding Heuristic and a Local Search Heuristic to find new integer solutions "close to" existing solutions. 

These strategies often drastically speed up the solution of integer problems, often by factors of 1000 or more over the standard Excel Solver.

Speeding the Solution of MIP Problems

You have complete control over the strategies used by the SDK to speed the solution of mixed-integer problems.  You simply set the appropriate "parameter" properties of the LP/Quadratic Solver engine.  For example, to ask the SDK to generate "lift and cover cuts" (a powerful strategy for many problems), you would write:

problem.Engine.Params["LiftAndCoverCuts"].Value = 1;

If you're programming in a procedural language such as C, you can accomplish the same thing with:

SolverEngParamSet (problem, L"LiftAndCoverCuts", 1);

You can also control how much time is spent generating these and other cuts, at the root or deeper in the Branch and Bound tree.  As another example, to activate the "strong branching" strategy, you would simply write:

problem.Engine.Params["StrongBranching"].Value = 1;

Controlling Solution Time on Integer Problems

The Solver Platform SDK provides several ways to control the solution time of problems with integer constraints. You can limit the number of subproblems explored and/or the number of integer solutions found, as well as the maximum time in seconds.  Simply set the appropriate "parameter" property:

problem.Engine.Params["MaxSubProblems"].Value = 10000;

As another example, if you have the objective value of a known integer solution for a problem from a previous Solver run, you can enter it as an integer cutoff value, which the Solver can use to speed up the solution process on new runs, by eliminating branches whose objective must be worse than the "cutoff" value. Just set the appropriate property:

problem.Engine.Params["IntCutoff"].Value = MyKnownObj;

< Back to Solver Platform SDK Product Overview