Skip to Main content Skip to Navigation
Reports

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

David Coudert 1
1 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués, CRISAM - Inria Sophia Antipolis - Méditerranée
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.
Complete list of metadata

Cited literature [32 references]  Display  Hide  Download

https://hal.inria.fr/hal-01271838
Contributor : David Coudert Connect in order to contact the contributor
Submitted on : Tuesday, February 9, 2016 - 4:47:02 PM
Last modification on : Tuesday, June 22, 2021 - 8:14:03 PM
Long-term archiving on: : Saturday, November 12, 2016 - 3:45:00 PM

File

cwmip.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

261588

Files downloads

2166