15th EUROPT Workshop on Advances in Continuous Optimization

Montréal, Canada, 12 — 14 juillet 2017

15th EUROPT Workshop on Advances in Continuous Optimization

Montréal, Canada, 12 — 14 juillet 2017

Horaire Auteurs Mon horaire
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

Mixed Integer Conic Optimization and Applications

12 juil. 2017 13h30 – 15h10

Salle: Nancy et Michel-Gaucher

Présidée par Matthias Takouda

4 présentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    13h30 - 13h55

    Computational Study of Valid Inequalities for the Maximum k-Cut Problem

    • Vilmar Jefte Rodrigues De Sousa, prés., Polytechnique Montréal
    • Miguel F. Anjos, GERAD, Polytechnique Montréal
    • Sebastien Le Digabel, Polytechnique Montréal

    We consider the maximum k-cut problem that consists in partitioning the vertex set of a graph into k subsets such that the sum of the weights of edges joining vertices in different subsets is maximized. We focus on strengthening conic relaxations of max-k-cut by adding facet-defining inequalities, specifically clique, general clique, wheel and bicycle wheel inequalities. We also study valid linear inequalities based on a reformulation of the semidefiniteness constraint. Our computational results suggest that these inequalities considerably improve the performance of the relaxations.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    13h55 - 14h20

    Pathological Cases for Disjunctive Conic Cuts in Mixed Integer Second Order Cone Optimization Problems

    • Tamas Terlaky, prés., Lehigh University
    • Julio Goez, Lehigh University
    • Mohammad Shahabsafa, ISE, Lehigh University

    The development of Disjunctive Conic Cuts (DCCs) for Mixed Integer Second Order Cone Optimization (MISOCO) problems has recently gained significant interest in the optimization community. In this paper we focus on the identification of cases when DCCs are not helping to save computational time. In particular, we identify cases where the DCC methodology leads to cuts which do not cut off any part of the feasible region. Such cases include the MISOCO representation of mixed integer p-order cone optimization problems.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    14h20 - 14h45

    Hub location under the risk of interdiction

    • Prasanna Ramamoorthy, Indian Institute of Management Ahmedabad
    • Sachin Jayaswal, prés., Indian Institute of Management Ahmedabad
    • Ankur Sinha, Indian Institute of Management Ahmedabad
    • Navneet Vidyarthi, Concordia University

    We study the hub-and-spoke network design problem under the risk of interdiction. The problem is modeled as a 3-stage sequential game, resulting in a tri-level mixed integer program. We present different approaches to reduce the model to 2 levels, followed by an efficient exact method to solve the problem to optimality.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    14h45 - 15h10

    An improved mixed integer semidefinite optimization model for the unequal-areas facility layout problem

    • Matthias Takouda, prés., Laurentian University
    • Miguel F. Anjos, GERAD, Polytechnique Montréal

    The unequal-areas facility layout problem is a hard optimization problem that consists in partitioning a rectangular facility of known dimensions into departments, which have pre-specified but possibly unequal areas. The objective is to minimize the total cost associated with the known (or projected) interactions between the departments. We propose an improved mixed integer semidefinite model where the area constraints are formulated as a semidefinite constraint, the Manhattan distances are linearized, and the disjunctive non-overlapping constraints are expressed using only two binary variables per pair of departments. Non-trivial bounds and approximate solutions are computed for benchmark instances from the literature.