Exploiting surrogate constraint analysis for fixing variables in both bounds for multidimensional knapsack problems

The exploitation by Osorio et al. (2002) of surrogate constraints and constraint pairing is strengthened to give better results in multidimensional knapsack problems, by excluding simple bounding constraints as component constraints. The surrogate constraint is obtained by weighting the original pro...

Full description

Saved in:
Bibliographic Details
Main Authors: Osorio, M.A., Glover, F.
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Constraint theory
Genetic algorithms
Heuristic algorithms
Lagrangian functions
Linear programming
Multidimensional systems
Operations research
Resource management
Upper bound
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The exploitation by Osorio et al. (2002) of surrogate constraints and constraint pairing is strengthened to give better results in multidimensional knapsack problems, by excluding simple bounding constraints as component constraints. The surrogate constraint is obtained by weighting the original problem constraints by their associated dual values in the LP relaxation of the problem. This surrogate constraint is paired with the objective function to obtain a combined constraint where negative variables are replaced by complemented variables and the resulting constraint used to fix variables to zero or one.
DOI:10.1109/ENC.2003.1232903