1. Circuit Constraint

The Circuit constraint enforces a Hamiltonian circuit on a successor array. In the following example, the successor array a=[2,4,1,5,3,0] has for each index i (0 ≤ i ≤ 5) a directed edge that goes from node i to node a[i]:

All the successors must be different. However, enforcing just an AllDifferent constraint is not enough as we must also guarantee that a proper Hamiltonian circuit (without sub-circuits) is formed.

This can be done efficiently and incrementally by keeping track of any partial paths (non-closed circuits) that appear during search. Note that each node is on at most one partial path. For your implementation, use the following arrays of stateful integers as the data structure to keep track of the partial paths:

IntVar [] x;
StateInt [] dest;
StateInt [] orig;
StateInt [] lengthToDest;

where:

• dest[i] is the last (non-fixed) node that can be reached from node i if node i is fixed and on a partial path; otherwise it is i;
• orig[i] is the first (fixed) node that can reach node i if node i is on a partial path; otherwise it is i;
• lengthToDest[i] is the length of the partial path from node i to node dest[i] if node i is on a partial path; otherwise it is 0.

Consider the following example where edges originating from fixed nodes are colored grey:

Before node 5 has been fixed, the green edge has not yet been added, so we have:

dest = [2,1,2,5,5,5];
orig = [0,1,0,4,4,4];
lengthToDest = [1,0,0,1,2,0];

After node 5 has been fixed, the green edge has been added, so we have:

dest = [2,1,2,2,2,2];
orig = [4,1,4,4,4,4];
lengthToDest = [1,0,0,3,4,2];

In your implementation, you must update the stateful integers in order to reflect the changes after the addition of new edges to the circuit. An edge is added whenever a node becomes fixed: you can use the CPIntVar.whenFix(...) method to run some code block when this event occurs.

The filtering algorithm is to prevent closing each partial path that would have a length less than n (the total number of nodes) as that would result in a non-Hamiltonian circuit. Since node 4 (the origin of a partial path) has a length to its destination (node 2) of 4 (<6), the destination node 2 cannot have the origin node 4 as a successor and the red edge is deleted. This filtering was introduced in [TSP1998] for solving the traveling salesperson problem (TSP) with CP.

Implement a propagator Circuit.java. Check that your implementation passes the tests CircuitTest.java.

2. Custom Search for TSP

Modify buildModel method from TSP.java in order to implement a custom search strategy. Use the following as skeleton code:

dfs = makeDfs(cp, () -> {
    IntVar xs = selectMin(succ,
            xi -> xi.size() > 1, // filter
            xi -> xi.size()); // variable selector
    if (xs == null)
        return EMPTY; // all variables are fixed: this is a solution

    int v = xs.min(); // value selector (TODO)
    return branch(() -> cp.post(equal(xs, v)),
            () -> cp.post(notEqual(xs, v)));
});

It branches on the successor variables succ in the following manner:

• The selected unfixed variable is the one with the smallest domain (first-fail).
• The selected variable is then fixed to the minimum value in its domain.

This value selection strategy is not well-suited for the TSP, and for the vehicle routing problem (VRP) in general. The one you design should be more similar to the decision you would make in a greedy algorithm. For instance, you can select as a successor for xi a closest city in its domain.

Hint1: Since there is no iterator on the domain of a variable, you can iterate from its minimum value to its maximum one by using a for loop and checking that the value of the current iteration is in the domain using the contains method. You can also use your domain iterator from IntVar (the fillArray method).

Hint2: You might need to adapt the variable selector so that it gives you the index i of a variable succ[i] instead of the variable itself. This way you can use the index to access easily values within the distance matrix.

You can also implement a min-regret variable selection strategy: it selects a variable with the largest difference between a closest successor city and a second-closest one. The idea is that it is critical to decide the successor for this city first, because otherwise one will regret it the most.

Observe the first solution obtained to the provided instance and its objective value: is it better than upon naive first-fail? Also observe the time and number of backtracks necessary for proving optimality: by how much did you reduce the computation time and number of backtracks?

Check that your implementation passes the tests testOptimality and testAgainstFirstFail in TSPTest.java.

3. LNS Applied to TSP

Implement and apply large-neighborhood search (LNS) by modifying the lns method from TSP.java.

What you should do:

• Read and understand the existing implementation
• Have a look at the parameter for the LNS: although they are working, they are not the best ones for this specific problem
• Try different combinations of failureLimit and percentage to get better solutions

Have a look at the following questions, they will help you to find good parameters:

• Does the LNS converge faster to good solutions than the standard DFSearch? Use the instance with 26 nodes.
• What is the impact of the percentage of variables relaxed (experiment with 5%, 10%, and 20%)?
• What is the impact of the failure limit (experiment with 50, 100, and 1000)?
• (Bonus, not required to pass the tests) Implement a relaxation that is specific to this problem. Currently, the variables to relax are chosen at random. Instead, you can try to relax the variables that have the strongest impact on the objective with a greater probability (the choice of relaxed variables should still be somehow randomized). You can for instance select a subset of cities with the largest distance to their successor and permit those cities to be reinserted anywhere in the circuit. This requires keeping the relaxed cities (those that are to be reinserted) within the domains of the successor variables of the non-relaxed cities.

Check that your implementation passes the test testLNS from TSPTest.java.

4. From TSP to VRP

Within the file VRP.java you will find a variation of TSP: there are now \(k\) vehicles that can visit the nodes. The depot is the city at index 0, and every other city must be visited exactly once by exactly one of the \(k\) vehicles. The current model works for k=1 but still need a few things to handle more vehicles:

• The correct number of nodes within the problem if k>1, using the dupplication of the depot presented in the course.
• The extended distance matrix for multiple vehicles.

Your implementation needs to pass the tests within VRPTest.java.