Skip to Main content Skip to Navigation
Journal articles

Lexicographical Order in Integer Programming

Martine Labbé 1, 2 Alfredo Marin 3 Antonio M. Rodriguez-Chia 4
1 INOCS - Integrated Optimization with Complex Structure
Inria Lille - Nord Europe, ULB - Université libre de Bruxelles, 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 : Tuesday, September 29, 2020 - 12:24:14 PM




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