A theoretical and empirical investigation on the Lagrangian capacities of the 0-1 multidimensional knapsack problem

DOI10.1016/J.EJOR.2011.11.011zbMATH Open1244.90163OpenAlexW2069994399MaRDI QIDQ439503FDOQ439503

Yourim Yoon, Yong-Hyuk Kim, Byung-Ro Moon

Publication date: 16 August 2012

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2011.11.011

Recommendations

• The multidimensional 0-1 knapsack problem -- bounds and computational aspects
• Sac à dos multidimensionnel en variables 0-1 : encadrement de la somme des variables à l'optimum
• Publication:3487140
• On the capacitated lot-sizing and continuous 0-1 knapsack polyhedra
• Lagrangean heuristics combined with reoptimization for the 0-1 bidimensional knapsack problem
• Some new results on multi-dimension Knapsack problem
• A new Lagrangian based branch and bound algorithm for the 0-1 knapsack problem
• A Note on Approximation Schemes for Multidimensional Knapsack Problems
• On The Strength Of Relaxations Of Multidimensional Knapsack Problems
• Improved results on the 0--1 multidimensional knapsack problem

zbMATH Keywords

integer programmingLagrangian method\(0\)-\(1\) multidimensional knapsack problemLagrangian capacity

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Integer programming (90C10) Boolean programming (90C09)

Cites Work

• Title not available (Why is that?)
• MOTGA: a multiobjective Tchebycheff based genetic algorithm for the multidimensional knapsack problem
• Title not available (Why is that?)
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)
• Tabu Search—Part I
• Obtaining test problems via Internet
• Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Approximate Algorithms for the 0/1 Knapsack Problem
• Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
• Approximation algorithms for knapsack problems with cardinality constraints
• Problem reduction heuristic for the \(0\)-\(1\) multidimensional knapsack problem
• Improved results on the 0--1 multidimensional knapsack problem
• New convergent heuristics for 0-1 mixed integer programming
• Reduced costs propagation in an efficient implicit enumeration for the 01 multidimensional knapsack problem
• A dynamic programming based reduction procedure for the multidimensional 0-1 knapsack problem
• Generalized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of Resources
• Extensions of Lagrange Multipliers in Nonlinear Programming
• Surrogate Mathematical Programming
• A multi-level search strategy for the 0-1 multidimensional knapsack problem
• Heuristics for the 0-1 multidimensional knapsack problem
• A genetic algorithm for the multidimensional knapsack problem
• An exact search for the solution of the surrogate dual of the 0-1 bidimensional knapsack problem
• The multidimensional 0-1 knapsack problem: an overview.
• Title not available (Why is that?)
• Surrogate Constraints
• On separating cover inequalities for the multidimensional knapsack problem
• Fast, effective heuristics for the 0-1 multi-dimensional knapsack problem
• Improved convergent heuristics for the 0-1 multidimensional knapsack problem
• An efficient tabu search approach for the 0-1 multidimensional knapsack problem
• A new ant colony optimization algorithm for the multidimensional Knapsack problem
• A heuristic solution procedure for the multiconstraint zero-one knapsack problem
• The multidimensional 0-1 knapsack problem -- bounds and computational aspects
• A Branch and Bound Method for the Multiconstraint Zero-One Knapsack Problem
• Tight oscillations tabu search for multidimensional knapsack problems with generalized upper bound constraints
• Title not available (Why is that?)
• Some Experiences On Solving Multiconstraint Zero-One Knapsack Problems With Genetic Algorithms
• Solving multidimensional knapsack problems with generalized upper bound constraints using critical event tabu search
• A Survey of Lagrangean Techniques for Discrete Optimization
• A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem
• Title not available (Why is that?)
• An iterative variable-based fixation heuristic for the 0-1 multidimensional knapsack problem
• LP relaxation of the two dimensional knapsack problem with box and GUB constraints
• An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem
• The 0-1 bidimensional knapsack problem: Toward an efficient high-level primitive tool
• Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions
• Lagrangean heuristics combined with reoptimization for the 0-1 bidimensional knapsack problem
• An Exact Algorithm for the Two-Constraint 0–1 Knapsack Problem
• Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality
• An $0 (n^3)$ worst case bounded special $LP$ knapsack $(0-1)$ with two constraints
• Some relationships between lagrangian and surrogate duality in integer programming
• Technical Note—Searchability of the Composite and Multiple Surrogate Dual Functions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Generalized Penalty-Function Concepts in Mathematical Optimization
• On The Strength Of Relaxations Of Multidimensional Knapsack Problems
• A heuristic algorithm for the multidimensional zero-one knapsack problem
• Scatter search for the 0-1 multidimensional knapsack problem

Cited In (3)

• Solving large-scale multidimensional knapsack problems with a new binary harmony search algorithm
• Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
• A memetic Lagrangian heuristic for the 0-1 multidimensional knapsack problem

Uses Software

• MOTGA
• OR-Library
• Knapsack

This page was built for publication: A theoretical and empirical investigation on the Lagrangian capacities of the \(0\)-\(1\) multidimensional knapsack problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q439503)