Search

MaxiCP provides a flexible, compositional search framework. The core engine is depth-first search (DFSearch) with branch-and-bound for optimization.

Source of the search package: org.maxicp.search

Depth-First Search with Closures

Following the design of MiniCP [1], the search in MaxiCP is defined by a branching function: a Supplier of an array of Runnable closures, one per child branch. An empty array signals a solution.

DFSearch search = makeDfs(cp, () -> {
    CPIntVar qs = selectMin(q,      // first-fail: pick the variable
        qi -> qi.size() > 1,        //   that is not yet fixed
        qi -> qi.size());           //   with the smallest domain
    if (qs == null) return EMPTY;   // all fixed -> solution found
    int v = qs.min();
    return branch(
        () -> cp.post(eq(qs, v)),   // left branch: assign v
        () -> cp.post(neq(qs, v))   // right branch: remove v
    );
});

The branch method returns a Runnable[]. Each closure calls cp.post() which registers the constraint and immediately runs a full fixed-point computation, propagating all consequences of the decision. An InconsistencyException causes the search to backtrack.

Built-In Heuristics: Variable and Value Selectors

Searches offers a compositional alternative to writing branching closures by hand, separating two orthogonal concerns:

1. A variable selector (Supplier<IntExpression>) — returns the next unfixed variable, or null when all are fixed.

2. A value selector (Function<IntExpression, Integer>) — given the variable, returns the value to try first.

Binary branching — heuristicBinary(varSel) or heuristicBinary(varSel, valSel)

Left branch assigns x = v; right branch removes it (x ≠ v).

// (a) most concise — built-in first-fail
DFSearch s1 = makeDfs(cp, firstFailBinary(q));

// (b) explicit variable selector, default value (min)
DFSearch s2 = makeDfs(cp, heuristicBinary(minDomVariableSelector(q)));

// (c) explicit variable AND value selectors
DFSearch s3 = makeDfs(cp,
    heuristicBinary(minDomVariableSelector(q), x -> x.min()));

N-ary branching — heuristicNary(varSel) creates one child branch per domain value. An overload accepts a scoring function h: int -> int and sorts values by increasing h(v).

// values tried in increasing order
DFSearch s4 = makeDfs(cp, heuristicNary(minDomVariableSelector(q)));

// values closer to n/2 tried first
DFSearch s5 = makeDfs(cp,
    heuristicNary(minDomVariableSelector(q), v -> Math.abs(v - n / 2)));

Built-in variable selectors

• minDomVariableSelector(x) — first-fail (smallest domain).

• staticOrderVariableSelector(x) — first unfixed variable in array order.

Custom variable selectors are trivial to write:

Supplier<IntExpression> maxDom = () ->
    selectMin(q, qi -> !qi.isFixed(), qi -> -qi.size());
DFSearch s6 = makeDfs(cp, heuristicBinary(maxDom));

Advanced Value Selection

• boundImpactValueSelector(objective) — for each candidate value, temporarily assigns it, measures the resulting objective bound, then backtracks. Returns the value that tightens the bound the least — biasing the search towards high-quality subtrees [16].

Conflict-Aware Heuristics

• lastConflict — after a failure, the variable that caused it is retried before consulting the fallback variable selector [17].

• conflictOrderingSearch — maintains a conflict counter per variable; the most conflicted variable is selected first [18].

Scheduling and Sequencing Heuristics

• fds(tasks) — Failure-Directed Search [19] for interval variables. Very effective for proving optimality; supports optional tasks. Branches on status, start time, and duration.

• setTimes(tasks) — branches on the start time of the task with the smallest slack [20]. Assumes all tasks are mandatory.

• rank(tasks) — imposes a total order on tasks (assumes mandatory tasks).

For sequence variables: firstFailBinary(seqVars) selects the insertable node with fewest insertion points; branchesInsertingNode sorts branches by a user-supplied detour cost.

Combinators

• and(b1, b2, ...) — composes strategies sequentially; each strategy is activated only when all preceding ones return EMPTY.

• limitedDiscrepancy(branching, maxDisc) — prunes paths with more than maxDisc right branches (Limited Discrepancy Search) [21].

Branch-and-Bound Optimization

// Minimize with a 60-second time limit
SearchStatistics stats = search.optimize(
    minimize(cost),
    stats -> stats.timeInMillis() > 60_000);

Each time a solution is found, the objective bound is tightened to exclude worse solutions.

Large Neighborhood Search (LNS)

LNS iteratively improves an incumbent by fixing a large subset of variables to their current best values (the freeze phase) then re-solving the relaxed sub-problem [22].

The example below applies LNS to the Quadratic Assignment Problem (QAP).

Model

CPSolver cp = makeSolver();
CPIntVar[] x = makeIntVarArray(cp, n, n);

CPIntVar[] weightedDist = new CPIntVar[n * n];
int ind = 0;
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        weightedDist[ind++] = mul(element(d, x[i], x[j]), w[i][j]);

CPIntVar totCost = sum(weightedDist);
Objective obj = cp.minimize(totCost);
DFSearch dfs = makeDfs(cp, firstFailBinary(x));

Tracking the best solution

int[] xBest = IntStream.range(0, n).toArray();  // identity permutation

dfs.onSolution(() -> {
    for (int i = 0; i < n; i++) xBest[i] = x[i].min();
    System.out.println("objective: " + totCost.min());
});

LNS loop

int nRestarts = 100;
int failureLimit = 100;
Random rand = new Random(0);

for (int i = 0; i < nRestarts; i++) {
    dfs.optimizeSubjectTo(obj,
        stats -> stats.numberOfFailures() >= failureLimit,
        () -> {
            // Fix 95 % of variables to their best-known value
            for (int j = 0; j < n; j++) {
                if (rand.nextInt(100) < 95)
                    cp.post(eq(x[j], xBest[j]));
            }
        }
    );
}

After each call to optimizeSubjectTo the solver automatically restores its state, retracting all temporary fixing constraints. xBest lives outside the reversible state and always reflects the globally best solution found so far.

Full example: QAPLNS.java (raw)

Variable Objective LNS (VOLNS)

Standard LNS applies to well-constrained problems where a feasible solution always exists and the goal is purely to minimise an objective. Many real-world problems are over-constrained: a fully feasible solution may not exist, and the goal is to find an assignment that violates as few constraints as possible.

Variable Objective LNS (VOLNS) [23] handles this by reformulating each hard constraint that may be violated as a soft constraint with an individual violation variable, then minimising the sum of those violations. The key insight is that tightening the individual violations during the LNS loop drives the search towards globally feasible solutions more effectively than simply minimising the total violation sum alone.

The MinimizeObjectiveSum class encapsulates this strategy.

Source: MinimizeObjectiveSum.java

Example: Magic Square

The Magic Square problem requires placing the numbers 1 … n² in an n×n grid so that every row, column, and diagonal sums to the same target S = n(n²+1)/2. It is a pure feasibility problem, but for large n it is extremely hard to find a feasible solution directly. VOLNS turns it into a minimisation problem by treating each row sum constraint as a soft constraint; columns and diagonals remain hard. The violation of row i is |sum(row_i) − S|; the total violation is their sum. The search succeeds when the total violation reaches 0.

Full source: MagicSquareVOLNS.java

Step 1 — Model hard and soft constraints

int sumResult = n * (n * n + 1) / 2;

// Hard: all-different, column sums, diagonal sums
cp.post(allDifferent(xFlat));
for (int j = 0; j < n; j++) {
    CPIntVar[] col = new CPIntVar[n];
    for (int i = 0; i < n; i++) col[i] = x[i][j];
    cp.post(sum(col, sumResult));
}
cp.post(sum(diagonalLeft,  sumResult));
cp.post(sum(diagonalRight, sumResult));

// Soft: row sums — violation = |sum(row_i) - sumResult|
CPIntVar[] rowViolation = new CPIntVar[n];
for (int i = 0; i < n; i++)
    rowViolation[i] = abs(minus(sum(x[i]), sumResult));

CPIntVar totalViolation = sum(rowViolation);

Step 2 — Create the VOLNS objective

MinimizeObjectiveSum globalObjective = new MinimizeObjectiveSum(rowViolation);

MinimizeObjectiveSum internally wraps each individual rowViolation[i] and their sum in separate IntObjective objects. On construction, only the sum objective is filtered (i.e., actively used for pruning); the individual terms are tracked but not yet enforced.

Step 3 — Find an initial solution

int[] xFlatSol = new int[n * n];
int[] totalViolationSol = new int[]{0};

DFSearch dfs = makeDfs(cp, firstFailBinary(xFlat));
dfs.onSolution(() -> {
    totalViolationSol[0] = totalViolation.min();
    for (int j = 0; j < n * n; j++) xFlatSol[j] = xFlat[j].min();
});

// stop as soon as one feasible solution (or best approximation) is found
dfs.optimize(globalObjective, stats -> stats.numberOfSolutions() >= 1);

Step 4 — VOLNS loop

The loop applies three tightening strategies each iteration before re-running optimizeSubjectTo:

Random random = new Random(42);
for (int iter = 0; iter < maxIter && globalObjective.getBound() > 0; iter++) {

    // (1) Weak-tighten all terms: next solution must ≥ each current bound
    globalObjective.weakTightenAll();
    // (2) Strong-tighten the sum: next solution must strictly improve the total
    globalObjective.strongTightenSum();
    // (3) Strong-tighten the worst individual term: force improvement of the
    //     row that currently contributes the most violation
    globalObjective.strongTigthenWorseTerm();

    double relaxValue = random.nextDouble();
    dfs.optimizeSubjectTo(globalObjective,
        s -> s.numberOfFailures() >= 100,
        () -> {
            for (int j = 0; j < n * n; j++)
                if (random.nextDouble() > relaxValue)
                    cp.post(eq(xFlat[j], xFlatSol[j]));
        });
}

The three tightening modes create a progressive pressure:

Method	Effect
weakTightenAll()	Every individual violation and the sum must be at most equal to their current best values — no term may get worse.
strongTightenSum()	The total violation must strictly decrease (delta = 1).
strongTigthenWorseTerm()	The individual violation that is currently largest must also strictly decrease, focusing search on the hardest-to-satisfy row.

The combination forces the search to simultaneously avoid global regression, improve the aggregate quality, and attack the most violated constraint. As iterations proceed, more rows reach violation 0 and the surviving violated rows are progressively tightened until the total violation reaches 0 — a valid magic square.