The Multidimensional Knapsack Problem: Structure and Algorithms
From MaRDI portal
Publication:2899058
DOI10.1287/ijoc.1090.0344zbMath1243.90190OpenAlexW2168848281WikidataQ61638331 ScholiaQ61638331MaRDI QIDQ2899058
Ulrich Pferschy, Jakob Puchinger, Günther R. Raidl
Publication date: 28 July 2012
Published in: INFORMS Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://hal.inria.fr/hal-01224914/file/puchinger-07.pdf
Integer programming (90C10) Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Boolean programming (90C09)
Related Items (35)
Generalized average shadow prices and bottlenecks ⋮ A randomized heuristic repair for the multidimensional knapsack problem ⋮ A ``reduce and solve approach for the multiple-choice multidimensional knapsack problem ⋮ An Iterated Dual Substitution Approach for Binary Integer Programming Problems Under the Min-Max Regret Criterion ⋮ Decomposition based hybrid metaheuristics ⋮ Surrogate upper bound sets for bi-objective bi-dimensional binary knapsack problems ⋮ Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems ⋮ Robust efficiency measures for linear knapsack problem variants ⋮ Bi-dimensional knapsack problems with one soft constraint ⋮ Improving problem reduction for 0-1 multidimensional knapsack problems with valid inequalities ⋮ On the complexity of separation from the knapsack polytope ⋮ A Modified Binary Particle Swarm Optimization for Knapsack Problems ⋮ A variable neighborhood search algorithm for an integrated physician planning and scheduling problem ⋮ Solving large 0-1 multidimensional knapsack problems by a new simplified binary artificial fish swarm algorithm ⋮ Pseudo-polynomial algorithms for solving the knapsack problem with dependencies between items ⋮ A two-phase tabu-evolutionary algorithm for the 0-1 multidimensional knapsack problem ⋮ Canonical Duality-Triality Theory: Unified Understanding for Modeling, Problems, and NP-Hardness in Global Optimization of Multi-Scale Systems ⋮ A memetic Lagrangian heuristic for the 0-1 multidimensional knapsack problem ⋮ Essential particle swarm optimization queen with tabu search for MKP resolution ⋮ An improved version of a core based algorithm for the multi-objective multi-dimensional knapsack problem: a computational study and comparison with meta-heuristics ⋮ Approximate and exact merging of knapsack constraints with cover inequalities ⋮ Inbound and outbound flow integration for cross-docking operations ⋮ Two-stage solution-based tabu search for the multidemand multidimensional knapsack problem ⋮ Improved core problem based heuristics for the 0/1 multi-dimensional knapsack problem ⋮ Improved LP-based algorithms for the closest string problem ⋮ Identifying redundancy in multi-dimensional knapsack constraints based on surrogate constraints ⋮ Computational experience with a core-based reduction procedure for the 2-knapsack problem ⋮ A binary differential search algorithm for the 0-1 multidimensional knapsack problem ⋮ Empirical orthogonal constraint generation for multidimensional 0/1 knapsack problems ⋮ Dichotomous binary differential evolution for knapsack problems ⋮ The basic train makeup problem in shunting yards ⋮ CORAL: An Exact Algorithm for the Multidimensional Knapsack Problem ⋮ Integrating workload smoothing and inventory reduction in three intermodal logistics platforms of a European car manufacturer ⋮ Revisiting surrogate relaxation for the multidimensional knapsack problem ⋮ On the exact separation of cover inequalities of maximum-depth
Uses Software
This page was built for publication: The Multidimensional Knapsack Problem: Structure and Algorithms