1994 | OriginalPaper | Chapter
The K-Walk Polyhedron
Authors : Collette R. Coullard, A. Bruce Gamble, Jin Liu
Published in: Advances in Optimization and Approximation
Publisher: Springer US
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Given a directed graph G = (V, E), with distinguished nodes s and t, a k-walk from s to t is a walk with exactly k arcs. In this paper we consider polyhedral aspects of the problem of finding a minimum-weight k-walk from s to t. We describe an extended linear programming formulation, in which the number of inequalities and variables is polynomial in the size of G(for fixed k),and all the coefficients have values 0,−1, +1. We apply the projection method on the extended formulation and give two natural linear programming formulations, each having one variable for each arc of G. These correspond to two natural polyhedra: the convex hull of the (s,t)-k-walk incidence vectors, and the dominant of that poly tope. We focus on the dominant. We give three classes of facet constraints, showing that the dominant has an exponential number of facet constraints and that some facet constraints have coefficients as large as the size of V.