Cutting analysis for MKP

This work presents a comparative analysis of different types of logic cuts obtained using the dual surrogate properties of multidimensional knapsack problems. Constraint pairing and an initial integer solution are used to combine the dual surrogate constraint with the objective function and generate...

Full description

Saved in:
Bibliographic Details
Main Authors: Osorio, M.A., Hernandez, E.G.
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Constraint theory
Genetic algorithms
Lagrangian functions
Linear programming
Logic
Multidimensional systems
Operations research
Performance evaluation
Testing
Citations: Items that cite this one
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This work presents a comparative analysis of different types of logic cuts obtained using the dual surrogate properties of multidimensional knapsack problems. Constraint pairing and an initial integer solution are used to combine the dual surrogate constraint with the objective function and generate new constraints. These constraints are used to obtain different type of logic cuts and these cuts are included in the model before solving the problem to optimality with branch and bound. Computational tests were performed in the set of small problems and the first subset of big instances in the OR-library. It can be seen that the presence of logic cuts in the model improved the branch and bound performance lowering the number of nodes in the search tree.
DOI:10.1109/ENC.2004.1342620