123 research outputs found
Neural combinatorial optimization: from routing to integer programming
No full textCombinatorial optimization problems (COPs) are an important branch of mathematical optimization. It covers practical applications in many fields such as communication, transportation, manufacturing and has received massive attention in domains of computer science, operations research, economics, etc. However, most COPs are difficult to solve exactly owing to their NP-hardness. Heuristics thus are often leveraged as a popular class of optimization methods to solve COPs. However, classic heuristic methods severely depend on the design of hand-crafted rules for every specific COP, which could limit their performance in practice. Also, finding effective rules in heuristics is non-trivial and often needs massive expertise and tuning work. To overcome the above issues, the neural combinatorial optimization (NCO) domain comes into being, which refers to the research and applications of deep learning for solving COPs. Although there is already abundant literature in such domain, some challenging aspects are still not tackled well. For example, the current deep models are generally still inferior to highly-specialized solvers in some specific COPs, and meanwhile it is still difficult for NCO methods to solve general COPs, especially the ones with uncertainty and multiple objectives. In this doctoral thesis, we propose several NCO methods to automatically learn heuristics to solve 1) routing problems, which are a specific and important class of COPs, 2) integer programming, which is a general formulation to model various COPs in different domains, 3) stochastic integer programming, which can model various COPs with uncertainty, and 4) multi-objective integer programming, which is used to optimize multiple objectives for general COPs. All the proposed NCO methods obviate the need of considerable trial-and-error and domain knowledge. They also manifest themselves in the desirable generalization capacities across problem sizes or distributions.
Firstly, we propose a deep reinforcement learning (DRL) framework to learn improvement heuristics for routing problems. We describe the solving process of improvement heuristics as a Markov decision process (MDP), and then design a self-attention based neural architecture for the policy in MDP so that it is used to select the next solution at each step of the local search. We deploy the method to solve two classic routing problems, i.e., travelling salesman problem (TSP) and capacitated vehicle routing problem (CVRP). Results show that the proposed method outperforms state-of-the-art learning based methods. The learned policies for improvement heuristics are more effective than conventional hand-crafted rules and they are able to well generalize to varying problem sizes and initial solutions.
However, the above method resorts to simplified pairwise local operators, which limit the efficiency to improve the solution, and it is not applicable to general COPs. To tackle these issues, we then employ DRL to learn large neighborhood search (LNS) algorithm for solving integer programs (IPs), which can be used to model general COPs. The policy in MDP is trained as the destroy operator to pick a subset of variables at each LNS step, which is reoptimized by an IP solver as the repair operator. Since the combinatorial number of variable subsets hinders the direct application of RL algorithms, we propose action factorization to represent all variable subsets with binary decisions on each variable. The policy is parameterized via a neural network and trained by the actor-critic algorithm to select actions for each variable in parallel. Our method is evaluated on four IP benchmark problems. Results show that it significantly boosts the bounded-time performance of SCIP and Gurobi, and the learned policies generalize well to larger problems.
Despite that the learned LNS can well solve general COPs by modeling them as IPs, some vital aspects in practical COPs are still not involved, e.g., the uncertainty and multiple objectives. Therefore, we propose two NCO methods to solve stochastic and multi-objective IPs. To solve two-stage stochastic integer programs (2SIPs), we use conditional variational autoencoder (CVAE) to learn scenario representations, where a graph convolutional network (GCN) based encoder embeds each scenario with the deterministic part (i.e. context) of a 2SIP instance into the latent space, from which a decoder reconstructs the scenario from its latent representation conditioned on the context. We apply the trained encoder to scenario reduction and objective prediction, which assist in the search of scenario representatives for attaining approximate solutions to original 2SIPs. Results show that our method achieves high-quality solutions in short runtime and the trained encoder generalizes well to larger problems, more scenarios and varying distributions.
To solve multi-objective integer programs (MOIPs), we design a NCO method to refine objective-space decomposition algorithms (ODAs). Since ODAs often encounter difficulties in handling scalarized problems, which could cause infeasibility or repetitive nondominated points and thus induce redundant runtime, we present a graph neural network (GNN) based method to learn the reduction rule in the ODA. We formulate the algorithmic procedure of generic ODAs as a Markov decision process and parameterize the policy (reduction rule) with a novel two-stage GNN for state representation. We train our model with imitation learning and deploy it on a state-of-the-art ODA. Results show that our method significantly improves the solving efficiency of the ODA. The learned policy generalizes fairly well to larger problems or more objectives, and the proposed GNN outperforms existing ones for integer programming in terms of test and generalization accuracy.Doctor of Philosoph
Deep reinforcement learning for solving vehicle routing problems with backhauls
Full text linkThe vehicle routing problem with backhauls (VRPBs) is a challenging problem commonly studied in computer science and operations research. Featured by linehaul (or delivery) and backhaul (or pickup) customers, the VRPB has broad applications in real-world logistics. In this article, we propose a neural heuristic based on deep reinforcement learning (DRL) to solve the traditional and improved VRPB variants, with an encoder-decoder structured policy network trained to sequentially construct the routes for vehicles. Specifically, we first describe the VRPB based on a graph and cast the solution construction as a Markov decision process (MDP). Then, to identify the relationship among the nodes (i.e., linehaul and backhaul customers, and the depot), we design a two-stage attention-based encoder, including a self-attention and a heterogeneous attention for each stage, which could yield more informative representations of the nodes so as to deliver high-quality solutions. The evaluation on the two VRPB variants reveals that, our neural heuristic performs favorably against both the conventional and neural heuristic baselines on randomly generated instances and benchmark instances. Moreover, the trained policy network exhibits a desirable capability of generalization to various problem sizes and distributions.</p
Solving two-stage stochastic integer programs via representation learning
No full textSolving stochastic integer programs (SIPs) is extremely intractable due to the high computational complexity. To solve two-stage SIPs efficiently, we propose a conditional variational autoencoder (CVAE) for scenario representation learning. A graph convolutional network (GCN) based VAE embeds scenarios into a low-dimensional latent space, conditioned on the deterministic context of each instance. With the latent representations of stochastic scenarios, we perform two auxiliary tasks: objective prediction and scenario contrast, which predict scenario objective values and the similarities between them, respectively. These tasks further integrate objective information into the representations through gradient backpropagation. Experiments show that the learned scenario representations can help reduce scenarios in SIPs, facilitating high-quality solutions in a short computational time. This superiority generalizes well to instances of larger sizes, more scenarios, and various distributions.</p
Collaborative Deep Reinforcement Learning for Solving Multi-Objective Vehicle Routing Problems
Full text linkExisting deep reinforcement learning (DRL) methods for multi-objective vehicle routing problems (MOVRPs) typically decompose an MOVRP into subproblems with respective preferences and then train policies to solve corresponding subproblems. However, such a paradigm is still less effective in tackling the intricate interactions among subproblems, thus holding back the quality of the Pareto solutions. To counteract this limitation, we introduce a collaborative deep reinforcement learning method. We first propose a preference-based attention network (PAN) that allows the DRL agents to reason out solutions to subproblems in parallel, where a shared encoder learns the instance embedding and a decoder is tailored for each agent by preference intervention to construct respective solutions. Then, we design a collaborative active search (CAS) to further improve the solution quality, which updates only a part of the decoder parameters per instance during inference. In the CAS process, we also explicitly foster the interactions of neighboring DRL agents by imitation learning, empowering them to exchange insights of elite solutions to similar subproblems. Extensive results on random and benchmark instances verified the efficacy of PAN and CAS, which is particularly pronounced on the configurations (i.e., problem sizes or node distributions) beyond the training ones. Our code is available at https://github.com/marmotlab/PAN-CAS
Damage Mechanism of Surrounding Rock under Blasting Excavation of the Tunnel
No full textBased on numerical simulation software LSDYNA and field monitoring data, this paper analyzes the peak particle velocity (PPV) of rock mass at different distances from the blasting face of the roadway. At the same time, the dynamic stress concentration coefficient of surrounding rock under the action of different blasting times and the blasting damage effect of the tunnel are studied. The results show that in the tunnel blasting near the area, the PPV in the vertical direction of the tunnel is maximum in three directions; PPV decreases more slowly in the excavated zone than in the nonexcavated zone. When the explosion source is close to the roadway, the dynamic stress concentration coefficient of the blasting side and the rear side is large, so the vibration standard of surrounding rock should be strictly controlled
Learning Large Neighborhood Search for Vehicle Routing in Airport Ground Handling
Full text linkDispatching vehicle fleets to serve flights is a key task in airport ground handling (AGH). Due to the notable growth of flights, it is challenging to simultaneously schedule multiple types of operations (services) for a large number of flights, where each type of operation is performed by one specific vehicle fleet. To tackle this issue, we first represent the operation scheduling as a complex vehicle routing problem and formulate it as a mixed integer linear programming (MILP) model. Then given the graph representation of the MILP model, we propose a learning assisted large neighborhood search (LNS) method using data generated based on real scenarios, where we integrate imitation learning and graph convolutional network (GCN) to learn a destroy operator to automatically select variables, and employ an off-the-shelf solver as the repair operator to reoptimize the selected variables. Experimental results based on a real airport show that the proposed method allows for handling up to 200 flights with 10 types of operations simultaneously, and outperforms state-of-the-art methods. Moreover, the learned method performs consistently accompanying different solvers, and generalizes well on larger instances, verifying the versatility and scalability of our method.</p
- …
