NDLI: A polyhedral study of the cardinality constrained knapsack problem

Content Provider	Springer Nature Link
Author	de Farias Jr, I.R. Nemhauser, G.L.
Copyright Year	2003
Abstract	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 such as finance, location, and scheduling. Traditionally, cardinality constraints are modeled by introducing auxiliary 0-1 variables and additional constraints that relate the continuous and the 0-1 variables. We use an alternative approach, in which we keep in the model only the continuous variables, and we enforce the cardinality constraint through a specialized branching scheme and the use of strong inequalities valid for the convex hull of the feasible set in the space of the continuous variables. To derive the valid inequalities, we extend the concepts of cover and cover inequality, commonly used in 0-1 programming, to this class of problems, and we show how cover inequalities can be lifted to derive facet-defining inequalities. We present three families of non-trivial facet-defining inequalities that are lifted cover inequalities. Finally, we report computational results that demonstrate the effectiveness of lifted cover inequalities and the superiority of the approach of not introducing auxiliary 0-1 variables over the traditional MIP approach for this class of problems.
Starting Page	439
Ending Page	467
Page Count	29
File Format	PDF
ISSN	00255610
Journal	Mathematical Programming
Volume Number	96
Issue Number	3
e-ISSN	14364646
Language	English
Publisher	Springer-Verlag
Publisher Date	2003-06-01
Publisher Place	Berlin Heidelberg
Access Restriction	One Nation One Subscription (ONOS)
Content Type	Text
Resource Type	Article
Subject	Mathematics Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A polyhedral study of the cardinality constrained knapsack problem (2001).

A Polyhedral Study of the Cardinality Constrained Knapsack Problem (2001)

A Polyhedral Study of the Cardinality Constrained Knapsack Problem (2001)

Polyhedral combinatorics of the cardinality constrained quadratic knapsack problem and the quadratic selective travelling salesman problem

A branch and cut approach to the cardinality constrained circuit problem

Lifting valid inequalities for the precedence constrained knapsack problem

Clique-based facets for the precedence constrained knapsack problem

On the facets of the mixed–integer knapsack polyhedron

Algorithm 632: A program for the 0–1 multiple knapsack problem

A polyhedral study of the cardinality constrained knapsack problem

Similar Documents

A polyhedral study of the cardinality constrained knapsack problem (2001).

A Polyhedral Study of the Cardinality Constrained Knapsack Problem (2001)

A Polyhedral Study of the Cardinality Constrained Knapsack Problem (2001)

Polyhedral combinatorics of the cardinality constrained quadratic knapsack problem and the quadratic selective travelling salesman problem

A branch and cut approach to the cardinality constrained circuit problem

Lifting valid inequalities for the precedence constrained knapsack problem

Clique-based facets for the precedence constrained knapsack problem

On the facets of the mixed–integer knapsack polyhedron

Algorithm 632: A program for the 0–1 multiple knapsack problem

A polyhedral study of the cardinality constrained knapsack problem