Integration of Constraint Programming, Artificial Intelligence, and Operations Research

We describe our experiences using Z3 for synthesizing and optimizing next generation plant configurations for a car manufacturing company (The views expressed in this writing are our own. They make no representation on behalf of others). Our approach leverages unique capabilities of Z3: a combination of specialized solvers for finite domain bit-vectors and uninterpreted functions, and a programmable extension that we call constraints as code. To optimize plant configurations using Z3, we identify useful formalisms from Satisfiability Modulo Theories solvers and integrate solving capabilities for the resulting non-trivial optimization problems.

It is well-known that experience can lead to increased efficiency, yet this is largely unaccounted for in project scheduling. We consider project scheduling problems where the duration of activities can be reduced when scheduled after certain other activities that allow for learning relevant skills. Since per-period availabilities of renewable resources are limited and precedence requirements have to be respected, the resulting optimization problems generalize the resource-constrained project scheduling problem. We introduce four constraint programming formulations that incorporate the alternative learning-based job durations via logical constraints, dynamic interval lengths, multiple job modes, and a bi-objective reformulation, respectively. To provide tight optimality gaps for larger problem instances, we further develop five lower bounding techniques based on model relaxations. We also devise a destructive lower bounding method. We perform an extensive computational study across thousands of instances based on the PSPlib to quantify the impact of project size, potential learning occurrences, and learning effects on the optimal project duration. In addition, we compare formulation strength and quality of the obtained lower bounds using a state-of-the-art constraint programming solver.

As for any decomposition method, the computational performance of a logic-based Benders decomposition (LBBD) scheme relies on the quality of the feedback information. Therefore, an important acceleration technique in LBBD is to strengthen feasibility cuts by reducing their sizes. This is typically done by solving additional subproblems to evaluate potential cuts. In this paper, we study three cut-strengthening algorithms that differ in the computational efforts made to find stronger cuts and in the guarantees with respect to the strengths of the cuts. We give a unified description of these algorithms and present a computational evaluation of their impact on the efficiency of a LBBD scheme. This evaluation is made for three different problem formulations, using over 2000 instances from five different applications. Our results show that it is usually beneficial to invest the time needed to obtain irreducible cuts. In particular, the use of the depth-first binary search cut-strengthening algorithm gives a good performance. Another observation is that when the subproblem can be separated into small independent problems, the impact of cut strengthening is dominated by that of the separation, which has an automatic strengthening effect.

We consider the longest common subsequence (LCS) problem and propose a new method for obtaining tight upper bounds on the solution length. Our method relies on the compilation of a relaxed multi-valued decision diagram (MDD) in a special way that is based on the principles of A\(^*\) search. An extensive experimental evaluation on several standard LCS benchmark instance sets shows that the novel construction algorithm clearly outperforms a traditional top-down construction (TDC) of MDDs. We are able to obtain stronger and at the same time more compact relaxed MDDs than TDC and this in shorter time. For several groups of benchmark instances new best known upper bounds are obtained. In comparison to existing simple upper bound procedures, the obtained bounds are on average 14.8% better.

The COVID-19 pandemic has forced educational institutions to make significant changes to safeguard the health and safety of their students and teachers. One of the most effective measures to reduce virus transmission is partitioning students into discrete cohorts.

In primary and middle schools, it is easy to create these cohorts (also known as “learning groups”), since students in each grade take the same set of required courses. However, in high schools, where there is much diversity in course preferences among individual students, it is extremely challenging to optimally partition students into cohorts to ensure that every section of a course only contains students from a single cohort.

In this paper, we define the Student Cohort Partitioning Problem, where our goal is to optimally assign cohorts to students and course sections, to maximize students being enrolled in their desired courses. We solve this problem by modeling it as an integer linear program, and apply our model to generate the Master Timetable for a Canadian all-boys high school, successfully enrolling students in 87% of their desired courses, including 100% of their required courses. We conclude the paper by explaining how our model can benefit all educational institutions that need to create optimal student cohorts when designing their annual timetable.

We study optimization problems where the objective function is modeled through feedforward neural networks. Recent literature has explored the use of a single neural network to model either uncertain or complex elements within an objective function. However, it is well known that ensembles can produce more accurate and more stable predictions than single neural network. We therefore study how neural network ensemble can be incorporated within an objective function, and propose a two-stage optimization algorithm for solving the ensuing optimization problem. Preliminary computational results applied to a global optimization problem and a real-world data set show that the two-stage model greatly outperforms a standard adaptation of previously proposed MIP formulations of single neural network embedded optimization models.

Recent work has demonstrated that neural sequence models can successfully solve combinatorial search problems such as program synthesis and routing problems. In these scenarios, the beam search algorithm is typically used to produce a set of high-likelihood candidate sequences that are evaluated to determine if they satisfy the goal criteria. If none of the candidates satisfy the criteria, the beam search can be restarted with a larger beam size until a satisfying solution is found. Inspired by works in combinatorial and heuristic search, we investigate whether heavy-tailed behavior can be observed in the search effort distribution of complete beam search in goal-oriented neural sequence decoding. We analyze four goal-oriented decoding tasks and find that the search effort of beam search exhibits fat- and heavy-tailed behavior. Following previous work on heavy-tailed behavior in search, we propose a randomized restarting variant of beam search. We conduct extensive empirical evaluation, comparing different randomization techniques and restart strategies, and show that the randomized restarting variant solves some of the hardest instances faster and outperforms the baseline.

This contribution deals with the development of a Constraint Programming (CP) model and solution strategy for a two-stage industrial formulation plant with parallel production units for crop protection chemicals. Optimal scheduling of this plant is difficult: a high number of units and operations have to be scheduled while at the same time a high degree of coupling between the operations is present due to the need for synchronizing charging and discharging operations.

In the investigated problem setting the formulation lines produce several intermediates that are filled into a variety of types of final containers by filling stations. Formulation lines and filling stations each consist of parallel, non-identical sets of equipment units. Buffer tanks are used to decouple the two stages, to increase the capacity utilization of the overall plant.

The CP model developed in this work solves small instances of the scheduling problem monolithically. To deal with large instances a decomposition algorithm is developed. The overall set of batches is divided into subsets which are scheduled iteratively. The algorithm is designed in a moving horizon fashion, in order to counteract the disadvantages of the limited lookahead that order-based decomposition approaches typically suffer from. The results show that the complex scheduling problem can be solved within acceptable solution times and that the proposed moving horizon strategy (MHS) yields additional benefits in terms of solution quality.

The Volleyball Nations League is the elite annual international competition within volleyball, with the sixteen best nations per gender contesting the trophy in a tournament that spans over 6 weeks. The first five weeks contain a single round robin tournament, where matches are played in different venues across the globe. As a result of this setup, there is a large discrepancy between the travel burdens of meeting teams, which is a disadvantage for the teams that have to travel a lot. We analyse this problem, and find that it is related to the well-known Social Golfer Problem. We propose a decomposition approach for the resulting optimization problem, leading to the so-called Venue Assignment Problem. Using integer programming methods, we find, for real-life instances, the fairest schedules with respect to the difference in travel distance.

Many pattern mining tasks have been modeled and solved using constraints programming (CP) and propositional satisfiability (SAT). In these two well-known declarative AI models, the problem is encoded as a constraints network or a propositional formula, whose associated models correspond to the patterns of interest. In this new declarative framework, new user-specified constraints can be easily integrated, while in traditional data mining, such additional constraints might require an implementation from scratch. Unfortunately, these declarative data mining approaches do not scale on large datasets, leading to huge size encodings. In this paper, we propose a compact SAT-based encoding for itemset mining tasks, by rewriting some key-constraints. We prove that this reformulation can be expressed as a Boolean matrix compression problem. To address this problem, we propose a greedy approach allowing us to reduce considerably the size of the encoding while improving the pattern enumeration step. Finally, we provide experimental evidence that our proposed approach achieves a significant reduction in the size of the encoding. These results show interesting improvements of this compact SAT-based itemset mining approach while reducing significantly the gap with the best state-of-the-art specialized algorithm.

In this work, we consider a pipe routing problem encountered in the space industry to design waveguides used in telecommunication satellites. The goal is to connect an input configuration to an output configuration by using a pipe composed of a succession of straight sections and bends. The pipe is routed within a 3D continuous space divided into non-regular convex cells in order to take obstacles into account. Our objective is to consider several non-standard features such as dealing with a set of bends restricted to a bend catalog that can contain both orthogonal and non-orthogonal bends, or with pipes that have a rectangular section, which makes the pipe orientation important. An approach is introduced to automate the design of such pipe systems and help designers to manage the high number of constraints involved. Basically, this approach formulates the pipe routing problem as a shortest path problem in the space of routing plans, where a routing plan is specified by the parts composing a pipe and by geometrical constraints imposed on these parts. The problem is then solved using weighted A* search combined with a linear program that quickly evaluates the feasibility and the cost of a routing plan. The paper shows that the approach obtained has the capacity to solve realistic instances inspired by industrial problems.

Discrete dynamical systems (DDS) are a model to represent complex phenomena appearing in many different domains. In the finite case, they can be identified with a particular class of graphs called dynamics graphs. In [9] polynomial equations over dynamics graphs have been introduced. A polynomial equation represents a hypothesis on the fine structure of the system. Finding the solutions of such equations validate or invalidate the hypothesis.

This paper proposes new algorithms that enumerate all the solutions of polynomial equations with constant right-hand term outperforming the current state-of-art methods [10]. The boost in performance of our algorithms comes essentially from a clever usage of Multi-valued decision diagrams.

These results are an important step forward in the analysis of complex dynamics graphs as those appearing, for instance, in biological regulatory networks or in systems biology.

This paper proposes two deadline adjustment techniques for scheduling non preemptive tasks subject to precedence relations, release dates and deadlines on a limited number of processors. This decision problem is denoted by \(P\vert prec, r_i, d_i\vert \star \) in standard notations. The first technique is an extension of the Garey and Johnson algorithm that integrates precedence relations in energetic reasoning. The second one is an extension of the Leung, Palem and Pnueli algorithm that builds iteratively relaxed preemptive schedules to adjust deadlines.

The implementation of the two classes of algorithms is discussed and compared on randomly generated instances. We show that the adjustments obtained are slightly different but equivalent using several metrics. However, the time performance of the extended Leung, Palem and Pnueli algorithm is much better than that of the extended Garey and Johnson ones.

This paper presents and evaluates two pruning techniques to reinforce the efficiency of constraint optimization solvers based on multi-valued decision-diagrams (MDD). It adopts the branch-and-bound framework proposed by Bergman et al. in 2016 to solve dynamic programs to optimality. In particular, our paper presents and evaluates the effectiveness of the local-bound (LocB) and rough upper-bound pruning (RUB). LocB is a new and effective rule that leverages the approximate MDD structure to avoid the exploration of non-interesting nodes. RUB is a rule to reduce the search space during the development of bounded-width-MDDs. The experimental study we conducted on the Maximum Independent Set Problem (MISP), Maximum Cut Problem (MCP), Maximum 2 Satisfiability (MAX2SAT) and the Traveling Salesman Problem with Time Windows (TSPTW) shows evidence indicating that rough-upper-bound and local-bound pruning have a high impact on optimization solvers based on branch-and-bound with MDDs. In particular, it shows that RUB delivers excellent results but requires some effort when defining the model. Also, it shows that LocB provides a significant improvement automatically; without necessitating any user-supplied information. Finally, it also shows that rough-upper-bound and local-bound pruning are not mutually exclusive, and their combined benefit supersedes the individual benefit of using each technique.

Linear modular constraints are a powerful class of constraints that arise naturally in cryptanalysis, checksums, hash functions, and the like. Given their importance, the past few years have witnessed the design of combinatorial solvers with native support for linear modular constraints, and the availability of such solvers has led to the emergence of new applications. While there exist global constraints in cp that consider congruence classes over domain values, linear modular arithmetic constraints have yet to appear in the global constraint catalogue despite their past investigation in the context of model counting for csps. In this work we seek to remedy the situation by advocating the integration of linear modular constraints in state-of-the-art cp solvers.

Recent research has shown how Deep Neural Networks trained on historical solution pools can tackle CSPs to some degree, with potential applications in problems with implicit soft and hard constraints. In this paper, we consider a setup where one has offline access to symbolic, incomplete, problem knowledge, which cannot however be employed at search time. We show how such knowledge can be generally treated as a propagator, we devise an approach to distill it in the weights of a network, and we define a simple procedure to extensively exploit even small solution pools. Rather than tackling a real-world application directly, we perform experiments in a controlled setting, i.e. the classical Partial Latin Square completion problem, aimed at identifying patterns, potential advantages, and challenges. Our analysis shows that injecting knowledge at training time can be very beneficial with small solution pools, but may have less reliable effects with large solution pools. Scalability appears as the greatest challenge, as it affects the reliability of the incomplete knowledge and necessitates larger solution pools.

Same-day delivery problems are challenging stochastic vehicle routing problems, where dynamically arriving orders have to be delivered to customers within a short time while minimizing costs. In this work, we consider the short-horizon planning of a problem variant where every order has to be delivered with the goal to minimize delivery tardiness, travel times, and labor costs of the drivers involved. Stochastic information as spatial and temporal order distributions is available upfront. Since timely routing decisions have to be made over the planning horizon of a day, the well-known sampling approach from the literature for considering expected future orders is not suitable due to its high runtimes. To mitigate this, we suggest to use a surrogate function for route durations that predicts the future delivery duration of the orders belonging to a route at its planned starting time. This surrogate function is directly used in the online optimization replacing the myopic current route duration. The function is trained offline by data obtained from running full day-simulations, sampling and solving a number of scenarios for each route at each decision point in time. We consider three different models for the surrogate function and compare with a sampling approach on challenging real-world inspired artificial instances. Results indicate that the new approach can outperform the sampling approach by orders of magnitude regarding runtime while significantly reducing travel costs in most cases.

This work develops a class of relaxations in between the big-M and convex hull formulations of disjunctions, drawing advantages from both. The proposed “P-split” formulations split convex additively separable constraints into P partitions and form the convex hull of the partitioned disjuncts. Parameter P represents the trade-off of model size vs. relaxation strength. We examine the novel formulations and prove that, under certain assumptions, the relaxations form a hierarchy starting from a big-M equivalent and converging to the convex hull. We computationally compare the proposed formulations to big-M and convex hull formulations on a test set including: K-means clustering, P_ball problems, and ReLU neural networks. The computational results show that the intermediate P-split formulations can form strong outer approximations of the convex hull with fewer variables and constraints than the extended convex hull formulations, giving significant computational advantages over both the big-M and convex hull.

This paper studies a real-life inter-modal freight transportation problem, comprised by three consecutive stages: disposition where orders are picked up by trucks, transferred and unloaded to a set of warehouses in Central and Eastern Europe, inter-region transport where the orders are packed into trailers, which are shipped to warehouses in Turkey using different inter-region transport modes, and last-mile delivery where the orders unloaded at the warehouses in Turkey are picked up by vans and delivered to their final destination. The objective is to minimise total transport and tardiness cost. After restricting the routes in the disposition stage, we formulate a mixed-integer linear program that captures the entire delivery process. Then, we propose a Benders’ decomposition and prove the validity of a set of optimality cuts and of a subproblem relaxation. We show the impact of this approach on large-scale real instances under user-imposed time limits. We further strengthening the master problem with a set of valid inequalities and speed up the solution of the subproblem using Constraint Programming.

We address the problem of verifying a constraint by a set of solutions S. This problem is present in almost all systems aiming at learning or acquiring constraints or constraint parameters. We propose an original approach based on MDDs. Indeed, the set of solutions can be represented by the MDD denoted by \(MDD_S\). Checking whether S satisfies a given constraint C can be done using MDD(C), the MDD that contains the set of solutions of C, and by searching if the intersection between MDD(S) and MDD(C) is equal to MDD(S). This step is equivalent to searching whether MDD(S) is included in MDD(C). Thus, we give an inclusion algorithm to speed up these calculations. Then, we generalize this approach for the computation of global constraint parameters satisfying C. Next, we introduce the notion of properties on the MDD nodes and define a new algorithm allowing to compute in only one step the set of parameters we are looking for. Finally, we present experimental results showing the interest of our approach.

The subgraph isomorphism problem is to find a small “pattern” graph inside a larger “target” graph. There are excellent dedicated solvers for this problem, but they require substantial programming effort to handle the complex side constraints that often occur in practical applications of the problem; however, general purpose constraint solvers struggle on more difficult graph instances. We show how to combine the state of the art Glasgow Subgraph Solver with the Minion constraint programming solver to get a “subgraphs modulo theories” solver that is both performant and flexible. We also show how such an approach can be driven by the Essence high level modelling language, giving ease of modelling and prototyping to non-expert users. We give practical examples involving temporal graphs, typed graphs from software engineering, and costed subgraph isomorphism problems.

Coordinating the mobile production fleet in underground mines becomes increasingly important as the machines are more and more automated. We present a scheduling approach that applies to several of the most important production methods used in underground mines. Our algorithm combines constraint programming with a large neighborhood search strategy that dynamically adjusts the neighborhood size. The resulting algorithm is complete and able to rapidly improve constructed schedules in practice. In addition, it has important benefits when it comes to the acceptance of the approach in real-life operations. Our approach is evaluated on public and private industrial problem instances representing different mines and production methods. We find significant improvements over the current industrial practice.

For personnel scheduling problems, mixed-integer linear programming formulations based on state-expanded networks in which nodes correspond to rule-related states often have very strong LP relaxations. A challenge of these formulations is that they typically give rise to large model instances. If one is willing to trade in optimality for computation time, a way to reduce the size of the model instances is to heuristically remove unpromising nodes and arcs from the state-expanded networks.

In this paper, we propose to employ machine learning models for guiding the reduction of state-expanded networks for multi-activity shift scheduling problems. More specifically, we train a model that predicts the flow through a node from its state attributes, and based on this prediction, we decide whether to keep a node or not. In experiments with a well-known set of multi-activity shift scheduling instances, we show that our approach substantially reduces both the size of the model instances and their solution times while still obtaining optimal solutions for the vast majority of the instances. The results indicate that our approach is competitive with a state-of-the art Lagrangian-relaxation-based matheuristic for multi-activity shift scheduling problems.

The design of efficient and generic algorithms for solving combinatorial optimization problems has been an active field of research for many years. Standard exact solving approaches are based on a clever and complete enumeration of the solution set. A critical and non-trivial design choice with such methods is the branching strategy, directing how the search is performed. The last decade has shown an increasing interest in the design of machine learning-based heuristics to solve combinatorial optimization problems. The goal is to leverage knowledge from historical data to solve similar new instances of a problem. Used alone, such heuristics are only able to provide approximate solutions efficiently, but cannot prove optimality nor bounds on their solution. Recent works have shown that reinforcement learning can be successfully used for driving the search phase of constraint programming (CP) solvers. However, it has also been shown that this hybridization is challenging to build, as standard CP frameworks do not natively include machine learning mechanisms, leading to some sources of inefficiencies. This paper presents the proof of concept for SeaPearl, a new CP solver implemented in Julia, that supports machine learning routines in order to learn branching decisions using reinforcement learning. Support for modeling the learning component is also provided. We illustrate the modeling and solution performance of this new solver on two problems. Although not yet competitive with industrial solvers, SeaPearl aims to provide a flexible and open-source framework in order to facilitate future research in the hybridization of constraint programming and machine learning.

In order to deal with the high development time of exact and approximation algorithms for NP-hard combinatorial optimisation problems and the high running time of exact solvers, deep learning techniques have been used in recent years as an end-to-end approach to find solutions. However, there are issues of representation, generalisation, complex architectures, interpretability of models for mathematical analysis etc. using deep learning techniques. As a compromise, machine learning can be used to improve the run time performance of exact algorithms in a matheuristics framework. In this paper, we use a pruning heuristic leveraging machine learning as a pre-processing step followed by an exact Integer Programming approach. We apply this approach to sparsify instances of the classical travelling salesman problem. Our approach learns which edges in the underlying graph are unlikely to belong to an optimal solution and removes them, thus sparsifying the graph and significantly reducing the number of decision variables. We use carefully selected features derived from linear programming relaxation, cutting planes exploration, minimum-weight spanning tree heuristics and various other local and statistical analysis of the graph. Our learning approach requires very little training data and is amenable to mathematical analysis. We demonstrate that our approach can reliably prune a large fraction of the variables in TSP instances from TSPLIB/MATILDA (>85%) while preserving most of the optimal tour edges. Our approach can successfully prune problem instances even if they lie outside the training distribution, resulting in small optimality gaps between the pruned and original problems in most cases. Using our learning technique, we discover novel heuristics for sparsifying TSP instances, that may be of independent interest for variants of the vehicle routing problem.

Recommender Systems have become the backbone of personalized services that provide tailored experiences to individual users. Still, data sparsity remains a common challenging problem, especially for new applications where training data is limited or not available. In this paper, we formalize a combinatorial problem that is concerned with selecting the universe of items for experimentation with recommender systems. On one hand, a large set of items is desirable to increase the diversity of items. On the other hand, a smaller set of items enable rapid experimentation and minimize the time and the amount of data required to train machine learning models. We show how to optimize for such conflicting criteria using a multi-level optimization framework. Our approach integrates techniques from discrete optimization, unsupervised clustering, and latent text embeddings. Experimental results on well-known movie and book recommendation benchmarks demonstrate the benefits of optimized item selection.

Combinatorial optimization has found applications in numerous fields, from transportation to scheduling and planning. The goal is to find an optimal solution among a finite set of possibilities. Most exact approaches use relaxations to derive bounds on the objective function, which are embedded within a branch-and-bound algorithm. Decision diagrams provide a new approach for obtaining bounds that, in some cases, can be significantly better than those obtained with a standard linear programming relaxation. However, it is known that the quality of the bounds achieved through this bounding method depends on the ordering of variables considered for building the diagram. Recently, a deep reinforcement learning approach was proposed to compute a high-quality variable ordering. The bounds obtained exhibited improvements, but the mechanism proposed was not embedded in a branch-and-bound solver. This paper proposes to integrate learned optimization bounds inside a branch-and-bound solver, through the combination of reinforcement learning and decision diagrams. The results obtained show that the bounds can reduce the tree search size by a factor of at least three on the maximum independent set problem.

At the beginning of the pandemic last year some hospitals had to change their physician schedules to take into account infection risks and potential quarantines for personnel. This was especially important for hospitals that care for high-risk patients, like the St. Anna Children’s Hospital in Vienna, which is a tertiary care center for pediatric oncology. It was very important to develop solving methods for this complex problem in short time. We relied on constraint solving technology which proved to be very useful in such critical situations. In this paper we present a constraint model that includes the variety of requirements that are needed to ensure day-to-day operations as well as the additional constraints imposed by the pandemic situation. We introduce an innovative set of grouping constraints to partition the staff, with the intention to easily isolate a small group in case of an infection. The produced schedules also keep part of the staff as backup to replace personnel in quarantine. In our case study, we evaluate and compare our proposed model on several state-of-the-art solvers. Our approach could successfully produce a high-quality schedule for the considered real-world planning scenario, also compared to solutions found by human planners with considerable effort.