Custom Constraint and Search.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Building Your Own Constraints and Search\n",
    "\n",
    "In this exercice, we will show how to build additional constraints in miniCP. We will also build a custom search procedure.\n",
    "\n",
    "\n",
    "## Circuit Constraint\n",
    "\n",
    "In the previous exercice about the Dial-A-Ride Problem, we used miniCP's Circuit constraint. We will now implement our own version of this constraint, and substitute it in the CP model.\n",
    "\n",
    "Remember that the Circuit constraint to enforce a hamiltonian circuit on a successor array. \n",
    "On the next example the successor array is `[2,4,1,5,3,0]`\n",
    "\n",
    "![Illustration of a hamiltonian circuit](https://minicp.readthedocs.io/en/latest/_images/circuit.svg)\n",
    "\n",
    "All the successors must be different.\n",
    "But enforcing the `allDifferent` constraint is not enough.\n",
    "We must also guarantee it forms a proper circuit (without sub-tours).\n",
    "This can be done efficiently and incrementally by keeping track of the sub-chains\n",
    "appearing during the search.\n",
    "The data-structure for the sub-chains should be a reversible.\n",
    "Our instance variables used to keep track of the sub-chains are:\n",
    "\n",
    "```java\n",
    "IntVar [] x;\n",
    "StateInt [] dest;\n",
    "StateInt [] orig;\n",
    "StateInt [] lengthToDest;\n",
    "```\n",
    "\n",
    "\n",
    "* `dest[i]` is the furthest node we can reach from node `i` following the instantiated edges.\n",
    "* `orig[i]` is the furthest node we can reach from node `i` following instantiated edges in reverse direction.\n",
    "* `lengthToDest[i]` is the number of instantiated edges on the path from node `i` to `dest[i]`.\n",
    "\n",
    "Consider the following example with instantiated edges colored in grey.\n",
    "\n",
    "![Circuit subtour](https://minicp.readthedocs.io/en/latest/_images/circuit-subtour.svg)\n",
    "\n",
    "Before the addition of the green link we have\n",
    "\n",
    "```java\n",
    "dest = [2,1,2,5,5,5];\n",
    "orig = [0,1,0,4,4,4];\n",
    "lengthToDest = [1,0,0,1,2,0];\n",
    "```\n",
    "\n",
    "After the addition of the green link we have\n",
    "\n",
    "```java\n",
    "dest = [2,1,2,2,2,2];\n",
    "orig = [4,1,4,4,4,4];\n",
    "lengthToDest = [1,0,0,3,4,2];\n",
    "```\n",
    "\n",
    "In your implementation you must update the reversible integers to reflect\n",
    "the change after the addition of every new edge.\n",
    "You can use the `CPIntVar.whenBind(...)` method for that.\n",
    "\n",
    "The filtering in itself consists in preventing to close a\n",
    "sub-tour that would have a length less than `n` (the number of nodes).\n",
    "Since node 4 has a length to destination (node 2) of 4 (<6), the destination node 2 can not have 4 as successor\n",
    "and the red link is deleted.\n",
    "This filtering was introduced in [TSP1998] for solving the TSP with CP.\n",
    "\n",
    "\n",
    "**[TSP1998]** Pesant, G., Gendreau, M., Potvin, J. Y., & Rousseau, J. M. (1998). An exact constraint logic programming algorithm for the traveling salesman problem with time windows. Transportation Science, 32(1), 12-29.\n",
    "\n",
    "### Implementation\n",
    "\n",
    "In miniCP, a constraint must extend the AbstractConstraint class, which has the following API:\n",
    "\n",
    "* `void post()`: called once when the constraint is initialized. It should state the constraint and hook up the variables' callbacks (e.g. [`propagateOnDomainChainge(...)`](https://minicp.bitbucket.io/apidocs/minicp/engine/core/IntVar.html#propagateOnDomainChange-minicp.engine.core.Constraint-) or [`whenBind(...)`](https://minicp.bitbucket.io/apidocs/minicp/engine/core/IntVar.html#whenBind-minicp.util.Procedure-)),\n",
    "* `void propagate()`: called by the fix-point algorithm during the search. It should remove the inconsistent values from the domain of the associated variables.\n",
    "\n",
    "\n",
    "The skeleton for the implementation of a circuit constraint is given in the next code cell. Complete the missing code, then check your custom constraint in the DARP model below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "%jars ./\n",
    "\n",
    "import minicp.engine.core.AbstractConstraint;\n",
    "import minicp.engine.core.IntVar;\n",
    "import minicp.state.StateInt;\n",
    "import minicp.util.exception.NotImplementedException;\n",
    "\n",
    "import static minicp.cp.Factory.allDifferent;\n",
    "\n",
    "/**\n",
    " * Hamiltonian Circuit Constraint with a successor model\n",
    " */\n",
    "public class MyCircuit extends AbstractConstraint {\n",
    "\n",
    "    private final IntVar[] x;\n",
    "    private final StateInt[] dest;\n",
    "    private final StateInt[] orig;\n",
    "    private final StateInt[] lengthToDest;\n",
    "\n",
    "    /**\n",
    "     * Creates an Hamiltonian Circuit Constraint\n",
    "     * with a successor model.\n",
    "     *\n",
    "     * @param x the variables representing the successor array that is\n",
    "     *          x[i] is the city visited after city i\n",
    "     */\n",
    "    public MyCircuit(IntVar[] x) {\n",
    "        super(x[0].getSolver());\n",
    "        assert (x.length > 0);\n",
    "        this.x = x;\n",
    "        dest = new StateInt[x.length];\n",
    "        orig = new StateInt[x.length];\n",
    "        lengthToDest = new StateInt[x.length];\n",
    "        for (int i = 0; i < x.length; i++) {\n",
    "            dest[i] = getSolver().getStateManager().makeStateInt(i);\n",
    "            orig[i] = getSolver().getStateManager().makeStateInt(i);\n",
    "            lengthToDest[i] = getSolver().getStateManager().makeStateInt(0);\n",
    "        }\n",
    "    }\n",
    "\n",
    "    @Override\n",
    "    public void post() {\n",
    "        getSolver().post(allDifferent(x));\n",
    "        // TODO\n",
    "        // Hint: use x[i].whenBind(...) to call the bind(int) method\n",
    "        throw new NotImplementedException(\"MyCircuit\");\n",
    "    }\n",
    "\n",
    "    private void bind(int i) {\n",
    "        // TODO\n",
    "        throw new NotImplementedException(\"MyCircuit\");\n",
    "    }\n",
    "}\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 22, 44, 31, 40, 18, 15]\n",
      "[22, 0, 22, 22, 22, 5, 32]\n",
      "[44, 22, 0, 31, 20, 26, 53]\n",
      "[31, 22, 31, 0, 14, 25, 30]\n",
      "[40, 22, 20, 14, 0, 26, 42]\n",
      "[18, 5, 26, 25, 26, 0, 29]\n",
      "[15, 32, 53, 30, 42, 29, 0]\n"
     ]
    }
   ],
   "source": [
    "%jars ./\n",
    "//********************************************\n",
    "//* miniPC model for the Dial-A-Ride Problem *\n",
    "//* using a custom constraint for Circuit    *\n",
    "//********************************************\n",
    "\n",
    "import minicp.engine.constraints.Circuit;\n",
    "import minicp.engine.constraints.Element1DVar;\n",
    "import minicp.engine.core.IntVar;\n",
    "import minicp.engine.core.Solver;\n",
    "import minicp.search.DFSearch;\n",
    "import minicp.util.Procedure;\n",
    "import minicp.search.SearchStatistics;\n",
    "\n",
    "import static minicp.cp.BranchingScheme.*;\n",
    "import static minicp.cp.Factory.*;\n",
    "\n",
    "import java.util.Arrays;\n",
    "import java.util.stream.IntStream;\n",
    "\n",
    "public static IntVar elementVar(IntVar[] array, IntVar y) {\n",
    "    Solver cp = y.getSolver();\n",
    "    int min = IntStream.range(0, array.length).map(i -> array[i].min()).min().getAsInt();\n",
    "    int max = IntStream.range(0, array.length).map(i -> array[i].max()).max().getAsInt();\n",
    "    IntVar z = makeIntVar(cp, min,max);\n",
    "    cp.post(new Element1DVar(array, y, z));\n",
    "    return z;\n",
    "}\n",
    "\n",
    "// DARP instance definition\n",
    "\n",
    "// coordinates of the positions involved in this problem\n",
    "int [][] coords = new int[][] {\n",
    "        {10,20}, // 0\n",
    "        {30,30}, // 1\n",
    "        {50,40}, // 2\n",
    "        {40,10}, // 3\n",
    "        {50,20}, // 4\n",
    "        {25,30}, // 5\n",
    "        {10,5}   // 6\n",
    "};\n",
    "\n",
    "// compute the symmetrical transition times as Euclidian distances\n",
    "int [][] transitions = new int[coords.length][coords.length];\n",
    "for (int i = 0; i < coords.length; i++) {\n",
    "    for (int j = 0; j < coords.length; j++) {\n",
    "        int x1 = coords[i][0];\n",
    "        int y1 = coords[i][1];\n",
    "        int x2 = coords[j][0];\n",
    "        int y2 = coords[j][1];\n",
    "        transitions[i][j] = (int) Math.sqrt(Math.pow(x1-x2,2.0)+Math.pow(y1-y2,2.0));\n",
    "    }\n",
    "    System.out.println(Arrays.toString(transitions[i]));\n",
    "}\n",
    "\n",
    "// the requests defined as {fromPos,toPos,deadline}\n",
    "int [][] requests = new int[][] {\n",
    "        {3,5,120},\n",
    "        {6,2,200},\n",
    "        {5,1,100},\n",
    "        {1,6,60},\n",
    "        {5,2,150},\n",
    "        {6,3,150},\n",
    "};\n",
    "\n",
    "// capacity of the vehicle\n",
    "int vehicleCapacity = 2;\n",
    "\n",
    "// CP model: visits, prev and succ\n",
    "\n",
    "Solver cp = makeSolver();\n",
    "\n",
    "int n = requests.length;\n",
    "int [] v = new int[2*n+1];\n",
    "v[0] = 0; // departure from the depot (position index 0)\n",
    "// [1..n+1] = pickups\n",
    "// [n+1..2n+1] = delivery\n",
    "for (int i = 0; i < n; i++) {\n",
    "    v[1+i] = requests[i][0];\n",
    "    v[n+1+i] = requests[i][1];\n",
    "}\n",
    "\n",
    "IntVar [] succ = makeIntVarArray(cp, 2*n+1,2*n+1);\n",
    "IntVar [] pred = makeIntVarArray(cp, 2*n+1,2*n+1);\n",
    "\n",
    "// channeling between pred and succ vectors\n",
    "for (int i = 0; i < succ.length; i++) {\n",
    "    // succ[pred[i]] == i\n",
    "    cp.post(equal(elementVar(succ,pred[i]),i));\n",
    "}\n",
    "\n",
    "//*******************************************\n",
    "//* NOTE: here we use our custom constraint *\n",
    "//*******************************************\n",
    "cp.post(new MyCircuit(pred));\n",
    "\n",
    "// CP model: time constraints\n",
    "\n",
    "IntVar [] time = makeIntVarArray(cp, 2*n+1,500);\n",
    "// departure time from the depot =  0\n",
    "cp.post(equal(time[0],0));\n",
    "\n",
    "// visit time update\n",
    "for (int i = 1; i < 2*n+1; i++) {\n",
    "    // time[i] = time[pred[i]] + transition[pred[i]][i]\n",
    "    IntVar tPredi = elementVar(time, pred[i]);\n",
    "    IntVar posPredi = element(v, pred[i]);\n",
    "    IntVar tt = element(transitions[v[i]],posPredi);\n",
    "    cp.post(equal(time[i],sum(tPredi,tt)));\n",
    "}\n",
    "\n",
    "// precedence between pickup and delivery + deadlines\n",
    "for (int i = 0; i < n; i++) {\n",
    "    // pickup before delivery)\n",
    "    cp.post(lessOrEqual(time[i+1],time[n+i+1]));\n",
    "    // delivery before the deadline\n",
    "    cp.post(lessOrEqual(time[n+i+1],requests[i][2]));\n",
    "}\n",
    "\n",
    "// CP model: load constraints\n",
    "\n",
    "IntVar [] load = makeIntVarArray(cp, 2*n+1,vehicleCapacity+1);\n",
    "// initial load of the vehicle = 0\n",
    "cp.post(equal(load[0],0));\n",
    "\n",
    "// load update after a pickup (+1)\n",
    "for (int i = 1; i <= n; i++) {\n",
    "    // load[i] = load[[pred[i]] + 1\n",
    "    IntVar loadPred = elementVar(load, pred[i]);\n",
    "    cp.post(equal(load[i], plus(loadPred, 1)));\n",
    "}\n",
    "\n",
    "// load update after a delivery (-1)\n",
    "for (int i = n+1; i <= 2*n; i++) {\n",
    "    // load[i] = load[[pred[i]] - 1\n",
    "    IntVar loadPred = elementVar(load, pred[i]);\n",
    "    cp.post(equal(load[i], plus(loadPred, -1)));\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "solution\n",
      "succ:[{3}, {7}, {10}, {9}, {2}, {8}, {12}, {5}, {11}, {4}, {6}, {0}, {1}]\n",
      "pred:[{11}, {12}, {4}, {0}, {9}, {7}, {10}, {1}, {5}, {3}, {2}, {8}, {6}]\n",
      "time:[{0}, {85}, {55}, {18}, {23}, {110}, {55}, {110}, {136}, {23}, {55}, {136}, {85}]\n",
      "load:[{0}, {2}, {2}, {1}, {1}, {2}, {2}, {1}, {1}, {0}, {1}, {0}, {1}]\n",
      "visiting position:0 at time:{0} load:{0}\n",
      "visiting position:5 at time:{18} load:{1}\n",
      "visiting position:1 at time:{23} load:{0}\n",
      "visiting position:1 at time:{23} load:{1}\n",
      "visiting position:6 at time:{55} load:{2}\n",
      "visiting position:6 at time:{55} load:{1}\n",
      "visiting position:6 at time:{55} load:{2}\n",
      "visiting position:3 at time:{85} load:{1}\n",
      "visiting position:3 at time:{85} load:{2}\n",
      "visiting position:5 at time:{110} load:{1}\n",
      "visiting position:5 at time:{110} load:{2}\n",
      "visiting position:2 at time:{136} load:{1}\n",
      "visiting position:2 at time:{136} load:{0}\n",
      "\n",
      "\t#choice: 31854\n",
      "\t#fail: 15923\n",
      "\t#sols : 1\n",
      "\tcompleted : false\n",
      "\n"
     ]
    }
   ],
   "source": [
    "DFSearch dfs = makeDfs(cp, firstFail(pred));\n",
    "\n",
    "dfs.onSolution(() -> {\n",
    "    System.out.println(\"solution\");\n",
    "    System.out.println(\"succ:\"+Arrays.toString(succ));\n",
    "    System.out.println(\"pred:\"+Arrays.toString(pred));\n",
    "    System.out.println(\"time:\"+Arrays.toString(time));\n",
    "    System.out.println(\"load:\"+Arrays.toString(load));\n",
    "\n",
    "    int curr = 0;\n",
    "    for (int i = 0; i < succ.length; i++) {\n",
    "        System.out.println(\"visiting position:\"+v[curr]+\" at time:\"+time[curr]+\" load:\"+load[curr]);\n",
    "        curr = succ[curr].min();\n",
    "    }\n",
    "\n",
    "});\n",
    "\n",
    "// search for the first feasible solution\n",
    "SearchStatistics stats = dfs.solve(statistics -> {\n",
    "    return statistics.numberOfSolutions() > 0;\n",
    "});\n",
    "\n",
    "System.out.println(stats);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Custom Search for DARP\n",
    "\n",
    "To write a custom search in miniCP, you can make use of the method [`Factory.makeDfs`](https://minicp.bitbucket.io/apidocs/minicp/cp/Factory.html#makeDfs-minicp.engine.core.Solver-java.util.function.Supplier-). It takes two parameters:\n",
    "* `Solver cp` the solver that will be used for the search\n",
    "* `Supplier<Procedure[]> branching` a generator that is called at each node of the depth first search tree to generate an array of [`Procedure`](https://minicp.bitbucket.io/apidocs/minicp/util/Procedure.html) objects that will be used to commit to child nodes. It should return `BranchingScheme#EMPTY` whenever the current state is a solution.\n",
    "\n",
    "Example of binary search: At each node it selects the first free variable `predi` from the array `pred`, and creates two branches `predi=v`, `predi!=v` where `v` is the min value domain\n",
    "\n",
    "```java\n",
    "DFSearch myDfs = makeDfs(cp, () -> {\n",
    "    Optional<IntVar> predi = Arrays.stream(pred)\n",
    "        .filter(b -> b.size() > 1) // only select free variables\n",
    "        .findFirst(); // select the first one\n",
    "    if (predi.isEmpty()) {\n",
    "        return EMPTY;\n",
    "    } else {\n",
    "        int v = predi.get().min();\n",
    "        Procedure left = () -> cp.post(equal(predi.get(), v)); // left branch\n",
    "        Procedure right = () -> cp.post(notEqual(predi.get(), v)); // right branch\n",
    "        return branch(left, right);\n",
    "    }\n",
    "});\n",
    "```\n",
    "\n",
    "The branching scheme used in our DARP model is called [`firstFail`](https://minicp.bitbucket.io/apidocs/minicp/cp/BranchingScheme.html#firstFail-minicp.engine.core.IntVar...-), and does this with the addition that the variable with the smallest domain is selected first for branching. The value selection strategy (always taking the min value from the domain) is not well suited for the DARP. The one you design should be more similar to the decision you would make manually in a greedy fashion. For instance you can explore first the branch `pred[i] = x` where `x` is the closest location to `i` in the domain.\n",
    "\n",
    "You can also implement a min-regret variable selection strategy. It selects the variable with the largest different between the closest predecessor city and the second closest one. The idea is that it is critical to decide the predecessor for this city first because otherwise you will regret it the most.\n",
    "\n",
    "Hint: Since there is no iterator on the domain of a variable, you can iterate from the minimum value to the maximum one using a for loop and check if it is in the domain with the contains method.\n",
    "\n",
    "Implement a custom DFS search in the code block below. Observe the first solution obtained and its objective value ? Is it better than the naive first fail ? Also observe the time and number of backtracks necessary for proving optimality. By how much did you reduce the computation time ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "solution\n",
      "succ:[{3}, {7}, {10}, {9}, {2}, {8}, {12}, {5}, {11}, {4}, {6}, {0}, {1}]\n",
      "pred:[{11}, {12}, {4}, {0}, {9}, {7}, {10}, {1}, {5}, {3}, {2}, {8}, {6}]\n",
      "time:[{0}, {85}, {55}, {18}, {23}, {110}, {55}, {110}, {136}, {23}, {55}, {136}, {85}]\n",
      "load:[{0}, {2}, {2}, {1}, {1}, {2}, {2}, {1}, {1}, {0}, {1}, {0}, {1}]\n",
      "visiting position:0 at time:{0} load:{0}\n",
      "visiting position:5 at time:{18} load:{1}\n",
      "visiting position:1 at time:{23} load:{0}\n",
      "visiting position:1 at time:{23} load:{1}\n",
      "visiting position:6 at time:{55} load:{2}\n",
      "visiting position:6 at time:{55} load:{1}\n",
      "visiting position:6 at time:{55} load:{2}\n",
      "visiting position:3 at time:{85} load:{1}\n",
      "visiting position:3 at time:{85} load:{2}\n",
      "visiting position:5 at time:{110} load:{1}\n",
      "visiting position:5 at time:{110} load:{2}\n",
      "visiting position:2 at time:{136} load:{1}\n",
      "visiting position:2 at time:{136} load:{0}\n",
      "\n",
      "\t#choice: 31854\n",
      "\t#fail: 15923\n",
      "\t#sols : 1\n",
      "\tcompleted : false\n",
      "\n"
     ]
    }
   ],
   "source": [
    "DFSearch myDfs = makeDfs(cp, () -> {\n",
    "    Optional<IntVar> predi = Arrays.stream(pred)\n",
    "        .filter(b -> b.size() > 1) // only select free variables\n",
    "        .min((a,b) -> a.size()-b.size()); // select the one with smallest domain\n",
    "    if (predi.isEmpty()) {\n",
    "        return EMPTY;\n",
    "    } else {\n",
    "        int v = predi.get().min(); // CHANGE THIS\n",
    "        Procedure left = () -> cp.post(equal(predi.get(), v)); // left branch\n",
    "        Procedure right = () -> cp.post(notEqual(predi.get(), v)); // right branch\n",
    "        return branch(left, right);\n",
    "    }\n",
    "});\n",
    "\n",
    "myDfs.onSolution(() -> {\n",
    "    System.out.println(\"solution\");\n",
    "    System.out.println(\"succ:\"+Arrays.toString(succ));\n",
    "    System.out.println(\"pred:\"+Arrays.toString(pred));\n",
    "    System.out.println(\"time:\"+Arrays.toString(time));\n",
    "    System.out.println(\"load:\"+Arrays.toString(load));\n",
    "\n",
    "    int curr = 0;\n",
    "    for (int i = 0; i < succ.length; i++) {\n",
    "        System.out.println(\"visiting position:\"+v[curr]+\" at time:\"+time[curr]+\" load:\"+load[curr]);\n",
    "        curr = succ[curr].min();\n",
    "    }\n",
    "\n",
    "});\n",
    "\n",
    "// search for the first feasible solution\n",
    "SearchStatistics stats = myDfs.solve(statistics -> {\n",
    "    return statistics.numberOfSolutions() > 0;\n",
    "});\n",
    "\n",
    "System.out.println(stats);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Java",
   "language": "java",
   "name": "java"
  },
  "language_info": {
   "codemirror_mode": "java",
   "file_extension": ".jshell",
   "mimetype": "text/x-java-source",
   "name": "Java",
   "pygments_lexer": "java",
   "version": "11.0.3+7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}