A heuristic for the minimum score separation problem, a combinatorial problem associated with the cutting stock problem

Kai Helge Becker, Gautam Appa

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

The Minimum Score Separation Problem (MSSP) is a combinatorial problem that was introduced in JORS 55 as an open problem in the paper industry arising in conjunction with the cutting stock problem. During the process of producing boxes, flat papers are prepared for folding by being scored with knives. The problem is to determine whether and how a given production pattern of boxes can be arranged such that a certain minimum distance between the knives can be kept. Introducing the concept of matching-based alternating Hamiltonian paths, this paper models the MSSP as the problem of finding an alternating Hamiltonian path on a graph that is the union of a matching and a type of graph known as a ‘threshold graph’. On this basis, we find a heuristic that can quickly recognize a large percentage of feasible and infeasible instances of the MSSP. Detailed computational experiments demonstrate the efficiency of our approach.
LanguageEnglish
Pages1297 - 1311
JournalJournal of the Operational Research Society
Volume66
Issue number8
Early online date29 Oct 2014
DOIs
Publication statusPublished - 31 Aug 2015

Fingerprint

Hamiltonians
Cutting stock problem
Heuristics
Graph
Industry
Experiments
Minimum distance
Experiment
Paper industry

Keywords

  • minimum score separation problem
  • paper industry
  • production pattern
  • alternating Hamiltonian paths
  • threshold graph
  • cutting stock problem
  • bin packing
  • heuristics
  • networks and graphs
  • Travelling Salesman Problem

Cite this

@article{136c887b2dd84985a26626407c9f28d9,
title = "A heuristic for the minimum score separation problem, a combinatorial problem associated with the cutting stock problem",
abstract = "The Minimum Score Separation Problem (MSSP) is a combinatorial problem that was introduced in JORS 55 as an open problem in the paper industry arising in conjunction with the cutting stock problem. During the process of producing boxes, flat papers are prepared for folding by being scored with knives. The problem is to determine whether and how a given production pattern of boxes can be arranged such that a certain minimum distance between the knives can be kept. Introducing the concept of matching-based alternating Hamiltonian paths, this paper models the MSSP as the problem of finding an alternating Hamiltonian path on a graph that is the union of a matching and a type of graph known as a ‘threshold graph’. On this basis, we find a heuristic that can quickly recognize a large percentage of feasible and infeasible instances of the MSSP. Detailed computational experiments demonstrate the efficiency of our approach.",
keywords = "minimum score separation problem, paper industry, production pattern, alternating Hamiltonian paths, threshold graph, cutting stock problem, bin packing, heuristics, networks and graphs, Travelling Salesman Problem",
author = "Becker, {Kai Helge} and Gautam Appa",
year = "2015",
month = "8",
day = "31",
doi = "10.1057/jors.2014.87",
language = "English",
volume = "66",
pages = "1297 -- 1311",
journal = "Journal of Operational Research Society",
issn = "0160-5682",
number = "8",

}

A heuristic for the minimum score separation problem, a combinatorial problem associated with the cutting stock problem. / Becker, Kai Helge; Appa, Gautam.

In: Journal of the Operational Research Society, Vol. 66, No. 8, 31.08.2015, p. 1297 - 1311 .

Research output: Contribution to journalArticle

TY - JOUR

T1 - A heuristic for the minimum score separation problem, a combinatorial problem associated with the cutting stock problem

AU - Becker, Kai Helge

AU - Appa, Gautam

PY - 2015/8/31

Y1 - 2015/8/31

N2 - The Minimum Score Separation Problem (MSSP) is a combinatorial problem that was introduced in JORS 55 as an open problem in the paper industry arising in conjunction with the cutting stock problem. During the process of producing boxes, flat papers are prepared for folding by being scored with knives. The problem is to determine whether and how a given production pattern of boxes can be arranged such that a certain minimum distance between the knives can be kept. Introducing the concept of matching-based alternating Hamiltonian paths, this paper models the MSSP as the problem of finding an alternating Hamiltonian path on a graph that is the union of a matching and a type of graph known as a ‘threshold graph’. On this basis, we find a heuristic that can quickly recognize a large percentage of feasible and infeasible instances of the MSSP. Detailed computational experiments demonstrate the efficiency of our approach.

AB - The Minimum Score Separation Problem (MSSP) is a combinatorial problem that was introduced in JORS 55 as an open problem in the paper industry arising in conjunction with the cutting stock problem. During the process of producing boxes, flat papers are prepared for folding by being scored with knives. The problem is to determine whether and how a given production pattern of boxes can be arranged such that a certain minimum distance between the knives can be kept. Introducing the concept of matching-based alternating Hamiltonian paths, this paper models the MSSP as the problem of finding an alternating Hamiltonian path on a graph that is the union of a matching and a type of graph known as a ‘threshold graph’. On this basis, we find a heuristic that can quickly recognize a large percentage of feasible and infeasible instances of the MSSP. Detailed computational experiments demonstrate the efficiency of our approach.

KW - minimum score separation problem

KW - paper industry

KW - production pattern

KW - alternating Hamiltonian paths

KW - threshold graph

KW - cutting stock problem

KW - bin packing

KW - heuristics

KW - networks and graphs

KW - Travelling Salesman Problem

U2 - 10.1057/jors.2014.87

DO - 10.1057/jors.2014.87

M3 - Article

VL - 66

SP - 1297

EP - 1311

JO - Journal of Operational Research Society

T2 - Journal of Operational Research Society

JF - Journal of Operational Research Society

SN - 0160-5682

IS - 8

ER -