3 Presentations

• 
  09:45 AM - 10:10 AM

  A Semidefinite Programming Approach for Transmission Network Expansion Planning

  • Bissan Ghaddar, presenter, University of Waterloo

  This talk presents a mixed-integer quadratic formulation for transmission expansion planning with an AC network model. The model is solved by combining a semidefinite programming relaxation with valid inequalities in a branch-and-cut framework. Computational results are presented to show the performance of the proposed method.

• 
  10:10 AM - 10:35 AM

  Quadratic convex reformulation for partitioning problems

  • Sourour Elloumi, presenter, UMA-CEDRIC
  • Amélie Lambert, Cedric-Cnam

  Quadratic convex reformulation is a general method to solve quadratic programs. We consider its specialization to partitioning-like problems, namely, quadratic assignment and k-way graph partitioning. We compare two reformulation families. In the first one, we rely on the space of the initial variables only and obtain compact reformulations. In the second family, we aim at getting tighter relaxation bounds by increasing the size of the reformulated problem. We illustrate through experiments.

• 
  10:35 AM - 11:00 AM

  A class of valid inequalities for multilinear 0-1 optimization problems

  • Elisabeth Rodriguez-Heck, presenter, University of Liege
  • Yves Crama, University of Liege

  A common approach for the unconstrained minimization of multilinear polynomials in 0-1 variables consists in defining a linear reformulation of the objective function and using classical ILP techniques to optimize it. The standard linearization is a well-known reformulation technique, which has the drawback of providing weak LP relaxations. We introduce the 2-link inequalities, which, added to the standard linearization, provide a complete description of the convex hull for the case of a function consisting of at most two nonlinear monomials. In our experiments, the 2-links provide better relaxation bounds and an improvement in computational performance of exact resolution methods.