New Valid Inequalities for the Fixed-Charge and Single-Node Flow Polytopes
Adam N. Letchford (a.n.letchfordlancaster.ac.uk)
Abstract: The most effective software packages for solving mixed 0-1 linear programs use strong valid linear inequalities derived from polyhedral theory. We introduce a new procedure which enables one to take known valid inequalities for the knapsack polytope, and convert them into valid inequalities for the fixed-charge and single-node flow polytopes. The resulting inequalities are very different from the previously known inequalities (such as flow cover and flow pack inequalities), and define facets under certain conditions.
Keywords: polyhedral combinatorics; branch-and-cut; mixed-integer linear programming
Category 1: Integer Programming ((Mixed) Integer Linear Programming )
Category 2: Integer Programming (Cutting Plane Approaches )
Citation: Eventually published as: A.N. Letchford & G. Souli (2019) New valid inequalities for the fixed-charge and single-node flow polytopes. Operations Research Letters, 47(5), 353-357.
Entry Submitted: 10/23/2018
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|