A Linear Programming Approach to the Cutting-Stock Problem

DOI10.1287/OPRE.9.6.849zbMath0096.35501OpenAlexW2144946856MaRDI QIDQ3275357

Paul C. Gilmore, Ralph E. Gomory

Publication date: 1961

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

Full work available at URL: https://semanticscholar.org/paper/141764b5e86dc6c2647dfce48098794c79d5a38b

zbMATH Keywords

applications of probability theory and statistics

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

Large-scale optimization with the primal-dual column generation method ⋮ An analysis of the integrated lot-sizing and cutting-stock problem formulation ⋮ Mathematical models and a heuristic method for the multiperiod one-dimensional cutting stock problem ⋮ A 71/60 theorem for bin packing ⋮ Decomposition-based heuristic for the zoning and crop planning problem with adjacency constraints ⋮ An exact scalarization method with multiple reference points for bi-objective integer linear optimization problems ⋮ Tightness of sensitivity and proximity bounds for integer linear programs ⋮ A comparison of five heuristics for the multiple depot vehicle scheduling problem ⋮ Solving real-world cutting stock-problems in the paper industry: mathematical approaches, experience and challenges ⋮ Optimal relay node placement in delay constrained wireless sensor network design ⋮ Near-optimal solutions to one-dimensional cutting stock problems ⋮ Huge tables and multicommodity flows are fixed-parameter tractable via unimodular integer Carathéodory ⋮ A generalization of column generation to accelerate convergence ⋮ Scheduling pumpoff operations in onshore oilfields under electric-power constraints ⋮ A branch-and-price algorithm for stable workforce assignments with hierarchical skills ⋮ Origin and early evolution of corner polyhedra ⋮ Lower bounding procedure for the asymmetric quadratic traveling salesman problem ⋮ Bin packing and cutting stock problems: mathematical models and exact algorithms ⋮ Heuristic algorithms for visiting the customers in a rolling schedule environment ⋮ Arcs-states models for the vehicle routing problem with time windows and related problems ⋮ Hybrid column generation for large-size covering integer programs: application to transportation planning ⋮ A GRASP/path relinking algorithm for two- and three-dimensional multiple bin-size bin packing problems ⋮ Mathematical programming algorithms for bin packing problems with item fragmentation ⋮ A new formulation and approach for the black and white traveling salesman problem ⋮ One-dimensional cutting stock optimization in consecutive time periods ⋮ Supervised classification and mathematical optimization ⋮ Solution approaches for the cutting stock problem with setup cost ⋮ A constraint programming based column generation approach to nurse rostering problems ⋮ Determining the \(K\)-best solutions of knapsack problems ⋮ Bin packing and related problems: general arc-flow formulation with graph compression ⋮ Exactly solving packing problems with fragmentation ⋮ A branch-and-price algorithm for the capacitated facility location problem ⋮ A column generation approach to the heterogeneous fleet vehicle routing problem ⋮ The constrained compartmentalised knapsack problem ⋮ A matrix generation approach for eigenvalue optimization ⋮ In situ column generation for a cutting-stock problem ⋮ A branch-and-price algorithm to solve the molten iron allocation problem in iron and steel industry ⋮ New bin packing fast lower bounds ⋮ On the cutting stock problem under stochastic demand ⋮ A survey of dual-feasible and superadditive functions ⋮ Lower and upper bounds for the bin packing problem with fragile objects ⋮ The constrained compartmentalized knapsack problem: mathematical models and solution methods ⋮ A parallel algorithm for two-staged two-dimensional fixed-orientation cutting problems ⋮ Cutting stock with no three parts per pattern: work-in-process and pattern minimization ⋮ A column generation heuristic for the two-dimensional two-staged guillotine cutting stock problem with multiple stock size ⋮ Reducing the number of cuts in generating three-staged cutting patterns ⋮ On the one-dimensional stock cutting problem in the paper tube industry ⋮ Trim loss optimization by an improved differential evolution ⋮ Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation ⋮ Characterization and modelling of guillotine constraints ⋮ Branch-and-price approach for the multi-skill project scheduling problem ⋮ A heuristic, dynamic programming-based approach for a two-dimensional cutting problem with defects ⋮ Turning restriction design in traffic networks with a budget constraint ⋮ A coupling cutting stock-lot sizing problem in the paper industry ⋮ A new warmstarting strategy for the primal-dual column generation method ⋮ Large gaps in one-dimensional cutting stock problems ⋮ An improved approximation scheme for variable-sized bin packing ⋮ The proper relaxation and the proper gap of the skiving stock problem ⋮ \(N\)-fold integer programming ⋮ The double pivot simplex method ⋮ Numerical optimization method for packing regular convex polygons ⋮ Polylithic modeling and solution approaches using algebraic modeling systems ⋮ Efficient branch-and-bound algorithms for weighted MAX-2-SAT ⋮ Recent advances on two-dimensional bin packing problems ⋮ A column generation method for the multiple-choice multi-dimensional knapsack problem ⋮ Integrating process optimization and inventory planning in cutting-stock with skiving option: an optimization model and its application ⋮ Production planning with approved vendor matrices for a hard-disk drive manufacturer ⋮ Semiconductor lot allocation using robust optimization ⋮ Optimal wafer cutting in shuttle layout problems ⋮ A short discussion of the OR crisis ⋮ A branch-and-price algorithm for placement routing for a multi-head beam-type component placement tool ⋮ Classification and literature review of integrated lot-sizing and cutting stock problems ⋮ Algorithms for the one-dimensional two-stage cutting stock problem ⋮ Stabilized branch-and-price algorithms for vector packing problems ⋮ Heuristics for the one-dimensional cutting stock problem with limited multiple stock lengths ⋮ Practical methods for shape fitting and kinetic data structures using coresets ⋮ Long-term staffing based on qualification profiles ⋮ The shortest path problem with forbidden paths ⋮ An inexact bundle variant suited to column generation ⋮ New lower bounds based on column generation and constraint programming for the pattern minimization problem ⋮ On the choice of explicit stabilizing terms in column generation ⋮ An effective solution for a real cutting stock problem in manufacturing plastic rolls ⋮ A computational evaluation of a general branch-and-price framework for capacitated network location problems ⋮ An integrated approach to the one-dimensional cutting stock problem in coronary stent manufacturing ⋮ A shortest path-based approach to the multileaf collimator sequencing problem ⋮ A sublinear-time approximation scheme for bin packing ⋮ The one-dimensional cutting stock problem with due dates ⋮ Models and heuristic algorithms for a weighted vertex coloring problem ⋮ The one-dimensional cutting stock problem with usable leftover - a heuristic approach ⋮ An exact approach to extend network lifetime in a general class of wireless sensor networks ⋮ New and improved level heuristics for the rectangular strip packing and variable-sized bin packing problems ⋮ 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 ⋮ Production planning and scheduling for an integrated container company ⋮ Vehicle routing via column generation ⋮ The cutting stock problem for large sections in the iron and steel industries ⋮ Heuristics for sequencing cutting patterns ⋮ Rapid prototyping of optimization algorithms using COIN-OR: a case study involving the cutting-stock problem ⋮ On compact formulations for integer programs solved by column generation

This page was built for publication: A Linear Programming Approach to the Cutting-Stock Problem