Minimal proper non-IRUP instances of the one-dimensional cutting stock problem

DOI10.1016/j.dam.2015.02.020zbMath1327.90118arXiv1405.5988OpenAlexW2007336577MaRDI QIDQ2348062

Artem V. Ripatti, Sascha Kurz, Guntram Scheithauer, Vadim M. Kartak

Publication date: 10 June 2015

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1405.5988

zbMATH Keywords

bin packing problemcutting stock problemequivalence of instancesinteger round-up propertyweighted simple games

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27)

Related Items (25)

The cost of getting local monotonicity ⋮ Bin packing and cutting stock problems: mathematical models and exact algorithms ⋮ The skiving stock problem and its relation to hypergraph matchings ⋮ A branch-and-price algorithm for capacitated hypergraph vertex separation ⋮ Constructing an instance of the cutting stock problem of minimum size which does not possess the integer round-up property ⋮ On weights and quotas for weighted majority voting games ⋮ Bounds for the Nakamura number ⋮ Large proper gaps in bin packing and dual bin packing problems ⋮ Nested \((2,3)\)-instances of the cutting stock problem ⋮ Solving the skiving stock problem by a combination of stabilized column generation and the reflect arc-flow model ⋮ On the characterization of weighted simple games ⋮ Enhanced Pseudo-polynomial Formulations for Bin Packing and Cutting Stock Problems ⋮ Correction to: ``On minimum sum representations for weighted voting games ⋮ Arc flow formulations based on dynamic programming: theoretical foundations and applications ⋮ The proper relaxation and the proper gap of the skiving stock problem ⋮ Characterizing IRDP-instances of the skiving stock problem by means of polyhedral theory ⋮ Integer rounding and modified integer rounding for the skiving stock problem ⋮ A comparative study of the arcflow model and the one-cut model for one-dimensional cutting stock problems ⋮ An upper bound of \(\Delta(E) < 3 \slash 2\) for skiving stock instances of the divisible case ⋮ The minimum raster set problem and its application to the \(d\)-dimensional orthogonal packing problem ⋮ Sensitive Instances of the Cutting Stock Problem ⋮ A New Branch-and-Price-and-Cut Algorithm for One-Dimensional Bin-Packing Problems ⋮ New exact techniques applied to a class of network flow formulations ⋮ Improved flow-based formulations for the skiving stock problem ⋮ A branch-and-price algorithm for the temporal bin packing problem

Cites Work

• Unnamed Item
• Unnamed Item
• On \(\alpha\)-roughly weighted games
• Heuristic and exact solutions to the inverse power index problem for small voting bodies
• Large gaps in one-dimensional cutting stock problems
• An instance of the cutting stock problem for which the rounding property does not hold
• The modified integer round-up property of the one-dimensional cutting stock problem
• Worst-case analyses, linear programming and the bin-packing problem
• Theoretical investigations on the modified integer round-up property for the one-dimensional cutting stock problem
• Families of non-IRUP instances of the one-dimensional cutting stock problem
• On minimum sum representations for weighted voting games
• Tighter relaxations for the cutting stock problem
• Friendly bin packing instances without integer round-up property
• Sufficient conditions for the integer round-up property to be violated for the linear cutting stock problem
• Bin Packing via Discrepancy of Permutations
• On the inverse power index problem
• A CLASS OF MAJORITY GAMES
• A Linear Programming Approach to the Cutting-Stock Problem
• Integer Rounding for Polymatroid and Branching Optimization Problems
• The cutting stock problem and integer rounding
• Tighter Bounds for the Gap and Non-IRUP Constructions in the One-dimensional Cutting Stock Problem

This page was built for publication: Minimal proper non-IRUP instances of the one-dimensional cutting stock problem