Mallach, Sven 
ORCID: 0000-0001-5335-0678
(2017).
Linear Ordering Based MIP Formulations for the Vertex Separation or Pathwidth Problem.
In:
Combinatorial Algorithms : 28th International Workshop, IWOCA 2017, Newcastle, NSW, Australia, July 17-21, 2017, Revised Selected Papers,
pp. 327-340.
Springer.
Abstract
We consider the vertex separation problem in directed graphs G=(V,A) that has been shown to be equivalent to the pathwidth problem. Naturally, it is modeled as finding a linear order (permutation) of the vertices V such that its induced maximum vertex separation is minimum. Mixed-integer programs proposed so far construct linear orders using either position or set assignment variables. We prove that, for any directed graph, solving their linear programming relaxations yields a lower bound of zero on the true vertex separation number. We then present a new and compact mixed-integer program that sustains stronger lower bounds. It is based on true linear ordering variables and a slightly different perspective on the problem. An experimental evaluation of three formulations in total, each representing a different modeling scheme, displays their potentials and limitations when used to solve the problem to optimality.
| Item Type: | Book Section, Proceedings Item or annotation in a legal commentary | ||||||||
| Creators: |
|
||||||||
| URN: | urn:nbn:de:hbz:38-640744 | ||||||||
| DOI: | 10.1007/978-3-319-78825-8_27 | ||||||||
| Title of Book: | Combinatorial Algorithms : 28th International Workshop, IWOCA 2017, Newcastle, NSW, Australia, July 17-21, 2017, Revised Selected Papers | ||||||||
| Series Name: | Lecture Notes in Computer Science | ||||||||
| Volume: | 10765 | ||||||||
| Page Range: | pp. 327-340 | ||||||||
| Date: | 2017 | ||||||||
| Publisher: | Springer | ||||||||
| Language: | English | ||||||||
| Faculty: | Faculty of Mathematics and Natural Sciences | ||||||||
| Divisions: | Faculty of Mathematics and Natural Sciences > Department of Mathematics and Computer Science > Institute of Computer Science | ||||||||
| Subjects: | Data processing Computer science | ||||||||
| Refereed: | Yes | ||||||||
| URI: | http://kups.ub.uni-koeln.de/id/eprint/64074 |
Downloads
Downloads per month over past year
Altmetric
Export
Actions (login required)
 |
View Item |