Article (Scientific journals)
On the strength of relaxations of multidimensional knapsack problems
Crama, Yves; Mazzola, Joseph B.
1994In INFOR : Information systems and operational research, 32, p. 219-225
Peer Reviewed verified by ORBi
 

Files


Full Text
Strength of relaxation INFOR.pdf
Publisher postprint (576.85 kB)
Request a copy

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Multidimensional knapsack; Lagrangian relaxation; Surrogate relaxation; composite relaxation
Abstract :
[en] Branch-and-bound algorithms for integer programming problems typically employ bounds derived from well-known relaxations, such as the Lagrangian, surrogate, or composite relaxations. Although the bounds derived from these relaxations are stronger than the bound obtained from the linear programming relaxation (LPR), in the case of multidimensional knapsack problems, i.e., integer programming problems with nonnegative objective-function and constraint coefficients, the improvement in the bound that can be realized using these relaxations is limited. In particular, we show that the improvement in the quality of the bound using any of these relaxations cannot exceed the magnitude of the largest coefficient in the objective function, nor can it exceed one-half of the optimal objective-function value of LPR. This implies, for example, that for those problem classes in which all of the objective-function coefficients are equal to 1, the bound derived from the surrogate relaxation cannot be better than the bound obtained by simply rounding the LPR bound. Awareness of these properties is important in the development of algorithms, since this class of problems subsumes many well-known integer programming problems.
Disciplines :
Quantitative methods in economics & management
Computer science
Mathematics
Author, co-author :
Crama, Yves  ;  Université de Liège > HEC Liège : UER > Recherche opérationnelle et gestion de la production
Mazzola, Joseph B.
Language :
English
Title :
On the strength of relaxations of multidimensional knapsack problems
Publication date :
1994
Journal title :
INFOR : Information systems and operational research
ISSN :
0315-5986
eISSN :
1916-0615
Publisher :
University of Toronto Press, Montreal, Canada
Volume :
32
Pages :
219-225
Peer reviewed :
Peer Reviewed verified by ORBi
Available on ORBi :
since 05 December 2016

Statistics


Number of views
88 (4 by ULiège)
Number of downloads
3 (3 by ULiège)

OpenCitations
 
1

Bibliography


Similar publications



Contact ORBi