The skiving stock problem and its relation to hypergraph matchings

DOI10.1016/J.DISOPT.2018.03.001MaRDI QIDQ1662646zbMATH OpenOpenAlexWikidataFDO

Authors J. 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

cutting and packinghypergraphskiving stock problem(fractional) matchingadditive integrality gap

Mathematics Subject Classification ID

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

Recommendations

• The proper relaxation and the proper gap of the skiving stock problem
• The skiving stock problem as a counterpart of the cutting stock problem
• An upper bound of \(\Delta(E) < 3 \slash 2\) for skiving stock instances of the divisible case
• LP-Based Relaxations of the Skiving Stock Problem—Improved Upper Bounds for the Gap
• Combinatorial investigations on the maximum gap for skiving stock instances of the divisible case

Cites work

• Q3993087 scientific article; zbMATH DE number 43754 (Why is no real title available?)
• Q4040221 scientific article; zbMATH DE number 193411 (Why is no real title available?)
• Q4083489 scientific article; zbMATH DE number 3503319 (Why is no real title available?)
• Q4099676 scientific article; zbMATH DE number 3522018 (Why is no real title available?)
• Q4145427 scientific article; zbMATH DE number 3573595 (Why is no real title available?)
• Q4165164 scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• Q5589781 scientific article; zbMATH DE number 3308885 (Why is no real title available?)
• Q5636932 scientific article; zbMATH DE number 3363617 (Why is no real title available?)
• Q5683869 scientific article; zbMATH DE number 3421490 (Why is no real title available?)
• A Linear Programming Approach to the Cutting-Stock Problem A Linear Programming Approach to the Cutting-Stock Problem
• A comparative study of the arcflow model and the one-cut model for one-dimensional cutting stock problems A comparative study of the arcflow model and the one-cut model for one-dimensional cutting stock problems
• A dual bin-packing approach to scheduling surgical cases at a publicly-funded hospital A dual bin-packing approach to scheduling surgical cases at a publicly-funded hospital
• A heuristic for the skiving and cutting stock problem in paper and plastic film industries A heuristic for the skiving and cutting stock problem in paper and plastic film industries
• Algorithmic graph theory and perfect graphs Algorithmic graph theory and perfect graphs
• An exact algorithm for the dual bin packing problem An exact algorithm for the dual bin packing problem
• An improved typology of cutting and packing problems An improved typology of cutting and packing problems
• Bin packing and cutting stock problems: mathematical models and exact algorithms Bin packing and cutting stock problems: mathematical models and exact algorithms
• Bin packing and related problems: general arc-flow formulation with graph compression Bin packing and related problems: general arc-flow formulation with graph compression
• Branch-and-price algorithms for the dual bin packing and maximum cardinality bin packing problem 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 Case Studies from Industry: Skiving Addition to the Cutting Stock Problem in the Paper Industry
• Combinatorial optimization. Theory and algorithms. Combinatorial optimization. Theory and algorithms.
• Finite Fano Planes Finite Fano Planes
• Graph theory Graph theory
• Integer linear programming models for the skiving stock problem Integer linear programming models for the skiving stock problem
• Integer rounding and modified integer rounding for the skiving stock problem Integer rounding and modified integer rounding for the skiving stock problem
• Introduction to cutting and packing optimization. Problems, modeling approaches, solution methods Introduction to cutting and packing optimization. Problems, modeling approaches, solution methods
• LP models for bin packing and cutting stock problems LP models for bin packing and cutting stock problems
• LP-Based Relaxations of the Skiving Stock Problem—Improved Upper Bounds for the Gap LP-Based Relaxations of the Skiving Stock Problem—Improved Upper Bounds for the Gap
• Matching theory Matching theory
• Matchings and covers in hypergraphs Matchings and covers in hypergraphs
• Mathematical methods of organizing and planning production. English translation by Robert W. Campbell and W. H. Marlow Mathematical methods of organizing and planning production. English translation by Robert W. Campbell and W. H. Marlow
• Maximum degree and fractional matchings in uniform hypergraphs Maximum degree and fractional matchings in uniform hypergraphs
• Minimal proper non-IRUP instances of the one-dimensional cutting stock problem Minimal proper non-IRUP instances of the one-dimensional cutting stock problem
• On a dual version of the one-dimensional bin packing problem On a dual version of the one-dimensional bin packing problem
• On the fractional matching polytope of a hypergraph On the fractional matching polytope of a hypergraph
• On the solution of generalized spectrum allocation problems On the solution of generalized spectrum allocation problems
• On-line and off-line approximation algorithms for vector covering problems On-line and off-line approximation algorithms for vector covering problems
• Packing Problems and Hypergraph Theory: A Survey Packing Problems and Hypergraph Theory: A Survey
• Probabilistic analysis of algorithms for dual bin packing problems Probabilistic analysis of algorithms for dual bin packing problems
• Probabilistic bounds for dual bin-packing Probabilistic bounds for dual bin-packing
• Projective Planes Projective Planes
• The difference and ratio of the fractional matching number and the matching number of graphs The difference and ratio of the fractional matching number and the matching number of graphs
• The fractional matching numbers of graphs The fractional matching numbers of graphs
• The proper relaxation and the proper gap of the skiving 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 The skiving stock problem as a counterpart of the cutting stock problem
• Tighter relaxations for the cutting stock problem Tighter relaxations for the cutting stock problem

Cited in

(3)

• 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
• Large proper gaps in bin packing and dual bin packing problems

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

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