ABSTRACT The general Capacitated Arc Routing Problem (CARP) is a well‐known optimization problem where a set of edges must be visited by a fleet of vehicles. It is known to be NP‐hard, meaning that it cannot in general be solved efficiently (unless ). This article introduces a polynomial‐time solvable special case of the CARP on regular grid graphs that arises in a practical application for routing of agrochemical‐spraying vehicles. Regular grid graphs are divided into two categories, single‐layer and multi‐layer. By utilizing mathematical insights, we are able to obtain optimal solutions and generate path patterns for both categories of grid graphs. Several theorems are presented to demonstrate the characteristics of the solution patterns under various conditions. These findings allow arbitrarily large‐scale problems of this type to be solved efficiently. It is also hoped that a deeper understanding of the regular grid graph case may form the basis for future research on approximation methods for irregular grid graphs.

Constraint programming (CP) is a powerful technique for solving constraint satisfaction and optimization problems. In CP solvers, the variable ordering strategy used to select which variable to explore first in the solving process has a significant impact on solver effectiveness. To address this issue, we propose a novel variable ordering strategy based on supervised learning, which we evaluate in the context of job shop scheduling problems. Our learning-based methods predict the optimal solution of a problem instance and use the predicted solution to order variables for CP solvers. Unlike traditional variable ordering methods, our methods can learn from the characteristics of each problem instance and customize the variable ordering strategy accordingly, leading to improved solver performance. Our experiments demonstrate that training machine learning models is highly efficient and can achieve high accuracy. Furthermore, our learned variable ordering methods perform competitively compared to four existing methods. Finally, we showcase the benefits of integrating machine learning-based variable ordering methods with conventional domain-based approaches through tie-breaking.

Column Generation (CG) is an effective method for solving large-scale optimization problems. CG starts by solving a subproblem with a subset of columns (i.e., variables) and gradually includes new columns that can improve the solution of the current subproblem. The new columns are generated as needed by repeatedly solving a pricing problem, which is often NP-hard and is a bottleneck of the CG approach. To tackle this, we propose a Machine-Learning-based Pricing Heuristic (MLPH) that can generate many high-quality columns efficiently. In each iteration of CG, our MLPH leverages an ML model to predict the optimal solution of the pricing problem, which is then used to guide a sampling method to efficiently generate multiple high-quality columns. Using the graph coloring problem, we empirically show that MLPH significantly enhances CG as compared to six state-of-the-art methods, and the improvement in CG can lead to substantially better performance of the branch-and-price exact method.

In this article, we investigate problem reduction techniques using stochastic sampling and machine learning to tackle large-scale optimization problems. These techniques heuristically remove decision variables from the problem instance, that are not expected to be part of an optimal solution. First we investigate the use of statistical measures computed from stochastic sampling of feasible solutions compared with features computed directly from the instance data. Two measures are particularly useful for this: 1) a ranking-based measure, favoring decision variables that frequently appear in high-quality solutions; and 2) a correlation-based measure, favoring decision variables that are highly correlated with the objective values. To take this further we develop a machine learning approach, called Machine Learning for Problem Reduction (MLPR), that trains a supervised learning model on easy problem instances for which the optimal solution is known. This gives us a combination of features enabling us to better predict the decision variables that belong to the optimal solution for a given hard problem. We evaluate our approaches using a typical optimization problem on graphs-the maximum weight clique problem. The experimental results show our problem reduction techniques are very effective and can be used to boost the performance of existing solution methods.

This paper presents a new method to automatically decompose general Mixed Integer Programs (MIPs). To do so, we represent the constraint matrix for a general MIP problem as a hypergraph and relax constraints by removing hyperedges from the hypergraph. A Breadth First Search algorithm is used to identify the individual partitions that now exist and the resulting decomposed problem. We propose that good decompositions have both a small number of constraints relaxed and small subproblems in terms of the number of variables they contain. We use the multiobjective Nondominated Sorting Genetic Algorithm II (NSGA-II) to create decompositions which minimize both the size of the subproblems and the number of constraints relaxed. We show through our experiments the types of decompositions our approach generates and test empirically the effectiveness of these decompositions in producing bounds when used in a Lagrangian Relaxation framework. The results demonstrate that the bounds generated by our decompositions are significantly better than those attained by solving the Linear Programming relaxation, as well as the bounds found via random and greedy constraint relaxation and decomposition generation.

In this paper we use a divide-and-conquer approach to tackle large-scale optimization problems with overlapping components. Decomposition for an overlapping problem is challenging as its components depend on one another. The existing decomposition methods typically assign all the linked decision variables into one group, thus cannot reduce the original problem size. To address this issue we modify the Recursive Differential Grouping (RDG) method to decompose overlapping problems, by breaking the linkage at variables shared by multiple components. To evaluate the efficacy of our method, we extend two existing overlapping benchmark problems considering various level of overlap. Experimental results show that our method can greatly improve the search ability of an optimization algorithm via divide-and-conquer, and outperforms RDG, random decomposition as well as other state-of-the-art methods. We further evaluate our method using the CEC’2013 benchmark problems and show that our method is very competitive when equipped with a component optimizer.

Conventional mixed-integer programming (MIP) solvers can struggle with many large-scale combinatorial problems, as they contain too many variables and constraints. Meta-heuristics can be applied to reduce the size of these problems by removing or aggregating variables or constraints. Merge search algorithms achieve this by generating populations of solutions, either by heuristic construction [4], or by finding neighbours to an initial solution [12]. This paper presents a merge search algorithm that improves the population generation heuristic in [12] and utilises a variable grouping heuristic that exploits the common information across a population to aggregate groups of variables in order to create a reduced subproblem. The algorithm is tested on some well known benchmarks for a complex problem called the constrained pit (CPIT) problem and it is compared to results produced by a merge search algorithm previously used on the same problem and the results published on the minelib [9] website.

Many large-scale combinatorial problems contain too many variables and constraints for conventional mixed-integer programming (MIP) solvers to manage. To make the problems easier for the solvers to handle, various meta-heuristic techniques can be applied to reduce the size of the search space, by removing, or aggregating, variables and constraints. A novel meta-heuristic technique is presented in this paper called merge search, which takes an initial solution and uses the information from a large population of neighbouring solutions to determine promising areas of the search space to focus on. The population is merged to produce a restricted sub-problem, with far fewer variables and constraints, which can then be solved by a MIP solver. Merge search is applied to a complex problem from open-pit mining called the constrained pit (CPIT) problem, and compared to current state-of-the-art results on well known benchmark problems minelib [7] and is shown to give better quality solutions in five of the six instances.

This study considers a resource constrained job scheduling problem. Jobs need to be scheduled on different machines satisfying a due time. If delayed, the jobs incur a penalty which is measured as a weighted tardiness. Furthermore, the jobs use up some proportion of an available resource and hence there are limits on multiple jobs executing at the same time. Due to complex constraints and a large number of decision variables, the existing solution methods, based on meta-heuristics and mathematical programming, are very time-consuming and mainly suitable for small-scale problem instances. We investigate a genetic programming approach to automatically design reusable scheduling heuristics for this problem. A new representation and evaluation mechanisms are developed to provide the evolved heuristics with the ability to effectively construct and refine schedules. The experiments show that the proposed approach is more efficient than other genetic programming algorithms previously developed for evolving scheduling heuristics. In addition, we find that the obtained heuristics can be effectively reused to solve unseen and large-scale instances and often find higher quality solutions compared to algorithms already known in the literature in significantly reduced time-frames.

In this paper, a novel bi-level grouping optimization (BIGO) model is proposed for solving the storage location assignment problem with grouping constraint (SLAP-GC). A major challenge in this problem is the grouping constraint which restricts the number of groups each product can have and the locations of items in the same group. In SLAP-GC, the problem consists of two subproblems, one is how to group the items, and the other one is how to assign the groups to locations. It is an arduous task to solve the two subproblems simultaneously. To overcome this difficulty, we propose a BIGO. BIGO optimizes item grouping in the upper level, and uses the lower-level optimization to evaluate each item grouping. Sophisticated fitness evaluation and search operators are designed for both upper and lower level optimization so that the feasibility of solutions can be guaranteed, and the search can focus on promising areas in the search space. Based on the BIGO model, a multistart random search method and a tabu search algorithm are proposed. The experimental results on the real-world dataset validate the efficacy of the BIGO model and the advantage of the tabu search method over the random search method.

Nurse rostering problems are typically too large and hard to be solved exactly.In order to achieve quality solutions to these difficult problems, meta-heuristics are often employed.One such meta-heuristic is Ant Colony Optimisation (ACO), inspired by the pheromone trails left by ants.ACO works by guiding a heuristic solution construction by using these pheromones to direct weighted random choices.When the problem to be solved is highly constrained, finding feasible solutions is difficult, which can result in poor performance for ACO.To address this, we propose an ACO algorithm using an integer programming based solution construction method to ensure feasibility and select from a collection of schedules.The approach also uses a novel solution merging step that combines the information from multiple ants to generate a better final roster.We discuss several challenges inherent in this approach, and how they may be overcome.Computational results on highly constrained nurse rostering problem instances from the literature demonstrate the effectiveness of our proposed new hybrid metaheuristic.

Pit planning and long-term production scheduling are important tasks within the mining industry. This is a great opportunity for optimisation techniques, as the scale of a lot of mining operations means that a small percentage increase in efficiency can translate to millions of dollars in profit. The precedence constrained production scheduling problem (PCPSP) combines both of these aspects of mine optimisation and aims to find a solution which tells a mining company what part of the orebody to mine, and at what time during the life of the mine. This paper presents a GRASP-Mixed Integer Programming hybrid metaheuristic algorithm for solving the PCPSP which consists of two parts: a fast, period-by-period, random construction phase and a local improvement heuristic. It is compared to the current published state-of-the-art results on well known benchmark problems from minelib [5] and is shown to give better quality results in four of the six instances, and within 2% of the LP upper bound in the remaining two. The PCPSP is a good candidate for hybrid metaheuristics as the size of the problems make solving them with mathematical solvers alone intractable.

The Steiner tree problem in graphs (STPG) is a well known NP-hard combinatorial problem with various applications in transport, computational biology, network and VLSI design. Exact methods have been developed to solve this problem to proven optimality, however the exponential nature of these algorithms mean that they become intractable with large-scale instances of the problem. Because of this phenomenon, there has been considerable research into using metaheuristics to obtain good quality solutions in a reasonable time. This paper presents a hybrid local search technique which is an extension of techniques from the literature with an added random jump operator which prevents the algorithm from becoming stuck in local minima. It is compared against greedy local search, the hybrid local search technique it extends and two metaheuristic techniques from the current literature and is shown to outperform them in nearly all cases.

The Storage Location Assignment Problem (SLAP) is a significant optimisation problem in warehouse management. Given a number of products, each with a set of items with different popularities (probabilities of being ordered), SLAP is to find the best locations for the items of the products in the warehouse to minimise the warehouse operational cost. Specifically, the operational cost is the expected cost of picking the orders. Grouping constraints are included to take the practical considerations into account in the problem. That is, the items belonging to the same product are more desirable to be placed together. In this paper, the SLAP with Grouping Constraints (SLAP-GC) is investigated, and an efficient Restricted Neighbourhood Tabu Search (RNTS) algorithm is proposed to solving it. RNTS adopts the problem-specific search operators to maintain solution feasibility, and the tabu list to prevent searching back and forth. RNTS was empirically compared with the mathematical programming method and a previously designed Genetic Programming method, which is demonstrated to be the state-of-the-art algorithm for SLAP-GC. The experimental results on the real-world data show that RNTS outperforms the state-of-the-art algorithms for SLAP-GC in terms of solution quality and speed. It managed to achieve optimal solutions for most of the small-scale instances much faster and outperformed the Genetic Programming method in terms of both solution quality and running time on all the test instances.

This study proposes a method for solving real-world warehouse Storage Location Assignment Problem (SLAP) under grouping constraints by Genetic Programming (GP). Integer Linear Programming (ILP) formulation is used to define the problem. By the proposed GP method, a subset of the items is repeatedly selected and placed into the available current best location of the shelves in the warehouse, until all the items have been assigned with locations. A heuristic matching function is evolved by GP to guide the selection of the subsets of items. Our comparison between the proposed GP approach and the traditional ILP approach shows that GP can obtain near-optimal solutions on the training data within a short period of time. Moreover, the evolved heuristics can achieve good optimization results on unseen scenarios, comparable to that on the scenario used for training. This shows that the evolved heuristics have good reusability and can be directly applied for slightly different scenarios without any new search process.

Recently a novel hybrid heuristic combining various Lagrangian heuristic ideas with Particle Swarm Optimization has been proposed and tested in the context of degree constrained minimum spanning trees. This paper investigates the applicability of the new hybrid meta-heuristic to a challenging scheduling problem. The resource constrained scheduling problem involves a set of jobs that need to be scheduled on multiple machines so as to minimise total weighted tardiness in the presence of precedence constraints and release dates. This is further complicated by the need for the jobs to consume a shared resource with limited capacity. The paper shows that the Lagrangian Particle Swarm Optimization approach can produce both high quality upper bounds (heuristic solutions) and useful lower bounds giving a performance guarantee for these heuristic solutions. Computational results are presented to show that the new method can outperform previous approaches in the literature for this problem.

Hybrid methods for solving combinatorial optimization problems have become increasingly popular recently. The present paper is concerned with hybrids of ant colony optimization and constraint programming which are typically useful for problems with hard constraints. However, the original algorithm suffered from large CPU time requirements. It was shown that such an integration can be made efficient via a further hybridization with beam search resulting in CP-Beam-ACO. The original work suggested this in the context of job scheduling. We show here that this algorithm type is also effective on another problem class, namely the car sequencing. We consider an optimization version, where we aim to optimize the utilization rates across the sequence. Car sequencing is a notoriously difficult problem, because it is difficult to obtain good bounds via relaxations. We show that stochastic sampling provides superior results to well known lower bounds for this problem when combined with CP-Beam-ACO.

This paper presents a new hybrid heuristic combining particle swarm optimization with a Lagrangian heuristic along the lines first proposed by Wedelin. We will refer to this as a Combinatorial Lagrangian Particle Swarm Optimization Algorithm (CoLaPSO). It uses a problem representations that works simultaneously in the dual space (Lagrangian multipliers) and the primal space in the form of cost perturbations. The CoLaPSO method is applied to solving the degree constrained minimum spanning tree problem. This NP-hard problem consists of finding a minimum cost spanning tree on a graph such that none of the vertices is connected to more than a fixed number of edges. The hybrid heuristic inherits from the Lagrangian parent an ability to calculate lower bounds on the objective and from the particle swarm optimization the ability to effectively parallelise the algorithm. Empirical evaluation using standard test problems from the literature show that the new method outperforms previously published heuristics for this problem and also computes useful lower bounds.

In this paper, we introduce an exact method based on constraint programming ideas for a combinatorial optimization problem that arises from the treatment planning of intensity-modulated radiotherapy—the minimum cardinality problem (MCP). The MCP is to find a decomposition of a given integer matrix into a weighted sum of binary matrices with consecutive ones, such that the number of such binary matrices is minimised. We compare our method with two recent exact methods for the same problem and a recent exact method for a special case of the problem. Numerical results are presented that indicate that our method is computationally more efficient than the three existing methods.

This paper investigates the use of hybrid meta-heuristics based on ant colony optimization (ACO) for the strip packing problem. Here, a fixed set of rectangular items of fixed sizes have to be placed on a strip of fixed width and infinite height without overlaps and with the objective to minimize the height used. We analyze a commonly used basic placement heuristic (BLF) by itself and in a number of hybrid combinations with ACO. We compare versions that learn item order only, item rotation only, both independently, and rotations conditionally upon placement order. Our analysis shows that integrating a learning meta-heuristic provides a significant performance advantage over using the basic placement heuristic by itself. The experiments confirm that even just learning a placement order alone can provide significant performance improvements. Interestingly, learning item rotations provides at best a marginal advantage. The best hybrid algorithm presented in this paper significantly outperforms previously reported strip packing meta-heuristics.

Several of the more important endmember-finding algorithms for hyperspectral data are discussed and some of their shortcomings highlighted. A new algorithm - iterated constrained endmembers (ICE) - which attempts to address these shortcomings is introduced. An example of its use is given. There is also a discussion of the advantages and disadvantages of normalizing spectra before the application of ICE or other endmember-finding algorithms.

Several of the more important endmember-finding algorithms for hyperspectral data are discussed and their shortcomings highlighted. A new algorithm, ICE, which attempts to overcome these shortcomings is introduced. An example of is use is given.

The problem of scheduling aircraft landings on one or more runways is an interesting problem that is similar to a machine job scheduling problem with sequence-dependent processing times and with earliness and tardiness penalties. The aim is to optimally land a set of planes on one or several runways in such a way that separation criteria between all pairs of planes (not just successive ones) are satisfied. Each plane has an allowable time window as well as a target time. There are costs associated with landing either earlier or later than this target landing time. In this paper, we present a specialized simplex algorithm which evaluates the landing times very rapidly, based on some partial ordering information. This method is then used in a problem space search heuristic as well as a branch-and-bound method for both single- and multiple-runway problems. The effectiveness of our algorithms is tested using some standard test problems from the literature. © 1999 John Wiley & Sons, Inc. Networks 34: 229–241, 1999

The problem of locating hub facilities arises in the design of transportation and telecommunications networks. The p-hub median problem belongs to a class of discrete location-allocation problems in which all the hubs are fully interconnected. Nonhub nodes may be either uniquely or multiply allocated to hubs. The hubs are uncapacitated and the total number of hubs, p is specified a priori. We describe a novel exact-solution approach for solving the multiple-allocation case of the p-hub median problem and show how a similar method can be adapted for solving the more difficult single-allocation case. The methods for both of these solve shortest-path problems to obtain lower bounds, which are used in a branch-and-bound scheme to obtain the exact solution. Numerical results show the superiority of this new approach over traditional LP-based methods.