An upper bound of (E) < 3 2 for skiving stock instances of the divisible case

DOI10.1016/J.DAM.2017.05.015MaRDI QIDQ2012070zbMATH OpenOpenAlexFDO

Authors J. Martinovic, Guntram Scheithauer

Publication date 27 July 2017

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

Full work available at URL https://doi.org/10.1016/j.dam.2017.05.015

zbMATH Keywords

(modified) integer round-down propertycutting and packingdivisible casegapskiving stock problem

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Production models (90B30) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Combinatorial investigations on the maximum gap for skiving stock instances of the divisible case
• Integer rounding and modified integer rounding for the skiving stock problem
• An improved upper bound for the gap of skiving stock instances of the divisible case
• The proper relaxation and the proper gap of the skiving stock problem
• LP-Based Relaxations of the Skiving Stock Problem—Improved Upper Bounds for the Gap

Cites work

• A dual bin-packing approach to scheduling surgical cases at a publicly-funded hospital
• A Linear Programming Approach to the Cutting-Stock Problem
• A logarithmic additive integrality gap for bin packing
• An exact algorithm for the dual bin packing problem
• An improved typology of cutting and packing problems
• An instance of the cutting stock problem for which the rounding property does not hold
• Bin packing and cutting stock problems: mathematical models and exact algorithms
• Bin packing with divisible item sizes
• Branch-and-price algorithms for the dual bin packing and maximum cardinality bin packing problem
• Case Studies from Industry: Skiving Addition to the Cutting Stock Problem in the Paper Industry
• Cutting and packing optimization. Problems modeling and solution methods.
• Families of non-IRUP instances of the one-dimensional cutting stock problem
• Friendly bin packing instances without integer round-up property
• Integer linear programming models for the skiving stock problem
• Integer Rounding for Polymatroid and Branching Optimization Problems
• Large gaps in one-dimensional cutting stock problems
• LP models for bin packing and cutting stock problems
• Mathematical methods of organizing and planning production. English translation by Robert W. Campbell and W. H. Marlow
• Minimal proper non-IRUP instances of the one-dimensional cutting stock problem
• On a dual version of the one-dimensional bin packing problem
• Probabilistic analysis of algorithms for dual bin packing problems
• Probabilistic bounds for dual bin-packing
• The modified integer round-up property of the one-dimensional cutting stock problem
• The proper relaxation and the proper gap of the skiving stock problem
• The skiving stock problem as a counterpart of the cutting stock problem
• Windows scheduling as a restricted version of bin packing

Cited in

(10)

• The skiving stock problem and its relation to hypergraph matchings
• Combinatorial investigations on the maximum gap for skiving stock instances of the divisible case
• Integer rounding and modified integer rounding for the skiving stock problem
• Improved flow-based formulations for the skiving stock problem
• Large proper gaps in bin packing and dual bin packing problems
• Integer linear programming models for the skiving stock problem
• Characterizing IRDP-instances of the skiving stock problem by means of polyhedral theory
• An improved upper bound for the gap of skiving stock instances of the divisible case
• The proper relaxation and the proper gap of the skiving stock problem
• Exact combinatorial algorithms for solving the bin covering problems with strong divisibility and rejection profit

This page was built for publication: An upper bound of \(\Delta(E) < 3 \slash 2\) for skiving stock instances of the divisible case

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