11:30 AM - 11:55 AM
Penalty Alternating Direction Methods for Mixed-Integer Optimization: A New View on Feasibility Pumps
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
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
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.