0. Assignment Instructions

Before starting with your Java implementation, read the assignment instructions and grading rules on the course web page: https://user.it.uu.se/~pierref/courses/COCP/assignments/assignment6/assignment6.pdf .

This part of the assignment is on the programming tasks of Modules 6 to 9 of the MiniCP on-line teaching materials.

For this part of the assignment, you first have to implement Large-Neighborhood Search (LNS) for the Traveling Salesperson Problem before implementing two black-box branching strategies.

1. 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 parameters for 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

Ponder the following questions, as they will help you to find good parameters:

• Does LNS converge faster to good solutions than the standard DFSearch? Use the instance with 26 nodes.
• What is the impact of the percentage of relaxed variables (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 TSP.java.

When you previously modified the search heuristics, you only did it when knowing about the structure of the problem at hand. For instance, the search done on the TSP was taking into account the distance matrix in the problem.

You will now implement branching strategies that do not care about the structure of the problem. The black-box strategies that you will implement are:

2. Last Conflict, branching on the most recent variable that caused a failure.
3. Conflict Ordering Search, an extension of Last Conflict where all failures are time-stamped.

2. Last Conflict

Implement the Last Conflict [LC2009] heuristic presented in the lecture. Your implementation needs to be done within the lastConflict method from BranchingScheme.java.

To detect if a failure happened, you can surround a cp.post(...) call by a try-catch(-finally) block in the branching procedure:

try {
    cp.post(...)
} catch (InconsistencyException inconsistency) {
    // update the last conflicted variable
}

Hint: use an AtomicReference<IntVar> for storing the last conflicted variable.

Test your implementation in LastConflictSearchTest.java.

3. Conflict Ordering Search

Implement the Conflict Ordering Search [COS2015] heuristic presented in the lecture. Your implementation needs to be done within the conflictOrderingSearch method from BranchingScheme.java.

Test your implementation in ConflictOrderingSearchTest.java.

Before submitting, remember to fetch the latest changes from upstream (the MiniCP GitHub repository).

Note that the original tests of the MiniCP GitHub repository will be run.