ABSTRACT. In recent years, there has been a growing interest in employing learning- based approaches for solving combinatorial problems, either in an end-to-end manner or in conjunction with traditional optimization algorithms. In both sce- narios, the challenge lies in encoding the targeted combinatorial problems into a structure compatible with the learning algorithm. Many existing works have pro- posed problem-specific representations, often in the form of a graph, to leverage the advantages of graph neural networks. However, these approaches often lack generality, as the representation cannot be easily transferred from one combinato- rial problem to another. While some attempts have been made to bridge this gap, they still offer only partial generality. In response to this challenge, this paper advocates for progress towards a fully generic representation of combinatorial problems for learning-based approaches. The approach we propose involves con- structing a graph by breaking down any constraint of a combinatorial problem into an abstract syntax tree and expressing relationships (e.g., a variable involved in a constraint) through edges. Furthermore, we introduce a GNN architecture capable of efficiently learning from this representation. The tool provided oper- ates on combinatorial problems expressed in the XCSP3 format, handling all the constraints available in the 2023 mini-track competition. Experimental results on five combinatorial problems demonstrate that our architecture achieves perfor- mance close to dedicated architectures while maintaining generality. Our code and trained models are publicly available at https://github.com/jardinetsouffleton/Graph-Representation

ABSTRACT. A fundamental challenge when modeling combinatorial optimization problems is that often multiple sub-objectives need to be weighted against each other, but it is not clear how much weight each sub-objective should be given: consider routing problems with different definitions of distance, or planning problems with different definitions of costs, where the importance of these costs is not known a priori. In recent work, it has been proposed to use machine learning algorithms from the domain of structured output prediction to learn such weights from examples of desirable solutions. However, until now such techniques were only evaluated on relatively simple optimization problems. We propose and evaluate three techniques that make it feasible to apply the structured perceptron on NP-hard optimization problems: 1) using heuristic solving methods during the learning process, 2) solving well-chosen satisfaction problems, 3) caching solutions computed during the learning process and reusing them. Experiments confirm the validity and speed-ups of these techniques, enabling structured output learning on larger combinatorial problems than before.

ABSTRACT. In recent years, deep neural networks have demonstrated remarkable performance in addressing combinatorial optimization challenges. The expressive power of graph neural networks combined with Reinforcement Learning enabled learning heuristics that rival or even surpass conventional methods. Such advancements have paved the way for neural combinatorial optimization (NCO), an emerging paradigm that enables end-to-end heuristic learning without the reliance on expert knowledge. In this paper, we propose an NCO approach to learn heuristics for the vast family of combinatorial optimization problems defined on $K$-partite hypergraphs, including multi-dimensional assignment or scheduling problems. Central to our approach is the ability to represent sophisticated functions on $K$-partite hypergraphs, using a novel family of neural networks. We show that our heuristic competes with other heuristics in comparable settings, and that our method can also be applied to more complex real-life assignment and scheduling problems.

ABSTRACT. Algorithm selection is a class of meta-algorithms that has emerged as a crucial approach for solving complex combinatorial optimization problems, as evidenced by its application in the context of Boolean Satisfiability and Constraint Programming. Successful algorithm selection involves navigating a diverse landscape of solvers, each designed with distinct heuristics and search strategies. It is a classification problem in which statistical features of a problem instance are used to select the algorithm that should tackle it most efficiently. However, minimal attention has been given to investigating algorithm selection decisions. This work presents a framework for iterative feature selection and explainable multi-class classification in Algorithm Selection for the Capacitated Lot Sizing Problem (CLSP). The CLSP is a combinatorial optimization problem widely studied with important industrial applications. The framework reduces the features considered by the machine learning approach and uses SHAP analysis to investigate their contribution to the selection. The analysis shows which instance type characteristics positively affect the relative performance of a heuristic. The approach can be used to improve the algorithm selection's transparency and inform the developer of an algorithm's weak and strong points. The experimental analysis shows that the framework selector provides valuable insights with a narrow optimality gap close to a parallel deployment of the heuristic set. Evaluating the framework on a test set of instances considerably bigger than the training ones showed that both the selection process and its explanations generalize well on unseen data outside the training distribution.

ABSTRACT. Deep generative models excel at replicating the mechanisms that generate a specific set of data. However, learning the underlying constraints preventing the generation of forbidden data poses a challenge. Recently, RL-Tuner, a reinforcement learning framework designed for the ad hoc fine-tuning of a neural model to adhere to given constraints, was enhanced to learn from the output of two constraint programming models. The first model computes a score representing the degree of constraint violation from the currently generated token while the second model provides the marginal probability of that token being generated if no additional violation is allowed. In this paper, we significantly enhance the latter framework in three ways. First, we propose a simplified architecture that requires only a single constraint programming model. Second, we evaluate constraint violations in a more accurate and consistent manner. Third, we propose a reward signal based on belief propagation on this new model that further improves performance. Our experiments, conducted on the same learning task of music generation, demonstrate that our approach surpasses the previous framework both in terms of convergence speed during training and in post-training accuracy. Additionally, our approach exhibits superior generalization to longer sequences than those used during training.

ABSTRACT. Proof logging in constraint programming is an approach to certifying a conclusion reached by a solver. To allow for this, different propagators must be augmented to produce justifications for any inferences they make, so that an independent proof checker can certify correctness. The Circuit constraint is used to enforce a Hamiltonian cycle on a set of vertices, e.g. for vehicle routing. Maintaining consistency for the Circuit constraint is hard, so various ad-hoc propagation techniques have been devised and implemented in solvers. We show that standard Circuit constraint inference rules can be efficiently justified within a pseudo-Boolean proof system (VeriPB), either by using a simple sequence of cutting planes steps or through a conditional counting argument.

ABSTRACT. The reduced cost filtering is a technique that consists in filtering a constraint using the reduced cost of a linear program that encodes this constraint. Sellmann [13] shows that while doing a Lagrangian relaxation of a constraint, suboptimal Lagrange multipliers can provide more filtering than optimal ones. Boudreault and Quimper [5] make an algorithm that locally alters the Lagrange multipliers for the WeightedCircuit constraint to enhance filtering and achieve a speedup of 30%. We seek to design an algorithm like Boudreault and Quimper, but for the AtMostNValue constraint. Based on the work done by Cambazard and Fages [6] on this constraint, we use a subgradient algorithm which takes into consideration the reduced cost to boost the Lagrange multipliers in the optimal filtering direction. We test our methods on the dominating queens and the p-median problem. On the first, we record a speed up of 72% on average. On the second, there are three classes of instances. On the first two, we have an average speed up of 33% and 8%. On the hardest class, we find up to 13 better solutions than the previous algorithm on the 30 instances in the class.

ABSTRACT. Domain filtering techniques such as Generalized Arc Consistency (GAC) are powerful tools to prune partially inconsistent assignments in a branch-and-prune scheme. Although such techniques are usually applied to exact approaches, we show that metaheuristic algorithms can benefit from domain filtering. In this paper, we propose a variation of the well-known AC3 algorithm that iteratively approximates GAC over the structural information of the constraint network. We integrate the algorithm with an interval-based Differential Evolution (DE) to tackle numerical constrained global optimization problems. Our method consists of a hybrid approach: at first, the interval-based DE iteratively explores the search domain generating a population of interval boxes; then, these boxes are pruned by the local consistency algorithm; at last, a real-based black box DE is used as a local search within each box. The experimental results, over a subset of COCONUT Benchmark instances with up to 100 dimensions, show that the use of the proposed domain filtering to prune the boxes can improve the quality of the solutions by 37.15%, at the cost of 7.82% in processing time. The results indicate the benefits of integrating constraint propagation techniques and metaheuristic algorithms to tackle optimization problems.

ABSTRACT. Constraint programming (CP) has become increasingly prevalent in recent years for performing pattern mining tasks, particularly on binary datasets. While numerous CP models have been designed for mining on binary data, there does not exist any model designed for mining on numerical datasets. Therefore these kinds of datasets need to be pre-processed to fit the existing methods. Afterward a post-processing is also required to recover the patterns into a numerical format. This paper presents two CP approaches for mining closed interval patterns directly from numerical data. Our proposed models seamlessly execute pattern mining tasks without any loss of information or the need for pre- or post-processing steps. Experiments conducted on different numerical datasets demonstrate the effectiveness of our proposed CP models compared to previous declarative methods.

ABSTRACT. Planers in different industries use optimization software for decision-making. In numerous practical applications, these optimization tools are often not readily adjustable or configurable by end users due to limited knowledge, resources, or the required investment to consistently make such customizations. As a result, planners frequently adjust the solutions obtained from software based on implicit internal operational rules and preferences to make them feasible in practice. These practices may differ across various business units and subsidiaries. One can leverage data-driven methods to learn and embed implicit side constraints as soft constraints in a mixed integer linear program (MILP) to ensure that such rules can be learned and systematically incorporated into optimization models. These customization constraints can be created from machine learning models trained using previously implemented solutions. To this end, we extend a data-driven constraint customization framework in the literature developed to extract constraints in the form of a traditional linear regression model to the case when constraints take the form of decision trees. This allows us to learn and incorporate customization constraints non-linearly or logically. Experiments were conducted on the knapsack and nurse rostering problems, where various combinations of hidden operational rules were simulated to demonstrate the data-driven constraint customization value of this dion framework. The solutions obtained by our proposed solution framework suggest that it can effectively adjust the solutions based on the constraints extracted from historical solutions. The customization constraints that take the form of decision trees generally outperform those based on linear regression models, especially when part of the decision model comprises discrete variables.

ABSTRACT. We present BiOptSat, an approach to exact bi-objective optimization under Pareto optimality. BiOptSat builds on algorithms for maximum satisfiability (MaxSAT) and makes incremental use of a solver for propositional satisfiability (SAT). It allows for both finding the non-dominated set (with a representative solution for each element) and enumerating all Pareto-optimal solutions of NP-hard bi-objective optimization problems encoded in propositional logic. BiOptSat constitutes an algorithmic framework which can be instantiated in multiple ways. In addition to describing the algorithm itself, we provide an open-source implementation and an empirical evaluation, showing that BiOptSat outperforms competitors on several real-world domains from the literature.

ABSTRACT. Multi-objective optimization problems are widespread in real-world scenarios, as multiple conflicting criteria must be considered simultaneously. As such, a multitude of optimal solutions exist due to the numerous possible trade-offs. One potential strategy for addressing such problems involves enumerating the entire Pareto front, from which the decision maker (DM) can choose its preferred solution. However, this quickly becomes impractical due to the typically large number of Pareto optimal solutions, which would take a long time to compute and overwhelm the user. Multiple studies have focused on identifying a subset of the Pareto front that satisfies certain criteria like coverage, uniformity, and so on. However, all these methods operate without considering prior knowledge or preferences of the DM. This could potentially result in a set of low-quality solutions, not reflecting the DM’s goals. We fill this gap by introducing the problem of finding top-k non-dominated solutions according to a DM’s ranking over objectives, aiming to provide a limited set of only high-quality solutions. This ranking, being used as lexicographic ordering, provides the prior knowledge, while the k value restricts the number of solutions that will be shown. We discuss how existing methods for Pareto enumeration do not fit, and propose two new algorithms: FI and FWI. As our experimental evaluation shows, our proposed approaches are able to enumerate top-k lexicographically ordered non-dominated solutions more efficiently than existing methods, especially when this part of the Pareto front is dense.

ABSTRACT. A key advantage of cloud computing is the ability to outsource computations, liberating users from the limitations of resource-constraint devices. The transition to cloud outsourcing, however, raises serious privacy and security concerns as users typically lose control over data that may otherwise contain sensitive or proprietary information. In this work, we address the challenge of obfuscating SAT instances prior to outsourcing. We improve upon previous obfuscation methods by creating more compact and easier to outsource obfuscated formulas. These formulas exhibit a distinctive structure consisting of a CNF part containing disjunctions of XORs, followed by additional XOR constraints. Our study of these special XOR-CNF formulas reveals that state-of-the-art SAT solvers scale exponentially on them, emphasizing the need for new techniques that combine SAT solving with built-in XOR support. Further investigation of the runtime behavior on these formulas have led to a surprising discovery regarding the shattering of the solution space.

ABSTRACT. Abstract: Most practically relevant discrete optimisation problems are NP-hard. When such problems are also complex and large-scale, there is a great risk that state-of-the-art optimisation solvers will fail to solve them. In some cases, the use of decomposition-based methods can make a significant difference and allow you to solve challenging problems within a reasonable time frame. Decomposition means making a reformulation of a problem into a set of simpler problems that are typically solved by an iterative scheme to produce a solution to the original problem. The purpose is to distribute the computational burden of the original problem onto the simpler ones in a way that pays off with respect to total solution time. Critical for obtaining this is to exploit problem structure in the decomposition and to design an efficient solution scheme for the simpler problems. In this overview talk, I will address Dantzig-Wolfe decomposition and logic-based Benders decomposition and give some examples of method development and the impact of applying decomposition for some practical applications.

Bio: Elina Rönnberg is a Senior Associate Professor in Optimisation at the Department of Mathematics, Linköping University, where she leads the Mathematics and algorithms for intelligent decision-making group. She has experience from working in both industry and academia. Her research is in discrete optimisation, with a special interest in decomposition methods and applications in scheduling and resource allocation. The applied projects are often carried out in collaboration with industry. Current application areas include air traffic management, electric vehicle routing, and the design of electronic systems in aircraft. Contributions to decomposition methods include Dantzig-Wolfe decomposition, Lagrangian relaxation, column generation for integer programs, and logic-based Benders decomposition.

ABSTRACT. Clustering is an unsupervised learning task that aims to partition data into a set of clusters. In many applications, these clusters correspond to real-world constructs (e.g. electoral districts) whose benefit can only be attained by groups when they reach a minimum level of representation (e.g. 50\% to elect their desired candidate). This paper considers the problem of performing k-means and k-medians clustering while ensuring groups (e.g. demographic groups) have that minimum level of representation in a specified number of clusters. We formulate the problem through a mixed-integer optimization framework and present an alternating minimization algorithm, called MiniReL, that directly incorporates the fairness constraints. While incorporating the fairness criteria leads to an NP-Hard assignment problem within the algorithm, we provide computational approaches that make the algorithm practical even for large datasets. Numerical results show that the approach is able to create fairer clusters with practically no increase in the clustering cost across standard benchmark datasets.

ABSTRACT. Statistical parity metrics have been widely studied and endorsed in the AI community as a means of achieving fairness, but they suffer from at least two weaknesses. They disregard the actual welfare consequences of decisions and may therefore fail to achieve the kind of fairness that is desired for disadvantaged groups. In addition, they are often incompatible with each other, and there is no convincing justification for selecting one rather than another. This paper explores whether a broader conception of social justice, based on optimizing a social welfare function (SWF), can be useful for assessing various definitions of parity. We focus on the well-known alpha fairness SWF, which has been defended by axiomatic and bargaining arguments over a period of 70 years. We analyze the optimal solution and show that it can justify demographic parity or equalized odds under certain conditions, but frequently requires a departure from these types of parity. In addition, we find that predictive rate parity is of limited usefulness. These results suggest that optimization theory can shed light on the intensely discussed question of how to achieve group fairness in AI.

ABSTRACT. Electric buses serve as a key leverage in mitigating the transportation sector's carbon footprint. However, they pose a challenge, requiring transit agencies to adapt to a new operational approach. In particular, the assignment of buses to trips is more complex because it must consider the planning of the recharging operations. Unlike diesel buses, electric buses have less autonomy and take longer to refuel. In this paper, we address the assignment of electric buses to trips and the scheduling of charging events, taking into account parking constraints at the depot (a novelty in the literature). These constraints are particularly relevant in countries such as Canada where the buses are parked indoors to shelter them from harsh winter conditions. This problem, called the electric Bus Assignment Problem with Parking Constraints (eBAP-PC), is a feasibility problem. We propose a Constraint Programming model to solve it and compare it to mixed-integer linear programming approaches. In particular, we show its benefits for solving this problem with a one-day horizon and minimum end-of-day charge level constraints.

ABSTRACT. We consider a waste collection problem with intermediate disposal facilities to accommodate the usage of smaller, but more sustainable vehicles, with less capacity than the traditional waste collecting trucks. The optimization problem consists in determining the locations to place the collection points and the routes of a capacitated collection vehicle that visits these locations. We first present a mixed-integer linear programming formulation that exploits the sparsity of the road network. To efficiently solve practical instances, we propose a Benders decomposition approach in which a set covering problem to select the collection points is solved in the master problem and a capacitated vehicle routing problem with intermediate facilities to determine the routes and price the set covering solution is solved in the sub problem. We show a way to derive valid Benders cuts when solving the Benders sub problem with column generation and propose a heuristic Benders approach that provides better solutions for larger instances and approximated lower bounds to assess the quality of the obtained solutions.

ABSTRACT. Ridesharing is an innovative on-demand transport service which provide convenient and cost-effective travel options for diverse population segments. This service has the potential to mitigate congestion and pollution by increasing vehicle occupancy and reducing car utilization, thereby contributing to a more sustainable transportation system. The rise of commercial ride-sourcing companies offering this service at a large-scale underscores the necessity for advanced optimization techniques capable of efficiently managing a substantial number of ride demands in real time. However, state-of-the-art optimization methods are rarely used in practice due to their complex implementation, consequently restricting their potential benefits. This paper focuses on the development of a real-time dispatching system for a ride-sharing service, employing primal methods that scale effectively to handle thousands of customers per hour. The primary goal is to address the dynamic Dial-and-Ride Problem, aiming to minimize waiting times while ensuring service quality by limiting ride duration. We introduce a rolling horizon-based framework, involving the division of the time horizon into small epochs, batching requests within each epoch, and re-optimizing the problem for the batch of requests. Unlike prior studies that restart optimization for each period, we leverage the strength of integral primal simplex to reuse previously computed solutions as a warm start, extending current routes with new incoming requests. Computational experiments, conducted on instances derived from historical taxi trips in New York City, involving up to 30,000 requests per hour, illustrate the efficacy and potential advantages of the method in effectively managing large-scale and dynamic scenarios.

ABSTRACT. The dismantling and recycling of aircraft is one of the future challenges for the air transport industry in terms of sustainability. This problem is hard to solve and optimize as planning operations are highly constrained. Indeed, extracting each part requires technicians with the necessary qualifications and equipment. The parts to be extracted are constrained by precedence relations and the number of simultaneous technicians on specific zones is restricted. It is also essential to avoid unbalancing the aircraft during disassembly. Cost is a significant factor, influenced by the duration of ground mobilization and the choice of technicians for each operation. This paper presents a first constraint programming model for this problem using optional interval variables. This model is used to solve a real-life instance provided by our industrial partner, involving up to 1500 tasks. The results show that the model can find feasible solutions for all variations of the instance and compares the solutions obtained to several lower bounds.