The most common method for finding guaranteed global optima of mathematical programs is the Branch-and-Bound (BB) algorithm. There exist reliable implementations of BB for Mixed-Integer Linear Programs (MILPs) ; for Mixed-Integer Nonlinear Programs (MINLPs) the situation is not as advanced, but there are nonetheless some implementations that can be used profitably (e.g. Couenne, Baron). There are many factors that impact the performance of a BB algorithm, the main ones being the bound quality and branching strategy. Symmetries in the solution space can adversely impact the quality of the bound, especially in lower BB search tree levels. If a given problem has many symmetric optima, many leaf nodes in the BB tree will contain optimal solutions, which means that the BB algorithm will never be able to prune the branches leading to these leaves. As a consequence, the BB tree exploration will yield trees of disproportionate sizes. If it were possible to detect symmetries before the solution process, we might then attempt to adjoin constraints eliminating some symmetric solutions whilst guaranteeing that at least one optimum is kept. Such constraints provide a reformulation of the narrowing type. In this talk we introduce some basic concepts of group theory applied to mathematical programming, survey some existing techniques in detecting and breaking symmetry, and present some results related to exploiting formulation symmetry in MINLPs.

Jean Bernard Lasserre
LAAS-CNRS

On présente d’abord ce que nous appelons l’approche joint+marginal" pour l’optimisation polynomiale paramétrique. On définit une hiérarchie de relaxations semidéfinies qui permet de fournir des approximations de la valeur optimale et des solutions optimales vues comme des fonctions des paramètres. On utilise ensuite ce résultat pour l’optimisation 0-1 en considérant la variable x_1 comme un paramètre dans 0,1, puis x_2 comme un paramètre etc. Quelques résultats numériques sont présentés.

We call "on/off" constraint an algebraic constraint that is activated if and only if a corresponding boolean variable is turned "on" or equals 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 deriving explicit projections into lower dimensional 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 for sums of univariate monotone functions. As a direct application to our results, we present new formulations to an up to date telecommunication problem : The delay constrained routing problem. While classical multi-flow routing problems deal with only one design specification, usually a total average delay constraint, this model takes into account individual delays for each type of demand, allowing operators to offer a so-called "differentiated quality of service". Numerical results on randomly generated and real world networks are presented in order to assess the efficiency of the new models.

Le problème de minimiser une fonction quadratique quelconque, sous des contraintes linéaires, et dont les variables sont entières est un problème fondamental en optimisation. Appelons (QP) un tel problème. (QP) appartient à la classe des problèmes NP-difficiles. Sa difficulté réside à la fois dans l’intégrité de ses variables, mais aussi dans la non-convexité de sa fonction objectif. Il existe des solveurs efficaces pour résoudre (QP), dans le cas particulier où sa fonction objectif est convexe. Ces solveurs utilisent des algorithmes de Branch and Bound basés sur la borne obtenue par relaxation continue. Ainsi, l’approche que nous avons proposée pour résoudre (QP) est une méthode en deux phases. La première consiste en la reformulation de (QP) en un problème quadratique convexe équivalent, noté (QP’), et la deuxième consiste à utiliser les performances des solveurs en leur soumettant (QP’). De plus, nous prouvons que notre reformulation (QP’) est la meilleure, du point de vue de la borne obtenue par relaxation continue, au sein d’un schéma de reformulation convexe. Cette reformulation, que nous appelons IQCR (Integer Quadratic Convex Reformulation), est basée sur la solution duale d’une relaxation semi-définie de (QP).