cardinality constrained programming

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

    A Family of Facets for the p-Median Polytope

  • Ismael de Farias
    • Categories (Mixed) Integer Linear Programming, Branch and Cut Algorithms, Transportation Tags , , , ,

    We present a nontrivial family of facet-defining inequalities for the p-median polytope. We incorporate the inequalities in a branch-and-cut scheme, and we report computational results that demonstrate their effectiveness. CitationDepartment of Industrial Engineering, State University of New York at Buffalo, submittedArticleDownload View PDF