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

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 ⋮ On nonlinear optimization in integers ⋮ Une approche hybride pour le sac à dos multidimensionnel en variables 0–1 ⋮ Hybrid approaches for the two-scenario max-min knapsack problem ⋮ On maximal and minimal triangular planar graphs: an optimization approach ⋮ The one dimensional Compartmentalised Knapsack problem: a case study ⋮ Analysis of the knapsack problem using L-partition ⋮ Ameso optimization: a relaxation of discrete midpoint convexity ⋮ A minimal algorithm for the Bounded Knapsack Problem ⋮ An introduction to the two‐dimensional rectangular cutting and packing problem ⋮ Constrained two‐dimensional guillotine cutting problem: upper‐bound review and categorization ⋮ Exact approaches for the unconstrained two-dimensional cutting problem with defects ⋮ A few strong knapsack facets ⋮ Intuitionistic fuzzy knapsack problem trough the index matrices prism ⋮ An improved best-first branch-and-bound algorithm for unconstrained two-dimensional cutting problems ⋮ An iterative sequential heuristic procedure to a real-life 1.5-dimensional cutting stock problem ⋮ The Unbounded Knapsack Problem ⋮ Intelligent water drops algorithm ⋮ Guillotine cutting of defective boards ⋮ Solving Stochastic and Bilevel Mixed-Integer Programs via a Generalized Value Function ⋮ Modeling multiple plant sourcing decisions ⋮ A dynamic programming based reduction procedure for the multidimensional 0-1 knapsack problem ⋮ A solution method for a knapsack problem and its variant ⋮ Shortest path algorithms for knapsack type problems ⋮ Strip generation algorithms for constrained two-dimensional two-staged cutting problems ⋮ An algorithm for the 0/1 Knapsack problem ⋮ Two-stage integer programs with stochastic right-hand sides: A superadditive dual approach ⋮ A bi-objective guillotine cutting problem of stamping strips of equal circles ⋮ Asignacion de recuerdos max-min: Propiedades y algoritmos ⋮ The pallet packing problem for non-uniform box sizes ⋮ Fractional knapsack problems ⋮ Empirical orthogonal constraint generation for multidimensional 0/1 knapsack problems ⋮ A serial inventory system with supplier selection and order quantity allocation considering transportation costs ⋮ Superadditive characterizations of pure integer programming feasibility ⋮ A bottom-up packing approach for modeling the constrained two-dimensional guillotine placement problem ⋮ A generalized knapsack problem with variable coefficients ⋮ Convexity and Solutions of Stochastic Multidimensional 0-1 Knapsack Problems with Probabilistic Constraints ⋮ A Stackelberg equilibrium for a missile procurement problem ⋮ An algorithm for the computation of knapsack functions ⋮ Semi-Infinite Relaxations for the Dynamic Knapsack Problem with Stochastic Item Sizes ⋮ Glass cutting in a small firm ⋮ Some polyhedra related to combinatorial problems ⋮ Using GPU Computing for Solving the Two-Dimensional Guillotine Cutting Problem ⋮ A note on constraint aggregation and value functions for two-stage stochastic integer programs ⋮ Generating optimal two-section cutting patterns for rectangular blanks ⋮ Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality ⋮ A primal-like algorithm for zero-one integer Fractional Programming Problem