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.

Full text not available from this repository.
Identification Number:10.1007/978-3-319-78825-8_27

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
Creators:
Creators
Email
ORCID
ORCID Put Code
Mallach, Sven
UNSPECIFIED
https://orcid.org/0000-0001-5335-0678
UNSPECIFIED
URN: urn:nbn:de:hbz:38-640744
Identification Number: 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 View Item