15th EUROPT Workshop on Advances in Continuous Optimization

Montréal, Canada, July 12 — 14, 2017

15th EUROPT Workshop on Advances in Continuous Optimization

Montréal, Canada, July 12 — 14, 2017

Schedule Authors My Schedule
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

Advances in Mixed-Integer Nonlinear Optimization II

Jul 13, 2017 11:30 AM – 12:45 PM

Location: TD Assurance Meloche Monnex

Chaired by Francesco Rinaldi

3 Presentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    11:30 AM - 11:55 AM

    Penalty Alternating Direction Methods for Mixed-Integer Optimization: A New View on Feasibility Pumps

    • Lars Schewe, presenter, Friedrich-Alexander-Universität Erlangen-Nürnberg
    • Björn Geißler, Friedrich-Alexander-Universität Erlangen-Nürnberg
    • Antonio Morsi, Friedrich-Alexander-Universität Erlangen-Nürnberg
    • Martin Schmidt, Friedrich-Alexander-Universität Erlangen-Nürnberg

    Feasibility pumps are highly effective primal heuristics for
    mixed-integer linear and nonlinear optimization.
    However, despite their success in practice there are only few works
    considering their theoretical properties.
    We show that feasibility pumps can be seen as alternating
    direction methods applied to special reformulations of the original
    problem, inheriting the convergence theory of these methods.
    Moreover, we propose a novel penalty framework that encompasses
    this alternating direction method, which allows us to refrain from random
    perturbations that are applied in standard versions of feasibility
    pumps in case of failure.
    We present a convergence theory for the new penalty based alternating
    direction method and compare the new variant of the feasibility
    pump with existing versions in an extensive numerical study for
    mixed-integer nonlinear problems. We also discuss extensions to use penalty alternating direction methods for block-structured MINLPs.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    11:55 AM - 12:20 PM

    Benders Decomposition for Binary Quadratic Programming

    • Borzou Rostami, presenter, École de technologie supérieure

    The constrained quadratic binary programming is a very general class of optimization problems and has a wide range of applications. In this paper a novel mixed integer linear programming formulation (MILP) is proposed. Due to the large number of constraints of the resulting MILP, we exploit the problem
    structure and develop a branch-and-cut algorithm based on benders decomposition with efficiently solvable subproblems. The Computational experiments on some challenging benchmark instances show the advantage of the proposed approach.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    12:20 PM - 12:45 PM

    A Frank-Wolfe Based Branch-and-Bound Algorithm for Mean-Risk Optimization

    • Christoph Buchheim, Technische Universität Dortmund
    • Marianna De Santis, University of Padova
    • Francesco Rinaldi, presenter, University of Padova
    • Long Trieu, Technische Universität Dortmund

    We present an exact algorithm for mean-risk optimization subject to a budget constraint, where decision variables may be continuous or integer. The risk is measured by the covariance matrix and weighted by an arbitrary monotone function, which allows to model risk-aversion in a very individual way. Our approach is a branch-and-bound algorithm, where at each node, the continuous relaxation is solved by a Frank-Wolfe type algorithm. Experimental results on portfolio optimization problems show that our approach clearly outperforms commercial state-of-the art solvers.