A branch-and-price-and-cut algorithm for the pattern minimization problem

DOI10.1051/ro:2008027zbMath1198.90293OpenAlexW2006514713MaRDI QIDQ3163667

Cláudio Alves, José M. Valério de Carvalho

Publication date: 26 October 2010

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

Full work available at URL: https://eudml.org/doc/105413

zbMATH Keywords

column generationbranch-and-boundcutting planesdual feasible functionsPattern Minimization Problem

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Related Items (8)

Solution approaches for the cutting stock problem with setup cost ⋮ Pattern-based ILP models for the one-dimensional cutting stock problem with setup cost ⋮ Formulations and theoretical analysis of the one-dimensional multi-period cutting stock problem with setup cost ⋮ A survey of dual-feasible and superadditive functions ⋮ Cutting stock with no three parts per pattern: work-in-process and pattern minimization ⋮ Optimal job splitting on a multi-slot machine with applications in the printing industry ⋮ Two heuristics for the capacitated multi-period cutting stock problem with pattern setup cost ⋮ New lower bounds based on column generation and constraint programming for the pattern minimization problem

Uses Software

• CUTGEN1

Cites Work

• Unnamed Item
• Unnamed Item
• CUTGEN1: A problem generator for the standard one-dimensional cutting stock problem
• A simulated annealing heuristic for the one-dimensional cutting stock problem
• Optimal solutions for the cutting stock problem
• One-dimensional cutting stock problem to minimize the number of different patterns
• Embedding of linear programming in a simulated annealing algorithm for solving a mixed integer production planning problem
• A Linear Programming Approach to the Cutting-Stock Problem
• Controlling Cutting Pattern Changes in One-Dimensional Trim Problems
• Pattern reduction in one-dimensional cutting stock problems
• Exact Algorithm for Minimising the Number of Setups in the One-Dimensional Cutting Stock Problem
• A Heuristic Programming Solution to a Nonlinear Cutting Stock Problem
• New classes of fast lower bounds for bin packing problems

This page was built for publication: A branch-and-price-and-cut algorithm for the pattern minimization problem