ABSTRACT. While games like Chess, Checkers and Go have been the subject of extensive research in AI for decades, there has been comparatively little study of single player card games.  These games are generally called ``Patience'' in British English and "Solitaire" in US English, and have been popular for hundreds of years and remain so today. In fact,our ignorance ofthe winnability percentage of just one such game -- "Klondike" -- has been described as "one of the embarrassments of applied mathematics'' by the distinguished statistician Persi Diaconis.

I will talk about "Solvitaire", a program to solve patience games given a simple JSON description of the rules of the game and the initial layout.  We have used Solvitaire to determine the winnability percentage of dozens different single-player card games with a 95% confidence interval of plus-or-minus 0.1% or better.  For example, we  now know the winnability of Klondike as 81.945% plus-or-minus 0.084% (in the "thoughtful" variant where the player knows the rank and suit of all cards), a 30-fold reduction in confidence interval over the best previous result.  The vast majority of results we obtained with Solvitaire are either entirely new or represent significant improvements on previous knowledge.

Solvitaire is very much a "Good Old Fashioned AI" approach to solving patience games, without using Machine Learning or Neural networks.    It uses exhaustive depth-first search to explore all possibleways that a game could possibly be won, ensuring that games reported unwinnable really are so.  This can involve searching extraordinary seach spaces with depths in the millions even including cases where unwinnability is proven.   Numerous techniques imported from AI search play an important role in making this search practicable.   Particularly important ones are: the use of transposition tables; the exploitation of symmetry in search; the use of dominances to force certain moves to be made when it is safe to do so; and the use of streamliners.Solvitaire does have some games it performs poorly on, where exhaustive search is unable to prove that no win is possible but an alternative simple proof is in fact available.   I will also talk about using constraint models do this, leading to slight improvements in some variants of Klondike but dramatic improvements in others.

This talk will include personal anecdotes, explaining for example why it is dedicated to my mother Margaret Gent (1923-2021) for her patience in teaching me to love the game of patience.

ABSTRACT. This paper addresses the High Multiplicity Resource-Constrained Project Scheduling Problem (HM-RCPSP), in which multiple projects are performed iteratively while sharing limited resources. We extend this problem by integrating the learning effect, which makes the duration of some activities decrease when they are repeated. Learning effect can be represented by any decreasing function, allowing us to get flexibility in modeling various scenarios. Additionally, we take composition of activities into consideration for reasoning about precedence and resources in a more abstract way. A Constraint Programming model is proposed for this richer problem, including a symmetry-breaking technique applied to some activities. We also present a heuristic-based search strategy. The effectiveness of these solving approaches is evaluated through an experimentation conducted on data concerning real-world satellite assembly lines, as well as on some adapted literature benchmarks. Obtained results demonstrate that our methods serve as robust baselines for addressing this novel problem (denoted by HM-RCPSP/L-C).

ABSTRACT. Proof logging has long been the established method to certify correctness of Boolean satisfiability (SAT) solvers, but has only recently been introduced for SAT-based optimization (MaxSAT). The focus of this paper is solution-improving search (SIS) in which a SAT solver is iteratively queried for increasingly better solutions until an optimal one is found. A central challenge is that modern SIS solvers make use of complex ``without loss of generality'' arguments that are quite involved to understand even at a human meta-level, let alone to express in a simple, machine-verifiable proof.

In this work, we develop pseudo-Boolean proof logging methods for solution-improving MaxSAT solving, and use them to produce a certifying version of the state-of-the-art solver Pacose with VeriPB proofs. Our experimental evaluation demonstrates that this approach can be made to work in practice. We hope that this is yet another step towards general adoption of proof logging in MaxSAT solving.

ABSTRACT. Following the successful use of Propositional Satisfiability (SAT) algorithms in Boolean optimization (e.g., Maximum Satisfiability), several SAT-based algorithms have been proposed for Multi-Objective Combinatorial Optimization (MOCO). However, these new algorithms either provide a small subset of the Pareto front or follow a more exploratory search procedure and the solutions found are usually distant from the Pareto front.

We extend the state of the art with a new SAT-based MOCO solver, Slide and Drill (Slide&Drill), that hones an upper bound set of the exact solution. Moreover, we show that Slide&Drill neatly complements proposed UNSAT-SAT algorithms for MOCO. These algorithms can work in tandem over the same shared “blackboard” formula, in order to enable a faster convergence. Experimental results in several sets of benchmark instances show that Slide&Drill can outperform other SAT-based algorithms for MOCO, in particular when paired with previously proposed UNSAT-SAT algorithms.

ABSTRACT. The enhanced performance of today's MaxSAT solvers has elevated their appeal for many large-scale applications, notably in software analysis and computer-aided design. Our research delves into refining anytime MaxSAT solving by repeatedly identifying and solving smaller subinstances chosen based on the graphical structure of the instance with a complete solver. We investigate various strategies to pinpoint these subinstances. This structure-guided selection of substances provides a complete solver with a high potential for improving the current solution. Our exhaustive experimental analyses contrast our methodology as instantiated in our tool MaxSLIM with previous studies and benchmark it against leading-edge MaxSAT solvers.

ABSTRACT. As a broadly applied technique in numerous optimization problems, recently, local search has been employed to solve Pseudo-Boolean Optimization (PBO) problem. A representative local search solver for PBO is LS-PBO. In this paper, firstly, we improve LS-PBO by a dynamic scoring mechanism. Moreover, on top of this improved LS-PBO, we develop the first parallel local search PBO solver. The main idea is to share good solutions among different threads to guide the search, by maintaining a pool of feasible solutions. For evaluating solutions when updating the pool, we propose a function that considers both the solution quality and the diversity of the pool. Furthermore, we calculate the polarity density in the pool to enhance the scoring function of local search. Our empirical experiments show clear benefits of the proposed parallel approach, making it competitive with the parallel version of the famous commercial solver Gurobi.

ABSTRACT. Researchers recently extended Distributed Constraint Optimization Problems (DCOPs) to Communication-Aware DCOPs so that they are applicable in scenarios in which messages can be arbitrarily delayed. Distributed asynchronous local search and inference algorithms designed for CA-DCOPs are less vulnerable to message latency than their counterparts for regular DCOPs. However, unlike local search (regular) DCOP algorithms that converge to k-opt solutions (with k > 1), that is, they converge to solutions that cannot be improved by a group of k agents), local search CA-DCOP algorithms are limited to 1-opt solutions only.

In this paper, we introduce Latency-Aware Monotonic Distributed Local Search-2 (LAMDLS-2), where agents form pairs and coordinate bilateral assignment replacements. LAMDLS-2 is monotonic, converges to a 2-opt solution, and is also robust to message latency, making it suitable for CA-DCOPs. Our results indicate that LAMDLS-2 converges faster than MGM-2 (benchmark) to a similar 2-opt solution, in various message latency scenarios.

ABSTRACT. A bottleneck in the more wide-spread use of approaches, such as Large Neighborhood Search, is the need for domain-specific knowledge. To this end, a number of generic LNS methods have previously been proposed which automate the selection of variables in the neighborhood with the aim of reducing the expertise requirement. Recently a new generic approach, Improved Variable-Relationship Guided LNS (iVRG), was proposed which showed promising initial results. This method combines static information regarding problem structure and dynamic information from search performance in its neighborhood selection.

In this work, we first show the generalizability of the approach by comparing it on two widely studied problems, car sequencing and steel mill slab, where it outperformed existing generic approaches. We then provide a detailed examination of iVRG, investigating its key components (static/dynamic information, the use of a Tournament Selection operator) to assess their individual impact and provide insight into iVRGs overall behavior.

ABSTRACT. Domain-independent dynamic programming (DIDP) is a recently proposed technology forsolving combinatorial optimization based on dynamic programming (DP). DIDP is a model-based paradigm similar to constraint programming (CP): a user formulates a problem as a DP model and solves it using a general-purpose DP solver. However, unlike CP, the DP model describes the problem using states and transitions between states. Recent research has demonstrated that DIDP has state-of-the-art performance in multiple combinatorial optimization problem classes, outperforming commercial CP and mixed integer programming (MIP) solvers.This tutorial introduces the basics of DIDP and does a hands-on session using DIDPPy, the Python interface of our DIDP software framework. After introducing the background, we present an example of a DP model that is implemented and solved with DIDPPy. Then, we do a hands-on session using the Jupyter Notebook, where participants formulate and solve a DP model for a given combinatorial optimization problem. We then introduce the heuristic search algorithms that are used in the currently developed DIDP solvers and present their empirical performance evaluated in our recent paper.

ABSTRACT. Significant research efforts have focused on black-box variable selection, with less attention given to value heuristics. An ideal value heuristic enables depth-first-search to prioritize high-quality solutions first. The Bound-Impact Value Selection achieves this goal through a look-ahead strategy, trying every value of the selected variable and ranking them based on their impact on the objective. However, this method is generally too computationally intensive for the entire search tree. We introduce two simple yet powerful modifications to improve its scalability. First, a lighter fix point computation involving only the constraints on the shortest path in the constraint graph between the variable and the objective. Second, a reverse look-ahead strategy optimistically fixes the objective variable to its minimum in order to prioritize the remaining values. These two ideas have been empirically validated on a range of academic problems and in the XCSP3 competition, demonstrating significant improvements in scalability.

ABSTRACT. Finding high-quality bounds is key to devising efficient exact solution approaches for Discrete Optimization (DO) problems. To this end, Decision Diagrams (DDs) provide strong and generic bounding mechanisms. This paper focuses on so-called relaxed DDs which, by merging nodes, over-approximate the solution space of DO problems and provide dual bounds the quality of which hinges upon the ordering of the variables in the DD compilation and on the selection of the nodes to merge. Addressing the Maximum Independent Set Problem, we present a novel dynamic variable ordering strategy relying on induced subgraphs of the original graph, and a new tie-based merge heuristic. In a set of computational experiments, we show that our strategies yield much stronger bounds than the standard state-of-the-art approach. Furthermore, implementing our heuristics in a DD-based branch-and-bound, we reduce the solution times by around 33% on average and by more than 50% on hard instances.

ABSTRACT. Distributed Constraint Optimization Problems (DCOPs) is a framework for representing and solving distributed combinatorial problems. When agents represent people, the constraint information that the agents hold may be incomplete. For such scenarios, researchers proposed Incomplete DCOPs (I-DCOPs), which allow agents to elicit from their human users some of the missing information. Existing I-DCOP approaches evaluate solutions not only by their quality, but also the elicitation costs spent to find them (ex-post). Unfortunately, this may result in the agents spending a lot of effort to find high-quality solutions, and then ignoring them.

We propose to evaluate solutions based on their quality and to consider the elicitation costs beforehand (ex-ante). Agents are limited in the amount of information that they can elicit and, therefore, need to make smart decisions on choosing which information to elicit. We propose several heuristics for making these decisions, which significantly outperform the previously proposed ex-post heuristics.

ABSTRACT. Lagrangian relaxation is a versatile mathematical technique employed to relax constraints in an optimization problem, enabling the generation of dual bounds and the design of efficient propagators in constraint programming. However, the conventional process of deriving Lagrangian multipliers is often computationally intensive. To address this challenge, we propose an innovative unsupervised learning approach that harnesses the capabilities of graph neural networks to exploit the problem structure, aiming to generate accurate Lagrangian multipliers efficiently. We apply this technique to the Held-Karp Lagrangian relaxation for the traveling salesman problem. The core idea is to predict accurate Lagrangian multipliers and to employ them for generating Held-Karp relaxation bounds. These bounds are subsequently utilized to enhance the filtering process carried out by branch-and-bound algorithms. The results on the TSP illustrate that our approach can improve the filtering level of the weighted circuit global constraint, yielding to better performances for the solving process.