New Valid Inequalities for the Fixed-Charge and Single-Node Flow Polytopes

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.

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.