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 17-21, 2017, Revised Selected Papers, Lecture Notes in Computer Science. 10765 Springer 2017, pp. 327-340.


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.

Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
Depositing User: Sven Mallach
Date Deposited: 11 May 2017 09:18
Last Modified: 20 Aug 2018 14:35