Guneshwar Anand

Characterization of Knapsack Polytopes using Minimal Cover Inequalities

  • Shreyas Bhowmik
  • Guneshwar Anand
  • Sachin Jayaswal
    • Categories 0-1 Programming Tags , , ,

    In this paper, we compare the strength of alternate formulations (polyhedra) of the binary knapsack set. We introduce a specific class of knapsack sets for which we prove that the polyhedra based on their minimal cover inequalities (together with the bounds on the variables) are strictly contained inside the polyhedra defined by their continuous knapsack … Read more

    Facets of the knapsack polytope from non-minimal covers

  • Guneshwar Anand
  • Sachin Jayaswal
  • B. Srirangacharyulu
    • Categories (Mixed) Integer Linear Programming, Polyhedra, Transportation Tags , , , , ,

    We propose two new classes of valid inequalities (VIs) for the binary knapsack polytope, based on non-minimal covers. We also show that these VIs can be obtained through neither sequential nor simultaneous lifting of well-known cover inequalities. We further provide conditions under which they are facet-defining. The usefulness of these VIs is demonstrated using computational … Read more