Combinatorial Optimization – Page 142

Solving Large Quadratic Assignment Problems on Computational Grids

Published: 2000/10/27, Updated: 2000/10/31

(Mixed) Integer Linear Programming, Combinatorial Optimization, Parallel Algorithms

The quadratic assignment problem (QAP) is among the hardest combinatorial optimization problems. Some instances of size n >= 30 have remained unsolved for decades. The solution of these problems requires both improvements in mathematical programming algorithms and the utilization of powerful computational platforms. In this article we describe a novel approach to solve QAPs using … Read more

Tighter Linear and Semidefinite Relaxations for Max-Cut Based on the Lov\’asz-Schrijver Lift-and-Project Procedure

Published: 2000/10/12, Updated: 2002/06/24

Monique Laurent

Combinatorial Optimization, Linear, Cone and Semidefinite Programming lift-and-project, linear relaxation, max-cut problem, semidefinite relaxation

We study how the lift-and-project method introduced by Lov\’az and Schrijver \cite{LS91} applies to the cut polytope. We show that the cut polytope of a graph can be found in $k$ iterations if there exist $k$ edges whose contraction produces a graph with no $K_5$-minor. Therefore, for a graph with $n\ge 4$ nodes, $n-4$ iterations … Read more