The skiving stock problem and its relation to hypergraph matchings

DOI10.1016/j.disopt.2018.03.001zbMath1506.90228OpenAlexW2793916479WikidataQ130097142 ScholiaQ130097142MaRDI QIDQ1662646

John Martinovic, Guntram Scheithauer

Publication date: 20 August 2018

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2018.03.001

zbMATH Keywords

hypergraphcutting and packingskiving stock problem(fractional) matchingadditive integrality gap

Mathematics Subject Classification ID

Integer programming (90C10) Hypergraphs (05C65) Combinatorial optimization (90C27)

Related Items (2)

Two-dimensional skiving and cutting stock problem with setup cost based on column-and-row generation ⋮ Improved flow-based formulations for the skiving stock problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Integer linear programming models for the skiving stock problem
• Bin packing and cutting stock problems: mathematical models and exact algorithms
• Bin packing and related problems: general arc-flow formulation with graph compression
• The proper relaxation and the proper gap of the skiving stock problem
• On the fractional matching polytope of a hypergraph
• The difference and ratio of the fractional matching number and the matching number of graphs
• Probabilistic bounds for dual bin-packing
• Matching theory
• Maximum degree and fractional matchings in uniform hypergraphs
• On-line and off-line approximation algorithms for vector covering problems
• Introduction to cutting and packing optimization. Problems, modeling approaches, solution methods
• 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
• Tighter relaxations for the cutting stock problem
• Matchings and covers in hypergraphs
• LP models for bin packing and cutting stock problems
• Algorithmic graph theory and perfect graphs
• An exact algorithm for the dual bin packing problem
• A dual bin-packing approach to scheduling surgical cases at a publicly-funded hospital
• Minimal proper non-IRUP instances of the one-dimensional cutting stock problem
• Branch-and-price algorithms for the dual bin packing and maximum cardinality bin packing problem
• An improved typology of cutting and packing problems
• Mathematical Methods of Organizing and Planning Production
• On a dual version of the one-dimensional bin packing problem
• Finite Fano Planes
• A Linear Programming Approach to the Cutting-Stock Problem
• Probabilistic analysis of algorithms for dual bin packing problems
• Packing Problems and Hypergraph Theory: A Survey
• Case Studies from Industry: Skiving Addition to the Cutting Stock Problem in the Paper Industry
• LP-Based Relaxations of the Skiving Stock Problem—Improved Upper Bounds for the Gap
• On the Solution of Generalized Spectrum Allocation Problems
• The fractional matching numbers of graphs
• The skiving stock problem as a counterpart of the cutting stock problem
• Projective Planes
• Combinatorial optimization. Theory and algorithms.
• A heuristic for the skiving and cutting stock problem in paper and plastic film industries

This page was built for publication: The skiving stock problem and its relation to hypergraph matchings