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.
To appear In: Proceedings 28th International Workshop On Combinatorial Algorithms (IWOCA), Lecture Notes in Computer Science. Springer 2017.

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.


Actions:
Full text not available from this repository.
Export as: [error in script]
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: [error in script]
Depositing User: Sven Mallach
Date Deposited: 11 May 2017 09:18
Last Modified: 11 May 2017 09:18
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/905