Optimisation discrète et continue
Org:
Dan Bienstock (Columbia) et
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 mixedinteger linear optimization formulations of the unit commitment problem. The first is a new class of facetdefining 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 mixedinteger 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. sumofsquares 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 mixedinteger polynomial optimization problems where the intersection graph of the constraints has fixed treewidth. 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 LPbased polynomialtime approximation algorithm for the ACOPF problem on graphs with bounded treewidth.
 SANTANU DEY, Georgia Institute of Technology
Analysis of Sparse Cuttingplane for Sparse IPs with applications to Stochastic IPs [PDF]

In this talk, we present an analysis of the strength of sparse cuttingplanes 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 nonnegative. 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 cuttingplanes from very sparse to completely dense. (iii) Assume that we decide on support of cuttingplanes 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 scenariospecific 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 integerprogramming problems that gives rise to important inequalities like the Gomory MixedInteger (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 facetdefining inequalities as extreme points of a “polartype” 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 2slope condition, which states that if the function that defines the cut has 2slopes and is minimal, then it is facetdefining. In this work we extend such 2slope condition for the MEP setting and show how it extends to an infinite relaxation setting as well.
 MICHEL GOEMANS, MIT
PolynomialTime 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 highmultiplicity scheduling problems can be solved in polynomial time.
This is joint work with Thomas Rothvoss.
 DOMINIQUE ORBAN, École Polytechnique Montréal
A MatrixFree Regularized Sequential Quadratic Optimization Method [PDF]

When formulated appropriately, augmented Lagrangian methods require the solution of a symmetric quasidefinite 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 matrixfree implementations. We illustrate how the adequatelyformulated augmented Lagrangian method for equalityconstrained problems provides the motivation for regularized sequential quadratic optimization. We present an efficient matrixfree implementation for largescale 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.
© Société mathématique du Canada