A note on Integer Linear Programming formulations for linear ordering problems on graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2016

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

Résumé

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.
Fichier principal
Vignette du fichier
cwmip.pdf (562.86 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01271838 , version 1 (09-02-2016)

Identifiants

  • HAL Id : hal-01271838 , version 1

Citer

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⟩
344 Consultations
1903 Téléchargements

Partager

Gmail Facebook X LinkedIn More