ABSTRACT. 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.

ABSTRACT. 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.

ABSTRACT. 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. Polynomial equations over dynamics graphs have been introduced in previous work. 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. 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.

ABSTRACT. 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 for itemsets 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 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.

ABSTRACT. Contemporary research explores the possibilities of integrating machine learning (ML) approaches with traditional combinatorial optimisation solvers. Since optimisation hybrid solvers, which combine propositional satisfiability (SAT) and constraint programming (CP), dominate recent benchmarks, it is surprising that the literature has paid limited attention to machine learning approaches for hybrid CP-SAT solvers. We identify the technique of minimal unsatisfiable subsets as promising to improve the performance of the hybrid CP-SAT lazy clause generation solver Chuffed. We leverage a graph convolutional network (GCN) model, trained on an adapted version of the MiniZinc benchmark suite. The GCN predicts which variables belong to an unsatisfiable subsets on CP instances; these predictions are used to initialise the activity score of Chuffed's Variable-State Independent Decaying Sum (VSIDS) heuristic. We benchmark the ML-aided Chuffed on the MiniZinc benchmark suite and find a robust 2.5% gain over baseline Chuffed on MRCPSP instances. This paper thus presents the first, to our knowledge, successful application of machine learning to improve hybrid CP-SAT solvers, a step towards improved automatic solving of CP models.

ABSTRACT. 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.

ABSTRACT. Mixed-integer programming (MIP) is a powerful method of solving various combinatorial optimization problems. To this end, a MIP solver employs a variety of algorithms, from greedy heuristics to exhaustive branch-and-cut search. A MIP solver's hyper-parameters, called configuration, control the behavior and interaction of all these components and, thus, have great influence on the solving performance. Recently, there has been an increasing interest in automated approaches to learn the solver's best configuration, but such research is very challenging due to extremely high computational costs of the required numerical experiments. Typically, solving a single MIP instance takes minutes or hours, and there are many dozens of parameters to tune. To address this challenge, we introduce MipConfigBench containing pre-computed solve data for a variety of MIP instances solved with SCIP, exhaustively sampled under a number of different configurations. In total, our dataset contains the results from over 50 million MIP solves. Our intention is to facilitate future research on algorithm configuration, algorithm selection, parallel algorithm portfolios, and related techniques, by replacing solves with simple queries to the dataset. We demonstrate the usefulness of the constructed dataset by using it in SMAC to successfully tune SCIP.

ABSTRACT. 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 in-stances 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.

ABSTRACT. We study optimization problems where the objective function is modeled through 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 networks. We therefore study how ensembles of neural networks 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 benchmark real-world data set show that the two-stage model greatly outperforms a standard adaptation of previously proposed MIP formulations of single neural network models.

ABSTRACT. 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.

ABSTRACT. In the field of machine learning the focus has been largely on the development of methods that can achieve increasingly high classification and prediction accuracies. In the past couple of years the interpretability of classification and prediction methods has gained attention as well. Motivated by applications in bioinformatics, where understanding the input-output relationship is at least as important as obtaining good predictions, this work focuses on the development of a method that learns the relationship between binary input- and output data, where the input-output relationship is described by a Boolean phrase in disjunctive normal form (DNF). Existing methods have been shown to work very well on small datasets and give intuitive results, but run into computational issues for datasets with a large number of samples and input features. With the recent advent of big data, particularly in the field of bioinformatics, there is a need for a faster solution algorithm. The algorithm proposed here allows for the analysis of datasets with tens of thousands of samples and features.

ABSTRACT. Recommender Systems have become the backbone of personalized services to 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. While a large set of items is desirable to increase item diversity, the need for rapid experimentation and to minimize the time and the amount of data required to train machine learning models favors a smaller set of items. 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.