Constraint Programming (CP) has been around for decades, yet it remains largely unknown in industry. When faced with combinatorial optimization problems, industry practitioners not knowledgeable in CP techniques often resort to more creative but not necessarily adequate solutions. This paper is the result of an actual case study brought by Technord, an industry consultant. The problem at hand is the optimization of the activation schedule for high-power pumps in a water treatment facility under fluctuating energy costs. The schedule was previously generated using Discrete Particle Swarm Optimization (DPSO). This method struggled with the increasing complexity of volatile market signals and strict operational constraints. Our simpler model, developed in Python using the CPMpy library, formalizes the problem as a CP model. Our experiments demonstrate the benefits of our model’s simplicity compared to the DPSO solution. This use case also showcases the importance of the accessibility of constraint modelling solutions for less knowledgeable practitioners.

We study a routing problem for delivering and picking up multiple commodities with different priorities, motivated by the need to provide basic services to people in depopulated rural areas with a driver shortage. We define our problem as a generalization of the team orienteering problem with time windows, with additional constraints motivated by real-world applications. We develop constraint programming (CP) and mixed-integer programming (MIP) models to solve the formulated problem. In addition, we propose an incremental warm-starting strategy, which obtains an initial solution by solving a problem considering only a subset of commodities. In our experiment, CP outperforms MIP, and incremental warm-starting improves the performance of both approaches.

Column generation and branch-and-price (B&P) are leading mathematical optimization methods for large-scale exact optimization, iterating between solving a master problem and a pricing problem. Due to the difficulty of discrete optimization, high-performance column generation often relies on a custom pricing algorithm built specifically to exploit the problem’s structure. This bespoke nature of the pricing solver makes column generation a problem-specific method and hinders the use of generic implementations across a wide range of problems. We show that domain-independent dynamic programming (DIDP), a model-based paradigm for dynamic programming, can be used as a generic pricing solver. We develop new modeling features and a solving algorithm for DIDP to achieve better performance in typical pricing problems. We demonstrate that in four problem classes, our implementations of B&P, with pricing by DIDP, empirically outperform an existing automated B&P solver and B&P with pricing by mixed-integer programming or constraint programming.

The Quadratic Traveling Salesman Problem (QTSP) is a generalization of the Traveling Salesman Problem (TSP) with important applications in robotics and bioinformatics. The QTSP objective value depends on pairs of consecutive edges in the tour; hence, it is quadratic and generally hard to optimize. While various exact-solving approaches have been explored, many rely on specialized procedures and struggle to scale on large instances. More recently, carefully crafted metaheuristics have demonstrated better primal bounds and scalability, but they cannot provide any guarantees of solution quality nor prove the optimality of any solution. In this work, we propose new exact models for QTSP. We define direct encodings of QTSP in domain-independent dynamic programming (DIDP), constraint programming (CP), mixed integer quadratic programming (MIQP), and mixed integer linear programming (MILP), and compare them with the best-known exact method, a branch and cut (B&C) algorithm, and the state-of-the-art metaheuristic, a hybrid genetic algorithm (HGA). Our experimental results demonstrate that the DIDP model shows better scalability and finds the best feasible solutions on average among all exact solvers, including the B&C algorithm. HGA finds the best feasible solution among all approaches, with DIDP within 15% of the HGA cost on all experimented instances. Also, interestingly, our MILP model with the subtour elimination constraints generally finds better feasible solutions than the B&C algorithm while matching it in proving optimality, suggesting that lazily adding sub-tour elimination cuts is not particularly helpful in QTSP.

Domain-independent dynamic programming (DIDP), a model-based paradigm based on dynamic programming, has shown promising performance on multiple combinatorial optimization problems compared with mixed integer programming (MIP) and constraint programming (CP). The current DIDP solvers are based on heuristic search, and the state-of-the-art solver, complete anytime beam search (CABS), uses beam search. However, the current DIDP solvers cannot utilize multiple threads, unlike state-of-the-art MIP and CP solvers. In this paper, we propose three parallel beam search algorithms and develop multi-thread implementations of CABS. With 32 threads, our multi-thread DIDP solvers achieve 9 to 39 times speedup on average and significant performance improvement over the sequential solver, finding the new best solutions for two instances of the traveling salesperson problem with time windows. In addition, our solvers outperform multi-thread MIP and CP solvers in four of the six combinatorial optimization problems evaluated.

In numeric AI planning, a state is represented by propositions and numeric variables, actions change the values of numeric variables in addition to adding and deleting propositions, and goals and preconditions of actions may include conditions over numeric variables. While domains of numeric variables are rational numbers in general, upper and lower bounds on variables affected only by constant increase and decrease can sometimes be determined and exploited by a heuristic function. In this paper, we generalize the existing method to variables that are changed by linear effects. We exploit the extracted bounds to improve the numeric LM-cut heuristic, a state-of-the-art admissible heuristic for linear numeric planning. Empirical evaluation shows that our method improves the performance of LM-cut in multiple domains. The proposed method can also detect unsolvability of some numeric tasks in polynomial time.

In my dissertation, I will propose Domain-Independent Dynamic Programming (DIDP), a novel model-based paradigm for combinatorial optimization (CO) based on dynamic programming (DP). In DIDP, a problem is first formulated as a declarative DP model and then solved by a general-purpose solver. The goal of my dissertation is to develop an algorithm-independent modeling formalism to define a DP model and general-purpose solvers for it and demonstrate that DIDP is promising for CO in practice. In particular, I will propose a modeling formalism based on a state transition system and heuristic search solvers for it.

The LM-cut heuristic, both alone and as part of the operator counting framework, represents one of the most successful heuristics for classical planning. In this paper, we generalize LM-cut and its use in operator counting to optimal numeric planning with simple conditions and simple numeric effects, i.e., linear expressions over numeric state variables and actions that increase or decrease such variables by constant quantities. We introduce a variant of hmaxhbd (a previously proposed numeric hmax heuristic) based on the delete-relaxed version of such planning tasks and show that, although inadmissible by itself, our variant yields a numeric version of the classical LM-cut heuristic which is admissible. We classify the three existing families of heuristics for this class of numeric planning tasks and introduce the LM-cut family, proving dominance or incomparability between all pairs of existing max and LM-cut heuristics for numeric planning with simple conditions. Our extensive empirical evaluation shows that the new LM-cut heuristic, both on its own and as part of the operator counting framework, is the state-of-the-art for this class of numeric planning problem.

Although symbolic bidirectional search is successful in optimal classical planning, state-of-the-art satisficing planners do not use bidirectional search. Previous bidirectional search planners for satisficing planning behaved similarly to a trivial portfolio, which independently executes forward and backward search without the desired ``meet-in-the-middle'' behavior of bidirectional search where the forward and backward search frontiers intersect at some point relatively far from the forward and backward start states. In this paper, we propose Top-to-Top Bidirectional Search (TTBS), a new bidirectional search strategy with front-to-front heuristic evaluation. We show that TTBS strongly exhibits ``meet-in-the-middle'' behavior and can solve instances solved by neither forward nor backward search on a number of domains.

It is known that seemingly small details such as tie-breaking among nodes with the same f-cost can significantly affect the performance of a best-first search algorithm on many domains (Asai and Fukunaga 2017). In this paper, we show that low-level algorithmic details of domain-independent planning heuristics can have a surprisingly large impact on search performance. As a case study, we consider the well-known FF heuristic (hff ) (Hoffmann and Nebel 2001).