2015 CMS Winter Meeting

McGill University, December 4 - 7, 2015

Discrete and Continuous Optimization
Org: Dan Bienstock (Columbia) and Andrea Lodi (École Polytechnique de Montréal)
[PDF]

MIGUEL ANJOS, Polytechnique Montreal
Improving Mixed Integer Linear Optimization Formulations for the Unit Commitment Problem  [PDF]

The unit commitment problem is a fundamental problem in the operation of electric power systems. We present two ways to improve mixed-integer linear optimization formulations of the unit commitment problem. The first is a new class of facet-defining inequalities for the convex hull of feasible generator schedules. The second is a modified orbital branching technique that exploits the symmetry created by identical generators. Computational results show that these approaches can significantly reduce overall solution times for realistic instances of unit commitment. This is joint work with James Ostrowski (University of Tennessee, Knoxville, USA) and Anthony Vannelli (University of Guelph, Canada).

DAN BIENSTOCK, Columbia University
Exploiting structured sparsity in mixed-integer polynomial optimization  [PDF]

Many ideas in (continuous) polynomial optimization algorithms make use of the structural sparsity of the intersection graph of the constraints (Waki et al, Lasserre et al). Often this leads to e.g. sum-of-squares or semidefinite relaxations whose solution is made more efficient by leveraging the sparsity; however concrete convergence results are scarce. In this talk we describe linear programming approximations to mixed-integer polynomial optimization problems where the intersection graph of the constraints has fixed tree-width. The LP formulations, given $\epsilon$, are polynomially large in the problem data and in $\epsilon^{-1}$, and provably attain $\epsilon$-optimality and feasibility guarantee. As a consequence we obtain an LP-based polynomial-time approximation algorithm for the ACOPF problem on graphs with bounded tree-width.

SANTANU DEY, Georgia Institute of Technology
Analysis of Sparse Cutting-plane for Sparse IPs with applications to Stochastic IPs  [PDF]

In this talk, we present an analysis of the strength of sparse cutting-planes for mixed integer linear programs (MILP) with sparse formulations. We examine three kinds of problems: packing problems, covering problems, and more general MILPs with the only assumption that the objective function is non-negative. For each of these problems: (i) We first present a method to describe the sparsity structure of the constraint matrix. This method is different for the different types of problems. (ii) We present a method to describe a hierarchy of cutting-planes from very sparse to completely dense. (iii) Assume that we decide on support of cutting-planes and the strongest inequalities on these supports are added. Call the optimal objective function value of the linear programming relaxation together with these cuts as zcut. We present bounds on the ratio of zcut and the optimal objective function value of the MILP that depends only on the sparsity structure of the constraint matrix and the support of sparse cuts selected, that is, these bounds are completely data independent. There results also shed light on the strength of scenario-specific cuts for two stage stochastic MILPs. This is joint work with Marco Molinaro and Qianyi Wang.

RICARDO FUKASAWA, University of Waterloo
A two slope theorem for the master equality polyhedron  [PDF]

The master cyclic group polyhedron (MCGP) is an important relaxation for integer-programming problems that gives rise to important inequalities like the Gomory Mixed-Integer (GMI) inequality. In a previous work, we generalized such relaxation to the Master Equality Polyhedron (MEP) and, in a manner similar to what was known for the MCGP, we characterized its facet-defining inequalities as extreme points of a “polar-type” polyhedron. While such characterization is important and allows for separation of inequalities via linear programming, more easily checkable sufficient conditions to derive strong inequalities are desirable. One such condition for the MCGP is the 2-slope condition, which states that if the function that defines the cut has 2-slopes and is minimal, then it is facet-defining. In this work we extend such 2-slope condition for the MEP setting and show how it extends to an infinite relaxation setting as well.

MICHEL GOEMANS, MIT
Polynomial-Time Solvability for Optimization Problems over Integer Cones in Fixed Dimension  [PDF]

Given two $d$-dimensional polytopes $P$ and $Q$, we consider the problem of finding the smallest number of integer points of $P$ whose sum lies in $Q$. We show that this can be solved in polynomial time for any fixed dimension. As applications, we show that the bin packing problem with a constant number of item types or many high-multiplicity scheduling problems can be solved in polynomial time.

This is joint work with Thomas Rothvoss.

DOMINIQUE ORBAN, École Polytechnique Montréal
A Matrix-Free Regularized Sequential Quadratic Optimization Method  [PDF]

When formulated appropriately, augmented Lagrangian methods require the solution of a symmetric quasi-definite linear system at each iteration. The latter are indefinite but their strong relationships with definite systems enable specialized linear algebra and make them prime candidates for matrix-free implementations. We illustrate how the adequately-formulated augmented Lagrangian method for equality-constrained problems provides the motivation for regularized sequential quadratic optimization. We present an efficient matrix-free implementation for large-scale problems, describe global and fast local convergence results, and report on numerical experiments. We conclude with comments on extensions to inequality constraints. This is joint work with S. Arreckx.

SEBASTIAN POKUTTA, Georgia Institute of Technology
An introduction to Extended Formulations - capturing the expressive power of LPs and SDPs  [PDF]

Linear and semidefinite programming are two core optimization paradigms with many important applications in mathematics, engineering, and business. However, the expressive power of these modeling paradigms is only partially understood so far and extended formulations are a powerful and natural tool to analyze the possibilities and limitations of linear and semidefinite programming formulations.

In this talk I will provide an overview of recent breakthrough results in extended formulations, both in the linear and the semidefinite setting, and lay out a reduction frameworks for establishing upper and lower bounds for the size of exact and approximate LP and SDP formulations. This framework allows for surprisingly simple and convenient analyzes without relying on any heavy machinery.