The Theory and Computation of Knapsack Functions

DOI10.1287/opre.14.6.1045zbMath0173.21502OpenAlexW2021328726MaRDI QIDQ5560786

Paul C. Gilmore, Ralph E. Gomory

Publication date: 1967

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

Full work available at URL: https://doi.org/10.1287/opre.14.6.1045

zbMATH Keywords

operations research

Related Items (only showing first 100 items - show all)

An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem ⋮ Interdicting facilities in tree networks ⋮ A simulated annealing approach for the circular cutting problem ⋮ Exact methods for the knapsack problem and its generalizations ⋮ An improved version of Wang's algorithm for two-dimensional cutting problems written by J. F. Oliveira and J. S. Ferraira ⋮ Determining an upper bound for a class of rectangular packing problems ⋮ Multiperiod capacity expansion of a telecommunications connection with uncertain demand ⋮ Generating optimal T-shape cutting patterns for circular blanks ⋮ A partial enumeration algorithm for pure nonlinear integer programming ⋮ Approximate and exact algorithms for the double-constrained two-dimensional guillotine cutting stock problem ⋮ A new enumeration scheme for the knapsack problem ⋮ Knapsack problems -- an overview of recent advances. I: Single knapsack problems ⋮ Origin and early evolution of corner polyhedra ⋮ Practical adaptations of the Gilmore-Gomory approach to cutting stock problems ⋮ An exact dynamic programming algorithm for large-scale unconstrained two-dimensional guillotine cutting problems ⋮ Rapid calculation of exact cell bounds for contingency tables from conditional frequencies ⋮ The integrated lot sizing and cutting stock problem with saw cycle constraints applied to furniture production ⋮ A shortest-path-based approach for the stochastic knapsack problem with non-decreasing expected overfilling costs ⋮ Determining the \(K\)-best solutions of knapsack problems ⋮ An improvement of Viswanathan and Bagchi's exact algorithm for constrained two-dimensional cutting stock ⋮ Reduction strategies and exact algorithms for the disjunctively constrained knapsack problem ⋮ Degeneracy in infinite horizon optimization ⋮ Binary accelerated particle swarm algorithm (BAPSA) for discrete optimization problems ⋮ An approximation algorithm for solving unconstrained two-dimensional knapsack problems ⋮ Exact solutions for constrained two-dimensional cutting problems ⋮ An analytical model for the container loading problem ⋮ Bun splitting: a practical cutting stock problem ⋮ A heuristic approach based on dynamic programming and and/or-graph search for the constrained two-dimensional guillotine cutting problem ⋮ An exact algorithm for orthogonal 2-D cutting problems using guillotine cuts ⋮ An exact algorithm for general, orthogonal, two-dimensional knapsack problems ⋮ Two-dimensional skiving and cutting stock problem with setup cost based on column-and-row generation ⋮ Improved heuristics for sequencing cutting patterns ⋮ A better step-off algorithm for the knapsack problem ⋮ A dynamic programming approach to the optimization of elastic trusses ⋮ A heuristic approach to minimize the number of saw cycles in small-scale furniture factories ⋮ A new discrete electromagnetism-based meta-heuristic for solving the multidimensional knapsack problem using genetic operators ⋮ The trim-loss and assortment problems: A survey ⋮ A two-phase tabu-evolutionary algorithm for the 0-1 multidimensional knapsack problem ⋮ Tight bounds for periodicity theorems on the unbounded knapsack problem ⋮ The cutting stock problem in a hardboard industry: A case study. ⋮ Exact algorithms for the guillotine strip cutting/packing problem. ⋮ Two-stage quadratic integer programs with stochastic right-hand sides ⋮ A best-first branch and bound algorithm for unconstrained two-dimensional cutting problems. ⋮ Improving the efficiency of a best-first bottom-up approach for the constrained 2D cutting problem ⋮ An exact algorithm for large unbounded knapsack problems ⋮ The multidimensional 0-1 knapsack problem: an overview. ⋮ Scatter search for the 0-1 multidimensional knapsack problem ⋮ Characterization and modelling of guillotine constraints ⋮ Exact algorithms for unconstrained three-dimensional cutting problems: A comparative study ⋮ A heuristic, dynamic programming-based approach for a two-dimensional cutting problem with defects ⋮ Cutting stock problems and solution procedures ⋮ An empirical analysis of exact algorithms for the unbounded knapsack problem ⋮ Essential particle swarm optimization queen with tabu search for MKP resolution ⋮ A new polynomial time algorithm for 0-1 multiple knapsack problem based on dominant principles ⋮ A two-phase kernel search variant for the multidimensional multiple-choice knapsack problem ⋮ Bringing order into the neighborhoods: Relaxation guided variable neighborhood search ⋮ Knowledge based approach to the cutting stock problem ⋮ Packing problems ⋮ Fast, effective heuristics for the 0-1 multi-dimensional knapsack problem ⋮ A constructive periodicity bound for the unbounded 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 ⋮ A multi-level search strategy for the 0-1 multidimensional knapsack problem ⋮ Alternating control tree search for knapsack/covering problems ⋮ Accelerating Greenberg's method for the computation of knapsack functions ⋮ Kernel search: a general heuristic for the multi-dimensional knapsack problem ⋮ Solving multidimensional knapsack problems with generalized upper bound constraints using critical event tabu search ⋮ An ant colony optimization approach for the multidimensional knapsack problem ⋮ Optimizing two types of discrete functions, subject to linear restrictions ⋮ Static main storage packing problems ⋮ A bidirectional building approach for the 2D constrained guillotine knapsack packing problem ⋮ An upper bound for the zero-one knapsack problem and a branch and bound algorithm ⋮ A hybrid algorithm for the unbounded knapsack problem ⋮ Solution for the constrained Guillotine cutting problem by simulated annealing ⋮ Lumber production optimization ⋮ A relation between the knapsack and group knapsack problems ⋮ A Gilmore-Gomory construction of integer programming value functions ⋮ An algorithm for the two-dimensional assortment problem ⋮ An improved partial enumeration algorithm for integer programming problems ⋮ An exact algorithm for the pallet loading problem ⋮ A recursive exact algorithm for weighted two-dimensional cutting ⋮ The DH/KD algorithm: A hybrid approach for unconstrained two-dimensional cutting problems ⋮ Least-cost partition algorithms ⋮ An improved version of Wang's algorithm for two-dimensional cutting problems ⋮ Selection of stockplate characteristics and cutting style for two dimensional cutting stock situations ⋮ The cutting stock problem in the canvas industry ⋮ Unbounded knapsack problem: Dynamic programming revisited ⋮ A worst case analysis of a dynamic programming-based heuristic algorithm for 2D unconstrained guillotine cutting ⋮ Heuristic and exact reduction procedures to solve the discounted 0-1 knapsack problem ⋮ Dynamic programming using the Fritz-John conditions ⋮ An iterative variable-based fixation heuristic for the 0-1 multidimensional knapsack problem ⋮ Integrated defect detection and optimization for cross cutting of wooden boards ⋮ Trim-loss pattern rearrangement and its relevance to the flat-glass industry ⋮ A note on modifying a two-dimensional trim-loss algorithm to deal with cutting restrictions ⋮ Fixed charge problems with identical fixed charges ⋮ Zero-one integer programs with few contraints - lower bounding theory ⋮ Heuristics for sequencing cutting patterns ⋮ An efficient tabu search approach for the 0-1 multidimensional knapsack problem ⋮ The multidimensional 0-1 knapsack problem -- bounds and computational aspects ⋮ An algorithm for the periodic solutions in the knapsack problem

This page was built for publication: The Theory and Computation of Knapsack Functions