Integration of AI and OR Techniques in Contraint Programming for Combinatorial Optimzation Problems

Frontmatter

A Contractor Based on Convex Interval Taylor

Abstract

Interval Taylor has been proposed in the sixties by the interval analysis community for relaxing continuous non-convex constraint systems. However, it generally produces a non-convex relaxation of the solution set. A simple way to build a convex polyhedral relaxation is to select a corner of the studied domain/box as expansion point of the interval Taylor form, instead of the usual midpoint. The idea has been proposed by Neumaier to produce a sharp range of a single function and by Lin and Stadtherr to handle n ×n (square) systems of equations.

This paper presents an interval Newton-like operator, called X-Newton, that iteratively calls this interval convexification based on an endpoint interval Taylor. This general-purpose contractor uses no preconditioning and can handle any system of equality and inequality constraints. It uses Hansen’s variant to compute the interval Taylor form and uses two opposite corners of the domain for every constraint.

The X-Newton operator can be rapidly encoded, and produces good speedups in constrained global optimization and constraint satisfaction. First experiments compare X-Newton with affine arithmetic.

Ignacio Araya, Gilles Trombettoni, Bertrand Neveu

fdcc: A Combined Approach for Solving Constraints over Finite Domains and Arrays

Abstract

Arrays are ubiquitous in the context of software verification. However, effective reasoning over arrays is still rare in CP, as local reasoning is dramatically ill-conditioned for constraints over arrays. In this paper, we propose an approach combining both global symbolic reasoning and local filtering in order to solve constraint systems involving arrays (with accesses, updates and size constraints) and finite-domain constraints over their elements and indexes. Our approach, named fdcc, is based on a combination of a congruence closure algorithm for the standard theory of arrays and a CP solver over finite domains. The tricky part of the work lies in the bi-directional communication mechanism between both solvers. We identify the significant information to share, and design ways to master the communication overhead. Experiments on random instances show that fdcc solves more formulas than any portfolio combination of the two solvers taken in isolation, while overhead is kept reasonable.

Sébastien Bardin, Arnaud Gotlieb

Variable Ordering for the Application of BDDs to the Maximum Independent Set Problem

Abstract

The ordering of variables can have a significant effect on the size of the reduced binary decision diagram (BDD) that represents the set of solutions to a combinatorial optimization problem. It also influences the quality of the objective function bound provided by a limited-width relaxation of the BDD. We investigate these effects for the maximum independent set problem. By identifying variable orderings for the BDD, we show that the width of an exact BDD can be given a theoretical upper bound for certain classes of graphs. In addition, we draw an interesting connection between the Fibonacci numbers and the width of exact BDDs for general graphs. We propose variable ordering heuristics inspired by these results, as well as a k-layer look-ahead heuristic applicable to any problem domain. We find experimentally that orderings that result in smaller exact BDDs have a strong tendency to produce tighter bounds in relaxation BDDs.

David Bergman, Andre A. Cire, Willem-Jan van Hoeve, John N. Hooker

Graph Coloring Facets from All-Different Systems

Abstract

We explore the idea of obtaining valid inequalities for a 0-1 model from a constraint programming formulation of the problem. In particular, we formulate a graph coloring problem as a system of all-different constraints. By analyzing the polyhedral structure of alldiff systems, we obtain facet-defining inequalities that can be mapped to valid cuts in the classical 0-1 model of the problem. We focus on cuts corresponding to cyclic structures and show that they are stronger than known cuts. For example, when an existing separation algorithm identifies odd hole cuts, we can supply stronger cuts with no additional calculation. In addition, we generalize odd hole cuts to odd cycle cuts that are stronger than any collection of odd hole cuts.

David Bergman, John N. Hooker

Complete Characterization of Near-Optimal Sequences for the Two-Machine Flow Shop Scheduling Problem

Abstract

In a two-machine flow shop scheduling problem, the set of ε-approximate sequences (i.e., solutions within a factor 1 + ε of the optimal) can be mapped to the vertices of a permutation lattice.

We introduce two approaches, based on properties derived from the analysis of permutation lattices, for characterizing large sets of near-optimal solutions. In the first approach, we look for a sequence of minimum level in the lattice, since this solution is likely to cover many optimal or near-optimal solutions. In the second approach, we look for all sequences of minimal level, thus covering all ε-approximate sequences.

Integer linear programming and constraint programming models are first proposed to solve the former problem. For the latter problem, a direct exploration of the lattice, traversing it by a simple tree search procedure, is proposed. Computational experiments are given to evaluate these methods and to illustrate the interest and the limits of such approaches.

Jean-Charles Billaut, Emmanuel Hebrard, Pierre Lopez

Global Cyclic Cumulative Constraint

Abstract

This paper proposes a global cumulative constraint for cyclic scheduling problems. In cyclic scheduling a project graph is periodically re-executed on a set of limited capacity resources. The objective is to find an assignment of start times to activities such that the feasible repetition period λ is minimized. Cyclic scheduling is an effective method to maximally exploit available resources by partially overlapping schedule repetitions. In our previous work [4], we have proposed a modular precedence constraint along with its filtering algorithm. The approach was based on the hypothesis that the end times of all activities should be assigned within the period: this allows the use of traditional resource constraints, but may introduce resource inefficiency. The adverse effects are particularly relevant for long activity durations and high resource availability. By relaxing this restriction, the problem becomes much more complicated and specific resource constrained filtering algorithms should be devised. Here, we introduce a global cumulative constraint based on modular arithmetic, that does not require the end times to be within the period. We show the advantages obtained for specific scenarios in terms of solution quality with respect to our previous approach, that was already superior with respect to state of the art techniques.

Alessio Bonfietti, Michele Lombardi, Luca Benini, Michela Milano

A Computational Geometry-Based Local Search Algorithm for Planar Location Problems

Abstract

Constraint-based local search is an important paradigm in the field of constraint programming, particularly when considering very large optimisation problems. We are motivated by applications in areas such as telecommunications network design, warehouse location and other problems in which we wish to select an optimal set of locations from a two dimensional plane. The problems we are interested in are so large that they are ideal candidates for constraint-based local search methods. Maintaining the objective function incrementally is often a key element for efficient local search algorithms. In the case of two dimensional plane problems, we can often achieve incrementality by exploiting computational geometry. In this paper we present a novel approach to solving a class of placement problems for which Voronoi cell computation can provide an efficient form of incrementality. We present empirical results demonstrating the utility of our approach against the current state of the art.

Hadrien Cambazard, Deepak Mehta, Barry O’Sullivan, Luis Quesada

The Conjunction of Interval Among Constraints

Abstract

An Among constraint holds if the number of variables that belong to a given value domain is between given bounds. This paper focuses on the case where the variable and value domains are intervals. We investigate the conjunction of Among constraints of this type. We prove that checking for satisfiability – and thus, enforcing bound consistency – can be done in polynomial time. The proof is based on a specific decomposition that can be used as such to filter inconsistent bounds from the variable domains. We show that this decomposition is incomparable with the natural conjunction of Among constraints, and that both decompositions do not ensure bound consistency. Still, experiments on randomly generated instances reveal the benefits of this new decomposition in practice. This paper also introduces a generalization of this problem to several dimensions and shows that satisfiability is \(\mathcal{R}\)-complete in the multi-dimensional case

Gilles Chabert, Sophie Demassey

Flow-Based Combinatorial Chance Constraints

Abstract

We study stochastic variants of flow-based global constraints as combinatorial chance constraints. As a specific case study, we focus on the stochastic weighted alldifferent constraint. We first show that determining the consistency of this constraint is NP-hard. We then show how the combinatorial structure of the alldifferent constraint can be used to define chance-based filtering, and to compute a policy. Our propagation algorithm can be extended immediately to related flow-based constraints such as the weighted cardinality constraint. The main benefits of our approach are that our chance-constrained global constraints can be integrated naturally in classical deterministic CP systems, and are more scalable than existing approaches for stochastic constraint programming.

Andre A. Cire, Elvin Coban, Willem-Jan van Hoeve

Explaining Flow-Based Propagation

Abstract

Lazy clause generation is a powerful approach to reducing search in constraint programming. For use in a lazy clause generation solver, global constraints must be extended to explain themselves. In this paper we present two new generic flow-based propagators (for hard and soft flow-based constraints) with several novel features, and most importantly, the addition of explanation capability. We discuss how explanations change the tradeoffs for propagation compared with the previous generic flow-based propagator, and show that the generic propagators can efficiently replace specialized versions, in particular for gcc and sequence constraints. Using real-world scheduling and rostering problems as examples, we compare against a number of standard Constraint Programming implementations of these contraints (and in the case of soft constraints, Mixed-Integer Programming models) to show that the new global propagators are extremely beneficial on these benchmarks.

Nicholas Downing, Thibaut Feydy, Peter J. Stuckey

Constraint Optimization Problems and Bounded Tree-Width Revisited

Abstract

The valued constraint satisfaction problem (VCSP) is an optimization framework originating from artificial intelligence which generalizes the classical constraint satisfaction problem (CSP). In this paper, we are interested in structural properties that can make problems from the VCSP framework, as well as other CSP variants, solvable to optimality in polynomial time. So far, the largest structural class that is known to be polynomial-time solvable to optimality is the class of bounded hypertree width instances introduced by Gottlob et al. Here, larger classes of tractable instances are singled out by using dynamic programming and structural decompositions based on a hypergraph invariant proposed by Grohe and Marx. In the second part of the paper, we take a different view on our optimization problems; instead of considering fixed arbitrary values for some structural invariant of the (hyper)graph structure of the constraints, we consider the problems parameterized by the tree-width of primal, dual, and incidence graphs, combined with several other basic parameters such as domain size and arity. Such parameterizations of plain CSPs have been studied by Samer and Szeider. Here, we extend their framework to encompass our optimization problems, by coupling it with further non-trivial machinery and new reductions. By doing so, we are able to determine numerous combinations of the considered parameters that make our optimization problems admit fixed-parameter algorithms.

Tommy Färnqvist

A High Level Language for Solver Independent Model Manipulation and Generation of Hybrid Solvers

Abstract

This paper introduces a high level language that allows for the specification and manipulation of solver independent models and allows for easily generating complex solvers in the Comet language. As Constraint Programming (CP) techniques have increased in complexity, it has become more difficult and time consuming to implement models that take advantage of state-of-the-art modeling techniques and search heuristics. This is particularly problematic for problems that have not been well studied as it is often unclear a priori which modeling technologies and search strategies will be effective.

This work builds on previous solver independent languages by introducing a more general framework based on abstract models and model operators. Model operators represent complex model transformations that can be applied in various combinations to yield a wide array of concrete solvers, including hybrid solvers. Furthermore, Local Search (LS) is fully supported allowing for sequential and parallel bounds-passing hybrids that have not been possible in previous solver independent languages. Large Neighborhood Search (LNS) and column generation based models are also demonstrated.

Daniel Fontaine, Laurent Michel

Explaining Propagators for s-DNNF Circuits

Abstract

Smooth decomposable negation normal form (s-DNNF) circuits are a compact form of representing many Boolean functions, that permit linear time satisfiability checking. Given a constraint defined by an s-DNNF circuit, we can create a propagator for the constraint by decomposing the circuit using a Tseitin transformation. But this introduces many additional Boolean variables, and hides the structure of the original s-DNNF. In this paper we show how we can build a propagator that works on the s-DNNF circuit directly, and can be integrated into a lazy-clause generation-based constraint solver. We show that the resulting propagator can efficiently solve problems where s-DNNF circuits are the natural representation of the constraints of the problem, outperforming the decomposition based approach.

Graeme Gange, Peter J. Stuckey

Reconsidering Mixed Integer Programming and MIP-Based Hybrids for Scheduling

Abstract

Despite the success of constraint programming (CP ) for scheduling, the much wider penetration of mixed integer programming (MIP ) technology into business applications means that many practical scheduling problems are being addressed with MIP, at least as an initial approach. Furthermore, there has been impressive and well-documented improvements in the power of generic MIP solvers over the past decade. We empirically demonstrate that on an existing set of resource allocation and scheduling problems standard MIP and CP models are now competitive with the state-of-the-art manual decomposition approach. Motivated by this result, we formulate two tightly coupled hybrid models based on constraint integer programming (CIP ) and demonstrate that these models, which embody advances in CP and MIP, are able to out-perform the CP, MIP, and decomposition models. We conclude that both MIP and CIP are technologies that should be considered along with CP for solving scheduling problems.

Stefan Heinz, J. Christopher Beck

Activity-Based Search for Black-Box Constraint Programming Solvers

Abstract

Robust search procedures are a central component in the design of black-box constraint-programming solvers. This paper proposes activity-based search which uses the activity of variables during propagation to guide the search. Activity-based search was compared experimentally to impact-based search and the wdeg heuristics but not to solution counting heuristics. Experimental results on a variety of benchmarks show that activity-based search is more robust than other heuristics and may produce significant improvements in performance.

Laurent Michel, Pascal Van Hentenryck

Instance-Specific Algorithm Configuration as a Method for Non-Model-Based Portfolio Generation

Abstract

Instance-specific algorithm configuration generalizes both instance-oblivious algorithm tuning as well as algorithm portfolio generation. ISAC is a recently proposed non-model-based approach for tuning solver parameters dependent on the specific instance that needs to be solved. While ISAC has been compared with instance-oblivious algorithm tuning systems before, to date a comparison with portfolio generators and other instance-specific algorithm configurators is crucially missing. In this paper, among others, we provide a comparison with SATzilla, as well as three other algorithm configurators: Hydra, DCM and ArgoSmart. Our experimental comparison shows that non-model-based ISAC significantly outperforms prior state-of-the-art algorithm selectors and configurators. The following study was the foundation for the best sequential portfolio at the 2011 SAT Competition.

Yuri Malitsky, Meinolf Sellmann

Pheromone-Based Heuristic Column Generation for Vehicle Routing Problems with Black Box Feasibility

Abstract

This paper proposes an abstraction of emerging vehicle routing problems, the Vehicle Routing Problem with Black Box Feasibility. In this problem the routes of a basic VRP need to satisfy an unknown set of constraints. A black box function to test the feasibility of a route is provided. This function is considered of non-linear complexity (in the length of the route). Practical examples of such problems are combinations of VRP with Loading problems or VRP with Scheduling problems. The difficulty in addressing the VRP with Black Box Feasibility lies in the unknown problem structure and the costly feasibility check. We propose a column generation-based approach to locally optimize this problem. Columns are heuristically generated by so-called Collector ants, executing a construction heuristic while guided by pheromones. To find an integer solution we solve an integer Set Partitioning Problem defined on the set of columns generated by the ants. We test the proposed approach on two applications from the literature, the Three-Dimensional Loading Capacitated Vehicle Routing Problem and the Multi-Pile Vehicle Routing Problem, showing the applicability of our approach and its good behavior compared to dedicated approaches.

Florence Massen, Yves Deville, Pascal Van Hentenryck

Simple Temporal Problems in Route Scheduling for the Dial–a–Ride Problem with Transfers

Abstract

The Dial–A–Ride Problem (DARP) consists in defining a set of routes that satisfy transportation requests between a set of pickup points and a set of delivery points. This paper addresses a variant of the DARP where requests can change of vehicle during their trip. This transshipment is made on specific locations called “transfer points”. The corresponding problem is called the Dial–A–Ride Problem with Transfers (DARPT). Solving the DARPT yields modeling and algorithmic difficulties. In this paper, we focus on efficiently checking the feasibility of routes with regards to the problem temporal constraints in a Large Neighborhood Search. This feasibility problem is a Simple Temporal Problem, well studied in particular in Artificial Intelligence [8]. We propose necessary and sufficient conditions to fasten the detection of unfeasible or feasible routes.

Renaud Masson, Fabien Lehuédé, Olivier Péton

Solving the Longest Simple Path Problem with Constraint-Based Techniques

Abstract

The longest simple path problem on graphs arises in a variety of context, e.g., information retrieval, VLSI design, robot patrolling. Given an undirected weighted graph G = (V,E), the problem consists of finding the longest simple path (i.e., no vertex occurs more than once) on G. We propose in this paper an exact and a tabu search algorithm for solving this problem. We show that our techniques give competitive results on different kinds of graphs, compared with recent genetic algorithms.

Quang Dung Pham, Yves Deville

On Beam Search for Multicriteria Combinatorial Optimization Problems

Abstract

In this article, the beam search approach is extended to multicriteria combinatorial optimization, with particular emphasis on its application to bicriteria {0,1} knapsack problems. The beam search uses several definitions of upper bounds of knapsack solutions as well as a new selection procedure based on ε-indicator that allows to discard uninteresting solutions. An in-depth experimental analysis on a wide benchmark set of instances suggests that this approach can achieve very good solution quality in a small fraction of time needed to solve the problem to optimality by state-of-the-art algorithms.

Aníbal Ponte, Luís Paquete, José R. Figueira

Combining Static and Dynamic Models for Boosting Forward Planning

Abstract

This paper presents an example of cooperation between AI planning techniques and Constraint Programming or Operations Research. More precisely, it presents a way of boosting forward planning using combinatorial optimization techniques. The idea consists in combining on one hand a dynamic model that represents the Markovian dynamics of the system considered (i.e. state transitions), and on the other hand a static model that describes the global properties that are required over state trajectories. The dynamic part is represented by so-called constraint-based timed automata, whereas the static part is represented by so-called constraint-based observers. The latter are modeled using standard combinatorial optimization frameworks, such as linear programming, constraint programming, scheduling, or boolean satisfiability. They can be called at any step of the forward search to cut it via inconsistency detection. Experiments show significant improvements on some benchmarks of the International Planning Competition.

Cédric Pralet, Gérard Verfaillie

Hybrid Heuristics for Multimodal Homecare Scheduling

Abstract

We focus on hybrid solution methods for a large-scale real-world multimodal homecare scheduling (MHS) problem, where the objective is to find an optimal roster for nurses who travel in tours from patient to patient, using different modes of transport. In a first step, we generate a valid initial solution using Constraint Programming (CP). In a second step, we improve the solution using one of the following metaheuristic approaches: (1) variable neighborhood descent, (2) variable neighborhood search, (3) an evolutionary algorithm, (4) scatter search and (5) a simulated annealing hyper heuristic. Our evaluation, based on computational experiments, demonstrates how hybrid approaches are particularly strong in finding promising solutions for large real-world MHS problem instances.

Andrea Rendl, Matthias Prandtstetter, Gerhard Hiermann, Jakob Puchinger, Günther Raidl

Guiding Combinatorial Optimization with UCT

Abstract

We propose a new approach for search tree exploration in the context of combinatorial optimization, specifically Mixed Integer Programming (MIP), that is based on UCT, an algorithm for the multi-armed bandit problem designed for balancing exploration and exploitation in an online fashion. UCT has recently been highly successful in game tree search. We discuss the differences that arise when UCT is applied to search trees as opposed to bandits or game trees, and provide initial results demonstrating that the performance of even a highly optimized state-of-the-art MIP solver such as CPLEX can be boosted using UCT’s guidance on a range of problem instances.

Ashish Sabharwal, Horst Samulowitz, Chandra Reddy

Maximising the Net Present Value for Resource-Constrained Project Scheduling

Abstract

The Resource-constrained Project Scheduling Problem (Rcpsp), in which a schedule must obey the resource constraints and the precedence constraints between pairs of activities, is one of the most studied scheduling problems. An important variation of the problem (RcpspDc) is to find a schedule which maximises the net present value (discounted cash flow), when every activity has a given cash flow associated with it. Given the success of lazy clause generation (Lcg) approaches to solve Rcpsp with and without generalised precedence relations it seems worthwhile investigating Lcg’s use on Rcpspdc. To do so, we must construct propagators for the net-present-value constraint that explain their propagation to the Lcg solver. In this paper we construct three different propagators for net-present-value constraints, and show how they can be used to rapidly solve RcpspDc.

Andreas Schutt, Geoffrey Chu, Peter J. Stuckey, Mark G. Wallace

Randomized Adaptive Vehicle Decomposition for Large-Scale Power Restoration

Abstract

This paper considers the joint repair and restoration of the electrical power system after significant disruptions caused by natural disasters. This problem is computationally challenging because, when the goal is to minimize the size of the blackout, it combines a routing and a power restoration component, both of which are difficult on their own. The joint repair/restoration problem has been successfully approached with a 3-stage decomposition, whose last step is a multiple-vehicle, pickup-and-delivery routing problem with precedence and capacity constraints whose goal is to minimize the sum of the delivery times (PDRPPCCDT). Experimental results have shown that the PDRPPCCDT is a bottleneck and this paper proposes a Randomized Adaptive Vehicle Decomposition (RAVD) to scale to very large power outages. The RAVD approach is shown to produce significant computational benefits and provide high-quality results for infrastructures with more than 24000 components and 1200 damaged items, giving rise to PDRPPCCDT with more than 2500 visits.

Ben Simon, Carleton Coffrin, Pascal Van Hentenryck

A Multilevel Algorithm for Large Unconstrained Binary Quadratic Optimization

Abstract

The unconstrained binary quadratic programming (UBQP) problem is a general NP-hard problem with various applications. In this paper, we present a multilevel algorithm designed to approximate large UBQP instances. The proposed multilevel algorithm is composed of a backbone-based coarsening phase, an asymmetric uncoarsening phase and a memetic refinement phase, where the backbone-based procedure and the memetic refinement procedure make use of tabu search to obtain improved solutions. Evaluated on a set of 11 largest instances from the literature (with 5000 to 7000 variables), the proposed algorithm proves to be able to attain all the best known values with a computing effort less than any existing approach.

Yang Wang, Zhipeng Lü, Fred Glover, Jin-Kao Hao

Backmatter