ARCHIVES - Faster Integer Solver...

 

Faster Integer Solver in What'sBest! and LINGO


The integer solver used in What'sBest! 3.0 and LINGO 3.1 utilizes several new enhancements. Modelers intimately familiar with the art of solving integer models might appreciate the description of the enhancements listed below. Those interested in the results of the enhancements should check out the time comparisons of selected models from the MIPLIB Mixed Integer Programming Library (bottom right). Compare these times to your current solver.

Cut Generation

On integer models with 0/1 knapsack constraints with Generalized Upper Bound (GUB) constraints, also known as Special Ordered Set (SOS) constraints, lifted cover inequalites are added. Primarily on mixed 0/1 models, lifted flow cover inequalities are added.

Preprocessing

Before the branch and bound procedure begins, the integer solver tightens variable bounds, reduces coefficients, fixes variables and deletes redundant constraints based upon feasibility and optimality conditions and GUB constraints.

Model Name
New IP Solver Time (seconds)
Old IP Solver Time (seconds)

fixnet4

13.07

36,000+

khb05250

3.13

531.1

misc07

3256.37

36,000+

modglob

112.26

36,000+

p0548

1.32

36,000+

p2756

18.51

36,000+

p6000

707.55

36,000+

set1a1

2.48

36,000+

stein45

1462.40

5,003.22

wpm1

1.64

36,000+

Reduced Cost Variable Fixing

At each node of the branch and bound tree, variables are fixed or tightened based upon reduced costs and feasibility condition.

Heuristics

Using the current LP solution and feasibility condition at each node, heuristics are used to quickly find a good IP solution. If an IP solution is found that is better than the incumbent, then it is used to fix or tighten global and local variable bounds.

Branching Strategies

Improved branching rules based upon penalties have been implemented.

Feel free to check out more information in our products pages, download a demonstration copy from our download page, or order a copy directly from our order page.