ABSTRACT. Multi-Agent Path Finding (MAPF) is a problem that requires one to compute a set of collision-free paths for a team of moving agents. The problem appears in variety of practical applications including warehouse logistics, traffic management, aircraft towing and computer games. The general version of the problem (minimizing makespan or sum of path costs, on graphs with parallel actions and rotations) is known to be NP-hard. One of the leading methods for solving MAPF optimally, employs a strategy known as Conflict-based Search (CBS). The central idea is to plan paths for each agent independently and resolve collisions by branching the current plan. Each branch is a new candidate plan wherein one agent or the other is forced to find a new path that avoids the selected collision. When we examine CBS from an optimisation perspective, it is clearly a form of (Logic-based) Benders Decomposition. This begs the question: can we use combinatorial optimisation techniques to tackle the MAPF problem efficiently? In this talk I will show two approaches: the first uses core-guided search together with a nogood learning Constraint Programming solver; the second uses Branch-and-Cut-and-Price to- gether with a MIP solver. Both methods prove to be highly competitive to previous CBS approaches.

ABSTRACT. A major limitation of current generations of quantum annealers is the sparse connectivity of manufactured qubits in the hardware graph. This technological limitation generated considerable interest, motivating efforts to design efficient and adroit minor-embedding procedures that bypass sparsity constraints. In this paper, starting from a previous equational formulation by Dridi et al. (arXiv:1810.01440), we propose integer programming (IP) techniques for solving the minor-embedding problem. The first approach involves a direct translation from the previous equational formulation to IP, while the second decomposes the problem into an assignment master problem and fiber condition checking subproblems. The proposed methods are able to detect instance infeasibility and provide bounds on solution quality, capabilities not offered by currently employed heuristic methods. We demonstrate the efficacy of our methods with an extensive computational assessment involving three different families of random graphs of varying sizes and densities. The direct translation as a monolithic IP model can be solved with existing commercial solvers yielding valid minor-embeddings, however, is outperformed overall by the decomposition approach. Our results demonstrate the promise of our methods for the studied benchmarks, highlighting the advantages of using IP technology for minor-embedding problems.

Q&A session (starts at 15:50)

ABSTRACT. The recent emergence of novel hardware platforms, such as quantum computers and Digital/CMOS annealers, capable of solving combinatorial optimization problems has spurred interest in formulating key problems as Ising models, a mathematical abstraction shared by a number of these platforms. In this work, we focus on constrained clustering, a semi-supervised learning task that involves using limited amounts of labelled data, formulated as constraints, to improve clustering accuracy. We present an Ising modeling framework that is flexible enough to support various types of constraints and we instantiate the framework with two common types of constraints: pairwise instance-level and partition-level. We study the proposed framework, both theoretically and empirically, and demonstrate how constrained clustering problems can be solved on a specialized CMOS annealer. Empirical evaluation across eight benchmark sets shows that our framework outperforms the state-of-the-art heuristic algorithms and that, unlike those algorithms, it can solve problems that involve combinations of constraint types. We also show that our framework provides high quality solutions orders of magnitudes more quickly than a recent constraint programming approach, making it suitable for mainstream data mining tasks.

Q&A session (starts at 15:50) - merged with first talk

ABSTRACT. The recent emergence of novel computational devices, such as quantum computers, neuromorphic co-processors and digital annealers presents new opportunities for hardware accelerated hybrid optimization algorithms. Unfortunately, demonstrations of unquestionable performance gains leveraging novel hardware platforms have faced significant obstacles. One key challenge is understanding the algorithmic properties that distinguish such devices from established optimization approaches. Through the careful design of contrived optimization tasks, this work provides new insights into the computation properties of quantum annealing and suggests that this model has an uncanny ability to avoid local minima and quickly identify the structure of high quality solutions. A meticulous comparison to a variety of algorithms spanning both complete and local search suggest that quantum annealing's performance on the proposed optimization tasks is unique. This result provides new insights into the time scales and types of optimization problems where quantum annealing has the potential to provide notable performance gains over established optimization algorithms and prompts the development of hybrid algorithms that combine the best features of quantum annealing and state-of-the-art classical approaches.

Q&A session (starts at 15:50) - merged with first talk

ABSTRACT. We consider the synthesis problem of a multi-speed gearbox, a mechanical system that receives an input velocity and transmits it to an outlet through a series of connected gears, decreasing or increasing the speed according to predetermined transmission ratios. Here we formulate this as a bi-level optimization problem, where the inner task involves non-convex optimization over continuous parameters of the components, and the outer task explores different configurations of the system. The outer problem is decomposed into sub-tasks and optimized by a variety of global search methods, namely simulated annealing, best-first search and estimation of distribution algorithm. Our experiments show that a three-stage decomposition coupled with a best-first search performs well on small-size problems, whereas it outmatches other techniques on larger problems when coupled with an estimation of distribution algorithm.

Q&A session (starts at 15:50)

ABSTRACT. For two families of time-series constraints with the aggregator Sum and features one and width, we provide parameterised sharp lower and upper bounds on the sum of the time-series variables wrt these families of constraints. This is important in many applications, as this sum represents the cost, for example the energy used, or the manpower effort expended. We use these bounds not only to gain a priori knowledge of the overall cost of a problem, we can also use them on increasing prefixes and suffixes of the variables to avoid infeasible partial assignments under a given cost budget. Experiments show that the bounds drastically reduce the effort to find cost limited solutions.

Q&A session (starts at 15:50)

ABSTRACT. Decision and optimization problems can be tackled with different techniques, such as Mixed Integer Programming, Constraint Programming or SAT solving. An important ingredient in the success of each of these approaches is the exploitation of common constraint structures with specialized (re-)formulations, encodings or other techniques. In this paper we present a new linear SAT encoding using binary decision diagrams over multiple variable orders as intermediate representation of a special form of constraints denoted as staircase at-most-one-constraints. The use of these constraints is motivated by recent work on the antibandwidth problem, where an iterative solution procedure using feasibility-mixed integer programs based on such constraints was most effective. In a computational study we compare the effectiveness of our new encoding against traditional SAT-encodings for staircase at-most-one-constraints. Additionally we compare against previous exact solution methods for the antibandwidth problem, such as a constraint programming approach and the one based on feasibility-mixed integer programs.

Q&A session (starts at 15:50)

ABSTRACT. We extend automatic instance generation methods to allow cross-paradigm comparisons. We demonstrate that it is possible to completely automate the search for benchmark instances that help to discriminate between solvers. Our system starts from a high level human-provided problem specification, which is translated into a specification for valid instances. We use the automated algorithm configuration tool irace to search for instances, which are translated into inputs for both MIP and CP solvers by means of the Conjure, Savilerow, and Minizinc tools. These instances are then solved by CPLEX and Chuffed, respectively. We constrain our search for instances by requiring them to exhibit a significant advantage for MIP over CP, or vice versa. Experimental results on four optimisation problem classes demonstrate the effectiveness of our method in identifying instances that highlight differences in performance of the two solvers.

Q&A session (starts at 15:50)

ABSTRACT. M. Sellmann showed that CP-based Lagrangian relaxation gave good results but the interactions between the filtering algorithms and the Lagrangian multipliers were quite difficult to understand. In other words, it is difficult to determine when filtering algorithms should be triggered. There are two main reasons for this: the best multipliers do not lead to the best filtering and each filtering disrupts the solving of the Lagrangian multiplier problem. In this paper, we study these interactions for the Traveling Salesman Problem (TSP) because the resolution of the TSP in CP is mainly based on a Lagrangian relaxation. We propose to match the calls to the filtering algorithms with the strong variations of the objective value. In addition, we try to avoid oscillations of the objective function. We introduce Scope Sizing Subgradient algorithm, denoted by SSSA, which is an adaptive algorithm, that implements this idea. We experimentally show the advantage of this approach by considering different search strategies or additional constraints. A gain of a factor of two in time is observed compared to the state of the art.

Q&A session (starts at 17:50)

ABSTRACT. Recently Machine Learning techniques have been applied to the Traveling Salesman Problem to find approximate solutions. Reinforcement Learning in particular is promising as it has achieved superhuman performance. This superior performance is attributed to allowing the model to discover unknown strategies without restricting it to those that are provided as implemented in Supervised Learning approaches. Instead, this paper proposes guiding and supervising, not confining, a Reinforcement Learning approach to solve the TSP with the strategies offered by Search Heuristics.

Q&A session (starts at 17:50) - merged with first talk

ABSTRACT. In this article we introduce a Minimum Cycle Partition Problem with Length Requirements (CPLR). This generalization of the Travelling Salesman Problem (TSP) originates from routing Unmanned Aerial Vehicles (UAVs). Apart from nonnegative edge weights, CPLR has an individual critical weight value associated with each vertex. A cycle partition, i.e., a vertex disjoint cycle cover, is regarded as a feasible solution if the length of each cycle, which is the sum of the weights of its edges, is not greater than the critical weight of each of its vertices. The goal is to find a feasible partition, which minimizes the number of cycles. In this article, a heuristic algorithm is presented together with a Mixed Integer Programming (MIP) formulation of CPLR. We furthermore introduce a conflict graph, whose cliques yield valid constraints for the MIP model. Finally, we report on computational experiments conducted on TSPLIB-based test instances.

Q&A session (starts at 17:50) - merged with first talk

ABSTRACT. The Dial a Ride family of Problems (DARP) consists in routing a fleet of vehicles to satisfy transportation requests with time-windows. This problem is at the frontier between routing and scheduling. The most successful approaches in dealing with DARP are often tailored to specific variants. A generic state-of-the-art constraint programming model consists in using a sequence variable to represent the ordering of visits in a route. We introduce a possible representation for the domain called Insertion Sequence Variable that naturally extends the standard subset bound for set variables with an additional insertion operator after any element already sequenced. We describe the important constraints on the sequence variable and their filtering algorithms required to model the classical DARP and one of its variants called the Patient Transportation Problem (PTP). Our experimental results on a large variety of benchmarks show that the proposed approach is competitive with existing sequence based approaches.

Q&A session (starts at 17:50)

ABSTRACT. This paper considers a generalization of the network design problem for On-Demand Multimodal Transit Systems (ODMTS). An ODMTS consists of a selection of hubs served by high frequency buses, and passengers are connected to the hubs by on-demand shuttles which serve the first and last miles. This paper generalizes prior work by including three additional elements that are critical in practice. First, different frequencies are allowed throughout the network. Second, additional modes of transit (e.g., rail) are included. Third, a limit on the number of transfers per passenger is introduced. Adding a constraint to limit the number of transfers has a significant negative impact on existing Benders decomposition approaches as it introduces non-convexity in the subproblem. Instead, this paper enforces the limit through transfer-expanded graphs, i.e., layered graphs in which each layer corresponds to a certain number of transfers. A real-world case study is presented for which the generalized ODMTS design problem is solved for the city of Atlanta. The results demonstrate that exploiting the problem structure through transfer-expanded graphs results in significant computational improvements.

Q&A session (starts at 17:50) - merged with first talk

ABSTRACT. This study focuses on integrating user behavior in the design of on-demand multimodal transit network systems. The resulting planning problem then becomes a bilevel optimization approach where the transit network designer aims to find the most cost and time efficient network design, whereas each user optimizes her route under the given network. The proposed bilevel problem is solved using a novel decomposition algorithm, combining a cut generation procedure along with formulation enhancements and the paper proves the finite convergence of the presented algorithm. The approach is evaluated on a case study using historical data from Ann Arbor, Michigan, with a user choice model based on the income levels of the studied region.

Q&A session (starts at 17:50) - merged with first talk

ABSTRACT. We extend a previously defined problem, the Service Point Distribution Problem (SPDP), for distributing service points with special focus on mobility applications. The SPDP, more or less corresponds to a rather generic facility location problem, and the focus was on an interactive optimization approach in which a broader base of potential users provides iteratively feedback on solution scenarios in order to guide a heuristic search for a solution that maximizes the expected fulfilled demand. While being quite general, the SPDP lacks important aspects that need to be considered in order to model certain mobility applications like the charging of electric vehicles in more realistic ways. Hence, we now aim to investigate a problem formulation more suitable for such applications by extending the SPDP. We limit the demand a station can serve by introducing capacities to each station. Moreover, we introduce resources, which are occupied when a station serves a customer, such that a station can only serve a limited amount of customers at the same time. After motivating and formalizing the problem, we present solution approaches based on a mixed integer linear programming (MILP) formulation as well as on a large neighborhood search heuristic.

Q&A session (starts at 17:50) - merged with first talk

ABSTRACT. Integer programming games (IPGs) are a class of problems that can suitably model non-cooperative interactions between decision makers (players). Under such formulations, each player goal in the game is described by a parametric integer program where interactions between players are reflected in their objective functions. This talk will begin with the description of IPGs, the challenge they represent and an algorithmic framework to solve them that integrates ideas of normal-form games. The notion of solution to IPGs will motivate the second part of this talk, where refinements will be discussed, in particular, in the context of policy making for the kidney exchange game. In this context, the problem of integrating (patients) fairness will be addressed as a constraint satisfaction problem.