Exact methods for nonlinear combinatorial optimization
Loading...
Date
2014-09-05
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
We consider combinatorial optimization problems with nonlinear objective functions.
Solution approaches for this class of problems proposed so far are either
highly problem-specific or they apply generic algorithms for constrained nonlinear
optimization, which often does not yield satisfactory results in practice.
Our aim is to develop, implement and experimentally evaluate exact algorithms
that address the nonlinearity of the objective function and at the same time exploit
the underlying combinatorial structure of the problem. To this end we follow
two approaches. The first combines good polyhedral descriptions of the objective
function and the feasible set in a branch and cut-algorithm. The second approach
is based on Lagrangean decomposition. By decomposing the original problem into
an unconstrained nonlinear problem and a linear combinatorial problem, we are
able to compute strong dual bounds for the optimal value. The computation of
lower bounds is then embedded into a branch and bound-algorithm. For many
applications there already exist efficient algorithms for the combinatorial subproblem,
thus an important aspect of this thesis is the study of the corresponding
unconstrained nonlinear subproblems.
Both approaches have the advantage that they can easily be adapted to a wide
range of nonlinear combinatorial problems.We devise both polyhedral and decomposition-
based algorithms for submodular applications from wireless network design
and portfolio optimization and evaluate their performance experimentally.
Exploiting the equivalence between unconstrained binary quadratic optimization
and the maximum cut problem gives rise to a branch and cut-algorithm for
quadratic combinatorial problems which we use to compute optimal layouts of
tanglegrams, an application from computational biology. Additionally we study
the effect of quadratic reformulation of linear constraints, both theoretically and
experimentally. The last class of nonlinear combinatorial problems we consider
are two-scenario problems. Here we propose a new technique to compute lower
bounds in the unconstrained subproblem of the decomposition. Our computational
study of the two-scenario minimum spanning tree problem shows that
the new Lagrangean decomposition-based algorithm is able to solve significantly
larger instances than the standard linearization approach.
Description
Table of contents
Keywords
nonlinear combinatorial optimization, Lagrangean decomposition, branch and cut, branch and bound