NDLI: Reduced costs propagation in an efficient implicit enumeration for the 01 multidimensional knapsack problem

Content Provider	Springer Nature Link
Author	Vimont, Yannick Boussier, Sylvain Vasquez, Michel
Copyright Year	2007
Abstract	In a previous work we proposed a variable fixing heuristics for the 0-1 Multidimensional knapsack problem (01MDK). This approach uses fractional optima calculated in hyperplanes which contain the binary optimum. This algorithm obtained best lower bounds on the OR-Library benchmarks. Although it is very attractive in terms of results, this method does not prove the optimality of the solutions found and may fix variables to a non-optimal value. In this paper, we propose an implicit enumeration based on a reduced costs analysis which tends to fix non-basic variables to their exact values. The combination of two specific constraint propagations based on reduced costs and an efficient enumeration framework enable us to fix variables on the one hand and to prune significantly the search tree on the other hand. Experimentally, our work provides two main contributions: (1) we obtain several new optimal solutions on hard instances of the OR-Library and (2) we reduce the bounds of the number of items at the optimum on several harder instances.
Starting Page	165
Ending Page	178
Page Count	14
File Format	PDF
ISSN	13826905
Journal	Journal of Combinatorial Optimization
Volume Number	15
Issue Number	2
e-ISSN	15732886
Language	English
Publisher	Springer US
Publisher Date	2007-04-21
Publisher Place	Boston
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Multidimensional knapsack problem Implicit enumeration Variable fixing Reduced costs Constraint propagation Operations Research/Decision Theory Optimization Theory of Computation Mathematical Modeling and Industrial Mathematics Convex and Discrete Geometry Combinatorics
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Control and Optimization Discrete Mathematics and Combinatorics Computational Theory and Mathematics Computer Science Applications

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

Reduced costs propagation in an efficient implicit enumeration for the 01 multidimensional knapsack problem

Improving an exact approach for solving separable integer quadratic knapsack problems

Approximation algorithms on 0–1 linear knapsack problem with a single continuous variable

A best first search exact algorithm for the Multiple-choice Multidimensional Knapsack Problem

On threshold BDDs and the optimal variable ordering problem

A successive approximation algorithm for the multiple knapsack problem

On the number of local minima for the multidimensional assignment problem

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

Implicit cover inequalities

Reduced costs propagation in an efficient implicit enumeration for the 01 multidimensional knapsack problem

Similar Documents

Reduced costs propagation in an efficient implicit enumeration for the 01 multidimensional knapsack problem

Improving an exact approach for solving separable integer quadratic knapsack problems

Approximation algorithms on 0–1 linear knapsack problem with a single continuous variable

A best first search exact algorithm for the Multiple-choice Multidimensional Knapsack Problem

On threshold BDDs and the optimal variable ordering problem

A successive approximation algorithm for the multiple knapsack problem

On the number of local minima for the multidimensional assignment problem

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

Implicit cover inequalities

Reduced costs propagation in an efficient implicit enumeration for the 01 multidimensional knapsack problem