Hybrids of stochastic metaheuristics and constraint programming for combinatorial optimization

Combinatorial optimization problems are frequently encountered in scientific and industrial applications. A large number of these problems are known to be NP-hard and solving these problems by exact/complete methods is often impractical. Therefore, heuristic methods are often the best way to deal with such problems. However, when these problems additionally include hard constraints, heuristic/metaheuristic methods often fail and perform poorly. A solution to this is to integrate these methods with techniques like constraint programming (CP) where constraints may be easily specified and efficiently dealt with thereby providing effective solutions to combinatorial optimization problems with non-trivial hard constraints. This thesis specifically investigates the integration of stochastic metaheuristics and constraint programming for combinatorial optimization problems (COPs) with non-trivial hard constraints. Among stochastic metaheuristics, we consider ant colony optimization (ACO) and beam search. The base algorithm we begin with is the hybrid CP-ACO (Meyer and Ernst, 2004) and the aim of the thesis is to show that this algorithm can be made efficient by parallelizing the solution construction of ACO (dependent solution construction as opposed to solution construction on multiple machines/cores) via beam search leading to the hybrid CP-Beam-ACO. We consider three case studies to demonstrate the effectiveness of the new hybrid. The first problem is single machine job scheduling with sequence dependent setup times (SMJS). The aim here is to minimize makespan making sure hard release and due time constraints are not violated. Secondly, a resource constrained multiple machine job scheduled (MMJS) problem is tackled. Here, constraints include release times, due times, precedences, and a resource constraint across the machines. The aim is to minimize the total weighted tardiness of the scheduled jobs. The last problem considered is the car sequencing (CS) problem. Here a number of cars requiring options must be sequenced such that sub-sequences of a particular length may only allow a specific number of each option. We investigate the performance of our algorithms on the optimization version which further requires the utilization of options be effectively modulated across the sub-sequences. By applying ACO, Beam-ACO, CP-ACO and CP-Beam-ACO to the above problems we see that CP-ACO methods are by far the best performing algorithms in terms of solution quality. This is clearly seen on the SMJS and CS problems for which complex CP models have been defined. There is a slight disadvantage to CP-ACO for the MMJS problem where the CP model is relatively simple. In terms of finding feasible solutions, the feasibility advantages of CP-ACO are inherited by CP-Beam-ACO. We also see for the MMJS problem that CP-Beam-ACO has a significant advantage in this respect. In conclusion, this thesis demonstrates that constraint-based ACO is an efficient and effective method to tackle real-world COPs. In particular, CP-ACO can be made efficient by parallelizing the solution construction of the ACO component resulting in CP-Beam-ACO. The new algorithm provides significant advantages for three different types of real-world COPs with non-trivial hard constraints and can be viewed as the practically viable option for implementing ACO with CP.