Georgia Souli

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

  • Adam N. Letchford
  • Georgia Souli
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches

    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

  • Adam N. Letchford
  • Georgia Souli
    • Categories Combinatorial Optimization, Integer Programming Tags , ,

    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