The multidimensional 0-1 knapsack problem: an overview.
From MaRDI portal
Publication:1428041
DOI10.1016/S0377-2217(03)00274-1zbMath1045.90050MaRDI QIDQ1428041
Publication date: 14 March 2004
Published in: European Journal of Operational Research (Search for Journal in Brave)
HeuristicsBranch-and-bound algorithmsPreprocessingMultidimensional 0-1 knapsack problemProbabilistic and worst-case analysisSurrogate duality
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)
Related Items
Placement Optimization in Refugee Resettlement, An approximate algorithm for lexicographic search in multiple orders for the solution of the multidimensional Boolean knapsack problem, A randomized heuristic repair for the multidimensional knapsack problem, New convergent heuristics for 0-1 mixed integer programming, An exact algorithm for the reliability redundancy allocation problem, Surrogate upper bound sets for bi-objective bi-dimensional binary knapsack problems, 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, An approximate dynamic programming approach for improving accuracy of lossy data compression by Bloom filters, Hybrid approaches for the two-scenario max-min knapsack problem, Bi-dimensional knapsack problems with one soft constraint, Exploiting nested inequalities and surrogate constraints, Improving problem reduction for 0-1 multidimensional knapsack problems with valid inequalities, Discrete dynamical system approaches for Boolean polynomial optimization, A RNN-based hyper-heuristic for combinatorial problems, On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem, Optimal selection of touristic packages based on user preferences during sports mega-events, A deep real options policy for sequential service region design and timing, Logic Gate-based Evolutionary Algorithm for the multidimensional knapsack problem-wireless sensor network application, Solving large 0-1 multidimensional knapsack problems by a new simplified binary artificial fish swarm algorithm, A two-phase tabu-evolutionary algorithm for the 0-1 multidimensional knapsack problem, Reduced costs propagation in an efficient implicit enumeration for the 01 multidimensional knapsack problem, Features for the 0-1 knapsack problem based on inclusionwise maximal solutions, A decomposition approach for multidimensional knapsacks with family‐split penalties, Probabilistic Tabu search with multiple neighborhoods for the Disjunctively Constrained Knapsack Problem, An ant colony optimization approach for binary knapsack problem under fuzziness, A theoretical and empirical investigation on the Lagrangian capacities of the \(0\)-\(1\) multidimensional knapsack problem, Intelligent water drops algorithm, A memetic Lagrangian heuristic for the 0-1 multidimensional knapsack problem, Modeling multiple plant sourcing decisions, Resource allocation based on redundancy models for high availability cloud, Scatter search for the 0-1 multidimensional knapsack problem, On structural parameterizations of the bounded-degree vertex deletion problem, Artificial bee colony algorithm merged with pheromone communication mechanism for the 0-1 multidimensional knapsack problem, Computational experiment of critical event tabu search for the general integer multidimensional knapsack problem, Consideration of triple bottom line objectives for sustainability in the optimization of vehicle routing and loading operations: a systematic literature review, Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem, Two-dimensional knapsack-block packing problem, Bringing order into the neighborhoods: Relaxation guided variable neighborhood search, Optimal allocation of buffer times to increase train schedule robustness, Particle swarm optimization with time-varying acceleration coefficients for the multidimensional knapsack problem, A new exact approach for the 0-1 collapsing knapsack problem, Two-stage solution-based tabu search for the multidemand multidimensional knapsack problem, Fast, effective heuristics for the 0-1 multi-dimensional knapsack problem, Greedy algorithm for the general multidimensional knapsack problem, Solving the multidimensional knapsack problems with generalized upper bound constraints by the adaptive memory projection method, Using the idea of expanded core for the exact solution of bi-objective multi-dimensional knapsack problems, Improved core problem based heuristics for the 0/1 multi-dimensional 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, Identifying redundancy in multi-dimensional knapsack constraints based on surrogate constraints, Adaptive memory search for multidemand multidimensional knapsack problems, A multiobjective metaheuristic for a mean-risk static stochastic knapsack problem, The multiple multidimensional knapsack with family-split penalties, Empirical orthogonal constraint generation for multidimensional 0/1 knapsack problems, Dichotomous binary differential evolution for knapsack problems, A hybrid of nested partition, binary ant system, and linear programming for the multidimensional knapsack problem, The basic train makeup problem in shunting yards, Convexity and Solutions of Stochastic Multidimensional 0-1 Knapsack Problems with Probabilistic Constraints, Dual Inequalities for Stabilized Column Generation Revisited, Experiments concerning sequential versus simultaneous maximization of objective function and distance, Algorithmic aspects for power-efficient hardware/software partitioning, Effects of feasibility cuts in Lagrangian relaxation for a two-stage stochastic facility location and network flow problem, An agent-based stochastic ruler approach for a stochastic knapsack problem with sequential competition, Target-based computer-assisted orchestration: complexity and approximation algorithms, Heuristics for the 0-1 multidimensional knapsack problem, Solving the bi-objective multi-dimensional knapsack problem exploiting the concept of core, Counting and enumerating independent sets with applications to combinatorial optimization problems, Scheduling orders for multiple product types with due date related objectives, Allocation of advertising space by a web service provider using combinatorial auctions, Binary trie coding scheme: an intelligent genetic algorithm avoiding premature convergence, Revisiting surrogate relaxation for the multidimensional knapsack problem, Memory and Learning in Metaheuristics, The multidimensional 0-1 knapsack problem -- bounds and computational aspects
Uses Software
Cites Work
- 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
- A framework for tightening 0–1 programs based on extensions of pure 0–1 KP and SS problems
- An Improved Heuristic for Multidimensional 0-1 Knapsack Problems
- Discrete Programming by the Filter Method
- Solution of Integer Linear Programming Problems by Direct Search
- Solution of the Lorie-Savage and Similar Integer Programming Problems by the Generalized Lagrange Multiplier Method
- A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem
- Surrogate Constraints
- Algorithms for the Simple Plant-Location Problem with Some Side Conditions
- Direct Search Algorithms for Zero-One and Mixed-Integer Programming
- Integer Linear Programming: A Study in Computational Efficiency
- The Theory and Computation of Knapsack Functions
- An Improved Implicit Enumeration Approach for Integer Programming
- Efficient Heuristic Procedures for Integer Linear Programming with an Interior
- Minimum partition of a matroid into independent subsets
- An Additive Algorithm for Solving Linear Programs with Zero-One Variables
- An Approach to Solving Linear Discrete Optimization Problems
- An Enumeration Algorithm for Knapsack Problems
- The Traveling-Salesman Problem and Minimum Spanning Trees
- The traveling-salesman problem and minimum spanning trees: Part II
- Surrogate Mathematical Programming
- 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
- 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
- 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
- The bound improving sequence algorithm
- Heuristics and reduction methods for multiple constraints 0-1 linear programming problems
- A simulated annealing approach to the multiconstraint zero-one knapsack problem
- A revised bound improvement sequence algorithm
- A note on the pivot and complement heuristic for 0-1 programming problems
- Heuristic algorithms for the multiple knapsack problem
- An algorithm for the solution of the 0-1 knapsack problem
- 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
- The noising method: A new method for combinatorial optimization
- 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
- 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
- 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
- A class of generalized greedy algorithms for the multi-knapsack problem
- Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions
- Local search with memory: Benchmarking RTS
- Dynamic tabu list management using the reverse elimination method
- Balancing and optimizing a portfolio of R&D projects
- Extension of Reverse Elimination Method Through a Dynamic Management of the Tabu List
- Discrete Dynamic Programming and Capital Allocation
- 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
- A Note on Approximation Schemes for Multidimensional Knapsack Problems
- A heuristic solution procedure for the multiconstraint zero-one knapsack problem
- Note—An Approximate Algorithm for Multidimensional Zero-One Knapsack Problems—A Parametric Approach
- A New Algorithm for the 0-1 Knapsack Problem
- Probabilistic Analysis of the Multidimensional Knapsack Problem
- Generalized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of Resources
- Some relationships between lagrangian and surrogate duality in integer programming
- Fast Approximation Algorithms for Knapsack Problems
- (1,k)-configurations and facets for packing problems
- Heuristic improvement methods: How should starting solutions be chosen?
- New Greedy-Like Heuristics for the Multidimensional 0-1 Knapsack Problem
- Pivot and Complement–A Heuristic for 0-1 Programming
- Heuristic analysis, linear programming and branch and bound
- Interior Path Methods for Heuristic Integer Programming Procedures
- 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
- A recursive branch and bound algorithm for the multidimensional knapsack problem
- A Simplified Algorithm for Obtaining Approximate Solutions to Zero-One Programming Problems
- Experimental results on Hillier's linear search
- 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
- Heuristic 0-1 Linear Programming: An Experimental Comparison of Three Methods
- A hybrid approach to discrete mathematical programming
- Branch and Bound Methods for Mathematical Programming Systems
- 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
