Related Work

The 1990's witnessed a broad development of software for discrete
optimization. Almost without exception, these new software packages were based
on the techniques of branch, cut, and price. The packages fell into two main
categories--those based on general-purpose algorithms for solving
mixed-integer linear programs (MILPs) (without the use of special structure)
and those facilitating the use of special structure by interfacing with
user-supplied, problem-specific subroutines. We will call packages in this
second category *frameworks*. There have also been numerous
special-purpose codes developed for use in particular problem settings.

Of the two categories, MILP solvers are the most common. Among the dozens of
offerings in this category are MINTO [27], MIPO [3], bc-opt
[8], and SIP [26]. Generic frameworks, on the other hand, are
far less numerous. The three frameworks we have already mentioned (SYMPHONY,
ABACUS, and COIN/BCP) are the most full-featured packages available. Several
others, such as MINTO, originated as MILP solvers but have the capability of
utilizing problem-specific subroutines. CONCORDE [2,1], a
package for solving the *Traveling Salesman Problem* (TSP), also deserves
mention as the most sophisticated special-purpose code developed to date.

Other related software includes several frameworks for implementing parallel branch and bound. Frameworks for general parallel branch and bound include PUBB [33], BoB [4], PPBB-Lib [35], and PICO [10]. PARINO [23] and FATCOP [6] are parallel MILP solvers.

2010-03-24