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
We study the use of binary variables in reformulating general mixed-integer linear programs. We show that binary reformulations result in problems for which almost all the binary variables replacing a general integer variable need to be explored during branching. We also give computational results on the performance of such reformulations in solving the mixed-integer programs, … Read more
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