Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems

DOI10.1016/J.COR.2021.105693OpenAlexW4210457632MaRDI QIDQ2147011FDOQ2147011

Authors: Valentina Cacchiani, Manuel Iori, Alberto Locatelli, Silvano Martello 

Publication date: 22 June 2022

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2021.105693

Recommendations

• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• The quadratic knapsack problem -- a survey
• Some new results on multi-dimension Knapsack problem
• The multidimensional knapsack problem: structure and algorithms
• Generalized quadratic multiple knapsack problem and two solution approaches
• The multidimensional 0-1 knapsack problem: an overview.
• A Note on Approximation Schemes for Multidimensional Knapsack Problems
• The multiobjective multidimensional knapsack problem: a survey and a new approach
• A branch-and-bound algorithm for multi-dimensional quadratic 0–1 knapsack problems
• An approximate dynamic programming approach to multidimensional knapsack problems

zbMATH Keywords

surveycombinatorial optimizationmultiple and multidimensional knapsack problemsquadratic knapsack problems

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Cites Work

• Approximation algorithms for orthogonal packing problems for hypercubes
• Tight oscillations tabu search for multidimensional knapsack problems with generalized upper bound constraints
• 2D knapsack: packing squares
• Online removable knapsack with limited cuts
• Solving multidimensional knapsack problems with generalized upper bound constraints using critical event tabu search
• Heuristic algorithms for the multiple-choice multidimensional knapsack problem
• A column generation method for the multiple-choice multi-dimensional knapsack problem
• Multiple subset sum with inclusive assignment set restrictions
• An approximation scheme for the two-stage, two-dimensional knapsack problem
• Algorithms for 3D guillotine cutting problems: unbounded knapsack, cutting stock and strip packing
• Exact solution method to solve large scale integer quadratic multidimensional knapsack problems
• An iterative variable-based fixation heuristic for the 0-1 multidimensional knapsack problem
• A new upper bound for the 0-1 quadratic knapsack problem
• Lagrangean heuristics combined with reoptimization for the 0-1 bidimensional knapsack problem
• An Exact Algorithm for the Two-Constraint 0–1 Knapsack Problem
• Scatter search for the 0-1 multidimensional knapsack problem
• A fuzzy genetic algorithm based on binary encoding for solving multidimensional knapsack problems
• Bin completion algorithms for multicontainer packing, Knapsack, and covering problems
• Computational performance of basic state reduction based dynamic programming algorithms for bi-objective 0-1 knapsack problems
• A simplified binary artificial fish swarm algorithm for 0-1 quadratic knapsack problems
• Online unweighted knapsack problem with removal cost
• An adaptive population multi-objective quantum-inspired evolutionary algorithm for multi-objective 0/1 knapsack problems
• Multicriteria 0-1 knapsack problems with \(k\)-min objectives
• Relaxations and heuristics for the multiple non-linear separable knapsack problem
• New greedy heuristics for the multiple-choice multi-dimensional knapsack problem
• Heuristic algorithms for the general nonlinear separable knapsack problem
• Intelligent water drops algorithm
• Multiple criteria dynamic programming and multiple knapsack problem
• A bound and bound algorithm for the zero-one multiple knapsack problem
• Approximation of the quadratic knapsack problem
• Approximation of the quadratic knapsack problem
• An improved version of a core based algorithm for the multi-objective multi-dimensional knapsack problem: a computational study and comparison with meta-heuristics
• Using a mixed integer programming tool for solving the 0-1 quadratic knapsack problem
• Computational experience with a core-based reduction procedure for the 2-knapsack problem
• An iterative pseudo-gap enumeration approach for the multidimensional multiple-choice knapsack problem
• An ant colony optimization approach for the multidimensional knapsack problem
• Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications
• A hybrid of nested partition, binary ant system, and linear programming for the multidimensional knapsack problem
• A branch \& bound algorithm for the 0-1 mixed integer knapsack problem with linear multiple choice constraints
• A partheno-genetic algorithm for dynamic 0-1 multidimensional Knapsack problem
• A column-generation approach to the multiple knapsack problem with color constraints
• Valid inequalities for the multi-dimensional multiple-choice 0-1 knapsack problem
• Merging valid inequalities over the multiple knapsack polyhedron
• A cooperative swarm intelligence algorithm for multi-objective discrete optimization with application to the Knapsack problem
• Particle swarm optimization with time-varying acceleration coefficients for the multidimensional knapsack problem
• Grids for cutting and packing problems: a study in the 2D knapsack problem
• A branch-and-bound algorithm for the quadratic multiple knapsack problem
• Approximation and online algorithms for multidimensional bin packing: a survey
• CORAL: an exact algorithm for the multidimensional knapsack problem
• 0-1 quadratic knapsack problems: an exact approach based on a \(t\)-linearization
• The Quadratic Multiknapsack Problem with Conflicts and Balance Constraints
• A randomized heuristic repair for the multidimensional knapsack problem
• A modified descent method-based heuristic for binary quadratic knapsack problems with conflict graphs
• Online minimization knapsack problem
• Exact solution techniques for two-dimensional cutting and packing
• An exact algorithm for the fixed-charge multiple knapsack problem
• Lagrangian heuristics for the quadratic knapsack problem
• On the approximability of the two-phase knapsack problem
• A new upper bound for the multiple knapsack problem
• Faster Approximation Schemes for the Two-Dimensional Knapsack Problem
• A note on a two dimensional knapsack problem with unloading constraints
• Two-stage solution-based tabu search for the multidemand multidimensional knapsack problem
• An iterated ``hyperplane exploration approach for the quadratic knapsack problem
• A multi-start iterated local search algorithm for the generalized quadratic multiple knapsack problem
• Compressed data structures for bi-objective \(\{0,1\}\)-knapsack problems
• Emergency relocation of items using single trips: special cases of the multiple knapsack assignment problem
• Upper and lower bounding procedures for the multiple knapsack assignment problem
• An application of the multiple knapsack problem: the self-sufficient marine
• Mathematical models and decomposition methods for the multiple knapsack problem
• Title not available (Why is that?)
• A matheuristic for the 0--1 generalized quadratic multiple knapsack problem
• Two-dimensional knapsack-block packing problem
• Exact methods for three-dimensional cutting and packing: a comparative study concerning single container problems
• The multiple multidimensional knapsack with family-split penalties
• Polynomial-size formulations and relaxations for the quadratic multiple knapsack problem
• Irregular packing problems: a review of mathematical models
• Online knapsack of unknown capacity. How to optimize energy consumption in smartphones
• Packing groups of items into multiple knapsacks
• An Exact Algorithm for the Quadratic Multiknapsack Problem with an Application to Event Seating
• An EDA for the 2D knapsack problem with guillotine constraint
• An iterative bidirectional heuristic placement algorithm for solving the two-dimensional knapsack packing problem
• A logarithmic descent direction algorithm for the quadratic knapsack problem
• Approximation schemes for \(r\)-weighted minimization knapsack problems
• A nonlinear multidimensional knapsack problem in the optimal design of mixture experiments
• A hybrid evolutionary search for the generalized quadratic multiple knapsack problem
• On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem
• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• A two-phase kernel search variant for the multidimensional multiple-choice knapsack problem
• Empirical orthogonal constraint generation for multidimensional 0/1 knapsack problems
• Online knapsack problem under concave functions
• Parametric convex quadratic relaxation of the quadratic knapsack problem
• 0-1 quadratic knapsack problem solved with VNS algorithm
• Lower and upper bounds for the non-linear generalized assignment problem
• A cut-and-branch algorithm for the quadratic knapsack problem
• An exact algorithm for the budget-constrained multiple knapsack problem
• A Lexicographic 0.5-Approximation Algorithm for the Multiple Knapsack Problem
• New reduction strategy in the biobjective knapsack problem
• Title not available (Why is that?)
• The quadratic knapsack problem -- a survey
• Title not available (Why is that?)
• The symmetric quadratic knapsack problem: approximation and scheduling applications
• Title not available (Why is that?)
• A strongly polynomial FPTAS for the symmetric quadratic knapsack problem
• Multicriteria Optimization
• A Polynomial Time Approximation Scheme for the Multiple Knapsack Problem
• Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications
• A 3/4-approximation algorithm for multiple subset sum
• Online knapsack with resource augmentation
• The online knapsack problem: advice and randomization
• Online removable knapsack problem under convex function
• Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem
• Solving the multidimensional multiple-choice knapsack problem by constructing convex hulls
• Online knapsack revisited
• The multiple subset sum problem
• Title not available (Why is that?)
• A note on optimal solutions to quadratic knapsack problems
• Exact solution of bin-packing problems using column generation and branch-and-bound
• Maximizing the total profit of rectangles packed into a rectangle
• The online knapsack problem with incremental capacity
• Title not available (Why is that?)
• Randomized algorithms for online knapsack problems
• A successive approximation algorithm for the multiple knapsack problem
• On the two-dimensional knapsack problem
• Problem reduction heuristic for the \(0\)-\(1\) multidimensional knapsack problem
• Iterative semi-continuous relaxation heuristics for the multiple-choice multidimensional knapsack problem
• Dynamic programming and hill-climbing techniques for constrained two-dimensional cutting stock problems
• Improved results on the 0--1 multidimensional knapsack problem
• A population heuristic for constrained two-dimensional non-guillotine cutting
• 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
• A best first search exact algorithm for the multiple-choice multidimensional knapsack problem
• A reactive local search-based algorithm for the multiple-choice multi-dimensional knapsack problem
• Title not available (Why is that?)
• The multidimensional knapsack problem: structure and algorithms
• A ``reduce and solve approach for the multiple-choice multidimensional knapsack problem
• Dynamic programming algorithms for the bi-objective integer knapsack problem
• Algorithmic improvements on dynamic programming for the bi-objective \(\{0,1\}\) knapsack problem
• A Core-Based Exact Algorithm for the Multidimensional Multiple Choice Knapsack Problem
• A two state reduction based dynamic programming algorithm for the bi-objective \(0\)-\(1\) knapsack problem
• Hybrid algorithms for the multiple-choice multi-dimensional knapsack problem
• Heuristic approaches for the two- and three-dimensional knapsack packing problem
• A multi-level search strategy for the 0-1 multidimensional knapsack problem
• Kernel search: a general heuristic for the multi-dimensional knapsack problem
• The nonlinear knapsack problem - algorithms and applications
• A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem
• Iterated responsive threshold search for the quadratic multiple knapsack problem
• A hybrid genetic algorithm for the two-dimensional single large object placement problem
• A tabu search algorithm for a two-dimensional non-guillotine cutting problem
• A hybrid evolutionary algorithm for the two-dimensional packing problem
• A genetic algorithm for the two-dimensional knapsack problem with rectangular pieces
• Heuristics for the 0-1 multidimensional knapsack problem
• A genetic algorithm for the multidimensional knapsack problem
• The multidimensional 0-1 knapsack problem: an overview.
• The assignment and loading transportation problem
• Towards strong duality in integer programming
• The multiobjective multidimensional knapsack problem: a survey and a new approach
• Surrogate upper bound sets for bi-objective bi-dimensional binary knapsack problems
• On the solution of multidimensional convex separable continuous knapsack problem with bounded variables
• Solving the linear multiple choice knapsack problem with two objectives: Profit and equity
• On separating cover inequalities for the multidimensional knapsack problem
• A PTAS for the multiple subset sum problem with different knapsack capacities
• A computational study on the quadratic knapsack problem with multiple constraints
• Reoptimization in Lagrangian methods for the \(0\)-\(1\) quadratic knapsack problem
• Improved core problem based heuristics for the 0/1 multi-dimensional knapsack problem
• Tabu-enhanced iterated greedy algorithm: a case study in the quadratic multiple knapsack problem
• Adaptive memory search for multidemand multidimensional knapsack problems
• A local-search-based heuristic for the demand-constrained multidimensional knapsack problem
• Solution of large quadratic knapsack problems through aggressive reduction
• A dynamic programming heuristic for the quadratic knapsack problem
• An ejection chain approach for the quadratic multiple knapsack problem
• Asymptotic behavior of the quadratic knapsack problem
• Title not available (Why is that?)
• Exact Solution of the Quadratic Knapsack Problem
• An effective GRASP and tabu search for the 0-1 quadratic knapsack problem
• A Bibliographical Survey On Some Well-Known Non-Standard Knapsack Problems
• An exact method based on Lagrangian decomposition for the 0-1 quadratic knapsack problem
• Hard multidimensional multiple choice knapsack problems, an empirical study
• Model and algorithms for multi-period sea cargo mix problem
• Generalized quadratic multiple knapsack problem and two solution approaches
• Improved convergent heuristics for the 0-1 multidimensional knapsack problem
• A tabu search algorithm for large-scale guillotine (un)constrained two-dimensional cutting problems
• A procedure-based heuristic for 0-1 multiple knapsack problems
• Solving the multidimensional knapsack problems with generalized upper bound constraints by the adaptive memory projection method
• Strategic oscillation for the quadratic multiple knapsack problem
• A new ant colony optimization algorithm for the multidimensional Knapsack problem
• Very large-scale neighborhood search for the \(K\)-constraint multiple knapsack problem
• Solving large-scale multidimensional knapsack problems with a new binary harmony search algorithm
• Models and algorithms for packing rectangles into the smallest square
• Hybridization of tabu search with feasible and infeasible local searches for the quadratic multiple knapsack problem
• Improving problem reduction for 0-1 multidimensional knapsack problems with valid inequalities
• A binary multiple knapsack model for single machine scheduling with machine unavailability
• Parameterized approximation scheme for the multiple knapsack problem
• A theoretical and empirical investigation on the Lagrangian capacities of the \(0\)-\(1\) multidimensional knapsack problem
• The three-dimensional knapsack problem with balancing constraints
• A branch-and-bound algorithm for hard multiple knapsack problems
• The multidimensional 0-1 knapsack problem -- bounds and computational aspects
• Packing into the smallest square: worst-case analysis of lower bounds

Cited In (30)

• Learning-based multi-objective evolutionary algorithm for batching decision problem
• Generic polynomial algorithms for the knapsack problem in some matrix semigroups
• Mathematical models and decomposition methods for the multiple knapsack problem
• Approximating single- and multi-objective nonlinear sum and product knapsack problems
• Branch-and-price algorithms for large-scale mission-oriented maintenance planning problems
• Title not available (Why is that?)
• Knapsack problems with position-dependent item weights or profits
• Lagrangian matheuristics for the quadratic multiple knapsack problem
• LP relaxation and dynamic programming enhancing VNS for the multiple knapsack problem with setup
• A decomposition approach for multidimensional knapsacks with family‐split penalties
• Knapsack problems -- an overview of recent advances. I: Single knapsack problems
• Pseudo-polynomial algorithms for solving the knapsack problem with dependencies between items
• Title not available (Why is that?)
• A Bibliographical Survey On Some Well-Known Non-Standard Knapsack Problems
• Greedy heuristic guided by lexicographic excellence
• Improved approximation for two-dimensional vector multiple knapsack
• Distributed asynchronous column generation
• The multidimensional 0-1 knapsack problem: an overview.
• On a cube and subspace projections
• The quadratic knapsack problem -- a survey
• The multidimensional 0-1 knapsack problem -- bounds and computational aspects
• A survey of effective heuristics and their application to a variety of knapsack problems
• Cutting and packing problems under uncertainty: literature review and classification framework
• Adaptive feasible and infeasible evolutionary search for the knapsack problem with forfeits
• The knapsack problem with forfeit sets
• Approximation schemes for packing problems with \(\ell_p\)-norm diversity constraints
• Knapsack: connectedness, path, and shortest-path
• Verifying new instances of the multidemand multidimensional knapsack problem with instance space analysis
• Generalization of the subset sum problem and cubic forms
• A lifted-space dynamic programming algorithm for the quadratic knapsack problem

Uses Software

• Knapsack
• mkc7

This page was built for publication: Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems

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