The multidimensional 0-1 knapsack problem: an overview.

DOI10.1016/S0377-2217(03)00274-1zbMATH Open1045.90050MaRDI QIDQ1428041FDOQ1428041

Authors: Arnaud Fréville 

Publication date: 14 March 2004

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

Recommendations

• The multidimensional 0-1 knapsack problem -- bounds and computational aspects
• Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
• The multidimensional knapsack problem: structure and algorithms
• Improved results on the 0--1 multidimensional knapsack problem
• When to use Integer Programming Software to solve large multi-demand multidimensional knapsack problems: a guide for operations research practitioners

zbMATH Keywords

HeuristicsBranch-and-bound algorithmsPreprocessingMultidimensional 0-1 knapsack problemProbabilistic and worst-case analysisSurrogate duality

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Cites Work

• Octane: A New Heuristic for Pure 0–1 Programs
• A simulated annealing approach to the multiconstraint zero-one knapsack problem
• Title not available (Why is that?)
• Tabu Search—Part I
• Fast Approximation Algorithms for Knapsack Problems
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• The Traveling-Salesman Problem and Minimum Spanning Trees
• Minimum partition of a matroid into independent subsets
• The traveling-salesman problem and minimum spanning trees: Part II
• An Algorithm for Large Zero-One Knapsack Problems
• A Note on Approximation Schemes for Multidimensional Knapsack Problems
• Worst-Case Analysis of Greedy Heuristics for Integer Programming with Nonnegative Data
• Approximate Algorithms for the 0/1 Knapsack Problem
• Approximation algorithms for the m-dimensional 0-1 knapsack problem: Worst-case and probabilistic analyses
• Random knapsacks with many constraints
• New trends in exact algorithms for the \(0-1\) knapsack problem
• Title not available (Why is that?)
• Generalized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of Resources
• A hybrid approach to discrete mathematical programming
• Surrogate Mathematical Programming
• Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing
• Capital Budgeting Under Uncertainty—An Integrated Approach Using Contingent Claims Analysis and Integer Programming
• Preprocessing and Probing Techniques for Mixed Integer Programming Problems
• Heuristics and reduction methods for multiple constraints 0-1 linear programming problems
• 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
• On the Solution of Discrete Programming Problems
• Surrogate Constraint Duality in Mathematical Programming
• Sac à dos multidimensionnel en variables 0-1 : encadrement de la somme des variables à l'optimum
• Surrogate Constraints
• An Improved Implicit Enumeration Approach for Integer Programming
• An Additive Algorithm for Solving Linear Programs with Zero-One Variables
• An expanding-core algorithm for the exact \(0-1\) knapsack problem
• Balancing and optimizing a portfolio of R&D projects
• A New Algorithm for the 0-1 Knapsack Problem
• 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
• The Theory and Computation of Knapsack Functions
• Heuristic algorithms for the multiple knapsack problem
• Tabu search for the multilevel generalized assignment problem
• Solving zero-one mixed integer programming problems using tabu search
• A class of generalized greedy algorithms for the multi-knapsack problem
• The effects of coefficient correlation structure in two-dimensional knapsack problems on solution procedure performance
• Title not available (Why is that?)
• Heuristic analysis, linear programming and branch and bound
• The Reactive Tabu Search
• A ``logic-constrained knapsack formulation and a tabu algorithm for the daily photograph scheduling of an earth observation satellite
• An efficient tabu search approach for the 0-1 multidimensional knapsack problem
• A heuristic solution procedure for the multiconstraint zero-one knapsack problem
• New Greedy-Like Heuristics for the Multidimensional 0-1 Knapsack Problem
• A Simplified Algorithm for Obtaining Approximate Solutions to Zero-One Programming Problems
• Heuristic 0-1 Linear Programming: An Experimental Comparison of Three Methods
• MINTO, a Mixed INTeger Optimizer
• Discrete dynamic programming and capital allocation
• Title not available (Why is that?)
• Branch and Bound Methods for Mathematical Programming Systems
• A Branch and Bound Method for the Multiconstraint Zero-One Knapsack Problem
• Local search with memory: Benchmarking RTS
• Dynamic tabu list management using the reverse elimination method
• Tabu Search for General Zero-One Integer Programs Using the Pivot and Complement Heuristic
• Title not available (Why is that?)
• Une approche hybride pour le sac à dos multidimensionnel en variables 0–1
• Some Experiences On Solving Multiconstraint Zero-One Knapsack Problems With Genetic Algorithms
• Title not available (Why is that?)
• Discrete Programming by the Filter Method
• A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem
• Approximate algorithms for some generalized knapsack problems
• The noising method: A new method for combinatorial optimization
• (1,k)-configurations and facets for packing problems
• 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
• Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality
• 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?)
• On The Strength Of Relaxations Of Multidimensional Knapsack Problems
• Algorithms for the Simple Plant-Location Problem with Some Side Conditions
• A heuristic algorithm for the multidimensional zero-one knapsack problem
• An Improved Heuristic for Multidimensional 0-1 Knapsack Problems
• An Enumeration Algorithm for Knapsack Problems
• An algorithm for the solution of the 0-1 knapsack problem
• Pivot and Complement–A Heuristic for 0-1 Programming
• Interior Path Methods for Heuristic Integer Programming Procedures
• Experimental results on Hillier's linear search
• Efficient Heuristic Procedures for Integer Linear Programming with an Interior
• A fully polynomial approximation algorithm for the 0-1 knapsack problem
• Exact solution of multicommodity network optimization problems with general step cost functions
• Logical Reduction Methods in Zero-One Programming—Minimal Preferred Variables
• Direct Search Algorithms for Zero-One and Mixed-Integer Programming
• Title not available (Why is that?)
• Zero-one programming with many variables and few constraints
• Extension of reverse elimination method through a dynamic management of the tabu list
• Surrogate Dual Multiplier Search Procedures in Integer Programming
• Title not available (Why is that?)
• Worst-Case Analysis of Heuristic Algorithms
• Calculating surrogate constraints
• Integer Linear Programming: A Study in Computational Efficiency
• Title not available (Why is that?)
• Title not available (Why is that?)
• Tabu search within a pivot and complement framework
• Title not available (Why is that?)
• Note—An Approximate Algorithm for Multidimensional Zero-One Knapsack Problems—A Parametric Approach
• 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
• An Approach to Solving Linear Discrete Optimization Problems
• A note on the pivot and complement heuristic for 0-1 programming problems
• On rates of convergence and asymptotic normality in the multiknapsack problem
• The growth of multi-constraint random knapsack with various right-hand sides of the constraints
• Probabilistic properties of the dual structure of the multidimensional knapsack problem and fast statistically efficient algorithms
• The growth of multi-constraint random knapsacks with large right-hand sides of the constraints
• A statistical analysis of the knapsack problem
• Title not available (Why is that?)
• Probabilistic Analysis of the Multidimensional Knapsack Problem
• Coefficient reduction for inequalities in 0–1 variables
• A recursive branch and bound algorithm for the multidimensional knapsack problem
• A hybrid search combining interior point methods and metaheuristics for 0-1 programming
• Statistical mechanics of the knapsack problem
• A probabilistic analysis of the multiknapsack value function
• On the growth of random knapsacks
• The growth of m-constraint random knapsacks
• The bound improving sequence algorithm
• A revised bound improvement sequence algorithm
• Heuristic improvement methods: How should starting solutions be chosen?
• A framework for tightening 0–1 programs based on extensions of pure 0–1 KP and SS problems
• Title not available (Why is that?)

Cited In (89)

• Adaptive memory search for multidemand multidimensional knapsack problems
• The minmax multidimensional knapsack problem with application to a chance‐constrained problem
• Resource allocation based on redundancy models for high availability cloud
• Two-stage solution-based tabu search for the multidemand multidimensional knapsack problem
• A randomized heuristic repair for the multidimensional knapsack problem
• Bringing order into the neighborhoods: Relaxation guided variable neighborhood search
• 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
• Experiments concerning sequential versus simultaneous maximization of objective function and distance
• Greedy algorithm for the general multidimensional knapsack problem
• An approximate algorithm for lexicographic search in multiple orders for the solution of the multidimensional Boolean knapsack problem
• Scheduling orders for multiple product types with due date related objectives
• Memory and Learning in Metaheuristics
• Counting and enumerating independent sets with applications to combinatorial optimization problems
• Dual inequalities for stabilized column generation revisited
• Sac à dos multidimensionnel en variables 0-1 : encadrement de la somme des variables à l'optimum
• Exploiting nested inequalities and surrogate constraints
• Optimal allocation of buffer times to increase train schedule robustness
• Particle swarm optimization with time-varying acceleration coefficients for the multidimensional knapsack problem
• Allocation of advertising space by a web service provider using combinatorial auctions
• Hybrid approaches for the two-scenario max-min knapsack problem
• A two-phase tabu-evolutionary algorithm for the 0-1 multidimensional knapsack problem
• A hybrid of nested partition, binary ant system, and linear programming for the multidimensional knapsack problem
• Using the idea of expanded core for the exact solution of bi-objective multi-dimensional knapsack problems
• Optimal selection of touristic packages based on user preferences during sports mega-events
• An exact algorithm for the reliability redundancy allocation problem
• Surrogate upper bound sets for bi-objective bi-dimensional binary knapsack problems
• Algorithmic aspects for power-efficient hardware/software partitioning
• Scatter search for the 0-1 multidimensional knapsack problem
• Bi-dimensional knapsack problems with one soft constraint
• A multi-level search strategy for the 0-1 multidimensional knapsack problem
• Solving the bi-objective multi-dimensional knapsack problem exploiting the concept of core
• An approximate dynamic programming approach for improving accuracy of lossy data compression by Bloom filters
• Some new results on multi-dimension Knapsack problem
• An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem
• Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem
• Intelligent water drops algorithm
• Fast, effective heuristics for the 0-1 multi-dimensional knapsack problem
• Heuristics 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
• An agent-based stochastic ruler approach for a stochastic knapsack problem with sequential competition
• Improved convergent heuristics for the 0-1 multidimensional knapsack problem
• Improved results on the 0--1 multidimensional knapsack problem
• Improving problem reduction for 0-1 multidimensional knapsack problems with valid inequalities
• Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
• A theoretical and empirical investigation on the Lagrangian capacities of the \(0\)-\(1\) multidimensional knapsack problem
• The complexity of the 0/1 multi-knapsack problem
• Revisiting surrogate relaxation for the multidimensional knapsack problem
• The basic train makeup problem in shunting yards
• A multiobjective metaheuristic for a mean-risk static stochastic knapsack problem
• A multidimensional knapsack model for asset-backed securitization
• The multidimensional 0-1 knapsack problem -- bounds and computational aspects
• Solving large 0-1 multidimensional knapsack problems by a new simplified binary artificial fish swarm algorithm
• Une approche hybride pour le sac à dos multidimensionnel en variables 0–1
• New convergent heuristics for 0-1 mixed integer programming
• Reduced costs propagation in an efficient implicit enumeration for the 01 multidimensional knapsack problem
• 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)
• The multidimensional knapsack problem: structure and algorithms
• Solving the multidimensional knapsack problems with generalized upper bound constraints by the adaptive memory projection method
• A new exact approach for the 0-1 collapsing knapsack problem
• An ant colony optimization approach for binary knapsack problem under fuzziness
• A memetic Lagrangian heuristic for the 0-1 multidimensional knapsack problem
• Two-dimensional knapsack-block packing problem
• The restrict merger approach of a kind of multidimensional 0-1 knapsack problem
• An efficient relax-and-solve method for the multi-mode resource constrained project scheduling problem
• Features for the 0-1 knapsack problem based on inclusionwise maximal solutions
• The multiple multidimensional knapsack with family-split penalties
• A decomposition approach for multidimensional knapsacks with family‐split penalties
• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• A deep real options policy for sequential service region design and timing
• Empirical orthogonal constraint generation for multidimensional 0/1 knapsack problems
• Logic Gate-based Evolutionary Algorithm for the multidimensional knapsack problem-wireless sensor network application
• Convexity and solutions of stochastic multidimensional 0-1 knapsack problems with probabilistic constraints
• Modeling multiple plant sourcing decisions
• A RNN-based hyper-heuristic for combinatorial problems
• Discrete dynamical system approaches for Boolean polynomial optimization
• Dichotomous binary differential evolution for knapsack problems
• When to use Integer Programming Software to solve large multi-demand multidimensional knapsack problems: a guide for operations research practitioners
• Placement Optimization in Refugee Resettlement
• Identifying redundancy in multi-dimensional knapsack constraints based on surrogate constraints
• A comprehensive empirical demonstration of the impact of choice constraints on solving generalizations of the 0–1 knapsack problem using the integer programming option of CPLEX^®
• Effects of feasibility cuts in Lagrangian relaxation for a two-stage stochastic facility location and network flow problem
• Matheuristic fixed set search applied to the multidimensional knapsack problem and the knapsack problem with forfeit sets
• Binary trie coding scheme: an intelligent genetic algorithm avoiding premature convergence
• Target-based computer-assisted orchestration: complexity and approximation algorithms
• On structural parameterizations of the bounded-degree vertex deletion problem
• Probabilistic Tabu search with multiple neighborhoods for the Disjunctively Constrained Knapsack Problem

Uses Software

• CPLEX
• OR-Library
• MINTO
• Knapsack
• Tabu search
• OSL
• Octane

This page was built for publication: The multidimensional 0-1 knapsack problem: an overview.

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