Skip to Main content Skip to Navigation
Journal articles

Lexicographical Order in Integer Programming

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 metadata

https://hal.inria.fr/hal-01419551
Contributor : Bernard Fortz Connect in order to contact the contributor
Submitted on : Monday, December 19, 2016 - 4:13:53 PM
Last modification on : Wednesday, October 27, 2021 - 6:51:12 AM

Identifiers

Collections

`

Citation

Martine Labbé, Alfredo Marín, Antonio Rodríguez-Chía. Lexicographical Order in Integer Programming. Vietnam Journal of Mathematics, Springer, 2016, ⟨10.1007/s10013-016-0220-0⟩. ⟨hal-01419551⟩

Share

Metrics

Record views

271