{'fraction_non_alphanumeric': 0.027790048592426005, 'fraction_numerical': 0.011585880085137144, 'mean_word_length': 4.458461201227532, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Deep Learning Assisted Heuristic Tree Search for the Container Pre-marshalling Problem

One of the key challenges for operations researchers solving real-world problems is designing and implementing high-quality heuristics to guide their search procedures. In the past, machine learning techniques have failed to play a major role in operations research approaches, especially in terms of guiding branching and pruning decisions. We integrate deep neural networks into a heuristic tree search procedure to decide which branch to choose next and to estimate a bound for pruning the search tree of an optimization problem. We call our approach Deep Learning assisted heuristic Tree Search (DLTS) and apply it to a well-known problem from the container terminals literature, the container pre-marshalling problem (CPMP). Our approach is able to learn heuristics customized to the CPMP solely through analyzing the solutions to CPMP instances, and applies this knowledge within a heuristic tree search to produce the highest quality heuristic solutions to the CPMP to date.


Introduction
Tree search algorithms, such as branch and bound, have become the standard procedure for solving difficult operations research problems across a wide number of applications. Since tree search algorithms are generally applied to NP-complete (or harder) problems, heuristic tree search (HTS) is often used to provide good solutions to problems in little time, albeit with weak or no guarantees regarding the solution quality. The effectiveness of heuristic tree search (unsurprisingly) lies in the nature of the heuristics that domain experts develop.
The three main heuristics in any tree search algorithm (heuristic or otherwise) are the variable heuristic, which selects a variable to branch on, the value heuristic, which selects the branches of the variable to explore first, and the bound heuristic, which computes an estimated cost for completing a partial solution. Branching heuristics in particular have been given significant attention, especially for general-purpose mixed-integer programming approaches (e.g., Linderoth and Savelsbergh (1999), Achterberg et al. (2005)). In the case of heuristic tree search, problem specific approaches are generally applied, for example in the case of the container pre-marshalling problem (Bortfeldt and Forster 2012), or crew scheduling in Sellmann et al. (2002).
In this paper, we replace the branch, value and bound heuristics of an HTS with deep (artificial) neural networks (DNNs), creating a generalized form of an HTS that learns how to solve optimization problems all on its own. We call our novel approach Deep Learning Tree Search (DLTS). We train the DNNs offline and insert them into a tree search in place of the heuristics or lower bounds normally designed by domain experts. Our approach is inspired by the algorithm AlphaGo (Silver et al. 2016) for playing the game Go, but is adapted to perform heuristic optimization for industrial problems. This paper provides the first tree search algorithm for optimization problems with branching and bounding decisions made entirely through a learned model.
We apply DLTS to a well-known NP-complete problem from the container terminals literature, the container pre-marshalling problem (CPMP). The CPMP involves shuffling containers in a set of stacks with a minimal number of container movements such that the containers are organized for fast retrieval. The CPMP has a simple problem representation that is extraordinarily well-suited for DLTS. We show experimentally how DLTS is able to significantly outperform the state-of-the-art heuristic approach for the CPMP, finding gaps to optimality between 0% and 2% on real-world sized instances compared to gaps of 6 -15% for the state-of-the-art metaheuristic.
DLTS is able to achieve a high level of performance with very little problem specific knowledge in the search; problem specific information is only provided as input to the DNN. Thus, once an exact approach is designed for a problem, DLTS can be used to find high quality heuristic solutions in a fraction of the run time of the exact solution.
DLTS is a particularly flexible algorithm, and it contains a number of configurable components. Search strategies and decisions as to how to use information from the DNNs can be configured for specific datasets offline using an algorithm configurator (Adenso-Daz and Laguna 2006), such as GGA (Ansótegui et al. 2009) or GGA++ (Ansotegui et al. 2015), to increase the quality of the solutions found. This helps to ensure good performance of DLTS when deployed in practice.
This paper is organized as follows. First, we discuss related work in the area of combining data mining and optimization techniques in Section 2. We then introduce the DLTS algorithm along with several search strategies and parameterizations in Section 3, followed by a description of the CPMP in Section 4 and a discussion of the application of DLTS to the CPMP. In Section 5 we test our approach experimentally on a large dataset of CPMP instances. We conclude and discuss future work in Section 6.

Related work
We provide an overview of the literature regarding learning and optimization, splitting our discussion into four parts. First, we describe relevant selection procedures for algorithms and heuristics, followed by a discussion of learning techniques for branching and node selection in a mixed-integer program (MIP). We then make note of relevant combinations of learning techniques in heuristics, followed by a look at the integration of deep learning into search methods.

Heuristic and algorithm selection
Learning mechanisms have been successfully applied within search procedures to select which heuristics to apply online. The DASH method, introduced by Liberto et al. (2016), learns a model offline for branch heuristic selection of a MIP. In contrast to DASH, DLTS learns the branching heuristic itself, rather than selecting among different options provided by domain experts.
Hyper-heuristics involve the selection of heuristics within a generic metaheuristic procedure. Burke et al. (2013) provide an overview of the field. While most techniques involve static or "reactive" strategies (i.e., parameter adjustment based on the search trajectory). Some, such as Mısır et al. (2012), involve a learning component in which ratings for heuristics are dynamically updated according to the performance of the heuristics.
Algorithm selection techniques learn a model offline to attempt to choose the best algorithm out of a portfolio of options offline for a given problem instance, and have been applied to a number of problems. See, e.g., Bischl et al. (2016) for an overview. In contrast to these approaches, we seek to learn a heuristic directly for a problem in DLTS. Lodi and Zarpellon (2017), together with comments from Dilkina et al. (2017), provide an overview of methods applying learning to the problems of variable and node selection in MIP. Several of the articles identified by Lodi and Zarpellon (2017) are of particular relevance to our work on DLTS so we describe them here. He et al. (2014) propose a method to learn a node ordering over open nodes in a branch-andbound search. The features used for learning are similar to the DASH approach, but instead of guessing a branching heuristic at a node, the method identifies the next node to explore during search. A key difference to DLTS is that we use standard search strategies to order nodes and learn the order in which the branches of nodes should be explored. An advantage of DLTS is that we do not have to form a ranking over potentially hundreds or thousands of nodes. Instead, we only form a ranking over the branches of a node, but nonetheless have a strong heuristic guiding our search.

Learning in exact solvers
Several methods have been developed to provide a surrogate for strong branching scores, which are a way of ranking the possible branches during a MIP branch-and-bound search. These approaches approximate the scores faster than the true values can be calculated. Khalil et al. (2016) learn a model for predicting the rank of the scores of strong branching. They use features derived from the search trajectory and show speed ups using their method versus CPLEX without certain heuristics. Alvarez et al. (2017) also approximates strong branching scores. In contrast, DLTS directly predicts which branch to take, cutting out the intermediary step of trying to predict branching scores.
A logistic regression is used in Khalil et al. (2017) to predict when to apply a primal heuristic when solving a MIP. The authors use similar features to Khalil et al. (2016) and are able to improve the performance of a MIP solver.
Some MIP models can be decomposed to solve them more quickly. When one or more decompositions are available for a model, Kruber et al. (2017) learns whether or not to use one of the decompositions. A strategy is proposed in Fischetti and Monaci (2014) to cope with the erraticism in MIPs that arises when the columns and rows of the MIP A matrix are permuted. This changes how an instance looks to a solver, but does not actually change the instance itself. The proposed solution runs several transposed versions of a model sequentially and uses a set of criteria to determine which version is the most likely to be solved quickly.
The works of Bonfietti et al. (2015) and Lombardi et al. (2017) directly embed machine learning models into MIPs, other exact solution procedures, as well as heuristics. A key difference is that the embedding is used to learn about the nature of the problem itself, rather than being used for search guidance, as models are in DLTS.

Learning (in) heuristics
To the best of our knowledge, the first proposed use of learning methods within a heuristic search procedure comes from Glover's target analysis technique (Glover andGreenberg 1989, Glover 1986). The idea is to rate each branch based on a weighted sum of criteria and choose the branch with the highest rating. The weights can be adjusted offline using a learning procedure. A recent realization of this technique is hyper configurable reactive search, introduced in Ansótegui et al. (2017), in which the parameters of a metaheuristic are determined online with a linear regression. The weights of the regression are tuned offline with the GGA++ algorithm configurator (Ansotegui et al. 2015).
The Searn method (Daumé et al. 2009) inserts a learning algorithm into a greedy search process. It is assumed that a solution to a problem can be decomposed into a number of components, and a policy is learned to predict the components. A key limitation of this approach is that there is no mechanism for correcting "mistakes" (deviations from the optimal solution sequence). In the worst case, this can result in infeasible solutions, and even when feasible solutions are found, these might not be very good. Dai et al. (2017) present a method for learning a heuristic to solve NP-hard graph problems. The method works by updating a partial solution to a problem based on a deep learning model. In contrast to our approach, the authors do not utilize a tree search or a value network, meaning there is no backtracking, similar to the work of Daumé et al. (2009).

Deep learning and search
Our work is inspired by the approach of Silver et al. (2016), in which two DNNs are used to guide a Monte Carlo tree search to play the game Go. Segler et al. (2017) use a similar framework to Silver et al. (2016) to plan the synthesis of molecules. A DNN is used to assist a depth first search to write programs in Balog et al. (2016). Here, the DNN can optionally influence the search path by ordering search nodes based on their likelihood of success. A monte-carlo tree search with a supporting DNN is also used in Guo et al. (2014) to learn to play Atari games. Although similar to these approaches, DLTS additionally provides a highly configurable interface to its search and a DNN for bounding.

Deep Learning assisted heuristic Tree Search (DLTS)
DLTS consists of a heuristic (i.e., incomplete) tree search in which decisions about which branches to explore and how to bound nodes are made by a DNN. In HTS, the solution to a problem is built using a search through the space of partial solutions to the problem. DLTS can use a variety of search strategies, and we present several versions in this section, including a depth first search (DFS), a limited discrepancy search (LDS), and a weighted beam search (WBS). We note that all of our search algorithms are heuristics, even though in the general case DFS and LDS can find optimal solutions. This is because we use aggressive pruning of the search tree combined with a type of search beam in all search strategies. In this section, we first describe how DNNs work and how we integrate one into a tree search. We then provide pseudocode for DLTS using different search strategies.

DNNs
DNNs are a learning technique based on the idea of a neural network that accepts some input, processes it within the network, and provides output. The DNN consists of perceptrons (nodes) that accept one or more weighted inputs from other nodes, aggregate those inputs, and apply an activation function to the inputs. The value from this function is then sent out of the node to subsequently connected nodes. The DNN "learns" by adjusting the weights on the arcs of the network. In this work, we use DNNs purely in a supervised fashion. For more detail regarding DNNs we refer to the book by Goodfellow et al. (2016).
Consider a standard supervised learning setting in which the goal is to learn a function f : X → Y , where X is the input space and Y is the output space. DNNs can be used for both classification (the space Y consists of a set of discrete values) as well as regression (Y can take any value in R), and we use both types of DNNs in this work. The function f is trained offline and then applied during the tree search. We use a policy network to make predictions about which branch will be best (classification DNN) and a value network to predict the cost of completing a solution for a node in the search tree (regression DNN).
There are three main types of layers for a DNN: the input layer that accepts X and transmits it into the network; an output layer that consolidates the information of the network into a set of outputs; and hidden layers, which accept and re-transmit data through the network. The layers are organized sequentially, starting with an input layer, followed by one or more hidden layers, ending with the output layer. Figure 1 shows an overview of the DNN within DLTS. The problem is first converted into a form that can be accepted by the DNN and passed to the input layer. The connections within the network can be modified by the network designer, but usually the networks are highly connected, with each node being connected to a large number (or all) of the nodes in the following layer. For DLTS, the output layer represents a branching decision. We thus use a softmax activation function in the output layer to transform all of the outputs into values in [0, 1] such that they sum to 1. This allows DLTS to use the output as a probability distribution over the available branches.

Training
Training for the DLTS policy and value networks works as follows. A set of representative instances for a problem are split into a training and a validation set. The instances are solved using an exact procedure, although a heuristic could be used if no exact algorithm is available. A DNN training set is then created by examining each optimal (or near optimal) solution and extracting DNN training examples.
The solution to a problem can be seen as a sequence of constructive steps that create a solution. We note that for some OR problems this is easier to model than for others, and DLTS is geared towards those in which this way of viewing the problem is intuitive. Each DNN training example consists of the partial solution as input to the DNN, along with any other problem-relevant information. The DNN output is the next step in the construction of a solution.
Formally, consider a solution that consists of a sequence of n components c 1 , . . . , c n . The components are sequentially added to an empty solution through a constructive process to create a valid solution. The contribution to the objective function of all components must have the same sign (i.e., all positive or all negative). Each partial solution j, consisting of components c 1 , . . . , c j , is associated with a problem state s j . The state s 0 is empty and represents a starting solution with no components. For the policy network, defined over j ≥ 1, a training example is defined as X j := s j−1 and Y j := ∆ j , where ∆ j is a 0-1 vector with an entry for every component that can be appended to state s j−1 (this is known as a one-hot encoding). The vector takes the value 1 for the entry associated with component c j . Thus, the length of ∆ j is the number of candidate components for c j .
For the value network, there is only a single output representing cost of completing a partial solution. Given the objective value f * associated with a solution to an instance and f j , which is the objective value of a partial solution j with components c 1 , . . . , c j , we construct DNN training examples X j := s j and Y j := f * − f j .
During training, each DNN is presented with a small subsample of m problem states s 1 , . . . , s m that are then propagated through the network to generate the associated output f (s 1 ), . . . , f (s m ). These values are then compared to the expected output (using a loss function) to calculate the error of the network. In the next step, the weights of the network are adjusted according to their influence on the error to reduce the error in the next iteration (gradient descent). Once all problem states of the training set X have been processed, the first epoch of the training is completed. The training can be continued for several epochs until no further improvement of the error is observed. We again refer to the book by Goodfellow et al. (2016) for more details regarding the learning process.

Depth first search
Algorithm 1 shows the depth-first DLTS approach. The algorithm is called with the initial configuration of the problem, stored in a node s, that has several properties. These are whether the instance is solved, Complete(s), the current (incomplete) objective value of the node, Cost(s), the depth of the node in the tree, Depth(s), and the successor node (children) of the current node, Successors(s). Furthermore, the value network query frequency k, the lower bound uncertainty adjustment d, the branch pruning adjustment parameter p, the maximum search depth seen so far md , and the best objective value seen so far ub (upper bound) are passed into the algorithm.
The function starts by checking whether the current node is feasible and if the cost is better than the current best known cost. If this is the case, the upper bound is updated and the node is returned. Optionally, the depth of the node with the best solution found so far can be updated. This is useful for problems where the cost and the depth are closely linked, such as in makespan minimization, but should not be done on problems where this is not the case. On line 7 we compute a heuristic lower bound of the current node, but only at depths mod k, as querying the value network is expensive. We multiply the value network estimate by a factor d, between 0 and 1, to reduce the risk of overestimating the bound. This results in a weakened bound, but less likelihood of cutting off the optimal solution. Should the cost of the current node or the heuristic lower bound exceed the current upper bound, we return the empty set and define Cost(∅) := ∞.
The policy network is queried on line 9 for each successor node. DNN-Policy forms a probability distribution over all valid moves from node s to another node s . We can interpret this probability value as the confidence the network has that a particular successor node is the optimal successor for s. We exclude any successors that are below a minimum probability threshold, on line 10, which can be computed through one of several functions that we describe in Section 3.5. The list of successors is sorted by the prediction from the DNN, and nodes with a higher value are explored first.

Limited discrepancy search
In our DFS, we order the search such that we always search nodes in the order recommended by the policy network. As with any heuristic, the policy network will sometimes be wrong. If a branching mistake happens near the root of the search tree, DFS will waste time searching entire sub-optimal subtrees before moving on to more promising areas. Limited discrepancy search (LDS) (Harvey and Algorithm 1 Depth first search based deep learning assisted heuristic tree search. if Cost(s) ≥ ub or hlb ≥ ub or CPU time exceeded then return ∅ 9: Ginsberg 1995) addresses this by changing the search order so that the search proceeds iteratively by the number of discrepancies. A discrepancy is a deviation from the search path recommended by the heuristic. The intuition of the search strategy is that the branching direction will be correct most of the time. Thus, we ought to first examine solutions using only the advice of the heuristic, followed by solutions that ignore the advice of the heuristic a single time, followed by solutions ignoring the advice two times, and so on. Figure 2 shows the search order for DFS and LDS in a typical tree search. Assume the branches in the figure are ordered from left to right according to the advice of the branching heuristic, i.e., it suggests going left first. DFS often examines nodes that have, according to the branching heuristic, a low probability of success before nodes with a high probability. LDS, however, searches in order of the likelihood of finding an optimal solution, according to the heuristic.
LDS is traditionally presented on binary search problems, i.e., each non-leaf node has exactly two child nodes. However, the branching factor in DLTS is not restricted to two. We adopt the generalized LDS scheme of Furcy and Koenig (2005), in which child nodes are ordered, and the discrepancy is computed as the number of nodes away from the recommended node. Furcy and Koenig (2005) also use a hash table to prevent cycles, however we do not implement this.
LDS is often implemented in an iterative process, in which a DFS explores all nodes of discrepancy 0, followed by a new DFS exploring nodes with discrepancy 1, then 2, and so on (see Korf (1996)). While the method of Korf (1996) avoids visiting any leaf node more than once, internal tree nodes can be visited multiple times. Querying the policy and value networks in our tree search is computationally expensive, so we do not want to repeat this work. We therefore use a priority queue approach instead of an iterative DFS, as shown in Algorithm 2.
Algorithm 2 Limited discrepancy search based deep learning assisted heuristic tree search. if Cost(s) < Cost(s*) and hlb < Cost(s*) then return s* The algorithm accepts the parameters s, which is the same as in the DFS, δ I , which indicates whether or not to use a binning mechanism for the discrepancy (described later), b, which is the number of bins to use, and z, which is the minimum depth from which to apply the discrepancy search. The algorithm starts by initializing the best known solution to nothing (∅) and creates a priority queue with the root node solution. The algorithm then loops until the queue is empty, popping the node with the lowest discrepancy. We note that if Depth(s) < z, then we set the discrepancy of the node to 0 for the purposes of the queue. This allows the search to open more nodes at the top of the tree before applying LDS. Ties between nodes of equal discrepancy are broken by examining nodes of higher depth first (i.e., those nodes closest to a leaf node) as in Sellmann et al. (2002). If the popped node is the best seen so far, s* is updated. Then, the value network is queried (depending on the value of k) and the child nodes are pruned if it is determined that they would be too expensive. Otherwise, branching is performed, using only those branches allowed by the policy network as in the DFS.
As discussed, LDS was originally designed for trees in which there are only two branches. In the CPMP, and indeed in many optimization problems, the branching factor can be much higher. This could pose an issue for determining the discrepancy of a node, since if the policy DNN assigns a "good" node a low score, the discrepancy of that node will be very high and it might not be explored. We thus introduce a binning mechanism that can be turned on by setting δ I equal to true. When this is the case, we reassign the discrepancies of nodes in Q as follows. We first calculate the size of each bin by dividing the maximum probability output from the policy network by b, the number of bins. That is, each bin represents a probability range [l i , u i ), with l i = u i+1 for i < b (i.e., the bins are sorted with higher probabilities first). For each potential branch of a node, we assign it a discrepancy according to the number of the bin it falls in to.

Weighted beam search
A further alternative to DFS and LDS is weighted beam search (WBS), which is a heuristic based on best first search. In best first search, nodes with the lowest lower bound are explored first and a heuristic version, beam search (Russell and Norvig 2011), has been widely applied in the AI and OR communities. Beam search limits the number of child nodes that are explored at each search node to a constant amount, β. This is the same concept as we use in our DFS and LDS, except we use a reactive width.
For WBS, we compute the bound used for sorting the nodes of the search using a weighted sum of the cost of the node plus the estimated lower bound of the node: f (n) = αg(n) + γh(n). WBS is thus able to place more emphasis on the value network's prediction if desired. This contrasts with DFS and LDS, which use the policy and value networks with relatively equal importance. In WBS, the policy network is only used to determine the beam width.
Since the pseudocode for DLTS-WBS is very similar to DLTS-LDS, we do not provide a separate code listing. The priority queue, Q, in Algorithm 2 is adjusted so that the sorting criterion is the heuristic lower bound as described. Furthermore, instead of only computing the lower bound when Depth(s) mod k = 0, it is computed for every node.

Branch pruning functions
Using the function MP, we artificially limit the branches that are explored in a given node to only those with sufficiently high probability. We define three simple functions, two of which that adjust the width to the depth of the search. The intuition for this is that at the top of the tree picking the wrong branch can be extremely costly, as the optimal solution or near optimal solutions may be removed from the tree. Mistakes further down in the search tree are not as bad, as the policy DNN will likely choose a good search path in a neighboring node. On problems where the cost function is proportional to the tree depth, we make MP reactive and update md whenever a new best solution is found. This adapts the pruning to the depth in which the best solutions are found.
All three functions accept the parameters (p, r, Depth, md ), which are the branch pruning adjustment parameter, the maximum probability assigned to any branch, the current depth of the search, and the maximum possible depth, respectively. Each of the three MP variants returns a value less than or equal to 1, and any branch assigned a probability by the policy DNN less than the value is pruned.
The function MP-Constant is the simplest of all the functions, as it simply returns p scaled to the largest probability r and ignores all other input as follows: The constant version of MP tends to be very expensive since the same number of branches are available at the top of the tree as at the bottom. The function MP-Quadratic aims to decrease the tree width more quickly so all areas of the tree can be searched within the time limit.

Container Pre-Marshalling
The CPMP is a key problem in the housekeeping operations of busy container terminals, and is introduced in Lee and Hsu (2007). It has been the focus of a number of recent works (e.g., Bortfeldt and Forster (2012), Wang et al. (2015), Hottung and Tierney (2016)). The CPMP arises when containers stacked in a terminal need to be re-sorted so that they can be quickly extracted from the stacks. Each container is assigned a group that corresponds to the scheduled exit time of the container from the stacks. If a container with a late exit time is stacked on top of a container with an early exit time, it blocks the removal of that container and must be re-stowed during port operations, wasting valuable time. Only a single crane is available to move one container at a time from the top of one stack to the top of another stack. The idea of pre-marshalling is to re-sort the containers with a minimal number of container movements during off-peak times, so that container retrieval operations run smoothly when the port is busy. The CPMP is NP-hard (Caserta et al. 2011).

Formal problem definition
The CPMP involves a set of C containers arranged into S stacks that have a maximum height T . The parameter g st provides the group value of the container in stack s at tier (height) t.
The objective of the CPMP is to find a minimal length sequence of movements (f, t) in which a container is moved from the top of stack f to the top of stack t, such that all stacks are sorted, i.e., g st ≥ g s,t+1 , ∀1 ≤ s ≤ S, 1 ≤ t < T . Figure 3 shows a CPMP problem instance and its optimal solution. Starting on the left, there are three stacks with a total of six containers, each one labeled with its group (note that multiple containers can have the same group value, but for ease of presentation, we assign a unique group to each container). The containers in gray are in blocking positions and must be moved so that they are not blocking any containers beneath them. Since there are three blocking containers, at least three movements are necessary to sort the stacks. Stronger lower bounds are available (e.g., in Tanaka and Tierney (2018)), but they are not relevant to this work, as we use a DNN to heuristically determine bounds.

Suitability for DLTS
The CPMP is particularly well-suited for DLTS for several reasons. First, construction-based heuristic approaches, such as the corridor method from Caserta and Voß (2009) or the biased-random key genetic algorithm approach in Hottung and Tierney (2016), are well-suited to solving the CPMP since a solution consists of a sequence of container movements. Second, heuristic tree search has been successfully applied to the CPMP by Bortfeldt and Forster (2012) (and which is outperformed by newer approaches), providing a baseline for comparison for DLTS. Third, a CPMP instance can be fully described with very little data, despite the problem complexity, meaning an entire instance can be inserted into a DNN without needing a very large DNN or specialized hardware. Finally, from a practical standpoint, CPMP problems in the real world do not vary in size, as the cranes used for pre-marshalling in a port cannot be easily exchanged for larger/smaller ones. Thus, configuring DLTS for a specific size of CPMP would not pose any issues for a real-world implementation.

DNN Model
The single domain specific component of DLTS is the insertion of the problem into the neural network. Figure 4 shows the structure of the policy DNN for the CPMP. The network is dependent on the size of the problem, although instances with less stacks and tiers can also be solved. The policy DNN's input layer consists of a single node for each stack/tier position in the instance. Directly following the input layer are locally connected layers (as opposed to fully connected layers) that bind each stack together. This provides the network with some knowledge about the stack structure of the CPMP. We include several locally connected layers, followed by fully connected layers that then connect to the output layer.
We use a technique called weight sharing directly following the input layer in which each tier is assigned a single weight, w i , as opposed to assigning each container a weight. As can be seen in the figure, for example in the topmost tier, the weight w 3 is applied to each stack. The group value is multiplied by this weight, and then inserted into the next layer of the network. The nodes of subsequent layers in the network process their inputs with an activation function that then sends an output into the next layer. Weight sharing is particularly useful for the CPMP because the stacks themselves do not really have any meaning -the stacks can be arbitrarily sorted and the problem stays the same. However, the tier of a container is very important, as containers that are higher up could be blocking a container below. In contrast to the first layers of the network, the last layers are fully-connected. All nodes of the hidden layers use the rectifier activation function, which simply returns the value 0 when the node input is less than or equal to 0, otherwise it returns the input value.
The output layer of the policy DNN consists of a node for each possible movement of a container from one stack to another stack. The DNN outputs a probability distribution over the outputs o s,s , with higher values corresponding to moves the DNN "thinks" are likely to lead to an optimal solution. These output values also provide a level of confidence, with higher values for a particular move meaning that the network is more certain about it being good.
The policy DNN can potentially select a move that is not feasible, for example moving a container to a stack that is already full. We filter such moves from the output of the DNN, leaving only feasible moves. Furthermore, we do not allow moves that undo the directly preceding move. The work of Tierney et al. (2016) and Tanaka and Tierney (2018) point out that the solution speed of the CPMP can be greatly increased when avoiding symmetries and implementing specialized branching rules. We purposefully do not model these in our approach and allow the DNN to learn these for itself.
The value DNN differs from the policy DNN only in terms of its output layer. There is only a single output node. This node provides the estimated lower bound for an instance. For each container movement i, we create a training example where X i := B i and Y i := ∆ i , where ∆ i is a vector of S(S − 1) entries with This provides both positive and negative information about what branches lead to an optimal solution to the DNN. We note, however, that other training schemes could be possible, such as when multiple optimal solutions are available for a particular instance.

Value network training
For training the value network, we use similar input as for the policy network. The key difference is that instead of an output for each branch, the value network has a single output that provides the lower bound on a bay. We thus create training examples with X i := B i and Y i := n − i + 1.

Computational Results
We now evaluate DLTS on the CPMP. In our experiments, we attempt to answer the following questions: To ensure a fair comparison of DNN structures and search strategies in research questions one and two, we use algorithm configuration either through a grid search or the configurator GGA (Ansótegui et al. 2009) to find high quality parameters for DLTS. With respect to research question three, we experiment on a variety of CPMP instances that we describe below. While we mainly use instances we generate ourselves, we also test DLTS on instances from the literature to show that the high quality performance of DLTS is not due to carefully selected instances. We also compare DLTS to the biased random-key genetic algorithm proposed in Hottung and Tierney (2016) and the targetguided heuristic from Wang et al. (2015). To our surprise, DLTS outperforms both of these heuristics despite not having any knowledge about solving the CPMP from the heuristics literature. In other words, DLTS outperforms over a decade of metaheuristics research from experts in the field through its own learning about the CPMP.

Experimental setup
Training DLTS on a particular problem requires a large number of instances. In total, we generate more than 900 thousand instance of various sizes using the generator from Tierney and Malitsky (2015) to train several DLTS instantiations. To ensure the applicability of DLTS to different types of CPMP problems, we create three different classes of instances: G1, G2 and G3. In G1, the group of every container is unique, as in the instances from Caserta and Voß (2009). In G2, every group is assigned to two containers. Logically, in G3, each group is assigned to three containers. We then make instances in each class in three different sizes defined as SxT (stacks x tiers): 5x7, 7x7 and 10x7. We leave the two top tiers free so there is room to move containers around during pre-marshalling. We chose these sizes based on the sizes of real-world pre-marshalling problems in container terminals, which generally are no more than 10 stacks wide due to the maximum width of the cranes that move the containers, and are around 7 containers high due to safety restrictions.
We focus the training of DLTS on two versions of the above instance classes: G1 and G123, which is a combination of G1, G2 and G3. For each size (5x7, 7x7 and 10x7) we generate 150,000 instances of G1 and 150,000 instances of G123, consisting of 50,000 instances each of G1, G2, and G3. Of these instances, 120,000 are used for training the networks and 30,000 for validation. With G1, we test how well DLTS can adapt to a single type of instance. In testing G123, we determine whether or not DLTS can learn how to solve problems with a mixture of different instance types.
The policy and value networks are trained on reference solutions generated by the TT algorithm (Tanaka and Tierney 2018). We attempt to solve all instances using TT with a time limit of 10, 20 and 30 minutes for 5x7, 7x7, and 10x7, respectively. If TT is unable to find an optimal solution within the time limit, the best solution found is used instead. We further generate validation and test sets consiting of 250 instances each to validate/test the DLTS approach as a whole. We run TT on these instances for seven days and use the results for investigating the gap of DLTS to optimality.
We implement DLTS in Python 3 using keras 1.1.0 (Chollet et al. 2015) with theano 0.8.2 (Theano Development Team 2016) as the backend for the implementation of the DNNs. All experiments are conducted using the Arminius Cluster of the Paderborn Center For Parallel Computing (PC 2 ) on Intel Xeon X5650 CPUs (2.67 GHz). All DNNs are trained on a single CPU using all six cores, resulting in a training time ranging from several hours to a few days. We run DLTS and evaluate the policy and value networks using a single thread. This means that, once trained, DLTS can be run on a typical desktop computer. This makes it especially useful for industrial applications.

Experimental question 1: DNN configurations
Configuring a DNN correctly is critical for it to perform well, and is a difficult problem in and of itself (Domhan et al. 2015). We therefore suggest three different possible configurations for the CPMP in which we adjust the number of shared weight layers (SWL) and non-shared weight layers (NSWL) for both the policy and value networks. All networks are trained using the Adam optimizer (Kingma and Ba 2014), which is based on a gradient descent.  Table 1 shows the validation performance of the policy networks on G123. The learning rate for the Adam optimizer was set to 0.001 for all networks, except for those trained on the 10x7 instances. For these, we set the learning rate to 0.0005 to avoid overfitting. Higher rates represent more aggressive adjustments of the DNN weights. We use the early stopping termination criteria, which stops the training after no performance improvement on the validation set is seen for a predetermined number of epochs (in our case 50). The columns of the table are as follows. The number of shared layers (i.e., those with shared weights as in Figure 4) and non-shared layers are given. The number of weights is the number of arcs in the DNN between perceptrons. We use the loss function categorical crossentropy (CCE) to judge the performance of the DNN. CCE measures the distance of the output of the DNN to the desired probability distribution. A key advantage of CCE over the classification error is that it not only penalizes incorrect predictions, but also correct predictions that are weak. For example, a DNN suggesting a correct move with only slightly higher confidence than incorrect moves will receive a worse CCE value than a DNN that assigns a high confidence value to the correct move. The accuracy refers to the percentage of the validation set for which the DNN predicts the correct move.
For DLTS we provide the average gap (computed as the total number of DLTS moves on the dataset divided by the total number of moves required to solve all instances to optimality) to the optimal solution on a dataset of 100 validation instances each of G1, G2 and G3. We also provide the average time to solve the validation instances using the DFS search strategy without a value network. We use the log branch pruning strategy with a p value found through a grid search.
A positive insight from these results are that lower CCE values also correspond to lower gaps. This makes training the DNN much easier, as no search procedure needs to be initiated to assess the quality of the predictions. A second insight is that bigger networks are not always better. For example, for 10x7 the network with 471,729 weights outperforms the network twice its size in terms of CCE, accuracy and DLTS gap. It is clear, however, that having a network that is too small hampers learning, especially on large instances. Since the predictions of small networks can be computed faster, it would be reasonable to expect them to have an advantage over large networks. However, networks that are too small sacrifice too much predictive accuracy, as seen for all three instance sizes. Figure 5 shows the validation performance of the policy networks for each training epoch in which a new incumbent network was found for each instance size, and all instances could be solved. Examining the training for 7x7 instances, we note that DLTS achieves a gap of around 9% to the best solutions found even for a DNN that has a CCE value of 0.95 -meaning it makes many mistakes. A gap of 9% is already better than heuristics from the literature for the CPMP on instances of this size, such as the corridor method Voß 2009) or LPFH (Expósito-Izquierdo et al. 2012). Table 2 shows the validation performance for the value networks. Since the value DNN is performing a regression, we swap CCE for the mean squared error (MSE) and provide the mean absolute error (MAE) instead of the accuracy. We run DLTS with the best performing policy network from each instance size. As in the case of the policy networks using the CCE criterion, the MSE score correlates with the DLTS gap we find. However, in contrast to the case of the policy networks, the larger networks result in nearly the same performance as the "medium" sized networks.

Experimental question 2: Search strategy evaluation
We now compare the three proposed search strategies across our datasets. To ensure a fair comparison between the strategies, we tune each search strategy with DLTS using GGA (Ansótegui et al. 2009) for a maximum of seven days. We give the tuning procedure the freedom to select the policy and value DNN (from those trained on G123), as well as to tune other DLTS parameters detailed in Section 3. Table 3 provides the results in terms of the gap from the best known solution to each instance in the validation set (note that in nearly all cases this is the optimal solution). A star indicates that not all 300 instances were solved, meaning that the value in the table cannot be used for a direct comparison between strategies.    LDS and DFS provide the best overall performance as they find solutions to every instance they are given. While LDS provides under half the gap of DFS for 5x7 instances, we note that this usually means LDS finds solutions with roughly one less move than DFS. On larger instance sizes, DFS again outperforms LDS. Given that neither DFS or LDS dominates the other on all instance categories, it is not possible to draw any sweeping conclusions regarding the two search strategies. The main takeaway, however, is that it is important to use an algorithm configurator when creating a DLTS approach, since the performance of the search strategies varies.
We note that the runtime of the results we obtain probably could be improved through using a faster programming language or using the GPU instead of the CPU for the neural networks. Table 4 shows the number of tree nodes we process during search compared to the TT method, which performs a iterative deepening branch-and-bound programmed in C. The number of nodes DLTS opens in comparison to TT is many orders of magnitude less, for a penalty of usually only one or two moves (a couple of percent) gap to optimality. For example, on the 10x7 instances, we explore roughly 36,000 nodes on average with LDS. The TT method explores upwards of 5 million nodes per second. This is a clear indication that the search guidance of the DNNs is extremely effective.

Experimental question 3: Comparison to the state-of-the-art
We compare DLTS to the state-of-the-art metaheuristic BRKGA from Hottung and Tierney (2016) in Table 5. We train DLTS on the G1 and on the G123 datasets and and report the performance of each on the test sets of G1, G2, G3, and G123. For DLTS-G123, we use the configuration with the best performance on the validation set in Table 3 for each instance size. For DLTS-G1, we configure a new set of parameters for each instance size on the G1 data, leaving the search strategy open, as well as all parameters tuned for DLTS-G123. For a fair comparison to the state-of-the-art, we also tune the BRKGA algorithm on the G123 data.  While the BRKGA finds its best solution faster than DLTS for all instance sizes, the solutions it finds have optimality gaps between 3 and 23 times larger than DLTS. The importance of training DLTS on instances drawn from the same distribution as those it will see during testing is emphasized by the DLTS-G1 gaps. While DLTS-G1 sometimes does perform better than the BRKGA on data it was not trained for, such as for G2 on all sizes, as the instances become increasingly different (G3), performance suffers. DLTS-G123, however, shows high quality results for all instance groups, meaning that training across a wide range of different types of instances does not hurt performance.
As a final test of DLTS, we solve instances from the CV dataset from Caserta and Voß (2009) in Table 6. We note that we perform no training or validation on these instances; we only run the DLTS approaches trained on instances generated to be similar to them. We report the average number of moves each solution procedure requires to solve the instances, along with the average number of moves when solved to optimality. Unsurprisingly, DLTS-G1 outperforms DLTS-G123, since the CV instances have the same structure as G1: a single group per container. DLTS-G1 achieves the best gap to optimality to date, and in less than 60 seconds of run time. Averaging only 42.17 moves over the 40 instances of the CV 5-10 category, its solutions are usually only about 1 move away from optimal, whereas BRKGA and BS-B (Wang et al. 2015) are between 3 and 4 moves, respectively. While BRKGA generally finds solutions within 60 seconds, BS-B sometimes requires significantly more time. In real container terminals, hundreds of CPMPs are solved for the various groups of stacks in the terminal, meaning improving the heuristic solution by even 2 moves could result in hundreds or even thousands of less pre-marshalling crane movements.

Conclusion and future work
We presented DLTS, a heuristic tree search that uses deep learning as a search guidance and pruning mechanism. We tested DLTS on a well-known problem from the container terminals literature, the container pre-marshalling problem, and showed that DLTS finds solutions 4% better than the stateof-the-art on real-world sized instances from the literature. DLTS does this with very little input from the user regarding a problem; it is only given solutions to existing instances and is then able to learn how to build a solution all on its own. To the best of our knowledge, DLTS is the first search approach for optimization problems that allows a learned model to fully control decisions during search and is able to achieve state-of-the-art performance.
There are many avenues of future work for DLTS. One clear way forward is applying DLTS to other optimization problems, such as routing/scheduling problems. Furthermore, reinforcement learning can be used as in Silver et al. (2016) to further improve performance. Moreover, there are many changes to DLTS that can be made, such as reconfiguring the DNN or adjusting the search procedure, that may improve the performance in terms of runtime and solution quality.