Exact methods for nonlinear combinatorial optimization

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.