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