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.