Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4652449 | Electronic Notes in Discrete Mathematics | 2009 | 7 Pages |
Abstract
We consider the set of integral solutions of Ax⩽b, x⩾0, where A is the edge-vertex incidence matrix of a bidirected graph. We characterize its corner polyhedron, i.e. the convex hull of the points satisfying all the constraints except the non-negativity of the basic variables. We show that the non-trivial inequalities necessary to describe this polyhedron can be derived as fractional Gomory cuts. It follows in particular that the split closure is equal to the Chvátal closure in this case.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics