A polyhedral study of the cardinality constrained knapsack problem

DOI10.1007/s10107-003-0420-8zbMath1023.90085OpenAlexW2910445340MaRDI QIDQ1404231

Ismael Regis jun. de Farias, Nemhauser, George I.

Publication date: 20 August 2003

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-003-0420-8

zbMATH Keywords

knapsack problembranch-and-cutcardinality constrained programmingmixed-integer programming

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Boolean programming (90C09)

Related Items

Knapsack polytopes: a survey, Branch-and-cut for linear programs with overlapping SOS1 constraints, The piecewise linear optimization polytope: new inequalities and intersection with semi-continuous constraints, Recent advances in mathematical programming with semi-continuous variables and cardinality constraint, Subset selection for multiple linear regression via optimization, A Combinatorial Approach for Small and Strong Formulations of Disjunctive Constraints, Branch-and-cut for separable piecewise linear optimization and intersection with semi-continuous constraints, A polyhedral study of the semi-continuous knapsack problem, Optimal rank-sparsity decomposition, Semi-continuous network flow problems, A polyhedral study of nonconvex quadratic programs with box constraints, A family of inequalities valid for the robust single machine scheduling polyhedron, Optimization algorithms for the disjunctively constrained knapsack problem, On the structure of linear programs with overlapping cardinality constraints, On cutting planes for cardinality-constrained linear programs, Convex optimization under combinatorial sparsity constraints, Integer-programming software systems

Uses Software

• MINTO