Improving Combinatorial Optimization - Extended Abstract

1 Introduction

Combinatorial Optimization is an important area of computer science that has many theoretical and practical applications. Constraint Programming (CP) is a relatively new, and very effective technology for solving combinatorial optimization problems. In the thesis [Chu, 2011], we present important contributions to a number of areas in CP, including nogood learning, symmetry breaking, dominance, relaxations, and parallelization. The thesis is divided into four parts, each addressing a different area of CP.

∗The thesis on which this extended abstract is based was the recipient of the 2012 ACP Doctoral Research Award [Chu, 2011]

2 Background and Definitions

Let ≡ denote syntactical identity, ⇒ denote logical implication and ⇔ denote logical equivalence. A Constraint Satisfaction Problem (CSP) is a tuple P ≡ (V,D,C), where V is a set of variables, D is a domain over V (i.e., a set of unary constraints), and C is a set of n-ary constraints. A assignment θ over V is a solution of P if it satisfies every constraint in D and C. The aim of a CSP is to find a solution or to prove that none exist. In a Constraint Optimization Problem (COP) P ≡ (V, D, C, f), we also have an objective function f mapping assignments to an ordered set, e.g., Z or R, and we wish to minimize or maximize f over the solutions of P .

A propagator pc for constraint c is a function mapping domains to domains s.t. c ∧D⇔ c ∧ pc(D), i.e., it performs inference based on c and the current domain D, pruning away any variable/value pairs that cannot be taken given c and D. A propagation based CP solver solves a CSP by interleaving search with inference. We begin with the original problem at the root of the search tree. At each node in the search tree, we propagate all the propagators until the domain reaches a fixed point. If some variable's domain becomes empty, then the problem has no solution and the solver backtracks. If all the variables are assigned and no constraint is violated, then a solution has been found and the solver can terminate. If inference is unable to detect either of the above two cases, then the solver divides the problem into a number of more constrained subproblems and searches each of those in turn.

3 Part 1 - Nogood Learning

Nogood learning techniques are used to speedup constraint solving by learning implied constraints called nogoods. A nogood is an implied constraint of form: ¬(l1 ∧ . . . ∧ ln), expressing a set of conditions under which there can be no solutions to the problem. They can be propagated to prune parts of the search space. There are various ways to derive nogoods. The simplest way is to derive them through exhaustive search. Whenever a subtree reached via a set of decisions has been exhaustively searched and has no solutions, the set of decisions we took to get to the subtree forms a nogood, which we call the decision nogood. Such decision nogoods are easy to derive but are also very weak in terms of pruning strength. It has been suggested that such nogoods can be used in CP solvers that perform restarts in order to prevent them from exploring previously explored parts of the search tree [Lecoutre et al., 2007]. Another way to derive nogoods is via constraint resolution. Such nogoods are used in SAT solvers [Silva and Sakallah, 1999], and in Lazy Clause Generation solvers [Ohrimenko et al., 2007; Feydy and Stuckey, 2009]. Whenever the solver finds a conflict, it is possible to find the subset of constraints responsible and to resolve them together to derive a new nogood. Such a nogood expresses the reason for the conflict, and can prevent the solver from making assignments that fail for the same reason again. They are very powerful and can provide orders of magnitude speedup on a wide range of problems.

In Part 1 of the thesis, we present a new nogood learning technique based on constraint projection. In many combinatorial optimization problems, different search paths lead to subproblems which are actually equivalent on the remaining unfixed variables. Naive CP solvers cannot recognize this and will therefore end up solving these equivalent subproblems again and again. We can prevent this by deriving nogoods which express the failure of such subproblems so that after it is examined once, equivalent subproblems will not be searched again. Such nogoods can be derived using constraint projection. Suppose that all subtrees of a particular search node N have been searched and has failed. Let F ⊆ V be the set of variables which were fixed at the propagation fixed point of N. We calculate the projection of each constraint and domain onto the remaining unfixed variables V \F given the values of the fixed variables at N. The conjunction of these projections then form a valid nogood.

To be precise, given a set of variables V ≡ {v1, . . . , vn} and an arbitrary logical expression c, let ∃V c ≡ ∃v1 ...∃vn c. ∃V is a projection operator which projects a logical expression onto the variables not in V . let DF be the domains of the variables in F at N. Then n ≡ ¬(∧c∈C∪D∃F (DF ∧ c)) is a nogood which expresses that the node N fails because of the effect that the current assignment on F has on the unfixed variables. This nogood can be used to prune other subtrees. If a different assignment to F gives the same projection onto the unfixed variables, then they actually lead to an equivalent subproblem as N and thus are also guaranteed to fail. We can detect this by storing these nogoods in a hash table. If another node generates a set of projections that match one of the nogoods currently in the hash table, then we know that we have examined an equivalent subproblem before and can prune this one. Note that these projections are quite easy to calculate, as we simply need to project the constraints in a piecewise manner and take their conjunction. On appropriate problems, our new nogood learning technique provides orders of magnitude speedup compared to a base solver which does not learn nogoods. Our technique is competitive with Lazy Clause Generation, which is the current state of the art in nogood learning. The nogoods derived through constraint projection are different in power to the nogoods derived by x9 ∈ {1, 2, 3}

Figure 1: A graph coloring problem where we can exploit additional symmetries.

Lazy Clause Generation through constraint resolution, and can be exponentially stronger on some problems. More details on the proofs and implementation can be found in [Chu et al., 2010] and [Chu et al., 2012].

4 Part 2 - Symmetry Breaking

Symmetry breaking techniques are used to speedup constraint solving in problems with symmetries. In such problems, examining one assignment is often enough to tell us everything we need to know about its symmetric counterparts (whether it is a solution, what its objective value is, etc). These redundancies in the search can exponentially increase the run time. One way to prevent this is to apply some form of symmetry breaking to prevent the CP solver from exploring symmetric parts of the search space. The most popular symmetry breaking techniques are lexicographical symmetry breaking constraints [Puget, 1993; Crawford et al., 1996; Luks and Roy, 2004; Puget, 2005; Frisch et al., 2003], Symmetry Breaking During Search (SBDS) [Gent and Smith, 2000], and Symmetry Breaking by Dominance Detection (SBDD) [Fahle et al., 2001]. Lexicographical symmetry breaking constraints can be statically added to the problem to constrain the solver to look only for solutions which are lexicographically least within its equivalence class. SBDS and SBDD are dynamic symmetry breaking techniques which, after each partial assignment has been explored, adds constraints to disallow all of its symmetric counterparts from being solutions.

In Part 2 of the thesis, we present a new symmetry breaking technique called SBDS-1UIP, which is an extension of SBDS. Given a symmetry σ, and any nogood n ≡ ¬(l1 ∧ . . . ∧ ln), where li are literals of the problem of the form x = v or x ̸= v for some variable x and value v, σ(n) ≡ ¬(σ(l1)∧. . .∧σ(ln)) is also a valid nogood. The original SBDS technique can be thought of as using symmetric versions of decision nogoods to prune symmetric parts of the search space. In our extension SBDS-1UIP, we use symmetric versions of the 1UIP nogoods derived by Lazy Clause Generation solvers instead. We show that SBDS-1UIP can exploit at least as many symmetries as SBDS, and that it is strictly more powerful on some problems.

Example 1 Consider the graph coloring problem shown in Figure 1 where we are trying to 5-colour the nodes so that no pair of adjacent nodes having the same color. let x1, . . . , x10 represent the colours of each node. Clearly, all 5 colors are interchangeable so we have a value symmetry. Suppose we have made decisions x1 = 1, x2 = 2, x3 = 3, x4 = 4, x5 = 5.

Propagation produces the domains shown in Figure 1. Suppose we decide to try x6 = 1 next. The search eventually fails since we have a 3-clique on x7, x8, x9 but only 2 colours available. The 1UIP nogood is x7 ̸= 4 ∧ x7 ̸= 5 ∧ x8 ̸= 4 ∧ x8 ̸= 5 ∧ x9 ̸= 4 ∧ x9 ̸= 5 → x6 ̸= 1, which tells us we should prune x6 = 1. However, we can apply the value symmetries between 1 and 2 to get a symmetric nogood: x7 ̸= 4 ∧ x7 ̸= 5∧x8 ̸= 4∧x8 ̸= 5∧x9 ̸= 4∧x9 ̸= 5 → x6 ̸= 2, allowing us to prune x6 = 2 as well. Similarly, we can apply the value symmetries between 1 and 3 to get a nogood that allows us to prune x6 = 3. None of the traditional methods such as SBDS, SBDD or lex-leader symmetry breaking constraints are capable of pruning x6 = 2 or x6 = 3, as all 5 values had previously already been used in x1, . . . , x5.

This is a very interesting result, as SBDS is already a complete method which guarantees that at most one solution in each equivalence class is found by the solver. However, SBDS1UIP can be strictly more powerful than that, as it is capable of taking advantage of the information about which subsets of decisions and constraints actually caused a conflict in order to do even more symmetry breaking. On some problems, SBDS1UIP can be exponentially faster than using the original SBDS. More details can be found in [Chu et al., 2011].

We also present two new methods for exploiting almost symmetries. Many problems arising from real world applications do not exhibit full problem symmetry, but instead exhibit almost symmetries, where the symmetries are broken by a small number of constraints. Such problems often still have large amounts of symmetries that can be exploited for speedup. However, traditional symmetry breaking methods like lexicographical symmetry breaking constraints, SBDS or SBDD cannot directly handle such partially broken symmetries. We present two new general methods for exploiting almost symmetries. The first is to modify SDBS-1UIP to handle almost symmetries. The second is to treat almost symmetries as conditional symmetries and exploit them by posting conditional symmetry breaking constraints.

In the first, we modify SBDS-1UIP to keep track of exactly which constraints were used in order to derive a nogood n. Given an almost symmetry σ, if none of the constraints which break the symmetry σ were used to derive n, then σ(n) is still a valid nogood and we can post it to achieve additional pruning. Alternatively, we could exploit the almost symmetry by considering it as a conditional symmetry. Suppose the set of constraints which break the symmetry σ is H, then we can post the conditional symmetry breaking constraint ∧c∈Hσ(c) → sb(σ), where ∧c∈Hσ(c) are the conditions, and sb(σ) is a standard symmetry breaking constraint for σ, e.g., a lex-leader symmetry breaking constraint. Both techniques are capable of producing orders of magnitude speedups on appropriate problems. More details of these methods can be found in the thesis.

5 Part 3 - Relaxation and Dominance

In Part 3 of the thesis, we examine several well studied problems. We present a new solver for the Minimization of Open Stacks Problem (MOSP) [Yuen and Richardson, 1995]. The MOSP was the subject of the 2005 Modeling Challenge. It has appeared in many different guises in the literature, e.g., graph pathwidth, gate matrix layout (see [Linhares and Yanasse, 2002] for a list of 12 equivalent problems). The MOSP is known to be NP-hard [Linhares and Yanasse, 2002]. The previous state of the art in solving the MOSP [Garcia de la Banda and Stuckey, 2007] utilizes a branch and bound algorithm and top down dynamic programming in order to exploit the massive amounts of subproblem equivalences inherent in the problem. This solver was several orders of magnitude faster than all the other entrants in the 2005 Modeling Challenge. Our new solver is many orders of magnitude faster yet again. We identify 4 dominance relations which describe several different conditions under which moving a task forward or backwards in the schedule will always lead to a solution which is at least as good. When exploited, these dominance relations provides some 5-6 orders of magnitude speedup. We also find an effective relaxation technique that allows us to speed up the proof of optimality on the hardest instances by a further 3-4 orders of magnitude. We identify the customers which are least densely connected with other customers (via shared product requests) and relax the problem by removing them. We relax the problem very aggressively initially. However, we try to detect when we have over relaxed and unrelax the problem by adding a removed customer back in. To do this, we first run a very good search heuristic on the original problem to get a probable optimal solution. When we relax the problem, we run this search heuristic again. If we find a solution better than the one we found for the original problem, then it is quite likely that we have over relaxed, in which case we stop relaxing and start unrelaxing until we can prove the correct optimality bound. On the hardest instances, we can often relax away up to one third of the customers and still be able to prove the same lower bound as the original problem. More details can be found in [Chu and Stuckey, 2009].

We present a new solver for the Talent Scheduling Problem [Cheng et al., 1993]. In the Talent Scheduling Problem, we have a set of actors and a set of scenes. We wish to find an ordering of the scenes such that the cost of hiring the actors are minimized. Each actor is involved in some subset of scenes and must be on location from the first to the last of their scenes, getting paid for each day they are on location. The Talent Scheduling Problem problem has a lot of subproblem equivalences which can be exploited by caching [Smith, 2005], dynamic programming, or similar techniques. We present a new solver based on dynamic programming that is some 2-3 orders of magnitude faster than the previous state of the art. We show that using bounded dynamic programming gives 1-2 orders of magnitude speedup compared to a naive dynamic programming approach. Exploiting dominance relations based on moving a scene forwards or backwards in the schedule gives a further ∼2 times speedup, and utilizing a lower bound calculation based on relaxations gives a further 1 order of magnitude speedup. More details can be found in [Garcia de la Banda et al., 2011].

We also completely solve the Maximum Density Still Life Problem [Bosch and Trick, 2004] for all n. The Maximum Density Still Life Problem is based on Conway's Game of Life. The aim is to find the maximum number of live cells that can appear in an n×n region in a still life according to the rules of the game. It is an extremely difficult combinatorial optimization problem with a raw search space of O(2n2 ). Previous search methods using IP [Bosch, 1999] and CP [Bosch and Trick, 2004] could only solve up to n = 9, while a CP/IP hybrid method with symmetry breaking [Bosch and Trick, 2004] could solve up to n = 15. An attempt using bucket elimination [Larrosa and Dechter, 2003] reduced the time complexity to O(n2 23n ) but increased the space complexity to O(n22n ). This method could solve up to n = 14 before it ran out of memory. A subsequent improvement that combined bucket elimination with search [Larrosa et al., 2005], used less memory and was able to solve up to n = 20. We completely solve the problem for all n by using a combination of remodeling, relaxations, bounded dynamic programming and customized search.

The key to solving the problem is a mathematical proof that a "wastage" number could be assigned to each 3 × 3 pattern such that the total number of live cells is a function of n minus the sum of the wastage of all the 3 × 3 patterns in the n × n region. This proof tells us exactly which 3 × 3 patterns are good and which ones are wasting space, and allows us to remodel the problem in terms of minimizing wastage rather than maximizing the number of live cells. The reformulation allows tighter bounds on the objective to be found, which allows branch and bound to prune failed subtrees earlier. Also, by analysing existing optimal solutions in terms of wastage, we found that wastage only occurs near the edge or corners of the n×n region in optimal solutions, leading to the conjecture that it is only the boundary conditions which are forcing wastage. This was subsequently confirmed and meant that we can derive a proof of optimality by relaxing the problem onto only a width 13 boundary no matter how large n is, significantly reducing the number of variables in the problem. Furthermore, the relaxed problem has a constraint graph with low pathwidth, and thus can be solved using dynamic programming in O(n) (albeit with a very large constant factor). By taking advantage of the translational symmetry inherent in the still life constraints, we were able to prove tight upper bounds on the number of live cells for all n in finite time. Then, by finding optimal solutions which achieve these upper bounds and which satisfy additional periodicity constraints, we were able to construct provably optimal solutions for all n. See Figure 2 for an optimal solution to n = 100. The Maximum Density Still Life problem is now completely closed. More details on the method can be found in [Chu et al., 2009c] and [Chu and Stuckey, 2012].

6 Part 4 - Parallelization

Parallelization is an obvious way to try to speedup constraint solving, especially in view of the recent proliferation of multicore systems. In part 4 of the thesis, we identify cache contention as a serious bottleneck that severely limits the amount of speedup achievable by parallel SAT and Lazy Clause Generation solvers on multi-core systems. We alter the data structures used in the state of the art SAT solver MiniSat [E´en and S¨orensson, 2003] to be more cache aware, leading to a sequential SAT solver that is some 80% faster on average and a parallel SAT solver that is some 140% faster on average.

More details on these data structures can be found in [Chu et al., 2009a].

We also examine the interaction between branching heuristics and dynamic load balancing schemes. This important theoretical issue has not been properly addressed in the literature. Many analyses of parallel search and load balancing schemes implicitly or explicitly assume that the total amount of work is fixed (e.g. [Kumar and Rao, 1987]). This assumption is not true for satisfiable problems or for optimization problems, as finding a (good) solution quickly can dramatically reduce the total amount of work required. Much work in CP is concerned with developing strong branching heuristics which can shape and order the branches of the search tree so that (good) solutions are found early on in the search. However, many commonly used parallelization schemes, e.g., splitting the search tree as close to the root as possible, focus on maximizing the granularity of the work partitions and completely ignore the branching heuristic. This can result in many of the processors searching in unfruitful parts of the search tree.

We analyze this problem and develop a new work stealing scheme called confidence based work stealing, which can make use of the information provided by the branching heuristic. The new scheme tries to partition the processors in proportion to the estimated solution density of each subtree. The solution densities are initially estimated using the strength of the branching heuristic at the node, and is then dynamically updated using negative reinforcement learning as nodes are searched and failed. The new parallel algorithm produced near linear or super linear speedup on all the problems we tested. More details on the method can be found in [Chu et al., 2009b].

7 Conclusion

This thesis presents important contributions to a number of areas in Constraint Programming, including nogood learning, symmetry breaking, relaxations, dominance and parallelization. These include new generic techniques such as nogood learning using constraint projection, SBDS-1UIP for symmetry breaking, SBDS-1UIP and conditional symmetry breaking constraints for almost symmetry breaking, and confidencebased work stealing for parallel search, as well as problem specific techniques such as dominance rules and relaxations which gave orders of magnitude speedup on the Minimization of Open Stacks Problem, the Talent Scheduling Problem, and the Maximum Density Still Life Problem.