Lexicographical Order in Integer Programming

Martine Labbé 1, 2 Alfredo Marin 3 Antonio M. Rodriguez-Chia 4
1 INOCS - Integrated Optimization with Complex Structure
ULB - Université Libre de Bruxelles [Bruxelles], Inria Lille - Nord Europe, CRIStAL - Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Abstract : Forcing lexicographical order in the solutions to an integer programming problem is a possible strategy to avoid symmetric solutions. An orbisack is the convex hull of the lexicographically ordered pairs of n-dimensional binary vectors. In this paper, we present a minimal complete description of orbisacks. In addition, we provide a polynomial formulation with exponential coefficients and a formulation with an exponential number of constraints but with unit coefficients, both of which still force lexicographical order. An exact separation procedure is also described.
Document type :
Journal articles
Complete list of metadatas

Contributor : Bernard Fortz <>
Submitted on : Monday, December 19, 2016 - 4:13:53 PM
Last modification on : Friday, March 22, 2019 - 1:35:46 AM




Martine Labbé, Alfredo Marin, Antonio M. Rodriguez-Chia. Lexicographical Order in Integer Programming. Vietnam Journal of Mathematics, Springer, 2016, ⟨10.1007/s10013-016-0220-0⟩. ⟨hal-01419551⟩



Record views