3 Presentations

• 
  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.

• 
  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.

• 
  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.