Many NP-Hard problems in operations research are routinely solved using general-purpose integer linear programming (ILP) solvers. This motivates a considerable amount of research both in the academia and the industry. The state of the art in such general-purpose ILP solvers is an approach known as "branch and bound and cut" (B&B). The B&B approach is a form of an exact tree search. Its performance depends crucially on four types of integral heuristics for finding (improving) solutions, strengthening (linear programming) bounds, and deciding what (variable) to branch on. Trivial as this approach may seem mathematically, no elegant alternative has been shown to be more efficient, yet.
There are, indeed, elegant alternatives based on branches of mathematics ranging from matroid theory to number theory. Many such approaches derive an object from the ILP instance, process it using tools known in the particular branch of mathematics, and translate the results of the processing back to the solution of the ILP. Three such approaches, based on low-width decompositions of hypergraphs, matroid minors, and "automating column generation", have been presented as "almost competitive" in IPCO, the conference, in recent years. Simple probabilistic arguments show, however, that there is only a vanishingly small class of instances where each of the three approaches is clearly superior to B&B. Notice such alternative approaches are also generally incompatible with B&B solvers.
We hence study alternative approaches that extract submatrices of the ILP instance allowing for an efficient implementation of the heuristics required in B&B solvers. Although the extraction of the maximum submatrices is NP-Hard with respect to many criteria, it is often not necessary to extract the maximum such submatrix to speed up the heuristics in B&B solvers considerably. Three examples of such approaches include the search for mutual-exclusion and precedence-constrained components, and aggregating variables. Storing such "useful" submatrices in a "pool" makes it possible to reuse them. The hope is this approach could allow for the use of the "elegant" structures in state-of-the-art solvers.
Current 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
