15th EUROPT Workshop on Advances in Continuous Optimization

Montréal, Canada, 12 — 14 juillet 2017

15th EUROPT Workshop on Advances in Continuous Optimization

Montréal, Canada, 12 — 14 juillet 2017

Horaire Auteurs Mon horaire

Advances in Mixed-Integer Nonlinear Optimization II

13 juil. 2017 11h30 – 12h45

Salle: TD Assurance Meloche Monnex

Présidée par Francesco Rinaldi

3 présentations

  • 11h30 - 11h55

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

    • Lars Schewe, prés., 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.

  • 11h55 - 12h20

    Benders Decomposition for Binary Quadratic Programming

    • Borzou Rostami, prés., É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.

  • 12h20 - 12h45

    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, prés., 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.

Retour