ABSTRACT. TBA

ABSTRACT. Given a user who asks why an algorithmic decision did not satisfy some conditions, a counterfactual explanation takes the form of a minimally perturbed input that would have led to a decision satisfying the user's conditions. Building on recent work, this paper develops techniques to generate counterfactual explanations for linear discrete constrained optimization problems. These explanations take the form of a minimally perturbed objective vector that induces an optimal solution satisfying the newly stated user constraints. Drawing inspiration from the inverse combinatorial optimization literature, we introduce a novel non-convex quadratic programming algorithm to generate such explanations. Furthermore, we develop conditions for the existence of an explanation, addressing a limitation of past approaches. Finally, we discuss several future directions for explanations in discrete optimization such as actionable and sparse explanations.

ABSTRACT. We introduce a column elimination procedure for the capacitated vehicle routing problem. In contrast to column generation, which works with a restricted set of columns (variables) to which columns are added, column elimination uses a relaxed set of columns from which infeasible columns are removed. Our procedure maintains a decision diagram to represent the relaxed set of columns, over which we define a constrained network flow. The optimal solution corresponds to a collection of paths in the decision diagram, and yields a dual bound. We remove infeasible paths from the diagram to iteratively strengthen the relaxation. The network flow model can be solved as a linear program with a conventional solver or via a Lagrangian relaxation. To solve the Lagrangian subproblem more efficiently, we implement a special successive shortest paths algorithm. We introduce several cutting planes to strengthen the dual bound, and demonstrate how these can exploit the structure of the decision diagram. We experimentally compare the bounds from column elimination with those from column generation for capacitated vehicle routing problems.

ABSTRACT. The Circuit constraint is useful to model many combinatorial problems in Constraint Programming. CP solvers extended with Belief Propagation, such as MiniCPBP, require that constraints be equipped with weighted counting algorithms in order to propagate probability mass functions over domains. This is not yet the case for Circuit. To this purpose we introduce a probabilistic sampling algorithm to count Hamiltonian cycles in a weighted graph. We show that our resulting estimator is unbiased, measure its empirical accuracy, and evaluate its impact on search performance.

ABSTRACT. Weighted model counting (WMC) is an extension of propositional model counting with applications to probabilistic inference and other areas of artificial intelligence. In recent experiments, WMC algorithms perform similarly overall but with significant differences on specific subsets of benchmarks. A good understanding of the differences in the performance of algorithms requires identifying key characteristics that favour some algorithms over others. In this paper, we introduce a random model for WMC instances with a parameter that influences primal treewidth — the parameter most commonly used to characterise the difficulty of an instance. We then use this model to experimentally compare the performance of WMC algorithms c2d, Cachet, d4, DPMC, and miniC2D. Using these random instances, we show that the easy-hard-easy pattern is different for algorithms based on dynamic programming and algebraic decision diagrams than for all other solvers. We also show how all WMC algorithms scale exponentially with respect to primal treewidth and how this scalability varies across algorithms and densities. Finally, we combine insights from experiments involving both random and competition instances to determine how the best-performing WMC algorithm varies depending on clause density and primal treewidth.

ABSTRACT. Motivated by identifying equations to automate the discovery of conjectures about sharp bounds on combinatorial objects, we introduce a CP model to acquire Boolean-arithmetic equations from a table providing sharp bounds for various combinations of parameters.

Boolean-arithmetic expressions consist of simple arithmetic conditions (SAC) connected by a single commutative operator such as `and', `or', `xor' or `+'. Each SAC can use up to three variables, two coefficients, and an arithmetic function such as `+', `-', `times', `floor', `mod' or `min'. We enhance our CP~model in the following way to limit the search space: (i) We break the symmetries linked to multiple instances of similar SACs in the same expression. (ii) We prevent the creation of SAC that could be simplified away.

We identify several use cases of our CP model for acquiring Boolean-arithmetic equations and show its applicability for learning sharp bounds for eight types of combinatorial objects as digraphs, forests, and partitions.

ABSTRACT. This invited talk aims to provide a comprehensive overview of the latest applications and ongoing research directions of Operations Research (OR) and Artificial Intelligence (AI) in the travel industry. We will discuss the main challenges faced by the travel industry actors (such as airlines, hotels, travel agencies among others) and how OR and AI is being used during the whole customer journey. This includes applications from the inspiration phase (where and when to travel?), search and booking (which flights to propose? which hotels? how to price tickets? Which alternatives to recommend?), the experience at the airports and during the trip (check-in, dealing with cancellations and delays), and finally the post travel activities (travel expenses for business trips, or post trip feed.

In terms of techniques, we will discuss discrete optimization problems, unsupervised and supervised machine learning, generative models, reinforcement learning, touching generic application areas such as NLP (natural language processing), Computer Vision, Recommender Systems among others.

ABSTRACT. Wildlife trafficking (WT), the illegal trade of wild fauna, flora, and their parts, directly threatens biodiversity and conservation of trafficked species, while also negatively impacting human health, national security, and economic development. Wildlife traffickers obfuscate their activities in plain sight, leveraging legal, large, and globally linked transportation networks. To complicate matters, defensive interdiction resources are limited, datasets are fragmented and rarely interoperable, and interventions like setting checkpoints place a burden on legal transportation. As a result, interpretable predictions of which routes wildlife traffickers are likely to take can help target defensive efforts and understand what wildlife traffickers may be considering when selecting routes. We propose a data-driven model for predicting trafficking routes on the global commercial flight network, a transportation network for which we have some historical seizure data and a specification of the possible routes that traffickers may take. While seizure data has limitations such as data bias and dependence on the deployed defensive resources, this is a first step towards predicting wildlife trafficking routes on real-world data. Our seizure data documents the planned commercial flight itinerary of trafficked and successfully interdicted wildlife. We aim to provide predictions of highly-trafficked flight paths for known origin-destination pairs with plausible explanations that illuminate how traffickers make decisions based on the presence of criminal actors, markets, and resilience systems. We propose a model that first predicts likelihoods of which commercial flights will be taken out of a given airport given input features, and then subsequently finds the highest-likelihood flight path from origin to destination using a differentiable shortest path solver, allowing us to automatically align our model's loss with the overall goal of correctly predicting the full flight itinerary from a given source to a destination. We evaluate the proposed model's predictions and interpretations both quantitatively and qualitatively, showing that the predicted paths are aligned with observed held-out seizures, and can be interpreted by policy-makers.

ABSTRACT. In a context of labor shortage and strong global competition for talent, salary management is becoming a critical issue for companies wishing to attract, engage and retain qualified employees. This paper presents a multi-objective optimization model to balance the internal equity, external equity and cost tradeoffs associated with the design of salary structures. Solutions are generated to estimate and explore the Pareto front using real compensation data from a unionized establishment in the public sector. Our work shows the interest of using combinatorial optimization techniques in the generation of salary structures.

ABSTRACT. Nowadays, constellations of satellites have to deal with heterogeneous and complex observation requests, such as one-shot, video, stereoscopic, and periodic requests. In this paper, we consider the problem of scheduling these requests in order to maximize a global reward. To solve this problem, we propose two Large Neighborhood Search algorithms that exploit a problem decomposition. These algorithms explore large neighborhoods respectively based on heuristic search and Constraint Programming. The experiments performed on instances generated with real constellation features and weather data show that the approaches improve the state of the art.

ABSTRACT. We consider a steelmaking-continuous casting (SCC) scheduling problem in the steel industry, which is a variant of the hybrid flow shop scheduling problem subject to practical constraints. Recently, Hong et al. (2022) developed an algorithm, called Iterated Greedy Matheuristic (IGM), in which a Mixed Integer Programming (MIP) model was proposed and its subproblems are iteratively solved to improve the solution. We propose a new constraint programming (CP) formulation for the SCC scheduling problem and develop an algorithm, called Iterated Greedy CP (IGC), which uses the framework of IGM but replaces the MIP model with our CP model. When we solve the CP subproblems iteratively, we also refine them by adding appropriate constraints, reducing the domains of the variables, and giving the variables hints derived from the current solution. From computational experiments in various settings, we show that IGC implemented with an open-source CP solver can be competitive with IGM running on a commercial MIP solver.

ABSTRACT. We present a new variation of the Stochastic Dual Dynamic Programming (SDDP) algorithm for solving multistage convex stochastic programming problems with the aim to obtain optimal operational strategies for the battery storage usage of residential households. We developed a lightweight algorithm that could be executed on edge computing at the household level.

ABSTRACT. We propose a method for maximum likelihood estimation of path choice model parameters and arc travel time using data of different levels of granularity. Hitherto these two tasks have been tackled separately under strong assumptions. Using a small example, we illustrate that this can lead to biased results. Results on both real (New York yellow cab) and simulated data show strong performance of our method compared to existing baselines.

ABSTRACT. We propose a data-driven regression-based joint chance constraint model for scheduling workover rigs under uncertainty. The uncertainty refers to the duration of the workover activities, which we estimate employing text mining, clustering and regression to a real database. The proposed model is capable of providing fleet sizing and scheduling decisions that are considerably more resilient to uncertainties and hinder the need for frequent and costly rescheduling.

ABSTRACT. This work proposes a fast solution algorithm to a fundamental data science problem, namely to identify Boolean rules in disjunctive normal form (DNF) that classify samples based on binary features. The algorithm is an explainable machine learning method: it provides an explicit input-output relationship. It is based on hypothesis tests through confidence intervals, where the used test statistic requires nothing more than counting samples that contain a certain set of features.