Tighter relaxations for the cutting stock problem

DOI10.1016/S0377-2217(97)00404-9zbMATH Open0933.90053MaRDI QIDQ1806682FDOQ1806682

Authors: Christoph Nitsche, Guntram Scheithauer, Johannes Terno 

Publication date: 8 November 1999

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

Recommendations

• scientific article; zbMATH DE number 1594516
• Solving one-dimensional cutting stock problems exactly with a cutting plane algorithm
• Large gaps in one-dimensional cutting stock problems
• Optimal solutions for the cutting stock problem

zbMATH Keywords

integer linear programmingcutting stock problemlinear programming relaxationinteger round-up property

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites Work

• A Linear Programming Approach to the Cutting-Stock Problem
• Integer Rounding for Polymatroid and Branching Optimization Problems
• The cutting stock problem and integer rounding
• The modified integer round-up property of the one-dimensional cutting stock problem
• Title not available (Why is that?)
• An instance of the cutting stock problem for which the rounding property does not hold
• Theoretical investigations on the modified integer round-up property for the one-dimensional cutting stock problem
• Title not available (Why is that?)
• Title not available (Why is that?)
• New cases of the cutting stock problem having MIRUP
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (24)

• An inexact bundle approach to cutting-stock problems
• Families of non-IRUP instances of the one-dimensional cutting stock problem
• On the linear relaxation of the \(s-t\)-cut problem with budget constraints
• Title not available (Why is that?)
• Large proper gaps in bin packing and dual bin packing problems
• A Note on Bounding a Class of Linear Programming Problems, Including Cutting Stock Problems
• Bin packing and cutting stock problems: mathematical models and exact algorithms
• The skiving stock problem and its relation to hypergraph matchings
• Sensitive instances of the cutting stock problem
• A comparative study of the arcflow model and the one-cut model for one-dimensional cutting stock problems
• Pattern-based ILP models for the one-dimensional cutting stock problem with setup cost
• Packing by scheduling: using constraint programming to solve a complex 2D cutting stock problem
• Enhanced Pseudo-polynomial Formulations for Bin Packing and Cutting Stock Problems
• Decomposition approaches for solving the integer one-dimensional cutting stock problem with different types of standard lengths
• A polynomial time OPT + 1 algorithm for the cutting stock problem with a constant number of object lengths
• LP-Based Relaxations of the Skiving Stock Problem—Improved Upper Bounds for the Gap
• Tighter Bounds for the Gap and Non-IRUP Constructions in the One-dimensional Cutting Stock Problem
• On LP relaxations for the pattern minimization problem
• Knowledge based approach to the cutting stock problem
• Integer rounding and modified integer rounding for the skiving stock problem
• A cutting plane algorithm for the one-dimensional cutting stock problem with multiple stock lengths
• A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting
• The proper relaxation and the proper gap of the skiving stock problem
• Minimal proper non-IRUP instances of the one-dimensional cutting stock problem

This page was built for publication: Tighter relaxations for the cutting stock problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1806682)