A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting

DOI10.1016/j.ejor.2004.08.036zbMath1091.90080OpenAlexW2059582160MaRDI QIDQ2576248

Yanyan Li

Publication date: 27 December 2005

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ejor.2004.08.036

zbMATH Keywords

column generationbranch-and-boundcutting planescutting

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Discrete location and assignment (90B80)

Related Items

A residual recombination heuristic for one-dimensional cutting stock problems ⋮ Solving real-world cutting stock-problems in the paper industry: mathematical approaches, experience and challenges ⋮ Approximate and exact algorithms for the double-constrained two-dimensional guillotine cutting stock problem ⋮ An introduction to stochastic bin packing-based server consolidation with conflicts ⋮ Integer linear programming models for the skiving stock problem ⋮ Bin packing and cutting stock problems: mathematical models and exact algorithms ⋮ One-dimensional cutting stock optimization in consecutive time periods ⋮ Heuristic for constrained T-shape cutting patterns of rectangular pieces ⋮ Consistent neighborhood search for one-dimensional bin packing and two-dimensional vector packing ⋮ An exact approach based on a new pseudo-polynomial network flow model for integrated planning and scheduling ⋮ An effective heuristic based on column generation for the two-dimensional three-stage steel plate cutting problem ⋮ Compact integer linear programming formulations for the temporal bin packing problem with fire-ups ⋮ Mathematical models and approximate solution approaches for the stochastic bin packing problem ⋮ On the cutting stock problem under stochastic demand ⋮ A note on branch-and-cut-and-price ⋮ Models for the two‐dimensional rectangular single large placement problem with guillotine cuts and constrained pattern ⋮ Lower and upper bounding procedures for the bin packing problem with concave loading cost ⋮ Mathematical models for the two-dimensional variable-sized cutting stock problem in the home textile industry ⋮ A generic exact solver for vehicle routing and related problems ⋮ A simulated annealing hyper-heuristic methodology for flexible decision support ⋮ A parallel algorithm for two-staged two-dimensional fixed-orientation cutting problems ⋮ On the one-dimensional stock cutting problem in the paper tube industry ⋮ Enhanced Pseudo-polynomial Formulations for Bin Packing and Cutting Stock Problems ⋮ The generalized assortment and best cutting stock length problems ⋮ O problema de corte de estoque em indústrias de móveis de pequeno e médio portes ⋮ BPPLIB: a library for bin packing and cutting stock problems ⋮ A branch-and-price algorithm for the two-dimensional vector packing problem with piecewise linear cost function ⋮ A comparative study of the arcflow model and the one-cut model for one-dimensional cutting stock problems ⋮ Average-weight-controlled bin-oriented heuristics for the one-dimensional bin-packing problem ⋮ Cutting stock problems with nondeterministic item lengths: a new approach to server consolidation ⋮ A two-objective mathematical model without cutting patterns for one-dimensional assortment problems ⋮ An integer programming model for two- and three-stage two-dimensional cutting stock problems ⋮ Characterizing the optimality gap and the optimal packings for the bin packing problem ⋮ A combined approach to the solution to the general one-dimensional cutting stock problem ⋮ Exact solution techniques for two-dimensional cutting and packing ⋮ One-dimensional cutting stock problem with a given number of setups: a hybrid approach of metaheuristics and linear programming ⋮ Integrating facility layout design and aisle structure in manufacturing systems: formulation and exact solution ⋮ Classification and literature review of integrated lot-sizing and cutting stock problems ⋮ Solving bin packing problems using VRPSolver models ⋮ Two-stage two-dimensional guillotine cutting stock problems with usable leftover ⋮ A lexicographic pricer for the fractional bin packing problem ⋮ The stochastic trim-loss problem ⋮ A New Branch-and-Price-and-Cut Algorithm for One-Dimensional Bin-Packing Problems ⋮ Solving robust bin-packing problems with a branch-and-price approach ⋮ An effective solution for a real cutting stock problem in manufacturing plastic rolls ⋮ The one-dimensional cutting stock problem with due dates ⋮ A worst case analysis of a dynamic programming-based heuristic algorithm for 2D unconstrained guillotine cutting ⋮ A Branch-and-Price-and-Cut Algorithm for the Cable-Routing Problem in Solar Power Plants ⋮ Cutting planes for branch-and-price algorithms ⋮ A branch-and-price algorithm for the two-dimensional vector packing problem ⋮ A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting ⋮ Friendly bin packing instances without integer round-up property ⋮ Column generation extensions of set covering greedy heuristics

Uses Software

• ABACUS
• bc-opt

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lift-and-project for mixed 0-1 programming: recent progress
• The modified integer round-up property of the one-dimensional cutting stock problem
• Solving binary cutting stock problems by column generation and branch- and-bound
• Integer linear programming models for 2-staged two-dimensional knapsack problems
• A new model for complete solutions to one-dimensional cutting stock problems.
• Strengthening Chvátal-Gomory cuts and Gomory fractional cuts
• Tighter relaxations for the cutting stock problem
• LP models for bin packing and cutting stock problems
• A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths
• Heuristics for the integer one-dimensional cutting stock problem: A computational study
• \(bc\)-\(opt\): A branch-and-cut code for mixed integer programs
• Computational study of a column generation algorithm for bin packing and cutting stock problems
• A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting
• Optimal Integer Solutions to Industrial Cutting-Stock Problems: Part 2, Benchmark Results
• Setup and Open-Stacks Minimization in One-Dimensional Stock Cutting
• A hybrid algorithm for the two-dimensional layout problem: the cases of regular and irregular shapes
• A Linear Programming Approach to the Cutting-Stock Problem
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• A Computational Study of Search Strategies for Mixed Integer Programming
• Exact Algorithm for Minimising the Number of Setups in the One-Dimensional Cutting Stock Problem
• Solving one-dimensional cutting stock problems exactly with a cutting plane algorithm
• The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization
• A Linear Programming Approach to the Cutting Stock Problem—Part II
• Multistage Cutting Stock Problems of Two and More Dimensions
• Approximate and exact algorithms for constrained (un)weighted two-dimensional two-staged cutting stock problems