Constraint-Based Local Search

Michel, Laurent; Hentenryck, Pascal Van

doi:10.1007/978-3-319-07124-4_7

Laurent Michel⁴ &
Pascal Van Hentenryck⁵

4571 Accesses
3 Citations

Abstract

Constraint-Based Local Search emerged in the last decade as a framework for declaratively expressing hard combinatorial optimization problems and solve them with local search techniques. It delivers tools to practitioners that enables them to quickly experiment with multiple models, heuristics, and meta-heuristics, focusing on their application rather than the delicate minutiae of producing a competitive implementation. At its heart, the declarative models are reminiscent of the modeling facilities familiar to constraint programming, while the underlying computational model heavily depends on incrementality. The net result is a platform capable of delivering competitive local search solutions at a fraction of the efforts needed with a conventional approach delivering model-and-run to local search users.

Access provided by CONRICYT-eBooks. Download reference work entry PDF

Constraint-Based Local Search

Local Search Algorithms for Solving the Combinatorial Optimization and Constraint Satisfaction Problems

Theory of Local Search

Keywords

Introduction

Complete techniques such as Integer Programming and Constraint Programming typically offer optimality guarantees on the results they deliver but do not always scale to large instances. This explains the appeal of local search methods that deliver a different trade-off in the algorithmic design space, favoring scalability at the expense of guarantees. Local search algorithms apply to diverse application domains such as routing, scheduling, resource allocation, or rostering to name just a few. In most cases, local search techniques scale to truly large problem instances that are often out of scope for complete techniques and are capable of producing streams of solutions of improving quality.

Yet, while modeling and high-level tools are ubiquitous for Mixed Integer Programming and Constraint Programming, they have been relatively unexplored for local search until recently. This is primarily due to the fact that the separation of models and algorithms is not as simple in local search compared to MIP and CP which are declarative in nature. Indeed, the vast majority of papers discussing local search describe their solution in algorithmic terms rather than declarative terms like models, decision variables, and constraints. The 1990s witnessed a shift in interest and the emergence of multiple tools expressly dedicated to local search techniques. GSAT [13, 14] and WalkSAT [15] offered the initial impetus behind formulating problems with a simple language (in clausal form) and using generic local search algorithms operating on that encoding. Integer Optimization by Local Search [25] generalized this line of work to the richer language of integer programming.

Localizer [8, 9] took a different approach, providing a first step to build a general-purpose modeling language for local search. It introduced the concept of invariants to express arbitrary one-way constraints that are automatically and incrementally updated under variable assignments. These invariants can then encode, in a declarative fashion, the incremental data structures typically needed in the implementation of meta-heuristics such as Tabu Search [5], Min-Conflict Search [10], Simulated Annealing [6], Scatter Search [7], or GRASP [4] to name just a few.

Constraint-Based Local Search is the culmination of this line of work. It complements the constraint programming efforts typically focused on complete search techniques and delivers a “model and search” framework in which one uses decision variables and constraints to model a problem and relies on search procedures to explore the underlying search space. Comet is an optimization platform that embodies Constraint-Based Local Search and is a direct descendant of Localizer. It is an object-oriented programming language with explicit support for modeling problems declaratively and solving them with local search techniques. The contributions underlying Comet span from the incremental computation model, the modeling abstractions, and the control mechanisms to specify and execute local search heuristics and meta-heuristics easily, efficiently, and compactly.

Foundations

Constraint-Based Local Search aims at implementing the vision captured by the equation

$$\displaystyle \begin{aligned} \text{Local Search = Model + Search}\end{aligned} $$

that expresses the belief that a local search algorithm is best viewed as the composition of a declarative model with a search component. This separation of concerns is central: it postulates the importance of expressing the structures of the problem being solved declaratively and compositionally and providing a search component which exploits those structures and guide the search toward high-quality local optima.

The Constraint-Based Local Search architecture delivers several key benefits:

Rich Language :: Constraints are declarative and capture the problem substructures. They range from simple arithmetic constraints, the indexing of arrays of variables with variables, meta-constraints (constraints on the truth value of other constraints) and logical constraints, to combinatorial constraints such as cardinality, sequence, or alldifferent constraints to name just a few. Constraints (and combinators) for local search were introduced in [24].
Rich Search :: Programming meta-heuristics is supported by a wealth of language combinators and control abstractions to automate the most tedious and error-prone aspects of an actual implementation. The abstractions foster the decoupling of neighborhood, heuristics, and meta-heuristics specifications while leveraging the incrementality exposed by the constraints present in the declarative model . Control abstractions were introduced in [20].
Separation :: The untangling of model and search promotes the independent design and evolution of these two components. With Constraint-Based Local Search, it is possible to explore alternative models independently of refinements to the search procedures.
Versatility :: The ability to specify meta-heuristics orthogonally to the model also enables a collection of generic search routines which are highly reusable and promote the experimental process to design an effective CBLS program. This versatility further promotes the reuse of highly generic “canned” search procedures.
Extensibility :: New constraints and objective functions can be added to the system library and used in conjunction with native constraints. Perhaps even more interestingly, the new constraints can be implemented directly in the host language (i.e., Comet), and the bulk of the implementation is often cast in terms of invariants. New heuristics and meta-heuristics can also be easily added to the system as the implementation of any heuristic or meta-heuristic relies on a few key concepts such as closures, continuations, selectors, and neighbors.
Performance :: Finally, the architecture heavily relies on incrementally maintaining the computational state over time. This capability is compositional and a direct by-product of the declarative model. The approach enables the platform to deliver Constraint-Based Local Search programs that are a fraction of the size and complexity of handcrafted code, yet deliver performance comparable, and sometime exceeding, manually crafted implementations .

The rest of this chapter starts with an illustration of Constraint-Based Local Search through the modeling and resolution of the classic n −queens problem in section “Getting Started.” Section “Foundations” discusses the theoretical underpinnings of Constraint-Based Local Search starting with models and concluding with programs. Section “Case Studies” focuses on how to model applications with a rich language that goes beyond Boolean formulas or linear equations. Section “Implementation” explores the implementation issues, starting with the support for incremental computation through invariants and proceeding with a discussion of differentiation. Section “Empirical Results” gives a brief survey of the type of performance that can be expected from Constraint-Based Local Search systems, and section “Conclusion” concludes the chapter.

Getting Started

To introduce Constraint-Based Local Search, it is valuable to start with the modeling and resolution of a simple well-known problem. The examples presented in this chapter uses the Comet platform.

The Problem

The n −queens problem is to place n queens on a chess board of size n × n so that no two queens can attack each other. While the problem is polynomial, its simplicity is appealing to illustrate Constraint-Based Local Search. The Comet program is shown in Fig. 1 and features two clear components that are discussed next.

The Model

The model definition spans lines 4–9, is declarative, and exclusively focuses on defining an array of decision variables queen in line 6 and three combinatorial constraints on lines 7–9. Variable queen_i models the row on which the queen in column i is to be placed. Each decision variable has a domain Size representing the set of permissible values for that variable. Each combinatorial alldifferent constraint takes as input an array of expressions and requires that the values of all entries in the array be pairwise distinct. For instance, line 7 states that no two queens can be assigned to the same row. The constraints on lines 8 and 9 play a similar role but for the upward and downward diagonals. Note how an operator all is used on line 8 to create an array of expressions

$$\displaystyle \begin{aligned} (\text{queen}_1+1,\mathrm{queen}_2 + 2,\mathrm{queen}_3 + 3,\cdots, \mathrm{queen}_7 + 7,\mathrm{queen}_8 + 8) \end{aligned}$$

which is the input of the combinatorial constraint.

The Search

A classic Constraint-Based Local Search starts from a tentative assignment of values to the decision variables and iteratively transforms it, moving from tentative assignments to tentative assignments using a local move operator. The local move used in this specific case is the assignment of a single variable to a new value. Namely, with n decision variables, each with a domain of size n, one could consider up to Θ(n²) such moves. To illustrate the search process, consider the left board in Fig. 2a which depicts a tentative assignment. Here, a move consists of relocating a queen to a new row and the algorithm chooses the best such move. The right side, Fig. 2b, shows the reduction in violations for each possible move. Therefore, a viable move is to relocate queen₄ to row 3, reducing the total number of conflicts (violations) from 7 to 5.

The search outlined above is a classic greedy search. The implementation spanning lines 11–14 obtains the set of constraints present in the model (line 11) and starts from a randomly initialized tentative assignment σ₀. It proceeds through a sequence of moves aimed at satisfying the three softened constraints present in S. The underlying neighborhood function N defined as

$$\displaystyle \begin{aligned} \begin{array}{ll} N(\sigma) = \{ \sigma' \:|\: \exists j \in 1\ldots8 \; \forall i &\in 1\ldots8, i\neq j: \sigma'(\mathrm{queen}_i) = \sigma(\mathrm{queen}_i) \wedge \\ & \sigma'(\mathrm{queen}_j) \in D(\mathrm{queen}_j) \setminus \{\sigma(\mathrm{queen}_j)\} \}\end{array} \end{aligned} $$

is implemented with the select statement on line 12 that considers the reassignment of a single decision variable at a time. Overall, the search produces a sequence of tentative assignments

$$\displaystyle \begin{aligned} \sigma_0,\sigma_1 \in N(\sigma_0),\sigma_2\in N(\sigma_1),\cdots,\sigma_k \in N(\sigma_{k-1}) \end{aligned}$$

delivering a solution σ_k that satisfies all the softened constraints (violations of S are 0).

Foundations

This section reviews the foundations of Constraint-Based Local Search, covering both models and programs. It introduces the main concepts behind the declarative and operational models.

Models

From an end-user perspective, constraints and objective function s are at the heart of Constraint-Based Local Search. They provide the declarative bricks needed to construct models describing requirements and properties of the solution being sought. They also support the underlying computational model. This section first reviews the key concepts of constraints and objective functions before finishing with a presentation of the underlying semantics.

Basics

Constraint-Based Local Search is the process of looking for an assignment of values to decision variables that meets specific requirements. Decision variables are central to the modeling process as they characterize solutions. This chapter focuses on integer variables only for simplicity. Extensions to more complex variables (i.e., set, paths, and trees) have been proposed in [12, 23]. The chapter also assumes that Constraint-Based Local Search models are defined over a set X of decision variables.

Definition 1 (Assignment)

An assignment σ is a mapping X → D(X) from variables to values in their domain. The value assigned to x in σ is denoted by σ(x). The set of all possible assignments is denoted by Σ.

For convenience, the expression σ[x∕v] denotes a new assignment σ′ which is similar to σ except that variable x is assigned to v, i.e.,

$$\displaystyle \begin{aligned} \forall y \in X \setminus \{x\} \: : \: \sigma'(y) = \sigma(y) \wedge \sigma'(x) = v. \end{aligned}$$

Constraints are used to impose requirements on the decision variables. Constraints are naturally declarative, can be expressed in a variety of ways, and always capture a relation over a subset of variables from X.

Definition 2 (Constraint)

A constraint c(x₁, ⋯, x_n) is a n −ary relation over variables x₁⋯x_n ∈ X. The set vars(c) is the set of n variables appearing in c, i.e., vars(c) = {x₁, ⋯, x_n}.

Constraints can be expressed through algebraic expressions, logical statements, or combinatorial structures.

Example 1

In the queens example, the requirement that any two variables cannot lay on the same row, i.e., alldifferent(x), is semantically equivalent to the conjunction of constraints

$$\displaystyle \begin{aligned} \bigwedge_{i \in 1\ldots8, j \in i+1\ldots8} x_i \neq x_j. \end{aligned}$$

Operationally, however, the alldifferent maintains its state and violations more efficiently than the naive reformulation above.

Example 2

A constraint system S is a set of constraints and its truth value is equivalent to the truth value of ∧_{c ∈ S} c.

Evaluations and Violations

The driving force behind Constraint-Based Local Search rests on the ability to assess how badly constraints are violated. This is captured by the concept of violation degrees (or violations for short).

Definition 3 (Violation Degree)

The violation degree of c(x₁, ⋯, x_n) is a function $\nu _c : \varSigma \rightarrow \mathbb {R}^+$ such that, for any assignment σ such that σ(x₁) ∈ D(x₁), ⋯, σ(x_n) ∈ D(x_n), it holds that

$$\displaystyle \begin{aligned} c(\sigma(x_1),\cdots,\sigma(x_n)) \equiv \nu_c(\sigma) = 0. \end{aligned}$$

The violation degree definition depends critically on the structure conveyed by constraint c. The definition of violation is constraint-dependent but is derived systematically for algebraic and logical expressions. For completeness, consider the specification of expression evaluation.

Definition 4 (Expression Evaluation)

Let $e \in {\mathcal {E}}$ be an arithmetic expression and σ ∈ Σ be an assignment. The evaluation of e with respect to (wrt) σ is specified by the function $\mathbb {E}(\sigma, e) : \mathcal {E} \times \varSigma \rightarrow \mathbb {Z}$ which is defined inductively on the structure of e in Fig. 3.

Algebraic constraints are based on relations and logical combinators. To reason about the violations of relational and logical constraints, it is useful to derive an expression modeling the violations of constraint c from the structure of c.

Definition 5 (Constraint Conversion)

Let c be a logical or relational constraint. The constraint conversion of c is an expression $\mathbb {V}(c)$ which can be evaluated to determine the violations of c with respect to some assignment. It is specified by the function $\mathbb {V}(c) : \mathcal {E} \rightarrow {\mathcal {E}}$ which is defined by induction on the structure of c as specified in Fig. 4.

The conversion for the conjunction of two constraints is none other than the sum of the converted relation violations.

Example 3

The conversion of x = 5 ∧ y ≠ 10 where x, y ∈ X is derived as follows:

$$\displaystyle \begin{aligned} \mathbb{V}(x{=}5 \wedge y\neq 10) {=} \mathbb{V}(x=5) + \mathbb{V}(y\neq 10) = \textsc{abs}(x - 5) + 1 - \min(1,\textsc{abs}(y - 10)). \end{aligned}$$

It is now possible to compose both functions to obtain the actual violations of an algebraic constraint c with respect to an assignment σ.

Example 4

The violation of an arithmetic constraint c ≡ l ≥ r is given by

$$\displaystyle \begin{aligned} \mathbb{E}(\sigma,\mathbb{V}(l \geq r)) \end{aligned}$$

The violation degree function for c is then given by

$$\displaystyle \begin{aligned} \nu_{c}(\sigma) = \mathbb{E}(\sigma,\textsc{abs}(r - l)) = \max(\mathbb{E}(\sigma,r) - \mathbb{E}(\sigma,l),0). \end{aligned}$$

Example 5

The violation of a conjunction c = c₁ ∧ c₂ is defined as

$$\displaystyle \begin{aligned} \nu_{c}(\sigma) = \mathbb{E}(\sigma,\mathbb{V}(c_1 \wedge c_2)). \end{aligned}$$

While the above mechanics are appropriate to obtain the violations of algebraic constraints, combinatorial constraints define their own notion of violations that capture the combinatorial substructure at hand. Consider the alldifferent constraint again.

Example 6

The violation function of c = alldifferent(x₁, ⋯, x_n) simply counts the number of values used more than once by variables x₁, …, x_n. More precisely, given an assignment σ and vars(c) = {x₁, ⋯, x_n},

$$\displaystyle \begin{aligned} \nu_{c}(\sigma) = \sum_{i \in S} \max(0,|\{ x_j \in \mathrm{vars}(c) | \sigma(x_j)= i\}| - 1) \end{aligned}$$

where S =⋃_{i ∈ 1…n}D(x_i). Consider the alldifferent constraint on the rows for the board in Fig. 2a. The assignment is σ = [1, 4, 5, 4, 8, 7, 8, 3]: It has 2 variables using value 4 and 2 variables using value 8, giving a violation of 2.

Differentiation

The infrastructure covered so far enables the incremental assessment of the satisfaction, and the number of violations, of a constraint c. However, it does not specify how to assess the impact of a local move on the satisfiability or violations of constraints. Gradients are the cornerstone of this process.

Definition 6 (Gradient)

Given an assignment σ and an arithmetic expression e, ↑_x(σ, e) denotes the maximum increase for the evaluation of e over all possible values in D(x) wrt σ, whereas ↓_x(σ, e) denotes the largest decrease for the evaluation of e over all possible values in D(x) wrt σ, i.e.,

$$\displaystyle \begin{aligned} \uparrow_x(\sigma,e) = \max_{v \in D(x)} \mathbb{E}(\sigma[x/v],e) - \mathbb{E}(\sigma,e) \end{aligned}$$

$$\displaystyle \begin{aligned} \downarrow_x(\sigma,e) = \mathbb{E}(\sigma,e) - \min_{v \in D(x)} \mathbb{E}(\sigma[x/v],e). \end{aligned}$$

Note that gradients are nonnegative in this specification. An efficient implementation can be derived inductively on the structure of expression e. Figure 5 gives an abridged version of such derivation. The definition for ↑_x(σ, x) is an interesting base case. Indeed, ↑_x(σ, x) =max_{v ∈ D(x)}v − σ(x) which has the effect of picking up the largest increase as the distance between the value currently assigned to x in σ and the largest value of the domain. Similarly, note how ↑_x(σ, e₁ − e₂) combines the largest increase in e₁ with the largest decrease in e₂.

The next concept, variable violation, is interesting: It captures how many violations can be attributed to a specific variable for a given assignment. Variable violations are specified in terms of gradients .

Definition 7 (Variable Violations)

Given a constraint c, the variable violations of c wrt x ∈vars(c) and assignment σ are specified by $\downarrow _x (\sigma, \mathbb {V}(c))$.

The concepts of violation degrees and variable violations are generic and hence they enable the specification of a common API for all constraints. This API makes it possible to implement the slogan

$$\displaystyle \begin{aligned} \text{Local Search = Model + Search} \end{aligned}$$

mentioned in the introduction. In particular, the API of a constraint is specified in Fig. 6. For instance, the method call violations() simply returns the evaluation of ν_c(σ), while the method call violations(x) return $\downarrow _x (\sigma, \mathbb {V}(c))$, for the current variable assignment σ. Finally, the call to method getAssignDelta(x,v) returns the variation in violation degree when using the assignment σ[x∕v] instead of σ, i.e., it returns

$$\displaystyle \begin{aligned} \nu_c(\sigma) - \nu_c(\sigma[x/v]). \end{aligned}$$

Combinatorial constraints like alldifferent also conform to this interface, and the implementation of the last two methods takes advantage of the constraint semantics to implement the specification incrementally .

Objective Functions

Objective functions play an equally critical role within Constraint-Based Local Search. Objectives provide the necessary mechanics to express and exploit objective functions. Interestingly, once gradients are available, objectives do not add much complexity. Objective functions must conform to the interface depicted in Fig. 7.

Given the current variable assignment σ, the call evaluation() returns $\mathbb {E}(\sigma, e)$, while the call increase(x) returns ↑_x(σ, e) and the call decrease(x) returns ↓_x(σ, e).

Models and Constraint Hardness

From a purely pragmatic and operational standpoint, it is often convenient to partition the actual constraint set C in two

$$\displaystyle \begin{aligned} C = S \cup R \;\;\;\; (S \cap R = \emptyset) \end{aligned}$$

where R represents a set of required but easy to solve constraints and S represents a set of softened constraints that are typically much harder to satisfy. The intent is to handle both type of constraints differently. Intuitively, required constraints are always satisfied during the search, while softened constraints may be violated. In the n −queens examples introduced earlier, R = ∅ and all the constraints are softened in S. In general, however, R may contain some constraints that are not worth relaxing in S. The membership in S or R is clearly a design decision for the modeler to consider.

Definition 8 (Constraint Model)

A Constraint-Based Local Search model M for a constraint optimization problem is a quintuplet M = 〈X, D, F, R, S〉 where

Every x ∈ X is a decision variable taking its value from D(x),
F is, without loss of generality, a minimization function,
R is a set of required constraints (easy to satisfy), and
S is a set of soft constraints (difficult to satisfy).

Declaratively, the semantics of a Constraint-Based Local Search model is given by the optimization problem

$$\displaystyle \begin{aligned} \begin{array}{l} \displaystyle \min_{\sigma \in \varSigma} \mathbb{E}(\sigma,F) + \sum_{c \in S} \nu_c(\sigma) \\ \mbox{subject to} \\ \nu_c(\sigma) = 0 \:\:: \forall c \in R \end{array} \end{aligned}$$

Namely, the objective is to minimize the sum of the violations over the softened constraints and the original objective function subject to the required constraints. In the case of constraint satisfaction, $\mathbb {E}(\sigma, F)=0$ for every σ as the objective is absent. Note that constraints can be weighted, which makes it possible to balance the two terms of the objective. It is simple to write a combinator to weight a constraint in a generic way [23].

Definition 9 (Feasible Solution)

A feasible solution σ to a Constraint-Based Local Search model M = 〈X, D, F, R, S〉 satisfies

$$\displaystyle \begin{aligned} \sum_{c \in S} \nu_c(\sigma) = 0. \end{aligned}$$

${\mathcal {F}}(M)$ denotes the set of feasible solutions to M.

Note that, by definition, every assignment σ also satisfy all the required constraints (ν_c(σ) = 0 : ∀c ∈ R).

Definition 10 (Optimal Solution)

An optimal solution σ^∗ to a Constraint-Based Local Search model M = 〈X, D, F, R, S〉 is a feasible solution $\sigma ^* \in {\mathcal {F}}(M)$ such that

$$\displaystyle \begin{aligned} \forall \sigma \in {\mathcal{F}}(M) : \mathbb{E}(\sigma^*,F) \leq \mathbb{E}(\sigma,F). \end{aligned}$$

Definition 11 (Search Procedure)

A search procedure produces a sequence of assignments σ₀, ⋯, σ_k where ∀i ∈ 0..k : ν_c(σ_i) = 0 (c ∈ R) and returns σ satisfying

$$\displaystyle \begin{aligned} \min_{\sigma \in \{\sigma_0,\cdots,\sigma_k\}} \mathbb{E}(\sigma,F) + \sum_{c \in S} \nu_c(\sigma). \end{aligned}$$

A Constraint-Based Local Search procedure succeeds if $\sigma \in {\mathcal {F}}(M)$.

Programs

The model specifies the properties satisfied by assignments appearing in a trace s₀, s₁, ⋯, s_k; It does not dictate how the assignments in the trace are generated. This is the prerogative of concrete search procedures which are often viewed as the composition of a neighborhood function, a legality restriction function, and a candidate selection function.

Definition 12 (Neighborhood)

The neighborhood of an assignment σ_k, denoted N(σ_k), is the set of assignments reachable from σ_k via a local move.

Local moves can be microscopic changes to the candidate solution such as the reassignment of a single variable or the swap of the values associated with two distinct variables. In specific domains, e.g., in scheduling, the move can be macroscopic and involve changing several variables to capture moves in more complex neighborhood, e.g., moving a task in a job sequence.

Example 7

In the 8 −queens example outlined in section “Getting Started”, the neighborhood is based on the reassignment of a single queen to a new row. The neighborhood consist of Θ(n²) assignments. It could be further restricted to Θ(n) assignments by only considering the queen appearing in the largest number of conflicts and its possible reassignments. Given a model M = 〈X, D, 0, ∅, S〉, where S is the set consisting of three softened alldifferent constraints, the quadratic neighborhood function is

$$\displaystyle \begin{aligned} N(\sigma_k)=\left\{\sigma_k[x/v] \:|\: x \in X \wedge v \in D(x) \setminus \{\sigma_k(x)\}\right\}, \end{aligned}$$

while the linear neighborhood function is

$$ N({\sigma _k}) = \left\{ {{\sigma _k}[x/v]\:|\:x \in *{\rm{arg - ma}}{{\rm{x}}_{y \in X}}{ \downarrow _y}({\sigma _k},(\mathop \wedge \limits_{_{c \in S}} c)) \wedge v \in D(x) \setminus \{ {\sigma _k}(x)\} } \right\}. $$

Definition 13 (Legal Neighbors)

The legal neighborhood of an assignment σ_k is a restriction of N(σ_k), namely, L(N(σ_k), σ_k) ⊆ N(σ_k), and the legal subset is required to at least satisfy all the required constraints R.

Note that the legal subset of N(σ_k) may even be more restrictive and reject neighbors that are feasible with respect to R but fail to exhibit other characteristics. The full characterization of the function L is part of the definition of a meta-heuristic . For instance, the tabu meta-heuristic excludes neighbors that were seen in the recent past.

Definition 14 (Neighbor Selection)

The selection function S is responsible for choosing the next assignment among legal neighbors . Namely,

$$\displaystyle \begin{aligned} \sigma_{k+1} = S(L(N(\sigma_k),\sigma_k),\sigma_k) \in L(N(\sigma_k),\sigma_k). \end{aligned}$$

For instance, a greedy selection chooses the best neighbor, i.e.,

$$\displaystyle \begin{aligned} \sigma_{k+1} \in \operatorname*{\mathrm{arg-min}}_{\sigma \in N(\sigma_k)} \mathbb{E}(\sigma,\mathbb{V}(S)) \end{aligned}$$

A heuristics or meta-heuristics specifies the three functions N, L, and S which parameterize the computation model.

Control Primitives

To support these abstractions, Constraint-Based Local Search programs rely on a handful of control primitives designed to automate tedious and error-prone implementation details.

While the specification of a program relies on three distinct functions N, L, and S, any implementation concerned with performance produces code that fuses the three functions often degrading the readability and maintainability in the process. Key considerations such as randomization and tiebreaking add another layer of complexity to the code. The implementation of meta-heuristics induces its share of complexity by refining move legality and selection further.

Comet attempts to strike a delicate balance between efficiency, code readability, and ease of maintenance by decoupling these aspects as much as possible. The language introduces selectors, neighbors, and randomized choosers as control abstractions.

Neighborhood Selectors

The concept of neighborhood selector is a cornerstone for the specification of complex local searches. A simplified version of its interface is presented below:

The key idea is that a neighbor is defined as a pair 〈q, c〉 consisting of a quality measure q and a closure c. The intuition is that, in general, the closure c defines the move which, when executed, will produce an objective value of q for the resulting assignment. Method insert adds a neighbor c of quality q (line 2), method hasMove checks whether the neighborhood is nonempty, and method getMove returns the selected move.

Concrete implementations of this interface commit to a specific selection policy. For instance, the concrete selector MinNeighborSelector implements the neighborhood interface and retains only a neighbor minimizing the quality measure. Namely, if the set of inserted neighbors is N = {〈q₁, c₁〉, ⋯, 〈q_n, c_n〉}, the selector retains one neighbor

$$\displaystyle \begin{aligned} \langle q,c\rangle \in \operatorname*{\mathrm{arg-min}}_{\langle q_j,c_j\rangle \in N} q_j \end{aligned}$$

and produces it as its selection when getMove is called. Alternative selectors include KMinNeighborSelector that returns one of the top− k best neighbors (k being a parameter of the selector).

The neighbor Control Primitive

Neighborhood selectors work in conjunction with the neighbor control primitive. The primitive has the following syntax:

neighbor(〈 e x p r〉, 〈 N〉) 〈 B o d y〉

where 〈expr〉 refers to an arbitrary arithmetic expression, 〈N〉 is an expression referring to a selector, and 〈Body〉 is a statement (or block of statements). From a semantics standpoint, the control primitive creates a closure c of the body code responsible for producing the assignment σ_k+1 from the current assignment σ_k. It then associates the closure with a quality measure q and submits the pair 〈q, c〉 to the selector denoted by N. What makes neighbor particularly attractive is the syntactic closeness between the code specifying the quality of the move and the code carrying out the move even if, in practice, there is a strong temporal disconnection between the time when the closure is recorded with the selector and the time it gets executed.

The search procedure in Fig. 8 illustrates an alternative implementation of the greedy search presented in Fig. 1. The loop on lines 3–4 scans all variables and values accumulating the reassignments in the selector N and associating with each one a quality measure based on the delta. The 1-instruction block queen[i] := v; on line 4 is automatically wrapped in a closure that is entrusted by neighbor to the selector N. The beauty in the construction lies in the ability to easily accumulate in the same selector the union of multiple neighborhoods , all defined with different move operators. This capability will be illustrated in the Progressive Party Problem use case in section “Progressive Party.”

Randomized Choosers

To support developers, Comet provides control abstractions to make greedy, semi-greedy, and randomized choices. The abstractions encapsulate the necessary state to deliver independent pseudorandom streams in each such instruction appearing in the program. For instance, the Θ(n)-sized neighborhood that considers reassigning the queen with the most violations to a new row, is easily modeled with instructions in lines 3–7 below.

The bracketed 2 on line 3 simply requests the selector to retain any value i among the best two (according to the violation measure).

Discussion

The Constraint-Based Local Search model appearing in Fig. 1 highlights the key features of the framework. It features a complete separation between a declarative model and a procedural search component. The declarative model relies on combinatorial constraints specifying the properties of solutions, while the search is exclusively devoted to the selection of a heuristic and meta-heuristic . In this model, the search remains problem specific. Yet, both the model and the search can evolve independently. One can add constraints without changing the search or choose a different search strategy without modifying the model. All these characteristics, when blended with the performance of an incremental computation, deliver an appealing architecture for producing local search solutions.

The program in Fig. 1 can still be improved. In particular, it is tempting to provide syntactic sugar to automatically handle the boiler plate code and support the notion of constraint annotations to partition the constraint set into soft and required constraints S ∪ R. The resulting program is shown in Fig. 9. The model m is now attaching a soft annotation to each constraint to dictate its addition to S, while line 10 is used to extract the set of soft constraints from m. Perhaps even more interestingly, the adoption of an explicit first-class model concept enables the authoring of completely generic search procedures. Indeed, the code in lines 10–13 can be packaged as the reusable min-conflict procedure depicted in Fig. 10.

Naturally, lines 10–13 from Fig. 9 disappear from the model in favor of a single line calling the generic minConflictSearch on model m program, i.e.,

This leaves us with a 10 lines Constraint-Based Local Search implementation.

Case Studies

To explore Constraint-Based Local Search, it is desirable to consider a few applications that are elegantly and effectively solved with Comet. The next three subsections consider the progressive party problem [16], car sequencing [3], and scene allocation [18] as each application illustrates a different aspect.

Progressive Party

The progressive party problem is a standard benchmark in combinatorial optimization and it illustrates two important features. It shows a rich model with many combinatorial constraints as well as constraints on the truth value of relations. It also shows how soft constraints may be instrumental in obtaining a neighborhood. The goal in this problem is to assign guest parties to boats (the hosts) over multiple time periods. Each guest can visit the same boat only once and can meet every other guest at most once over the course of the party. Moreover, for each time period, the guest assignment must satisfy the capacity constraints of the boats.

Figure 11 depicts the declarative part of the model. The decision variable boat[g,p] specifies the boat visited by guest g in period p. Lines 8–9 specify the alldifferent constraints for each guest, lines 10–11 specify the capacity constraints, and lines 12–13 state that two guests meet at most once during the evening. The soft(2) annotations added on lines 9 and 11 are not only specifying that the constraint must be softened, but they also associate a fixed static weight of 2 with each constraint. The weights can be easily incorporated in the inductive definition of $\mathbb {V}(c)$ shown in Fig. 4

$$\displaystyle \begin{aligned} \mathbb{V}(\mathtt{soft}(w) : c) = w \cdot \mathbb{V}(c)\end{aligned} $$

to handle statically weighted soft constraints.

The Neighborhood

The first sensible neighborhood to consider focuses on reassigning a single variable boat[g,p] to a new value. This can follow the same template used for the queens problem. These moves impact the violations of all the constraints. However, these moves may also prove too restrictive. When an instance is near satisfaction, one can expect most of the bins in any given knapsack to be near full. A single variable reassignment amounts to moving an item from one bin into another and that may prove fruitless from a violation standpoint. A natural idea is to include a second neighborhood that considers the exchange of values between two variables appearing in the same constraint. While such swaps have no effects on the alldifferent constraints, they can more easily lead to violation improvements for the knapsack constraints. Formally, the neighborhood is therefore

$$\displaystyle \begin{aligned} \begin{array}{lclll} N &= &\{ \sigma[x/v] &\:|\: &x = \operatorname*{\mathrm{arg-max}}_{z \in X} \downarrow_z(\sigma,\mathbb{V}(S)) \wedge v \in D(x) \setminus \{\sigma(x)\} \} \bigcup \\ & & \{ \sigma[x/c,y/d] &\:|\: &x = \operatorname*{\mathrm{arg-max}}_{z \in X} \downarrow_z(\sigma,\mathbb{V}(S))\: \wedge \\ & & & & y \in \bigcup_{c \in S \wedge x \in \mathrm{vars}(c)} \mathrm{vars}(c) \wedge c = \sigma(y) \wedge d = \sigma(x) \} \end{array} \end{aligned}$$

where S is the set of soft constraints.

The code in Fig. 12 implements that idea. The main loop (lines 7–30) seeks to improve the overall violations of the soft constraints. The selector on line 9 picks a variable boat[g,p] that induces the most violations. Once the variable is selected, the two nested selectors (lines 10–15 and lines 16–22) implement the two parts of the neighborhood structure. Lines 10–15 select the variable with the most violations and choose a new value that decreases its violations the most. The second selector is more interesting. It picks a second variable boat[g1,p] in the same period p as the first variable boat[g,p] in such a way that the swap between the two variables has the largest impact on the overall violations of S. Note that both variables appear in the knapsack constraint stated over period p. The remainder of the code (lines 23–28) executes the best move in N (if one exist) and updates the variable tabu tenure.

The 30 lines of code are compact and elegant: They benefit from the automation provided by the neighborhood selector, the selectors, and the neighbor construction. Yet, they still require some effort to analyze the model and produce a code template that follows a standard recipe. In addition, this code skeleton must still be updated with classic ideas like search intensification around high-quality local minima and diversification to escape from basins of attraction. However, the steps applied in deriving this search procedure are rather systematic: They rely on an analysis of the model to recognize the presence of specific types of constraints that then suggest a particular neighborhood structure. The is the idea behind the synthesis of search procedures that is described next .

The Synthesized Search

Given that models are first-class objects, Comet can manipulate and analyze them. Here, Comet recognizes the presence of knapsack constraints and generates a composite neighborhood consisting of the union of variable assignments and of the variable swaps appearing in violated knapsack constraints, an idea first articulated by Van Hentenryck [19]. The synthesis process per se was described in details in [22].

The skeleton of a synthesized tabu search is depicted in Fig. 13. It uses the fact that all variables have the same domains. Lines 7–9 associate with each decision variable x_i the set of constraints mentioning x_i and susceptible to benefit from exchanging (swapping) the values of two of its variables. This initial step is a straightforward projection of the constraint array in S that only retains constraints that refer to x_i and can use a swap. Line 10 defines a neighborhood selector. Line 15 selects the variable x_i with the most violations among the softened constraints S. Lines 16–20 focus on the first part of the neighborhood and consider simple reassignments that lead to the largest violation decrease. All the potential neighbors are submitted to N. Lines 21–29 consider all the constraints referring to variable x_i and for which swaps can be of potential benefit. For each such constraint, the code retrieves the variables of the constraint and accumulates in the selector N all the closures modeling swaps (along with their impact on violations).

It is appealing to notice the similarities between the manual and synthetic implementation. In essence, they both capture the same idea. Yet, the generic code adapts to the model and consider exploiting all the constraints susceptible to profit from swaps. The Comet extension required to do so is a minimal extension to query the capabilities of the constraint in the model.

As shown later, the synthesized search outperforms all published results on this problem. Note that, if the set of required constraints R was not empty (it is empty in this application), the two neighborhoods would have to discard assignments and swaps that yield nonzero values for the calls to getAssignDelta and getSwapDelta to implement the legality requirement correctly. Finally, observe that this skeleton implementation contains a very simply tabu condition to further restrict the legal moves to those that were not recently attempted; this is achieved with two simple data structures (one per neighborhood) that record the last iteration number when a move was performed. Supporting generic intensification and diversification is equally easy .

Car Sequencing

Figure 14 presents a model for car sequencing. In this application, n cars must be sequenced on an assembly line of length n. The customer demands for car configurations are specified in an array demand and the total demand is, of course, n. Each car configuration may require a different sets of options, while capacity constraints on the production units restrict the possible car sequences. For a given option o, these constraints are of the form k out of m meaning that, out of m successive cars, at most k can require o. The model declares the decision variables specifying which type of car is assigned to each slot in the assembly line (line 12). It states a hard constraint specifying which cars must be produced (line 13) and then states the soft capacity constraints for each option (lines 14–15).

The handcrafted search procedure, illustrated in Fig. 15, is modeled after a conflict minimization structure. The initialization satisfies the cardinality constraint by using a random permutation of an array of values that already meet the cardinality requirement (lines 4–7). The main loop (lines 10–27) minimizes the number of violations by selecting the slot of the assembly line causing the most violations and swapping its content with another slot that delivers the most improvements. The move itself appears on line 14. The search features a diversification component (lines 19–25) that randomly swaps a subset of slots in the assembly line when no improvement took place for a number of iterations. Each time an improving move is found, the stability counter is reset and the best value for this stage is recorded (line 18).

It is possible to recognize the combinatorial structure present in the model thanks to the presence of global sequence constraints and to automatically synthesize a search procedure that matches the ideas present in the handcrafted search procedure. The result is shown in Fig. 16. It depicts a generic tabu search procedure featuring several key components. Note how line 6 of the model retrieves the required constraints (line 3) and initializes the start assignment by delegating to each required constraint the task of picking a suitable assignment. A basic requirement for achieving this is the following independence property of the required constraints:

$$\displaystyle \begin{aligned} \forall c_i,c_j \in R \: \mbox{ s.t. }\: i \neq j : \mathrm{vars}(c_i) \cap \mathrm{vars}(c_j) = \emptyset. \end{aligned}$$

In this case, R = {atmost(demand,line)} and the sole cardinality constraint can create, in polynomial time, an array of values that meet the cardinality requirement and randomly permute it to produce the initial assignment to the variables in vars(c). The algorithm for the cardinality constraint uses a (randomized) feasible flow algorithm to match values to variables. As all variables appear in the cardinality constraint, swapping two variables is feasibility-preserving (the number of cars of each type is unchanged). Moreover, the cardinality constraint is tight, meaning that there is a bijection from variable to value occurrences. The core of the search spans lines 22–31 and features the selection of the most conflicting variable (line 23) together with the variable that yield the largest decrease in violations through a swap (lines 24–25). The actual move is performed on line 26 and the move is marked tabu in line 27.

The implementation of the diversification is more interesting. To modularize the capability, it relies on events. In Comet, objects like Counter, Integer, or var{int} are capable of dispatching notifications when specific events occur. For instance, a counter issues a change event when its value is modified. Comet provides the ability to associate a code fragment with events: The code is then executed in response to these events. This is illustrated on line 14 that states that, each time the iteration counter it changes, the stability counter stable must increase. Similarly, lines 15–21 specify that, when the stability counter changes, one should check whether it has reached a critical value, 500 in this example, in which case a diversification step is undertaken. This architecture promotes the separation of the diversification logic from the main heuristic . Indeed, the code for the diversification simply dictates how to react to changes to the stability counter and the Comet platform automatically weaves that code in the proper place. Finally, note how recording improvements in the violations are also done through an event hooked on the violations of the entire soft system S.

Scene Allocation

Figure 17 features a model for the scene allocation problem that is sometimes used to compare CP and MIP solvers since it is highly symmetric. The problem consists of assigning specific days for shooting scenes in a movie. There can be at most five scenes shot per day and all actors of a scene must be present. Each actor has a fee and is paid for each day she/he plays in a scene. The goal is to minimize the production cost. The decision variable scene (line 12) represents the day a scene is shot. The hard cardinality constraint (line 13) specifies the maximum number of scenes shot on any one day. The objective function minimizes the sum of actor compensations, which is the actor fee times the number of days he/she appears in a scene shot on that day.

The model in Fig. 17 is now a constraint optimization model featuring an objective function that demands a different strategy to obtain a suitable search procedure. In general, it is necessary to juggle three considerations. First, one should maintain the feasibility of the required constraints through a suitable initialization and the selection of moves that never violate the constraints in R. Second, one may have to deal with softened difficult constraints (S) for whom one searches for a feasible solution by driving down the violations. Third, it is essential to drive down the value of the objective function. The latter two considerations (true objective and softened constraint) are naturally conflicting as it is easier to drive the objective function down if one violates difficult constraints and vice versa. The practical response is to rely on a statically or a dynamically weighted sum of the two objectives where the search shifts the emphasis on either considerations by altering the weights.

In this application, S = ∅ and R = {atmost(occur, scene)}; hence, the task is somewhat simpler as there is only one component to the objective function . In this case, the generated tabu search is driven by the sole required constraint but with a significant difference. In the previous example, the soft constraint was tight, a fact detected by the model analysis . Indeed, the cardinality constraint in car sequencing is tight because the assembly line has as many slots as the number of cars to produce. This is not the case here: there are typically fewer scenes than the number of slots in which they can be scheduled and thus the required constraint is not a bijection between variables and value occurrences. As a result, limiting the neighborhood only to swaps would preserve the feasibility of the cardinality constraint at the expense of a significant decrease in solution quality. This is not surprising since the neighborhood would no longer be connected. The model analysis however recognizes that the atmost constraint is not tight and also considers feasibility-preserving assignments.

The generated skeleton is depicted in Fig. 18. As before, line 5 uses the required constraints to initialize the search to a feasible assignment (once again, the task is delegated to the required constraints and the model analysis ensures that vars(c_i) ∩vars(c_j) = ∅ ∀ c_i, c_j ∈ R before generating code. The core of the search spans lines 11–24 and relies on the union of two neighborhoods. Line 12 starts by selecting a variable x_i that can lead to the largest decrease in the objective function. Lines 13–15 consider all the swaps that include x_i and lead to the largest decrease in the objective function (i.e., the most negative delta). The selector on line 13 is semi-greedy and will select, uniformly at random, one of the top-3 such moves. Lines 16–19 are devoted to the second neighborhood and collect the best value to reassign x_i. Line 17 shows the conjunct that eliminates assignments that are not feasible with respect to R. The skeleton search uses a vanilla tabu data structure and omits the diversification component for simplicity .

Implementation

The implementation of a Constraint-Based Local Search system critically depends on incremental computation. Constraints and objective functions must respond to their APIs like violations, increase, decrease, or getAssignDelta extremely fast in order to consider large neighborhoods and long traces of assignment within an allotted time.

To deliver this performance, the implementation is presented in two distinct layers. The invariant layer is responsible for the basic incremental computation that occurs when an assignment is changed through a local move operator. The differentiability layer is responsible for implementing the response mechanism behind the constraints and objective function. Their implementation is primarily framed in terms of invariants. Both are highlighted in this section, starting with invariants (section “Invariants”) and finishing with differentiation (section “Differentiation”).

Invariants

Invariants provide a declarative concept that relieves programmers from the tedious task of maintaining complex data structures incrementally. By focusing on what to maintain, rather than how to maintain assignments under changes, programmers are relieved of an error-prone, yet critical, aspect of implementing constraints and objective functions . In essence, invariants capture so-called one-way constraints [1, 2, 11, 17], namely, they capture the value of an expression that must be maintained over time under changes to the value of its variables. An acyclic network of dependencies connects all the variables of the problems and is responsible for scheduling the evaluations. This subsection reviews examples and outlines the underlying implementation.

Definition 15 (Invariant)

An invariant ${\mathcal {I}}$ is a one-way constraint

$$\displaystyle \begin{aligned} \langle x_1, \ldots, x_n \rangle \leftarrow f(y_1,\ldots,y_m) \end{aligned}$$

where x₁, …, x_n are called invariant variables and y₁, …, y_m are either decision or invariant variables. The set O = {x₁, …, x_n} is the output variables of ${\mathcal {I}}$ The set I = {y₁, …, y_m} are the input variables of ${\mathcal {I}}$. We often abuse notation and rewrite the one-way constraints as

$$\displaystyle \begin{aligned} O \leftarrow f(I). \end{aligned}$$

${\mathcal {I}}_O$, ${\mathcal {I}}_I$, and ${\mathcal {I}}_f$ denote the output variables, the input variables, and the function of invariant ${\mathcal {I}}$.

Since invariants are one-way constraints, there are some necessary syntactic restrictions. One such restriction is that no two invariants have a common output variable. This ensures that every invariant variable is defined at most once.

The declarative semantics of an invariant specifies that the one-way constraints always holds.

Definition 16 (Declarative Semantics of an Invariant)

Let σ be an assignment before or after any atomic instruction of a program for which the invariant ${\mathcal {I}}$ has been posted. Then, it follows that

$$\displaystyle \begin{aligned} \langle \sigma(x_1), \ldots, \sigma(x_n) \rangle \leftarrow f(\sigma(y_1),\ldots,\sigma(y_m)) \end{aligned}$$

where ${\mathcal {I}}_O = \{x_1, \ldots, x_n\}$ and ${\mathcal {I}}_I=\{y_1, \ldots, y_m\}$. The narrative abuses notation and sometimes writes

$$\displaystyle \begin{aligned} \sigma({\mathcal{I}}_o) \leftarrow {\mathcal{I}}_f(\sigma({\mathcal{I}}_I)). \end{aligned}$$

Example 8 (Expression Invariant)

The numerical invariant

$$\displaystyle \begin{aligned} x \leftarrow y + 3 * z \end{aligned}$$

stating that, at any point in time, the value of x in an assignment σ, i.e., σ(x), should be the value σ(y) plus three times the value of σ(z).

Operationally, an invariant must maintain the link between its output and input variables under assignments to its input variables. The invariant maintains this link by keeping a local assignment of its input variables and by implementing an update function which updates the global and local assignments to reflect the change in one of its input variables.

Definition 17 (Operational Semantics of an Invariant)

Let ${\mathcal {I}}$ be an invariant. Operationally, ${\mathcal {I}}$ maintains a local store ${\mathcal {I}}_{\sigma }$ over variables ${\mathcal {I}}_I$ and implements an update procedure ${\mathcal {I}}_{u}: \varSigma \times X$. Let $\sigma _l = {\mathcal {I}}_{\sigma }$ be the local store of ${\mathcal {I}}$, σ be an assignment, and $y \in {\mathcal {I}}_I$. The update procedure ${\mathcal {I}}_{u}(\sigma, y)$ performs the following assignments:

$$\displaystyle \begin{aligned} \sigma({\mathcal{I}}_O) &:= {\mathcal{I}}_f(\sigma_l[\sigma(y)/y]({\mathcal{I}}_I));\\ \sigma_l(y)&:= \sigma(y); \end{aligned} $$

To propagate a collection of invariants effectively, the implementation constructs an incremental graph.

Definition 18 (Incremental Graph)

An incremental graph G(X ∪ I, A) is a directed acyclic graph whose vertices coincides with decision variables and invariants and whose arc set correspond to the dependencies induced by the invariant. Each invariant ${\mathcal {I}}$ introduces a dependency $ {\mathcal {I}} \leftarrow y $ for each $y \in {\mathcal {I}}_I$ and a dependency $ x \leftarrow {\mathcal {I}} $ for each $x \in {\mathcal {I}}_O$.

Figure 19 depicts the dependencies of the arithmetic invariant presented earlier.

Example 9 (Summation Aggregate)

A summation invariant captures the relation

$$\displaystyle \begin{aligned} x \leftarrow \sum_{i=0}^{n-1} y[i] \end{aligned}$$

where n is a constant and y denotes an array of n variables. The dependencies are shown below:

The update function ${\mathcal {I}}_u(\sigma, y)$ implements the following code:

where $\sigma _l = {\mathcal {I}}_{\sigma }$.

Example 10 (Counting)

A counting invariant x ←count(y) defined over an array of variables y yields an array of variables x indexed by $R = \bigcup _{i=0}^{n-1} D(y_i)$ that maintains the relations

$$\displaystyle \begin{aligned} \forall \: v \in R \::\: x_v = \sum_{i \:\in \:\mathrm{range}(y)} \left(y_i = v\right) \end{aligned}$$

Namely, x_v counts the number of variables in y currently assigned to v. The dependencies are as follows:

and there are |R|− 1 + n of them. The update function $\mathcal {I}_u(\sigma, y)$ implements the following code:

where $\sigma _l = {\mathcal {I}}_{\sigma }$.

Incremental Computation

Given G(X ∪ I, A), one can obtain a topological sort r of its vertices. Indeed, each dependency y ← x imposes the constraint

$$\displaystyle \begin{aligned} \begin{array}{lcl} 1 + r(x) \leq r(y). \end{array} \end{aligned}$$

The partial ordering expressed in r drives the propagation algorithm that updates all the variables following an assignment of new values to decision variables.

Figure 20 shows the pseudo-code for the invariant propagation algorithm. The propagate algorithm is invoked with the incremental graph G(X, A), an assignment σ and the set of decision variables Y that have been updated. Line 3 initializes a priority queue PQ with all the invariants mentioning any member of Y as one of its sources. The priority associated with invariant ${\mathcal {I}}$ is its topological number $r({\mathcal {I}})$. The main loop spanning lines 6–11 considers the invariants in priority order (see Line 7). The update function of the selected invariant is executed in Line 8. Line 9 collects in C the modified output variables and Line 10 enqueues the new invariant to reconsider.

The correctness of the propagate algorithm hinges on the facts that G(X, A) is acyclic. The use of topological numbers guarantee that the invariant considered in iteration i is handled only after its sources have reached final values in σ. As long as u meets its specification, the assignment σ is guaranteed to satisfy all the invariants considered in iterations 1…i. Computing the affected variables in C and scheduling any invariant depending on them cannot possibly schedule an earlier invariant since the graph is acyclic .