The cutting stock problem and integer rounding

DOI10.1007/BF01582013zbMath0584.90063MaRDI QIDQ3710296

Odile Marcotte

Publication date: 1985

Published in: Mathematical Programming (Search for Journal in Brave)

zbMATH Keywords

knapsack problemcutting stockinteger round-up propertyintegral decomposition property

Mathematics Subject Classification ID

Integer programming (90C10)

Related Items (42)

Solving binary cutting stock problems by column generation and branch- and-bound ⋮ An instance of the cutting stock problem for which the rounding property does not hold ⋮ Knapsack polytopes: a survey ⋮ A polynomial-time algorithm for knapsack with divisible item sizes ⋮ On the effectivity of gradient methods for cutting stock problems ⋮ Column generation for a UAV assignment problem with precedence constraints ⋮ Tighter Bounds for the Gap and Non-IRUP Constructions in the One-dimensional Cutting Stock Problem ⋮ Bin packing and cutting stock problems: mathematical models and exact algorithms ⋮ ATM VP-based network design ⋮ On the bin packing problem with a fixed number of object weights ⋮ Theoretical investigations on the modified integer round-up property for the one-dimensional cutting stock problem ⋮ On variations of the subset sum problem ⋮ The modified integer round-up property of the one-dimensional cutting stock problem ⋮ A new upper bound for the multiple knapsack problem ⋮ The Mixing Set with Divisible Capacities ⋮ Lifting for the integer knapsack cover polyhedron ⋮ Large proper gaps in bin packing and dual bin packing problems ⋮ A simple \(OPT+1\) algorithm for cutting stock under the modified integer round-up property assumption ⋮ On \(n\)-step MIR and partition inequalities for integer knapsack and single-node capacitated flow sets ⋮ Convex hulls of superincreasing knapsacks and lexicographic orderings ⋮ Combinatorial investigations on the maximum gap for skiving stock instances of the divisible case ⋮ Large gaps in one-dimensional cutting stock problems ⋮ Characterizing IRDP-instances of the skiving stock problem by means of polyhedral theory ⋮ Relaxations and discretizations for the pooling problem ⋮ Knowledge based approach to the cutting stock problem ⋮ Solving sequential knapsack problems ⋮ Strong IP formulations need large coefficients ⋮ A rounding theorem for unique binary tomographic reconstruction ⋮ A well-solvable special case of the bounded knapsack problem ⋮ A polynomial algorithm for the multiple knapsack problem with divisible item sizes ⋮ Integer knapsack and flow covers with divisible coefficients: Polyhedra, optimization and separation ⋮ Tighter relaxations for the cutting stock problem ⋮ Modified greedy heuristic for the one-dimensional cutting stock problem ⋮ Column-Generation in Integer Linear Programming ⋮ Random search in the one-dimensional cutting stock problem ⋮ Optimal solutions for the cutting stock problem ⋮ Exact Solution of Cutting Stock Problems Using Column Generation and Branch-and-Bound ⋮ L. V. Kantorovich and cutting-packing problems: new approaches for solving combinatorial problems of linear cutting and rectangular packing ⋮ An asymptotically exact algorithm for the high-multiplicity bin packing problem ⋮ Decomposition approaches for solving the integer one-dimensional cutting stock problem with different types of standard lengths ⋮ Minimal proper non-IRUP instances of the one-dimensional cutting stock problem ⋮ Continuous knapsack sets with divisible capacities

Cites Work

• Integer Rounding for Polymatroid and Branching Optimization Problems
• Unnamed Item
• Unnamed Item

This page was built for publication: The cutting stock problem and integer rounding