The Multiple Constant Multiplication (MCM) problem arises in many applications such as, for example, digital signal processing or deep neural network inference. Given a set T of target constants, the goal of MCM is to find the most efficient way for multiplying an input number with every constant in T, where multiplications are realized through bit-shifts and additions, and where intermediate results may be shared to produce different target constants. In this paper, we first introduce a basic Constraint Programming (CP) model to solve MCM. Then, we introduce symmetry breaking rules and a global constraint to ensure them. We experimentally evaluate our approach on a widely used benchmark extracted from a collection of digital filter designs. We show that the basic CP model is competitive with state-of-the-art Integer Linear Programming (ILP) and SAT models, and that the addition of our global symmetry breaking constraint allows us to clearly outperform all other existing approaches on the considered benchmark.

There are numerous NP-hard combinatorial problems which involve searching for an undirected graph satisfying a certain property. One way to solve such problems is to translate a problem into an instance of the boolean satisfiability (SAT) or constraint satisfaction (CSP) problem. Such reduction usually can give rise to numerous isomorphic representations of the same graph. One way to reduce the search space and speed up the search under these conditions is to introduce symmetrybreaking predicates. In this paper we introduce three novel and practically effective symmetry-breaking predicates for an undirected connected graph search based on breadth-first search (BFS) enumeration and compare with existing symmetry-breaking methods on several graph problems.

Algorithms are often evaluated on randomly generated instances to study scale-up properties with respect to features such as the size, for example. Also, machine learning based approaches often train models on randomly generated instances as they need large sets of training instances. In this paper, we consider the Euclidean Travelling Salesman Problem with Time Windows (TSPTW), and we study the impact of parameters used to randomly generate TSPTW instances on hardness and feasibility. We first consider the decision version of the problem, where feasibility depends on start and end times of time windows. We introduce two parameters, α and β, for controlling the tightness of the time horizon and the time windows. We show that instance hardness is related to a phase transition phenomenon: as we increase α and β, we pass from an unfeasible region (where almost all generated instances have no solution) to a feasible region (where almost all generated instances have solutions), and the hardest instances are located within the transition zone. We formally relate this transition zone with respect to α and β, thus allowing us to control hardness and feasibility when randomly generating instances. Then, we study the optimization problem, the goal of which is to find the smallest tour that satisfies all time windows. We show that the empirical hardness is still related to the phase transition: hardness increases when moving from the infeasible region to the transition zone, as in the decision problem. However, unlike the decision problem, some hard instances are also located in the feasible region where instances are very loosely constrained.

This paper deals with the anonymous multi-agent path finding (MAPF) problem for a team of tethered robots. The goal is to find a set of non-crossing paths such that the makespan is minimal. A difficulty comes from the fact that a safety distance must be maintained between two robots when they pass through the same subpath, to avoid collisions and cable entanglements. Hence, robots must be synchronized and waiting times must be added when computing the makespan. We show that bounds can be efficiently computed by solving linear assignment problems. We introduce a variable neighborhood search method to improve upper bounds, and a Constraint Programming model to compute optimal solutions. We experimentally evaluate our approach on three different kinds of instances.

We introduce a new Multi-Agent Path Finding (MAPF) problem which is motivated by an industrial application. Given a fleet of robots that move on a workspace that may contain static obstacles, we must find paths from their current positions to a set of destinations, and the goal is to minimise the length of the longest path. The originality of our problem comes from the fact that each robot is attached with a cable to an anchor point, and that robots are not able to cross these cables. We formally define the Non-Crossing MAPF (NC-MAPF) problem and show how to compute lower and upper bounds by solving well known assignment problems. We introduce a Variable Neighbourhood Search (VNS) approach for improving the upper bound, and a Constraint Programming (CP) model for solving the problem to optimality. We experimentally evaluate these approaches on randomly generated instances.

We consider a RCPSP (resource constrained project scheduling problem), the goal of which is to schedule jobs on machines in order to minimise job tardiness. This problem comes from a real industrial application, and it requires an additional constraint which is a generalisation of the classical cumulative constraint: jobs are partitioned into groups, and the number of active groups must never exceeds a given capacity (where a group is active when some of its jobs have started while some others are not yet completed). We first study the complexity of this new constraint. Then, we describe an Ant Colony Optimisation algorithm to solve our problem, and we compare three different pheromone structures for it. We study the influence of parameters on the solving process, and show that it varies from an instance to another. Hence, we identify a subset of parameter settings with complementary strengths and weaknesses, and we use a per-instance algorithm selector in order to select the best setting for each new instance to solve. We experimentally compare our approach with a tabu search approach and an exact approach on a data set coming from our industrial application.

We introduce the exactCover global constraint dedicated to the exact cover problem, the goal of which is to select subsets such that each element of a given set belongs to exactly one selected subset. This NP-complete problem occurs in many applications, and we more particularly focus on a conceptual clustering application. We introduce three propagation algorithms for exactCover, called Basic, DL, and DL+: Basic ensures the same level of consistency as arc consistency on a classical decomposition of exactCover into binary constraints, without using any specific data structure; DL ensures the same level of consistency as Basic but uses Dancing Links to efficiently maintain the relation between elements and subsets; and DL+ is a stronger propagator which exploits an extra property to filter more values than DL. We also consider the case where the number of selected subsets is constrained to be equal to a given integer variable k, and we show that this may be achieved either by combining exactCover with existing constraints, or by designing a specific propagator that integrates algorithms designed for the NValues constraint. These different propagators are experimentally evaluated on conceptual clustering problems, and they are compared with state-of-the-art declarative approaches. In particular, we show that our global constraint is competitive with recent ILP and CP models for mono-criterion problems, and it has better scale-up properties for multi-criteria problems.

In the context of Connected and Smart Cities, the need to predict short term traffic conditions has led to the development of a large variety of forecasting algorithms. In spite of various research efforts, there is however still no clear view of the requirements involved in network-wide traffic forecasting. In this paper, the ability of several state-of-the-art methods to forecast the traffic flow at each road segment is studied. Some of the multivariate methods use the information of all sensors to predict traffic at a specific location, whereas some others rely on the selection of a suitable subset. In addition to classical methods, this paper studies the advantage of learning this subset by using a new variable selection algorithm based on time series graphical models and information theory. This method has already been successfully used in natural science applications with similar goals, but not in the traffic community. A contribution is to evaluate all these methods on two real-world datasets with different characteristics and to compare the forecasting ability of each method in both contexts. The first dataset describes the traffic flow in the city center of Lyon (France), which exhibits complex patterns due to the network structure and urban traffic dynamics. The second dataset describes inter-urban freeway traffic on the outskirts of the French city of Marseille. Experimental results validate the need for variable selection mechanisms and illustrate the complementarity of forecasting algorithms depending on the type of road and the forecasting horizon.

The subgraph isomorphism problem involves deciding whether a copy of a pattern graph occurs inside a larger target graph. The non-induced version allows extra edges in the target, whilst the induced version does not. Although both variants are NP-complete, algorithms inspired by constraint programming can operate comfortably on many real-world problem instances with thousands of vertices. However, they cannot handle arbitrary instances of this size. We show how to generate "really hard" random instances for subgraph isomorphism problems, which are computationally challenging with a couple of hundred vertices in the target, and only twenty pattern vertices. For the non-induced version of the problem, these instances lie on a satisfiable / unsatisfiable phase transition, whose location we can predict; for the induced variant, much richer behaviour is observed, and constrainedness gives a better measure of difficulty than does proximity to a phase transition. These results have practical consequences: we explain why the widely researched "filter / verify" indexing technique used in graph databases is founded upon a misunderstanding of the empirical hardness of NP-complete problems, and cannot be beneficial when paired with any reasonable subgraph isomorphism algorithm.

We describe Constraint Programming (CP) models to solve a cryptanalytic problem: the chosen key differential attack against the standard block cipher AES. We show that CP solvers are able to solve these problems quicker than dedicated cryptanalysis tools, and we prove that a solution claimed to be optimal in two recent cryptanalysis papers is not optimal by providing a better solution.

The maximum common subgraph problem is an NP-hard problem which is very difficult to solve with exact approaches. To speed up the solution process, we may decompose it into independent subproblems which are solved in parallel. We describe a new decomposition method which exploits the structure of the problem to decompose it. We compare this structural decomposition with domain-based decompositions, which basically split variable domains. Experimental results show us that the structural decomposition leads to better speedups on two classes of instances, and to worse speedups on one class of instances.

We propose in this paper a generic algorithm based on ant colony optimization to solve multi-objective optimization problems. The proposed algorithm is parameterized by the number of ant colonies and the number of pheromone trails. We compare different variants of this algorithm on the multi-objective knapsack problem. We compare also the obtained results with other evolutionary algorithms from the literature.

We describe a novel incomplete approach for solving constraint satisfaction problems (CSPs) based on the ant colony optimization (ACO) metaheuristic. The idea is to use artificial ants to keep track of promising areas of the search space by laying trails of pheromone. This pheromone information is used to guide the search, as a heuristic for choosing values to be assigned to variables. We first describe the basic ACO algorithm for solving CSPs and we show how it can be improved by combining it with local search techniques. Then, we introduce a preprocessing step, the goal of which is to favor a larger exploration of the search space at a lower cost, and we show that it allows ants to find better solutions faster. Finally, we evaluate our approach on random binary problems.

A standard approach to solving mixed integer linear programs is to perform a global branch and bound search through all possible combinations. Due to the hardness of the problem, this search must be closely controlled by a constraint solver which uses constraints to prune the search space in an a priori way. In this paper, one defines a new domain reduction solver which uses in a cooperative way a set of linear programming solvers. The idea is to compute the actual range of values of the integer variables with respect to the continuous relaxation of the problem, and then narrow these domains to the closest integer interval. This narrowing is iteratively performed until a fixed point is reached where all domains are bound by integer values which belong to the continuous relaxation of the problem. This fixed point corresponds to a new partial consistency, which is stronger than the continuous relaxation and allows one to solve MILPs more efficiently.