Linear Ordering Based MIP Formulations for the Vertex Separation or Pathwidth Problem
Mallach, Sven
(2017)
Linear Ordering Based MIP Formulations for the Vertex Separation or Pathwidth Problem.
Published In:
Combinatorial Algorithms : 28th International Workshop, IWOCA 2017, Newcastle, NSW, Australia, July 1721, 2017, Revised Selected Papers, Lecture Notes in Computer Science. 10765 Springer 2017, pp. 327340.
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. Mixedinteger 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 mixedinteger 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:  Proceedings article 

Citations:  No citation data. 
Uncontrolled Keywords:  
Subjects: 

Divisions:  Institute of Computer Science > Computer Science Department  Prof. Dr. Juenger 
Related URLs: 
ZAIK Number:  UNSPECIFIED 

Depositing User:  Sven Mallach 
Date Deposited:  11 May 2017 09:18 
Last Modified:  20 Aug 2018 14:35 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/905 