Optimization Online


Improved Flow-based Formulations for the Skiving Stock Problem

John Martinovic(john.martinovic***at***tu-dresden.de)
Maxence Delorme(maxence.delorme***at***ed.ac.uk)
Manuel Iori(manuel.iori***at***unimore.it)
Guntram Scheithauer(guntram.scheithauer***at***tu-dresden.de)
Nico Strasdat(nico.strasdat***at***tu-dresden.de)

Abstract: Thanks to the rapidly advancing development of (commercial) MILP software and hardware components, pseudo-polynomial formulations have been established as a powerful tool for solving cutting and packing problems in recent years. In this paper, we focus on the one-dimensional skiving stock problem (SSP), where a given inventory of small items has to be recomposed to obtain a maximal number of larger objects, each satisfying a minimum threshold length. In the literature, different modeling approaches for the SSP have been proposed, and the standard flow-based formulation has turned out to lead to the best trade-off between efficiency and solution time. However, especially for instances of practically meaningful sizes, the resulting models involve very large numbers of variables and constraints, so that appropriate reduction techniques are required to decrease the numerical efforts. For that reason, this paper introduces two improved flow-based formulations for the skiving stock problem that are able to cope with much larger problem sizes. By means of extensive experiments, these new models are shown to possess significantly fewer variables as well as an average better computational performance compared to the standard arcflow formulation.

Keywords: Cutting and Packing, Skiving Stock Problem, Arcflow Model, ILP

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Combinatorial Optimization

Category 3: Applications -- OR and Management Sciences

Citation: Preprint MATH-NM-01-2019, Technische Universitšt Dresden, January 2019

Download: [PDF]

Entry Submitted: 02/12/2019
Entry Accepted: 02/12/2019
Entry Last Modified: 02/12/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society