# 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.

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 |