A note on Integer Linear Programming formulations for linear ordering problems on graphs

David Coudert 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : In this paper, we present a new set of constraints for modeling linear ordering problems on graphs using Integer Linear Programming (ILP). These constraints express the membership of a vertex to a prefix rather than the exact position of a vertex in the ordering. We use these constraints to propose new ILP formulations for well-known linear ordering optimization problems, namely the Pathwidth, Cutwidth, Bandwidth, SumCut and Optimal Linear Arrangement problems. Our formulations are not only more compact than previous proposals, but also more efficient as shown by our experimental evaluations on large benchmark instances.
Type de document :
Rapport
[Research Report] Inria; I3S; Universite Nice Sophia Antipolis; CNRS. 2016, pp.33
Liste complète des métadonnées

https://hal.inria.fr/hal-01271838
Contributeur : David Coudert <>
Soumis le : mardi 9 février 2016 - 16:47:02
Dernière modification le : vendredi 16 septembre 2016 - 15:21:17
Document(s) archivé(s) le : samedi 12 novembre 2016 - 15:45:00

Fichier

cwmip.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01271838, version 1

Collections

Citation

David Coudert. A note on Integer Linear Programming formulations for linear ordering problems on graphs. [Research Report] Inria; I3S; Universite Nice Sophia Antipolis; CNRS. 2016, pp.33. <hal-01271838>

Partager

Métriques

Consultations de
la notice

131

Téléchargements du document

173