Using a single broadcast camera, modern deep learning methods can detect and label players and ball positions on a frame-by-frame basis. This work focuses on post-game analysis, where frame-level labels are available for the entire video sequence. Deep learning alone performs poorly when retrieving intervals of frames in which specific spatio-temporal conditions or tactical patterns occur involving players and ball positions. A loosely coupled neuro-symbolic approach is proposed, in which these precomputed frame-level detections are processed through an SQL-like domain-specific query language. Each query is compiled into a Constraint Programming (CP) model that retrieves intervals of frames satisfying the specified constraints. The method leverages well-established CP constructs, such as time intervals and regular constraints. Experiments on real football games demonstrate that this approach is simple and efficient, enabling expressive querying for post-game tactical analysis while remaining accurate and scalable.

This paper addresses an assembly line balancing problem that combines task assignment, scheduling, and allocation of parallel workstations to minimize cycle time, subject to precedence and shared resource constraints. A key complexity in periodic production environments is the presence of cyclic resource constraints which arise when workers (resources) move between workstations within the same cycle. This scenario is particularly prevalent in large-scale manufacturing industries with long cycle times, such as aerospace assembly. Existing constraint programming (CP) models for this problem schedule tasks on an absolute time horizon. However, this approach relies on modulo operators to project task intervals into a cycle window, which hinders constraint propagation, and makes extending the model beyond fixed factory layouts difficult. We propose a novel cycle-relative CP formulation that addresses both shortcomings. Our model dynamically determines the optimal placement of parallel workstations and defines task decision variables directly within the cycle window, eliminating the need for modulo operators. Experimental evaluations demonstrate the cycle-relative model’s superiority, consistently finding equal or better solutions faster than the temporal approach. Furthermore, a direct engine comparison shows that OptalCP outperforms CP Optimizer on these models across the vast majority of instances.

Insertion sequence variables have recently been introduced as a computational domain for modeling routing and sequencing problems in constraint programming. Typically, search heuristics guide the insertion process of new nodes into a partial growing path, while constraints eliminate infeasible insertions. This paper investigates filtering for the (minimum) distance constraint over insertion sequence variables. This global constraint links a sequence to a distance variable based on a given distance matrix. So far, only a simple filtering algorithm has been proposed, which considers the partial path but ignores mandatory nodes. Our contribution is to introduce stronger lower bounds that also take mandatory nodes into account. These bounds further enable the derivation of additional filtering rules for node insertions. An experimental evaluation on the TourMustSee problem shows that the proposed filtering rules significantly reduce the search space compared to the existing filtering approach.

Composite structures are composed of plies (layers) of carbon fibers. For each ply, one must decide its orientation from the set of possible angles: -45°, 0°, 45°, and 90°. The stack of plies must follow strict constraints on the chosen orientations to achieve mechanical properties of the composite, such as sufficient buckling load. The design problem becomes more complex when determining the stack of plies for a complete surface material, that does not require the same number of plies in every region of the surface. Not only must the orientations be selected in each region, but it is also necessary to decide which plies are discontinued between adjacent regions. Thanks to its declarative nature, Constraint Programming (CP) offers an elegant modeling of the constraints, making it easy for designers to activate or deactivate them as needed. We propose a CP model, implemented in MiniZinc. The performance of this model on synthetic yet realistic instances when solved by different exact solvers, including Mixed Integer Programming (MIP) solvers, demonstrates the superiority of CP over MIP on our MiniZinc model, and over a commercial solution implemented by an industrial partner. It opens up the adoption of CP as an efficient building block of Computer-Aided Design tools for composite structures. By making the model and instances publicly available, we also hope to facilitate the inclusion of this problem in CP solver competitions and stimulate further research in this area.

The branch-and-bound algorithm based on decision diagrams is a framework for solving discrete optimization problems with a dynamic programming formulation. It works by compiling a series of bounded-width decision diagrams that can provide lower and upper bounds for any given subproblem. Eventually, every part of the search space will be either explored or pruned by the algorithm, thus proving optimality. This paper presents new ingredients to speed up the search by exploiting the structure of dynamic programming models. The key idea is to prevent the repeated expansion of nodes corresponding to the same dynamic programming states by querying expansion thresholds cached throughout the search. These thresholds are based on dominance relations between partial solutions previously found and on pruning inequalities given by rough upper bounds and local bounds — two additional filtering techniques recently introduced. Computational experiments show that the pruning brought by this caching mechanism allows for significantly reducing the number of nodes expanded by the algorithm. This results in more benchmark instances of difficult optimization problems being solved in less time while using narrower decision diagrams. History: Accepted by Andrea Lodi, Area Editor for Design and Analysis of Algorithms–Discrete. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2022.0340 ), as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2022.0340 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

Discrete optimization problems expressible as dynamic programs can be solved by branch-and-bound with decision diagrams. This approach dynamically compiles bounded-width decision diagrams to derive both lower and upper bounds on unexplored parts of the search space, until they are all enumerated or discarded. Assuming a minimization problem, relaxed decision diagrams provide lower bounds through state merging while restricted decision diagrams obtain upper bounds by excluding states to limit their size. As the selection of states to merge or delete is done locally, it is very myopic to the global problem structure. In this paper, we propose a novel way to proceed that is based on pre-solving a so-called aggregate version of the problem with a limited number of states. The compiled decision diagram of this aggregate problem is tractable and can fit in memory. It can then be exploited by the original branch-and-bound to generate additional pruning and guide the compilation of restricted decision diagrams toward good solutions. The results of the numerical study we conducted on three combinatorial optimization problems show a clear improvement in the performance of DD-based solvers when blended with the proposed techniques. These results also suggest an approach where the aggregate dynamic programming model could be used in replacement of the relaxed decision diagrams altogether.

Weighted model counting, that is, counting the weighted number of satisfying assignments of a propositional formula, is an important tool in probabilistic reasoning. Recently, the use of projected weighted model counting (PWMC) has been proposed as an approach to formulate and answer probabilistic queries. In this work, we propose a new simplified modeling language based on PWMC in which probabilistic inference tasks are modeled using a conjunction of Horn clauses and a particular weighting scheme for the variables. We show that the major problems of inference for Bayesian Networks, network reachability and probabilistic logic programming can be modeled in this language. Subsequently, we propose a new, relatively simple solver that is specifically optimized to solve the PWMC problem for such formulas. Our experiments show that our new solver is competitive with state-of-the-art solvers on the major problems studied.

Local search is a popular technique to solve combinatorial optimization problems efficiently. To escape local minima one generally uses metaheuristics or try to design large neighborhoods around the current best solution. A somewhat more black box approach consists in using an optimization solver to explore a large neighborhood. This is the large-neighborhood search (LNS) idea that we reuse in this work. We introduce a generic neighborhood exploration algorithm based on restricted decision diagrams (DD) constructed from the current best solution. We experiment DD-LNS on two sequencing problems: the traveling salesman problem with time windows (TSPTW) and a production planning problem (DLSP). Despite its simplicity, DD-LNS is competitive with the state-of-the-art MIP approach on DLSP. It is able to improve the best known solutions of some standard instances for TSPTW and even to prove the optimality of quite a few other instances.

Conflict-Based Search is a state-of-the-art algorithm solving the Multi-Agent Path Finding problem. Given multiple agents with start and goal locations, the problem is to find a set of collision-free paths of minimal cost. Continuous Conflict-Based Search is a recent adaptation of this algorithm for continuous time and agents with physical shapes. However, an important ingredient has not been adapted to this continuous version: the Conflict Avoidance Table. It is used as a tie-breaking strategy in single-agent search phases to favor paths causing fewer conflicts with the other agents. This paper explains how the R-Tree can be used as a Conflict Avoidance Table for Continuous Conflict-Based Search. The experiments show that using the Conflict Avoidance Table can reduce the number of nodes expanded by the algorithm by a large margin. As a result, the solving time is improved proportionally and especially when using the implementation based on R-Trees as opposed to a naive implementation.

The interest in algorithms for learning optimal decision trees (ODTs) has increased significantly in recent years. These algorithms use combinatorial search to find a predictive machine learning model in the form of a tree. It was shown that ODTs can obtain better predictive performance than trees found using traditional, heuristic algorithms. In many applications where accuracy is important, however, in practice machine learning developers use forests of decision trees instead of single trees. The most popular approaches for learning forests, such as Adaboost, are heuristic in nature, and it is not clear where their good performance comes from. In an attempt to study this, a number of earlier papers developed approaches that rely on the definition of a global optimization criterion for learning forests; however, unfortunately, these papers did not present algorithms for optimizing these criteria exactly, hence leaving the value of the optimization criteria unclear. In this work, we show that by using recent techniques for learning exact ODTs, we can now also optimize forests exactly. We show the optimization gap with existing approaches and evaluate the performance of optimal decision forests using different optimization criteria compared to Adaboost. This reveals that optimal decision forests can be a good approach depending on the optimization criterion and in some cases can outperform Adaboost.

Block modeling has been used extensively in many domains including social science, spatial temporal data analysis and even medical imaging. Original formulations of the problem modeled it as a mixed integer programming problem, but were not scalable. Subsequent work relaxed the discrete optimization requirement, and showed that adding constraints is not straightforward in existing approaches. In this work, we present a new approach based on constraint programming, allowing discrete optimization of block modeling in a manner that is not only scalable, but also allows the easy incorporation of constraints. We introduce a new constraint filtering algorithm that outperforms earlier approaches, in both constrained and unconstrained settings, for an exhaustive search and for a type of local search called Large Neighborhood Search. We show its use in the analysis of real datasets. Finally, we show an application of the CP framework for model selection using the Minimum Description Length principle.

Several recent publications have studied the use of Mixed Integer Programming (MIP) for finding an optimal decision tree, that is, the best decision tree under formal requirements on accuracy, fairness or interpretability of the predictive model. These publications used MIP to deal with the hard computational challenge of finding such trees. In this paper, we introduce a new efficient algorithm, DL8.5, for finding optimal decision trees, based on the use of itemset mining techniques. We show that this new approach outperforms earlier approaches with several orders of magnitude, for both numerical and discrete data, and is generic as well. The key idea underlying this new approach is the use of a cache of itemsets in combination with branch-and-bound search; this new type of cache also stores results for parts of the search space that have been traversed partially.

Constraint Programming (CP) is a powerful paradigm for solving combinatorial problems. In CP, the user creates a model by declaring variables with their domains and expresses the constraints that need to be satisfied in any solution. The solver is then in charge of finding feasible solutions—a value in the domain of each variable that satisfies all the constraints. The discovery of solutions is done by exploring a search tree that is pruned by the constraints in charge of removing impossible values. The CP framework has the advantage of exposing a rich high-level declarative constraint language for modeling, as well as efficient purpose-specific filtering algorithms that can be reused in many problems. In this work, we harness this flexibility and efficiency for the Block Modeling problem. It is a variant of the graph clustering problem that has been used extensively in many domains including social science, spatio-temporal data analysis and even medical imaging. We present a new approach based on constraint programming, allowing discrete optimization of block modeling in a manner that is not only scalable, but also allows the easy incorporation of constraints. We introduce a new constraint filtering algorithm that outperforms earlier approaches. We show its use in the analysis of real datasets.

Decision Trees (DTs) are widely used Machine Learning (ML) models with a broad range of applications. The interest in these models has increased even further in the context of Explainable AI (XAI), as decision trees of limited depth are very interpretable models. However, traditional algorithms for learning DTs are heuristic in nature; they may produce trees that are of suboptimal quality under depth constraints. We introduce PyDL8.5, a Python library to infer depth-constrained Optimal Decision Trees (ODTs). PyDL8.5 provides an interface for DL8.5, an efficient algorithm for inferring depth-constrained ODTs. The library provides an easy-to-use scikit-learn compatible interface. It cannot only be used for classification tasks, but also for regression, clustering, and other tasks. We introduce an interface that allows users to easily implement these other learning tasks. We provide a number of examples of how to use this library.

This paper presents ddo, a generic and efficient library to solve constraint optimization problems with decision diagrams. To that end, our framework implements the branch-and-bound approach which has recently been introduced by Bergman et al., (2016) to solve dynamic programs to optimality. Our library allowed us to successfully reproduce the results of Bergman et al. for MISP, MCP and MAX2SAT while using a single generic library. As an additional benefit, our ddo library is able to exploit parallel computing for its purpose without imposing any constraint on the user (apart from memory safety). Ddo is released as an open source rust library (crate) alongside with its companion example programs to solve the aforementioned problems. To the best of our knowledge, this is the first public implementation of a generic library to solve combinatorial optimization problems with branch-and-bound MDD.

Decision trees are among the most popular classification models in machine learning. Traditionally, they are learned using greedy algorithms. However, such algorithms have their disadvantages: it is difficult to limit the size of the decision trees while maintaining a good classification accuracy, and it is hard to impose additional constraints on the models that are learned. For these reasons, there has been a recent interest in exact and flexible algorithms for learning decision trees. In this paper, we introduce a new approach to learn decision trees using constraint programming. Compared to earlier approaches, we show that our approach obtains better performance, while still being sufficiently flexible to allow for the inclusion of constraints. Our approach builds on three key building blocks: (1) the use of AND/OR search, (2) the use of caching, (3) the use of the CoverSize global constraint proposed recently for the problem of itemset mining. This allows our constraint programming approach to deal in a much more efficient way with the decompositions in the learning problem.

Segment Routing (SR) is a powerful tool to solve traffic engineering in large networks. It enables steering the traffic along any arbitrary network path while limiting scalability issues as routers do not need to maintain a global state. Mathematical programming approaches proposed so far for SR either do not scale well with the size of topology or impose a strong limit on the number of possible detours (typically at most one). Moreover they do not support Segment Routing fully by ignoring the adjacency segments. This paper leverages column generation, a widely used technique for solving large scale linear programs, combined with a novel dynamic program for solving the pricing problem. Our approach reaches near optimal solutions with gap guarantees by also computing a strong lower-bound tighter than the multi-commodity flow relaxation. It scales even on large topologies and exploits the full expressiveness of SR including adjacency segments. Our experiments compared with existing traffic engineering techniques on various topologies and demand matrices demonstrate the advantages of our approach in terms of scalability, any-time behavior and quality of the solutions.

BACKGROUND: Transcriptome analysis aims at gaining insight into cellular processes through discovering gene expression patterns across various experimental conditions. Biclustering is a standard approach to discover genes subsets with similar expression across subgroups of samples to be identified. The result is a set of biclusters, each forming a specific submatrix of rows (e.g. genes) and columns (e.g. samples). Relevant biclusters can, however, be missed when, due to the presence of a few outliers, they lack the assumed homogeneity of expression values among a few gene/sample combinations. The Max-Sum SubMatrix problem addresses this issue by looking at highly expressed subsets of genes and of samples, without enforcing such homogeneity. RESULTS: We present here the K-CPGC algorithm to identify K relevant submatrices. Our main contribution is to show that this approach outperforms biclustering algorithms to identify several gene subsets representative of specific subgroups of samples. Experiments are conducted on 35 gene expression datasets from human tissues and yeast samples. We report comparative results with those obtained by several biclustering algorithms, including CCA, xMOTIFs, ISA, QUBIC, Plaid and Spectral. Gene enrichment analysis demonstrates the benefits of the proposed approach to identify more statistically significant gene subsets. The most significant Gene Ontology terms identified with K-CPGC are shown consistent with the controlled conditions of each dataset. This analysis supports the biological relevance of the identified gene subsets. An additional contribution is the statistical validation protocol proposed here to assess the relative performances of biclustering algorithms and of the proposed method. It relies on a Friedman test and the Hochberg's sequential procedure to report critical differences of ranks among all algorithms. CONCLUSIONS: We propose here the K-CPGC method, a computationally efficient algorithm to identify K max-sum submatrices in a large gene expression matrix. Comparisons show that it identifies more significantly enriched subsets of genes and specific subgroups of samples which are easily interpretable by biologists. Experiments also show its ability to identify more reliable GO terms. These results illustrate the benefits of the proposed approach in terms of interpretability and of biological enrichment quality. Open implementation of this algorithm is available as an R package.

Multi-Valued Decision Diagrams (MDDs) are instrumental in modeling combinatorial problems with Constraint Programming.In this paper, we propose a related data structure called sMDD (semi-MDD) where the central layer of the diagrams is non-deterministic.We show that it is easy and efficient to transform any table (set of tuples) into an sMDD.We also introduce a new filtering algorithm, called Compact-MDD, which is based on bitwise operations, and can be applied to both MDDs and sMDDs.Our experimental results show the practical interest of our approach, both in terms of compression and filtering speed.

Table constraints are very useful for modeling combinatorial constrained problems, and thus play an important role in Constraint Programming (CP). During the last decade, many algorithms have been proposed for enforcing the property known as Generalized Arc Consistency (GAC) on such constraints. A state-of-the art GAC algorithm called Compact-Table (CT), which has been recently proposed, significantly outperforms all previously proposed algorithms. In this paper, we extend this algorithm in order to deal with both short supports and negative tables, i.e., tables that contain universal values and conflicts. Our experimental results show the interest of using this fast general algorithm.

Reifying a constraint c consists in associating a Boolean variable b with c such that c is satisfied if and only if b is true, which can be denoted by c^{reif}: cb. Reification is useful for logically combining constraints and counting how many reified constraints can be satisfied. Since table constraints play an important role within constraint programming, in this paper, we are interested in their reification. We introduce a filtering algorithm that allows us to establish generalized arc consistency on reified table constraints, with no spatial overhead. We also propose a flexible approach that can generally reify any subsets of constraints. We show the practical interest of our work on the Max-CSP problem and a variation of the subgraph isomorphism problem.

SDN simplifies network management by relying on declarativity (high-level interface) and expressiveness (network flexibility). We propose a solution to support those features while preserving high robustness and scalability as needed in carrier-grade networks. Our solution is based on (i) a two-layer architecture separating connectivity and optimization tasks; and (ii) a centralized optimizer called framework, which translates high-level goals expressed almost in natural language into compliant network configurations. Our evaluation on real and synthetic topologies shows that framework improves the state of the art by (i) achieving better trade-offs for classic goals covered by previous works, (ii) supporting a larger set of goals (refined traffic engineering and service chaining), and (iii) optimizing large ISP networks in few seconds. We also quantify the gains of our implementation, running Segment Routing on top of IS-IS, over possible alternatives (RSVP-TE and OpenFlow).

Bi-Objective Combinatorial Optimization problems are ubiquitous in real-world applications and designing approaches to solve them efficiently is an important research area of Artificial Intelligence. In Constraint Programming, the recently introduced bi-objective Pareto constraint allows one to solve bi-objective combinatorial optimization problems exactly. Using this constraint, every non-dominated solution is collected in a single tree-search while pruning sub-trees that cannot lead to a non-dominated solution. This paper introduces a simpler and more efficient filtering algorithm for the bi-objective Pareto constraint. The efficiency of this algorithm is experimentally confirmed on classical bi-objective benchmarks.

Everyone having used Constraint Programming (CP) to solve hard combinatorial optimization problems with a standard exhaustive Branch & Bound Depth First Search (B&B DFS) has probably experienced scalability issues. In the 2011 Panel of the Future of CP, one of the identified challenges was the need to handle large-scale problems. In this paper, we address the scalability issues of CP when minimizing a sum objective function. We suggest extending the Large Neighborhood Search (LNS) framework enabling it with the possibility of changing dynamically the objective function along the restarts. The motivation for this extended framework - called the Variable Objective Large Neighborhood Search (VO-LNS) - is solving efficiently a real-life over-constrained timetabling application. Our experiments show that this simple approach has two main benefits on solving this problem: 1) a better pruning, boosting the speed of LNS to reach high quality solutions, 2) a better control to balance or weight the terms composing the sum objective function, especially in over-constrained problems.