The multidimensional 0-1 knapsack problem -- bounds and computational aspects
From MaRDI portal
Publication:817185
DOI10.1007/s10479-005-3448-8zbMath1091.90042OpenAlexW1968838253MaRDI QIDQ817185
Publication date: 7 March 2006
Published in: Annals of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10479-005-3448-8
preprocessingheuristics and metaheuristicsMIP solversmultidimensional 0-1 knapsack problemprobabilistic and worstcase analysissurrogate and composite duality
Approximation methods and heuristics in mathematical programming (90C59) Boolean programming (90C09)
Related Items
Exact solution method to solve large scale integer quadratic multidimensional knapsack problems, New convergent heuristics for 0-1 mixed integer programming, Consistency Cuts for Dantzig-Wolfe Reformulations, Knapsack problems -- an overview of recent advances. I: Single knapsack problems, Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems, Hybrid approaches for the two-scenario max-min knapsack problem, Exploiting nested inequalities and surrogate constraints, Improving problem reduction for 0-1 multidimensional knapsack problems with valid inequalities, Strong formulation for the spot 5 daily photograph scheduling problem, Refinement of Lagrangian bounds in optimization problems, A branch-and-price-and-cut algorithm for operating room scheduling under human resource constraints, Probabilistic Tabu search with multiple neighborhoods for the Disjunctively Constrained Knapsack Problem, A theoretical and empirical investigation on the Lagrangian capacities of the \(0\)-\(1\) multidimensional knapsack problem, A memetic Lagrangian heuristic for the 0-1 multidimensional knapsack problem, Scatter search for the 0-1 multidimensional knapsack problem, An Exact Algorithm for the Quadratic Multiknapsack Problem with an Application to Event Seating, Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem, Two-dimensional knapsack-block packing problem, Fast, effective heuristics for the 0-1 multi-dimensional knapsack problem, Solving the multidimensional knapsack problems with generalized upper bound constraints by the adaptive memory projection method, Problem reduction heuristic for the \(0\)-\(1\) multidimensional knapsack problem, Improved core problem based heuristics for the 0/1 multi-dimensional knapsack problem, Iterative semi-continuous relaxation heuristics for the multiple-choice multidimensional knapsack problem, A heuristic approach for allocation of data to RFID tags: a data allocation knapsack problem (DAKP), A multi-level search strategy for the 0-1 multidimensional knapsack problem, Improved convergent heuristics for the 0-1 multidimensional knapsack problem, A Lagrangian bound for many-to-many assignment problems, Studying properties of Lagrangian bounds for many-to-many assignment problems, Convexity and Solutions of Stochastic Multidimensional 0-1 Knapsack Problems with Probabilistic Constraints, An iterative variable-based fixation heuristic for the 0-1 multidimensional knapsack problem, Revisiting surrogate relaxation for the multidimensional knapsack problem, Memory and Learning in Metaheuristics, A novel multi-objective approach for link selection in aeronautical telecommunication networks, Advanced greedy algorithms and surrogate constraint methods for linear and quadratic knapsack and covering problems
Uses Software
Cites Work
- A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem
- Surrogate Constraints
- Direct Search Algorithms for Zero-One and Mixed-Integer Programming
- The Theory and Computation of Knapsack Functions
- Efficient Heuristic Procedures for Integer Linear Programming with an Interior
- An Enumeration Algorithm for Knapsack Problems
- Surrogate Mathematical Programming
- Stronger Inequalities for 0, 1 Integer Programming Using Knapsack Functions
- A ``logic-constrained knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A heuristic algorithm for the multidimensional zero-one knapsack problem
- Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
- A probabilistic analysis of the multiknapsack value function
- Coefficient reduction for knapsack-like constraints in 0-1 programs with variable upper bounds
- On the growth of random knapsacks
- Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing
- The growth of m-constraint random knapsacks
- Heuristics and reduction methods for multiple constraints 0-1 linear programming problems
- A simulated annealing approach to the multiconstraint zero-one knapsack problem
- A note on the pivot and complement heuristic for 0-1 programming problems
- A fully polynomial approximation algorithm for the 0-1 knapsack problem
- On rates of convergence and asymptotic normality in the multiknapsack problem
- Approximate algorithms for some generalized knapsack problems
- Zero-one programming with many variables and few constraints
- A genetic algorithm for the multidimensional knapsack problem
- Exact solution of multicommodity network optimization problems with general step cost functions
- An exact search for the solution of the surrogate dual of the 0-1 bidimensional knapsack problem
- Random knapsacks with many constraints
- An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem
- The growth of multi-constraint random knapsack with various right-hand sides of the constraints
- MINTO, a Mixed INTeger Optimizer
- Probabilistic properties of the dual structure of the multidimensional knapsack problem and fast statistically efficient algorithms
- The 0-1 bidimensional knapsack problem: Toward an efficient high-level primitive tool
- Generating cuts from surrogate constraint analysis for zero-one and multiple choice programming
- The growth of multi-constraint random knapsacks with large right-hand sides of the constraints
- Tabu search for the multilevel generalized assignment problem
- An expanding-core algorithm for the exact \(0-1\) knapsack problem
- The multidimensional 0-1 knapsack problem: an overview.
- New trends in exact algorithms for the \(0-1\) knapsack problem
- Solving zero-one mixed integer programming problems using tabu search
- An efficient tabu search approach for the 0-1 multidimensional knapsack problem
- Efficient reformulation for 0-1 programs -- methods and computational results
- A class of generalized greedy algorithms for the multi-knapsack problem
- Future paths for integer programming and links to artificial intelligence
- Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions
- A scheme for exact separation of extended cover inequalities and application to multidimensional knapsack problems
- Local search with memory: Benchmarking RTS
- Dynamic tabu list management using the reverse elimination method
- A dynamic programming based reduction procedure for the multidimensional 0-1 knapsack problem
- Balancing and optimizing a portfolio of R&D projects
- Extension of Reverse Elimination Method Through a Dynamic Management of the Tabu List
- The Effects of Coefficient Correlation Structure in Two-Dimensional Knapsack Problems on Solution Procedure Performance
- A statistical analysis of the knapsack problem
- On the Solution of Discrete Programming Problems
- Surrogate Dual Multiplier Search Procedures in Integer Programming
- Capital Budgeting Under Uncertainty—An Integrated Approach Using Contingent Claims Analysis and Integer Programming
- Octane: A New Heuristic for Pure 0–1 Programs
- Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality
- Solving Large-Scale Zero-One Linear Programming Problems
- A Note on Approximation Schemes for Multidimensional Knapsack Problems
- A heuristic solution procedure for the multiconstraint zero-one knapsack problem
- Lagrangean decomposition: A model yielding stronger lagrangean bounds
- Lagrangean decomposition for integer programming : theory and applications
- A New Algorithm for the 0-1 Knapsack Problem
- Probabilistic Analysis of the Multidimensional Knapsack Problem
- Some relationships between lagrangian and surrogate duality in integer programming
- Fast Approximation Algorithms for Knapsack Problems
- Pivot and Complement–A Heuristic for 0-1 Programming
- Heuristic analysis, linear programming and branch and bound
- Worst-Case Analysis of Heuristic Algorithms
- An Algorithm for Large Zero-One Knapsack Problems
- Technical Note—Searchability of the Composite and Multiple Surrogate Dual Functions
- Logical Reduction Methods in Zero-One Programming—Minimal Preferred Variables
- Calculating surrogate constraints
- The Lagrangian Relaxation Method for Solving Integer Programming Problems
- Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
- Tabu Search—Part I
- Coefficient reduction for inequalities in 0–1 variables
- Constraint Pairing In Integer Programming
- A recursive branch and bound algorithm for the multidimensional knapsack problem
- A Simplified Algorithm for Obtaining Approximate Solutions to Zero-One Programming Problems
- Surrogate Constraint Duality in Mathematical Programming
- Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
- Approximate Algorithms for the 0/1 Knapsack Problem
- A hybrid approach to discrete mathematical programming
- A Branch and Bound Method for the Multiconstraint Zero-One Knapsack Problem
- Sac à dos multidimensionnel en variables 0-1 : encadrement de la somme des variables à l'optimum
- Tabu Search for General Zero-One Integer Programs Using the Pivot and Complement Heuristic
- The Reactive Tabu Search
- Preprocessing and Probing Techniques for Mixed Integer Programming Problems
- Upper Bounds and Algorithms for Hard 0-1 Knapsack Problems
- Progress in Linear Programming-Based Algorithms for Integer Programming: An Exposition
- A Minimal Algorithm for the Bounded Knapsack Problem
- A hybrid search combining interior point methods and metaheuristics for 0-1 programming
- Une approche hybride pour le sac à dos multidimensionnel en variables 0–1
- On The Strength Of Relaxations Of Multidimensional Knapsack Problems
- Some Experiences On Solving Multiconstraint Zero-One Knapsack Problems With Genetic Algorithms
- Statistical mechanics of the knapsack problem
- Tabu search within a pivot and complement framework
