The proper relaxation and the proper gap of the skiving stock problem (Q510433)

The paper is devoted to the one-dimensional skiving stock problem presented by the standard pattern-based integer linear programming model. For the continuous proper relaxation of the standard pattern-based integer linear programming model the authors present the arc-flow model formulated as linear program with a pseudo-polynomial number of variables and constraints and prove that both models have the same optimal objective values. The authors investigate the gaps between the optimal objective values of the standard pattern-based integer linear programming model and its continuous relaxations. They introduce the concepts of the proper integer round-down property and the proper modified integer round-down property and prove that the skiving stock problem does not comprise instances with the proper integer round-down property. In the paper the method for constructing an infinite number of instances with non-proper integer round-down property is developed and the question about the biggest possible proper gap value is investigated. The authors apply the exhaustive enumeration approach from \textit{V. M. Kartak} et al. [Discrete Appl. Math. 187, 120--129 (2015; Zbl 1327.90118)] to the skiving stock problem and calculate gaps for a number of instances, among them an instance with the unit proper gap, an instance with the largest known value of the gap, and an instance with the largest known value of the proper gap.