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.

In the programming tasks of this assignment, you will use Constraint Programming to model and solve vehicle routing problems and scheduling problems.

You have to: 1. Implement the Circuit constraint; 2. Customize search for the Travelling Salesperson Problem; 3. Model a Vehicle Routing Problem; 4. Implement the CumulativeDecomposition constraint by using binary-decomposition filtering; 5. Implement the Profile data structure and the Cumulative constraint; 6. Model the Resource-Constrained Project Scheduling Problem (RCPSP); 7. Implement the DisjunctiveBinary constraint; 8. Model the Job Shop problem; and 9. Implement first-fail branching on precedences for the Job Shop.

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. 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 duplication of the depot presented in the lecture.
• The extended distance matrix for multiple vehicles.

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

4. Cumulative Constraint: Decomposition

The Cumulative constraint models a scheduling resource with fixed capacity. It has the following signature:

public Cumulative(IntVar[] start, int[] duration, int[] requirement, int capa)

where capa is the capacity of the resource and start, duration, and requirement are arrays of equal size representing the following properties of the activities:

• start[i] is the variable specifying the start time of activity i,
• duration[i] is the duration of activity i, and
• requirement[i] is the resource requirement of activity i.

The constraint ensures that the cumulative resource requirement of activities (also called the requirement profile) never exceeds the capacity:

The following example depicts three activities and their corresponding requirement profile. As can be observed, the profile never exceeds the capacity 4:

It corresponds to the instantiation of the following Cumulative constraint:

Cumulative(start = [1, 2, 3], duration = [8, 3, 3], requirement = [1, 1, 2], capa = 4)

Implement CumulativeDecomposition.java. This is a decomposition or reformulation of the Cumulative constraint in terms of simple arithmetic and logical constraints as used in the equation above to describe its semantics.

At any point in time t the BoolVar overlaps[i] designates whether activity i overlaps, potentially being performed at, time t or not. The overall resource requirement at t can then be obtained by:

First make sure you understand the following code, and then add the few lines in its TODO task in order to make sure overlaps has the intended meaning:

public void post() throws InconsistencyException {

    int min = Arrays.stream(start).map(s -> s.getMin()).min(Integer::compare).get();
    int max = Arrays.stream(end).map(e -> e.getMax()).max(Integer::compare).get();

    for (int t = min; t < max; t++) {

        BoolVar[] overlaps = new BoolVar[start.length];
        for (int i = 0; i < start.length; i++) {
            overlaps[i] = makeBoolVar(cp);

            // TODO
            // post the constraints to enforce
            // that overlaps[i] is true iff start[i] <= t && t < start[i] + duration[i]
            // hint: use IsLessOrEqual, introduce BoolVar, use views minus, plus, etc.
            //       logical constraints (such as logical and can be modeled with sum)

        }

        IntVar[] overlapHeights = makeIntVarArray(cp, start.length, i -> mul(overlaps[i], requirement[i]));
        IntVar cumHeight = sum(overlapHeights);
        cumHeight.removeAbove(capa);

    }

Check that your implementation passes the tests CumulativeDecompTest.java.

5. Cumulative Constraint: Time-Table Filtering

The timetable filtering algorithm introduced in [TT2015] is an efficient yet simple filtering algorithm for Cumulative.

It is a two-stage algorithm:

1. Build an optimistic profile of the resource requirement and check that it does not exceed the capacity.
2. Filter the earliest start of the activities such that they are not in conflict with the profile.

Consider in the next example the depicted activity that can be executed anywhere between the two solid brackets. It cannot execute at its earliest start since this would violate the capacity of the resource. We thus need to postpone the activity until a point in time where it can execute over its entire duration without being in conflict with the profile and the capacity. The earliest such point in time is 7:

Profiles

We provide a class Profile.java that is able to efficiently build a resource profile given an array of rectangles as input. A rectangle has three attributes: start, end, and height, as shown next:

Indeed, a profile is nothing more than a sequence of rectangles. An example profile is given next. It is built from three input rectangles provided to the constructor of Profile.java.

The profile consists of 7 contiguous rectangles. The first rectangle, R0, starts at Integer.MIN_VALUE with a height of zero, and the last rectangle, R6, ends at Integer.MAX_VALUE, also with a height of zero. These two dummy rectangles are convenient because they guarantee that there exists a rectangle in the profile for any point in time:

Make sure you understand how to build and manipulate Profile.java.

Have a look at ProfileTest.java for some examples of profile construction.

Filtering

Implement Cumulative.java. You have three TODO tasks:

1. Build the optimistic profile from the mandatory parts.
2. Check that the profile is not exceeding the capacity.
3. Filter the earliest start of activities.

TODO 1 is to build the optimistic profile from the mandatory parts of the activities. As can be seen in the next example, the mandatory part of an activity is a part that is always executed whatever the start time of the activity will be in its current domain. It is the rectangle starting at start[i].getMax() that ends in start[i].getMin()+duration[i] with a height equal to the resource requirement of the activity. Be careful because not every activity has a mandatory part:

You can check that your profile computation is correct by running the tests testBuildProfile1 and testBuildProfile2 from CumulativeTest.java.

TODO 2 is to check that the profile is not exceeding the capacity. You can check that each rectangle of the profile is not exceeding the capacity; otherwise you throw an InconsistencyException. Your implementation should pass the tests testAllDiffWithCumulative and testCapaOk.

TODO 3 is to filter the earliest start of unfixed activities by postponing each activity (if needed) to the earliest slot when it can be executed without exceeding the capacity.

for (int i = 0; i < start.length; i++) {
        if (!start[i].isFixed()) {
            // j is the index of the profile rectangle overlapping t
            int j = profile.rectangleIndex(start[i].getMin());
            // TODO 3: postpone i to a later point in time
            // hint:
            // Check that at every point in the interval
            // [start[i].getMin() ... start[i].getMin()+duration[i]-1]
            // there is enough remaining capacity.
            // You may also have to check the following profile rectangle(s).
            // Note that the activity you are currently postponing
            // may have contributed to the profile.
        }
    }

Check that your implementation passes the tests from CumulativeTest.java.

6. The Resource-Constrained Project Scheduling Problem (RCPSP)

A set of activities must be executed on a set of resources.

Your task is to complete the implementation in RCPSP.java:

• Post the Cumulative constraint
• Post the precedence constraints
• Add instructions to minimize the makespan
• Minimize the makespan

Several instances of increasing size are available, with 30, 60, 90, and 120 activities. In order to test your model, note that the instance j30_1_1.rcp should have a minimum makespan of 43. Do not expect to prove optimality for large-size instances, but you should reach it easily for 30 activities.

Check that your implementation passes the tests RCPSPTest.java.

7. Decomposing the Disjunctive Constraint

To implement the decomposition of the Disjunctive constraint, you first need to use the constraint IsLessOrEqualVar.java:

IsLessOrEqualVar(BoolVar b, IntVar x, IntVar y) creates a reified is-less-or-equal constraint \(b \Leftrightarrow (x \leq y)\).

This constraint is already provided to you. Based on it, implement the decomposition with reified constraints in the file DisjunctiveBinary.java.

Make sure your implementation passes all the tests in DisjunctiveBinaryTest.java.

8. Modeling the JobShop

Once your DisjunctiveBinary constraint is implemented, you can use it to model the JobShop problem. Part of the implementation is already done within JobShop.java. You still need to implement the TODO1 using the DisjunctiveBinary constraint for each pair of activities in order to have a working model.

You should now be able to solve tiny instances and pass the test testModel within JobShopTest.java.

However, the search procedure is still naive and quite slow. Let's speed things up!

9. First-Fail Branching on Precedences for the JobShop

As seen in the lecture, for the JobShop problem, one can perform the search on either start variables or precedence variables. Here, you will base your search procedure on precedence variables. A precedence variable has the format b[m][i][j], with \(m\) a machine and \(i\) and \(j\) two activities that are to be executed on \(m\), and denotes the precedence \(i \ll j\) on \(m\).

For the search, you then need criteria in order to decide:

• which machine \(m\) to consider;
• on machine \(m\): which two currently non-fixed activities \(i\) and \(j\) to consider;
• between the chosen activities \(i\) and \(j\), which branch to try first: b[m][i][j] = true or b[m][i][j] = false?

For the variable selection, it is well-known that the first-fail principle is one of the most straightforward CP search strategies that provide relatively good performance. You will use it here based on the sizes of the domains of the start variables.

Your mission is to implement the follwing search strategy (ignoring the one described in TODO2 of JobShop.java).

Machine selection \(m\).

Select a machine that has the smallest sum of the sizes of the domains of the activities that are to be executed on it. Let \(startOnMachine(m)\) be the set of activities that are to be executed on machine \(m\). Let \(start(i)\) be the variable representing the start time of activity \(i\).

Consider first a machine \(m\) that refers to at least one currently non-fixed variable \(start(i)\), with \(i \in startOnMachine(m)\), and has the minimum sum \(\Sigma_{i \in startOnMachine(m)} start(i).size()\).

Variable selection \(b_{ij}\).

For the selected machine \(m\), consider first a currently non-fixed variable \(b_{ij}\) (denoting the b[m][i][j] above), with \(i,j \in startOnMachine(m)\), that has the minimum product \(start(i).size() \cdot start(j).size()\).

Value selection.

Once the variable is selected, decide which decision to try first between \(b_{ij} = \mathit{true}\) and \(b_{ij} = \mathit{false}\). Often, it is better to try first the value that gives the most flexibility in the current domains. Let us define \(\mathit{slackJIfIStartBeforeJ}\) as the number of time slots available in the domain of \(start(j)\) if activity \(i\) starts before activity \(j\) on a given machine, and similarly for \(\mathit{slackIIfJStartBeforeI}\). The following figure shows an example:

Assuming that the currently non-fixed variable \(b_{ij}\) is selected: first try \(b_{ij} = \mathit{true}\) if \(\mathit{slackJIfIStartBeforeJ} > \mathit{slackIIfJStartBeforeI}\).

On the example illustrated above, we will have:

Hint1:

DisjunctiveBinary.java contains useful methods for implementing this search, such as slackIfBefore() and slackIfAfter(). Try to use them as much as possible!

Hint2:

When all the precedence variables are already fixed, you can fix the makespan and all the non-fixed start variables to their respective minimum domain values. You will get an optimal solution.

Hint3:

Does the value heuristic look a bit complicated? You can opt for a simpler (but less efficient) technique: once you have chosen \(b_{ij}\), branch on the left with \(b_{ij} = \mathit{false}\) and on the right with \(b_{ij} = \mathit{true}\). You can check that you are able to solve the first few instances in testFindOptimality within JobShopTest.java. To solve the remaining ones, implement the value selection described above.

You should now be able to solve the medium-size and big-size instances in data/jobshop and pass almost all instances from the testFindOptimality test within JobShopTest.java.

To find the best solution from the remaining instances, we will implement more efficient filtering algorithms.

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.