15th EUROPT Workshop on Advances in Continuous Optimization

Montréal, Canada, July 12 — 14, 2017

15th EUROPT Workshop on Advances in Continuous Optimization

Montréal, Canada, July 12 — 14, 2017

Schedule Authors My Schedule
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

Advances in Mixed-Integer Nonlinear Optimization I

Jul 13, 2017 09:45 AM – 11:00 AM

Location: TD Assurance Meloche Monnex

Chaired by Francesco Rinaldi

3 Presentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    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.