On the two-dimensional knapsack problem

DOI10.1016/S0167-6377(03)00057-9MaRDI QIDQ1433651zbMATH OpenFDO

Authors Alberto Caprara, Michele Monaci

Publication date 1 July 2004

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0167-6377(03)00057-9

zbMATH Keywords

Upper boundExact AlgorithmApproximation AlgorithmTwo-dimensional knapsackWorst-case Performance

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• An approximation algorithm for solving unconstrained two-dimensional knapsack problems
• An exact algorithm for general, orthogonal, two-dimensional knapsack problems
• Exact algorithms for the two-dimensional guillotine knapsack
• An approximation scheme for the two-stage, two-dimensional knapsack problem
• Heuristic approaches for the two- and three-dimensional knapsack packing problem

Cites work

• scientific article; zbMATH DE number 44282 (Why is no real title available?)
• scientific article; zbMATH DE number 1175962 (Why is no real title available?)
• A Combinatorial Characterization of Higher-Dimensional Orthogonal Packing
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• A new exact algorithm for general orthogonal d-dimensional knapsack problems
• Algorithms for Unconstrained Two-Dimensional Guillotine Cutting
• An Algorithm for Two-Dimensional Cutting Problems
• An Exact Two-Dimensional Non-Guillotine Cutting Tree Search Procedure
• An exact algorithm for general, orthogonal, two-dimensional knapsack problems
• An exact algorithm for orthogonal 2-D cutting problems using guillotine cuts
• An exact approach to the strip-packing problem
• Exact solution of the two-dimensional finite bin packing problem
• Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems
• Multistage Cutting Stock Problems of Two and More Dimensions
• New classes of fast lower bounds for bin packing problems
• New upper bounds for the two-dimensional orthogonal non-guillotine cutting stock problem
• Two Algorithms for Constrained Two-Dimensional Cutting Stock Problems

Cited in

(63)

• A quasi-PTAS for the two-dimensional geometric knapsack problem
• Two-dimensional knapsack-block packing problem
• Exact solution techniques for two-dimensional cutting and packing
• A genetic algorithm for the two-dimensional knapsack problem with rectangular pieces
• Online removable square packing
• Approximation algorithms for orthogonal packing problems for hypercubes
• Minimum tiling of a rectangle by squares
• Faster Approximation Schemes for the Two-Dimensional Knapsack Problem
• Conservative scales in packing problems
• PackLib\(^{2}\): an integrated library of multi-dimensional packing problems
• scientific article; zbMATH DE number 444958 (Why is no real title available?)
• Consecutive ones matrices for multi-dimensional orthogonal packing problems
• Solving the parallel processor scheduling and bin packing problems with contiguity constraints: mathematical models and computational studies
• Revenue maximization for multiple advertisements placement on a web banner using a pixel-price model
• Combinatorial Benders decomposition for single machine scheduling in additive manufacturing with two-dimensional packing constraints
• Combinatorial Benders Decomposition for the Two-Dimensional Bin Packing Problem
• Packing problems in space solved by CPLEX: an experimental analysis
• A note on a two dimensional knapsack problem with unloading constraints
• scientific article; zbMATH DE number 7656032 (Why is no real title available?)
• 2D knapsack: packing squares
• An approximation scheme for the two-stage, two-dimensional knapsack problem
• scientific article; zbMATH DE number 4160465 (Why is no real title available?)
• 2DCPackGen: a problem generator for two-dimensional rectangular cutting and packing problems
• Constrained two‐dimensional guillotine cutting problem: upper‐bound review and categorization
• MPQ-trees for orthogonal packing problem
• Grids for cutting and packing problems: a study in the 2D knapsack problem
• Consecutive ones matrices for multi-dimensional orthogonal packing problems
• A hybrid evolutionary algorithm for the two-dimensional packing problem
• On the rectangular knapsack problem
• Modeling two-dimensional guillotine cutting problems via integer programming
• Tight complexity bounds for the two-dimensional real knapsack problem
• Fast heuristic for constrained homogenous T-shape cutting patterns
• On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem
• Approximation and online algorithms for multidimensional bin packing: a survey
• Exact algorithms for the two-dimensional guillotine knapsack
• Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation
• A best-fit branch-and-bound heuristic for the unconstrained two-dimensional non-guillotine cutting problem
• Heuristic approaches for the two- and three-dimensional knapsack packing problem
• A new constraint programming approach for the orthogonal packing problem
• The off-line group seat reservation problem
• An improved typology of cutting and packing problems
• An MIP-CP based approach for two- and three-dimensional cutting problems with staged guillotine cuts
• On the \(L\)-approach for generating unconstrained two-dimensional non-guillotine cutting patterns
• Heuristics for container loading of furniture
• Maximizing revenue with allocation of multiple advertisements on a Web banner
• An EDA for the 2D knapsack problem with guillotine constraint
• Bidimensional packing by bilinear programming
• Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
• EATKG: an open-source efficient \underline{E}xact \underline{A}lgorithm for the \underline{T}wo-dimensional \underline{K}napsack problem with \underline{G}uillotine constraints
• The three-dimensional knapsack problem with balancing constraints
• A cutting plane method and a parallel algorithm for packing rectangles in a circular container
• A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem
• Approximate and exact algorithms for the double-constrained two-dimensional guillotine cutting stock problem
• Theoretical analysis of integer programming models for the two-dimensional two-staged knapsack problem
• MPQ-trees for the orthogonal packing problem
• An approximation algorithm for solving unconstrained two-dimensional knapsack problems
• A new heuristic recursive algorithm for the strip rectangular packing problem
• The two-dimensional bin packing problem with variable bin sizes and costs
• A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem
• A NEW HEURISTIC ALGORITHM FOR CONSTRAINED RECTANGLE-PACKING 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
• 2D knapsack: packing squares

This page was built for publication: On the two-dimensional knapsack problem

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