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
Mixed Integer Conic Optimization and Applications
12 juil. 2017 13h30 – 15h10
Salle: Nancy et MichelGaucher
Présidée par Matthias Takouda
4 présentations

13h30  13h55
Computational Study of Valid Inequalities for the Maximum kCut Problem
We consider the maximum kcut 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 maxkcut by adding facetdefining 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.

13h55  14h20
Pathological Cases for Disjunctive Conic Cuts in Mixed Integer Second Order Cone Optimization Problems
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 porder cone optimization problems.

14h20  14h45
Hub location under the risk of interdiction
We study the hubandspoke network design problem under the risk of interdiction. The problem is modeled as a 3stage sequential game, resulting in a trilevel 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.

14h45  15h10
An improved mixed integer semidefinite optimization model for the unequalareas facility layout problem
The unequalareas facility layout problem is a hard optimization problem that consists in partitioning a rectangular facility of known dimensions into departments, which have prespecified 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 nonoverlapping constraints are expressed using only two binary variables per pair of departments. Nontrivial bounds and approximate solutions are computed for benchmark instances from the literature.