### Jakub Marecek (University of Edinburgh)

#### The many approaches to integer programming

*Wednesday 21 March 2012 at 15.30, JCMB 6206*

##### Abstract

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.

### Seminars by year

*Current*
*2015*
*2014*
*2013*
*2012*
*2011*
*2010*
*2009*
*2008*
*2007*
*2006*
*2005*
*2004*
*2003*
*2002*
*2001*
*2000*
*1999*
*1998*
*1997*
*1996*