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 … Read more

On Lifted Cover Inequalities: A New Lifting Procedure with Unusual Properties

Lifted cover inequalities are well-known cutting planes for 0-1 linear programs. We show how one of the earliest lifting procedures, due to Balas, can be significantly improved. The resulting procedure has some unusual properties. For example, (i) it can yield facet-defining inequalities even if the given cover is not minimal, (ii) it can yield facet-defining … Read more