Mallach, Sven (2018). Linear Ordering Based MIP Formulations for the Vertex Separation or Pathwidth Problem. Journal of Discrete Algorithms. Elsevier.
Full text not available from this repository.Abstract
We consider the task to compute the pathwidth of a graph which is known to be equivalent to solving the vertex separation problem. The latter is naturally modeled as a linear ordering problem with respect to the vertices of the graph. Present mixed-integer programs for the vertex separation problem express linear orders using either position or set assignment variables. However, as we show, the lower bound on the pathwidth obtained when solving their linear programming relaxations is zero for any directed graph. This is one reason for their limited utility in solving larger instances to optimality. We then present a new formulation that is based on conventional linear ordering variables and a slightly different perspective on the problem. Its relaxation provably delivers non-zero lower bounds for any graph whose pathwidth is non-zero. Further structural results for and extensions to this formulation are discussed. Finally, an experimental evaluation of three mixed-integer programs, each representing one of the different yet existing modeling approaches, displays their potentials and limitations when used to solve the problem to optimality in practice.
| Item Type: | Journal Article | ||||||||
| Creators: |
|
||||||||
| URN: | urn:nbn:de:hbz:38-640727 | ||||||||
| Journal or Publication Title: | Journal of Discrete Algorithms | ||||||||
| Series Name: | Lecture Notes in Computer Science | ||||||||
| Date: | November 2018 | ||||||||
| Publisher: | Elsevier | ||||||||
| Language: | ["eprint_fieldopt_language_ARRAY(0x55f1434b3a60)" not defined] | ||||||||
| 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 | ||||||||
| URI: | http://kups.ub.uni-koeln.de/id/eprint/64072 |
Downloads
Downloads per month over past year
Export
Actions (login required)
 |
View Item |