A polyhedral study of the cardinality constrained knapsack problem

DOI10.1007/S10107-003-0420-8MaRDI QIDQ1404231zbMATH OpenOpenAlexFDO

Authors I. R. jun. de Farias, G. L. Nemhauser

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

branch-and-cutcardinality constrained programmingknapsack problemmixed-integer programming

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2086929
• On a cardinality constrained linear programming knapsack problem
• A polyhedral study of the semi-continuous knapsack problem
• Approximation algorithms for knapsack problems with cardinality constraints
• Polyhedral results for the precedence-constrained knapsack problem
• A polyhedral study on 0-1 knapsack problems with set packing constraints
• Knapsack polytopes: a survey
• Polyhedral combinatorics of the cardinality constrained quadratic knapsack problem and the quadratic selective travelling salesman problem
• On the solution of concave knapsack problems
• Knapsack problems: a parameterized point of view

Cited in

(29)

• Branch-and-cut for linear programs with overlapping SOS1 constraints
• Polyhedral results for a class of cardinality constrained submodular minimization problems
• A polyhedral study of nonconvex quadratic programs with box constraints
• Optimization algorithms for the disjunctively constrained knapsack problem
• Valid inequalities and facets for a hypergraph model of the nonlinear knapsack and the FMS part selection problems
• Branch-and-cut for separable piecewise linear optimization and intersection with semi-continuous constraints
• Convex optimization under combinatorial sparsity constraints
• Subset selection for multiple linear regression via optimization
• Semi-continuous network flow problems
• A family of inequalities valid for the robust single machine scheduling polyhedron
• On the structure of linear programs with overlapping cardinality constraints
• On cutting planes for cardinality-constrained linear programs
• A polyhedral study of the semi-continuous knapsack problem
• Implicit cover inequalities
• 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
• Cardinality constrained combinatorial optimization: complexity and polyhedra
• A polyhedral study on \(0\)-\(1\) knapsack problems with disjoint cardinality constraints: strong valid inequalities by sequence-independent lifting
• A polyhedral study on \(0\)-\(1\) knapsack problems with disjoint cardinality constraints: facet-defining inequalities by sequential lifting
• scientific article; zbMATH DE number 2086929 (Why is no real title available?)
• Optimal rank-sparsity decomposition
• scientific article; zbMATH DE number 7366679 (Why is no real title available?)
• A combinatorial approach for small and strong formulations of disjunctive constraints
• Cardinality minimization, constraints, and regularization: a survey
• Relaxations and cutting planes for linear programs with complementarity constraints
• A nonparametric robust optimization approach for chance-constrained knapsack problem
• On a cardinality constrained linear programming knapsack problem
• Integer-programming software systems
• Knapsack polytopes: a survey

Describes a project that uses

Uses Software

• MINTO

This page was built for publication: A polyhedral study of the cardinality constrained knapsack problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1404231)