Solving One-Dimensional Cutting Stock Problems with the Deep Reinforcement Learning

There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

Abstract

It is well known that the one-dimensional cutting stock problem (1DCSP) is a combinatorial optimization problem with nondeterministic polynomial (NP-hard) characteristics. Heuristic and genetic algorithms are the two main algorithms used to solve the cutting stock problem (CSP), which has problems of small scale and low-efficiency solutions. To better improve the stability and versatility of the solution, a mathematical model is established, with the optimization objective of the minimum raw material consumption and the maximum remaining material length. Meanwhile, a novel algorithm based on deep reinforcement learning (DRL) is proposed in this paper. The algorithm consists of two modules, each designed for different functions. Firstly, the pointer network with encoder and decoder structure is used as the policy network to utilize the underlying mode shared by the 1DCSP. Secondly, the model-free reinforcement learning algorithm is used to train network parameters and optimize the cutting sequence. The experimental data show that the one-dimensional cutting stock algorithm model based on deep reinforcement learning (DRL-CSP) can obtain the approximate satisfactory solution on 82 instances of 3 data sets in a very short time, and shows good generalization performance and practical application potential.

Related collections

Most cited references 48

Record: found
Abstract: found
Article: not found

Long Short-Term Memory

Jürgen Schmidhuber, Jürgen Schmidhuber (2003)

Learning to store information over extended time intervals by recurrent backpropagation takes a very long time, mostly because of insufficient, decaying error backflow. We briefly review Hochreiter's (1991) analysis of this problem, then address it by introducing a novel, efficient, gradient-based method called long short-term memory (LSTM). Truncating the gradient where this does not do harm, LSTM can learn to bridge minimal time lags in excess of 1000 discrete-time steps by enforcing constant error flow through constant error carousels within special units. Multiplicative gate units learn to open and close access to the constant error flow. LSTM is local in space and time; its computational complexity per time step and weight is O(1). Our experiments with artificial data involve local, distributed, real-valued, and noisy pattern representations. In comparisons with real-time recurrent learning, back propagation through time, recurrent cascade correlation, Elman nets, and neural sequence chunking, LSTM leads to many more successful runs, and learns much faster. LSTM also solves complex, artificial long-time-lag tasks that have never been solved by previous recurrent network algorithms.