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.
Type de document :
Article dans une revue
Vietnam Journal of Mathematics, Springer, 2016, 〈10.1007/s10013-016-0220-0〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01419551
Contributeur : Bernard Fortz <>
Soumis le : lundi 19 décembre 2016 - 16:13:53
Dernière modification le : jeudi 11 janvier 2018 - 06:27:32

Identifiants

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

93