21778 articles – 15587 references  [version française]

hal-00428716, version 1

Mixed Integer NonLinear Programs featuring “On/Off ” constraints: convex analysis and applications

Hassan Hijazi 12, Pierre Bonami () 2, Gérard Cornuéjols 23, Adam Ouorou () a1

Research Report (2009)

Abstract: We call ”on/off” constraint an algebraic constraint that is activated if and only if a corresponding boolean variable is turned ”on” or equal to 1. Our main subject of interest is to derive tight convex formulations of Mixed Integer NonLinear Programs (MINLPs) featuring ”on/off” constraints. We study the simple set defined by one ”on/off” constraint with bounded variables. Using disjunctive programming, we introduce convex hull formulations of this set defined in higher dimensional spaces. Because the large number of variables in these formulations appears to be practically disadvantageous, we concentrate our efforts on defining explicit projections into lower spaces. When the functions defining the ”on/off” constraint are order preserving or isotone, we show that the convex hull can be formulated in the space of original variables. This result applies in particular when the functions are additively separable, sum of one variable monotone functions. As a direct application to our results, we present new formulations to a well-known telecommunication problem: routing several commodities subject to multiple delay constraints. While classical multi-commodity routing problems deal with only one design specification, usually a total queuing delay constraint, this model takes into account individual delays for each type of commodity, allowing operators to offer a so-called ”differentiated quality of service”. Numerical results on randomly generated and real world networks are presented to assess the efficiency of the new models.

  • a –  France Télécom
  • 1:  France Télécom Recherche & Développement (FT R&D)
  • France Télécom
  • 2:  Laboratoire d'informatique Fondamentale de Marseille (LIF)
  • CNRS : UMR6166 – Université de la Méditerranée - Aix-Marseille II – Université de Provence - Aix-Marseille I
  • 3:  Tepper School of Business
  • Carnegie Mellon University
  • Domain : Computer Science/Operations Research
    Mathematics/Optimization and Control
  • Keywords : mixed integer nonlinear programming – on/off constraints – disjunctive constraints – convex programming – routing problems – multiple delay constraints
 
  • hal-00428716, version 1
  • oai:hal.archives-ouvertes.fr:hal-00428716
  • From: 
  • Submitted on: Thursday, 29 October 2009 15:24:41
  • Updated on: Thursday, 29 October 2009 15:37:56