|
Description: |
> |
The problem of optimizing a quadratic objective function over binary
variables subject to linear constraints arises in many
applications. However, it is much harder to solve than integer
linear programs in general. Previous approaches are either
restricted to very special problems or can only solve small
instances.
In our project, we focus on problems that could be solved efficiently
if the objective function was linear. Examples are the quadratic
assignment problem and the quadratic matching problem. Starting from
the standard linearization of the quadratic problem version, we aim at
developing general cutting plane approaches leading to improved
branch-and-cut algorithms.
Experience shows that a mere combination of the standard linearization
with a polyhedral description of the linear problem version yields
very weak LP-relaxations for the quadratic problem. It is thus crucial
to derive cutting planes that link the specific structure of the
underlying linear problem with the variables introduced for
linearization. For this, our main techniques are the separation of
inequalities valid for unconstrained quadratic optimization, and the
use of target cuts, a variant of the local cuts proposed by Applegate
et al. Experimentally, we proved that both separation algorithms lead to
much stronger LP-relaxations for all classes of instances considered,
yielding much shorter running times in practice.
|
|
