A Linear Programming Approach to the Cutting-Stock Problem

DOI10.1287/opre.9.6.849zbMath0096.35501MaRDI QIDQ3275357

Ralph E. Gomory, Paul C. Gilmore

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

Relaxation techniques applied to some loading problems, Analysis and modelling of a production line in a corrugated box factory, A sliding algorithm for optimal nesting of arbitrarily shaped sheet metal blanks, Column-Generation in Integer Linear Programming, Unnamed Item, Tighter Bounds for the Gap and Non-IRUP Constructions in the One-dimensional Cutting Stock Problem, Massive data discrimination via linear support vector machines, List-scheduling and column-generations for scheduling of n job-groups with set up time and due date through m identical parallel machines to minimize makespan, AN INTEGER L-SHAPED ALGORITHM FOR TIME-CONSTRAINED TRAVELING SALESMAN PROBLEM WITH STOCHASTIC TRAVEL AND SERVICE TIMES, From High-Level Model to Branch-and-Price Solution in G12, Integer programming approach to the printed circuit board grouping problem, Lower bounds and algorithms for the 2-dimensional vector packing problem, Analysis of upper bounds for the pallet loading problem, An integer programming approach to the time slot assignment problem in SS/TDMA systems with intersatellite links, The cutting stock problem in the canvas industry, An LP-based approach to cutting stock problems with multiple objectives, Optimal solutions for the cutting stock problem, A genetic algorithm solution for one-dimensional bundled stock cutting, Two-dimensional packing problems: a survey, LP models for bin packing and cutting stock problems, Decomposition approaches for solving the integer one-dimensional cutting stock problem with different types of standard lengths, Modeling multistage cutting stock problems, A solution procedure for a pattern sequencing problem as part of a one-dimensional cutting stock problem in the steel industry, One-dimensional cutting stock problem to minimize the number of different patterns, Algorithms for the variable sized bin packing problem, Generating optimal T-shape cutting patterns for circular blanks, Cutting aluminium coils with high length variabilities, Computing the nucleolus when the characteristic function is given implicitly: A constraint generation approach, Smart greedy procedure for solving a nonlinear knapsack class of reliability optimization problems, Heuristics for the integer one-dimensional cutting stock problem: A computational study, Interactive procedures in large-scale two-dimensional cutting stock problems, On the nucleolus of the basic vehicle routing game, Pattern minimisation in cutting stock problems, Computational results with a primal-dual subproblem simplex method, A combined cutting-stock and lot-sizing problem, Massive data classification via unconstrained support vector machines, Build-pack planning for hard disk drive assembly with approved vendor matrices and stochastic demands, An iterative sequential heuristic procedure to a real-life 1.5-dimensional cutting stock problem, Bi-dynamic constraint aggregation and subproblem reduction, An enumeration scheme to generate constrained exact checkerboard patterns, A model to optimize placement operations on dual-head placement machines, On the trade-off between staff-decomposed and activity-decomposed column generation for a staff scheduling problem, Carathéodory bounds for integer cones, Solving a combined cutting-stock and lot-sizing problem with a column generating procedure, Simultaneously determining the mix of space launch vehicles and the assignment of satellites to rockets, Solving a class of stochastic mixed-integer programs with branch and price, One-dimensional cutting stock problem with a given number of setups: a hybrid approach of metaheuristics and linear programming, An algorithm for the computation of knapsack functions, L. V. Kantorovich and cutting-packing problems: new approaches for solving combinatorial problems of linear cutting and rectangular packing, The two-dimensional bin packing problem with variable bin sizes and costs, An linear programming based lower bound for the simple assembly line balancing problem, Generating optimal multi-segment cutting patterns for circular blanks in the manufacturing of electric motors, A proximal trust-region algorithm for column generation stabilization, Branch-and-price algorithms for the dual bin packing and maximum cardinality bin packing problem, A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting, An improved typology of cutting and packing problems, A cutting-plane approach for the two-dimensional orthogonal non-guillotine cutting problem, The one dimensional Compartmentalised Knapsack problem: a case study, Models and algorithms for three-stage two-dimensional bin packing, A note on the approximability of cutting stock problems, Accelerating column generation for variable sized bin-packing problems, An integrated cutting stock and sequencing problem, A two-dimensional strip cutting problem with sequencing constraint, Alternative configurations for cutting machines in a tube cutting mill, Roll cutting in the curtain industry, or: a well-solvable allocation problem, Optimising the cutting of wood fibre plates in the hardboard industry, Metodos Duales y algoritmos hibridos para problemas de «Set Partitioning», Network design with grooming constraints, Chunking for massive nonlinear kernel classification, Improving Cutting-Stock Plans with Multi-objective Genetic Algorithm, An approach to two-dimensional cutting stock problems, A note on handling residual lengths, A dual algorithm for the one-machine scheduling problem, Optimal design of a manpower system, Glass cutting in a small firm, A column generation procedure for gang-rip saw arbor design and scheduling, Sequential design with applications to the trim-loss problem, Design of cellular manufacturing systems, The shortest path problem with forbidden paths, Recent advances on two-dimensional bin packing problems, 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, Fixed charge problems with identical fixed charges, 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, 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, One-dimensional cutting stock optimization in consecutive time periods, 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, Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation, Characterization and modelling of guillotine constraints, A coupling cutting stock-lot sizing problem in the paper industry, Large gaps in one-dimensional cutting stock problems, \(N\)-fold integer programming, 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, 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, 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, A 71/60 theorem for bin packing, Near-optimal solutions to one-dimensional cutting stock problems, A new approach for crew pairing problems by column generation with an application to air transportation, Practical adaptations of the Gilmore-Gomory approach to cutting stock problems, A comparison of two optimization procedures for 1- and 1\(1/2\)-dimensional cutting stock problems, A sequential heuristic procedure for one-dimensional cutting, The modified integer round-up property of the one-dimensional cutting stock problem, CUTGEN1: A problem generator for the standard one-dimensional cutting stock problem, Nesting planning based on production priorities and technological efficiency, The trim-loss and assortment problems: A survey, A heuristic procedure for solving the quadratic assignment problem, Bin packing can be solved within 1+epsilon in linear time, Cutting stock problems and solution procedures, On the problem of multiple mobile robots cluttering a workspace, One-dimensional cutting stock problems and solution procedures, Composite stock cutting through simulated annealing, Limiting the number of each piece in two-dimensional cutting stock patterns, Knowledge based approach to the cutting stock problem, Packing problems, Selection of parts and machines for cellularization: A mathematical programming approach, Profit-based FMS dynamic part type selection over time for mid-term production planning, Stock cutting to minimize cutting length, A simulated annealing heuristic for the one-dimensional cutting stock problem, Crew pairing at Air France, A generalized linear programming model for nurse scheduling, A branch and bound algorithm for the resource-constrained project scheduling problem, The cutting stock problem with mixed objectives: Two heuristics based on dynamic programming, Mixed-integer column generation algorithms and the probabilistic maximum satisfiability problem, HOP: A software tool for production scheduling at Bridgestone/Firestone Off-The-Road, Simulated annealing for order spread minimization in sequencing cutting patterns, An algorithm for the 2D guillotine cutting stock problem, A real-time one-dimensional cutting stock algorithm for balanced cutting patterns, Solving binary cutting stock problems by column generation and branch- and-bound, Solution procedures for cutting lumber into furniture parts, Procedures for solving a 1-dimensional cutting problem, Multiple-type, two-dimensional bin packing problems: Applications and algorithms, A column generation approach to job grouping for flexible manufacturing systems, An algorithm for the determination of optimal cutting patterns, An exact algorithm for IP column generation, Effective methods for a container packing operation, A branch-and-price algorithm for solving the cutting strips problem, Cluster analysis and mathematical programming, Optimization of roll cutting in clothing industry, Theoretical investigations on the modified integer round-up property for the one-dimensional cutting stock problem, The tolerance approach in multiobjective linear fractional programming, Improved heuristics for sequencing cutting patterns, Column generation applied to linear programs in course registration, Algorithms for the item assortment problem: an application to vending machine products, The cutting stock problem in a hardboard industry: A case study., A new model for complete solutions to one-dimensional cutting stock problems., Improving competitiveness in veneers production by a simple-to-use DSS., A column generation approach to capacitated \(p\)-median problems, Scheduling no-wait robotic cells with two and three machines, Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems, Row and column generation technique for a multistage cutting stock problem, Evaluation of algorithms for one-dimensional cutting, Families of non-IRUP instances of the one-dimensional cutting stock problem, A branch-and-price approach to \(p\)-median location problems, A cutting stock problem and its solution in the manufacturing industry of large electric generators, A combined approach to the solution to the general one-dimensional cutting stock problem, Tighter relaxations for the cutting stock problem, A hierarchical approach for one-dimensional cutting stock problems in the steel industry that maximizes yield and minimizes overgrading, A hybrid approach for optimization of one-dimensional cutting, An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment, A two-phase roll cutting problem, A one-dimensional cutting stock problem in the aluminium industry and its solution, A typology of cutting and packing problems, One-dimensional cutting stock decisions for rolls with multiple quality grades, Selection of stockplate characteristics and cutting style for two dimensional cutting stock situations