knapsack problem

Facets of a polyhedron closely related to the integer knapsack-cover problem

  • Leslie A. Hall
  • David R. Mazur
    • Categories (Mixed) Integer Linear Programming, Polyhedra Tags , ,

    We investigate the polyhedral structure of an integer program with a single functional constraint: the integer capacity-cover polyhedron. Such constraints arise in telecommunications planning and facility location applications, and feature the use of general integer (rather than just binary) variables. We derive a large class of facet-defining inequalities by using an augmenting technique that builds … Read more

    A Polyhedral Study of the Cardinality Cosntrained Knapsack Problem

  • Ismael de Farias
  • George L. Nemhauser
    • Categories Branch and Cut Algorithms, Combinatorial Optimization, Integer Programming Tags , , ,

    A cardinality constrained knapsack problem is a continuous knapsack problem in which no more than a specified number of nonnegative variables are allowed to be positive. This structure occurs, for example, in areas as finance, location, and scheduling. Traditionally, cardinality constraints are modeled by introducing auxiliary 0-1 variables and additional constraints that relate the continuous … Read more