Search

In many practical applications, the task is to optimize a non-linear objective function over the vertices of a well-studied polytope as, e.g., the matching polytope or the travelling salesman polytope (TSP). Prominent examples are the quadratic assignment problem and the quadratic knapsack problem; further applications occur in various areas such as production planning or automatic graph drawing. In order to apply branch-and-cut methods for the exact solution of such problems, the objective function has to be linearized. However, the standard linearization usually leads to very weak relaxations. On the other hand, problem-specific polyhedral studies are often time-consuming. Our goal is the design of general separation routines that can replace detailed polyhedral studies of the resulting polytope and that can be used as a black box. As unconstrained binary quadratic optimization is equivalent to the maximum-cut problem, knowledge about cut polytopes can be used in our setting. Other separation routines are inspired by the local cuts that have been developed by Applegate, Bixby, Chvatal and Cook for faster solution of large-scale traveling salesman instances. Finally, we apply quadratic reformulations of the linear constraints as proposed by Helmberg, Rendl and Weismantel for the quadratic knapsack problem. By extensive experiments, we show that a suitable combination of these methods leads to a drastic speedup in the solution of constrained quadratic 0–1 problems. We also discuss possible generalizations of these methods to arbitrary non-linear objective functions.

The quadratic linear ordering problem naturally generalizes various optimization problems such as bipartite crossing minimization or the betweenness problem, which includes linear arrangement. These problems have important applications, e.g., in automatic graph drawing and computational biology. We present a new polyhedral approach to the quadratic linear ordering problem that is based on a linearization of the quadratic objective function. Our main result is a reformulation of the 3-dicycle inequalities using quadratic terms. After linearization, the resulting constraints are shown to be face-inducing for the polytope corresponding to the unconstrained quadratic problem. We use this result both within a branch-and-cut algorithm and within a branch-and-bound algorithm based on semidefinite programming. Experimental results for bipartite crossing minimization show that this approach clearly outperforms other methods.

Linear Programming based lower bounds have been considered both for the general as well as for the symmetric quadratic assignment problem several times in the recent years. They have turned out to be quite good in practice. Investigations of the polytopes underlying the corresponding integer linear programming formulations (the non-symmetric and the symmetric quadratic assignment polytope) have been started by Rijal (1995), Padberg and Rijal (1996), and Jünger and Kaibel (1996, 1997). They have lead to basic knowledge on these polytopes concerning questions like their dimensions, affine hulls, and trivial facets. However, no large class of (facet-defining) inequalities that could be used in cutting plane procedures had been found. We present in this paper the first such class of inequalities, the box inequalities, which have an interesting origin in some well-known hypermetric inequalities for the cut polytope. Computational experiments with a cutting plane algorithm based on these inequalities show that they are very useful with respect to the goal of solving quadratic assignment problems to optimality or to compute tight lower bounds. The most effective ones among the new inequalities turn out to be indeed facet-defining for both the non-symmetric as well as for the symmetric quadratic assignment polytope.