Loading_a_solution.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this notebook, we are going to try to improve a given solution of an optimization problem, `Golomb ruler` of size 11.\n",
    "First, we load the snapshot version of choco (this version is not released at the time this notebook is written but contains helpful features)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%%loadFromPOM\n",
    "<repository>\n",
    "  <id>oss-sonatype-snapshots</id>\n",
    "  <url>https://oss.sonatype.org/content/repositories/snapshots/</url>\n",
    "</repository>\n",
    "<dependency>\n",
    "  <groupId>org.choco-solver</groupId>\n",
    "  <artifactId>choco-solver</artifactId>\n",
    "  <version>4.0.9</version>\n",
    "</dependency>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, let's import classes required for modeling."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import org.chocosolver.solver.Model;\n",
    "import org.chocosolver.solver.variables.IntVar;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "int m = 11;\n",
    "Model model = new Model();\n",
    "IntVar[] ticks = model.intVarArray(\"a\", m, 0, (m < 31) ? (1 << (m + 1)) - 1 : 9999, false);\n",
    "IntVar[] diffs = model.intVarArray(\"d\", (m * m - m) / 2, 0, (m < 31) ? (1 << (m + 1)) - 1 : 9999, false);\n",
    "model.arithm(ticks[0], \"=\", 0).post();\n",
    "\n",
    "for (int i = 0; i < m - 1; i++) {\n",
    "    model.arithm(ticks[i + 1], \">\", ticks[i]).post();\n",
    "}\n",
    "\n",
    "for (int k = 0, i = 0; i < m - 1; i++) {\n",
    "    for (int j = i + 1; j < m; j++, k++) {\n",
    "        // d[k] is m[j]-m[i] and must be at least sum of first j-i integers\n",
    "        model.arithm(ticks[j], \"-\", ticks[i], \"=\", diffs[k]).post();\n",
    "        model.arithm(diffs[k], \">=\", (j - i) * (j - i + 1) / 2).post();\n",
    "        model.arithm(diffs[k], \"-\", ticks[m - 1], \"<=\", -((m - 1 - j + i) * (m - j + i)) / 2).post();\n",
    "        model.arithm(diffs[k], \"<=\", ticks[m - 1], \"-\", ((m - 1 - j + i) * (m - j + i)) / 2).post();\n",
    "    }\n",
    "}\n",
    "model.allDifferent(diffs, \"BC\").post();\n",
    "// break symetries\n",
    "if (m > 2) {\n",
    "    model.arithm(diffs[0], \"<\", diffs[diffs.length - 1]).post();\n",
    "}\n",
    "model.setObjective(Model.MINIMIZE,ticks[m - 1]);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The model is now declared and ready to be solved.\n",
    "Here, we are considering the following case: we have pre-computed a good quality solution `good`.\n",
    "So, we want to find an improving solution *close* to the given one."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "int[] good = new int[]{0, 1, 7, 25, 28, 33, 47, 63, 67, 76, 78};\n",
    "ticks[m - 1].lt(78).post(); // a better solution must be find"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There are three options:\n",
    "1. using a Large Neighborhood Search strategy,\n",
    "2. using a Limited-Discrepancy Search strategy and\n",
    "3. using a solution-based phase saving approach."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Using LNS\n",
    "Large Neighborhood Search mimics a local search algorithm: it freezes some variables to their value in the last solution and let the others being fixed by the search strategy. \n",
    "Ususally, the user let the solver finds the first solution. But, it is also possible to load a solution to start from.\n",
    "\n",
    "The first step is to load the solution into a `Solution` object."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import org.chocosolver.solver.Solution;\n",
    "import java.util.stream.IntStream;\n",
    "\n",
    "Solution sol = new Solution(model, ticks);\n",
    "IntStream.range(0, m).forEach(i -> sol.setIntVal(ticks[i], good[i]));"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then, a LNS can be declared:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import org.chocosolver.solver.search.limits.FailCounter;\n",
    "import org.chocosolver.solver.search.loop.lns.INeighborFactory;\n",
    "import org.chocosolver.solver.search.loop.lns.neighbors.INeighbor;\n",
    "import org.chocosolver.solver.search.loop.move.MoveLNS;\n",
    "\n",
    "\n",
    "MoveLNS lns = new MoveLNS(\n",
    "    model.getSolver().getMove(), // this represents the default way to explore the search, ie DFS \n",
    "    INeighborFactory.random(ticks), // this represents the way neighborhood will be generated, here randomly\n",
    "    new FailCounter(model, 100) // this represents when to try a new neighborhood, here every 100 failures\n",
    ");  \n",
    "lns.loadFromSolution(sol, model.getSolver()); // the solution is then loaded\n",
    "model.getSolver().setMove(lns); // an LNS is declared"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now, the search can start:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "model.getSolver().showSolutions(() -> Arrays.toString(ticks));\n",
    "model.getSolver().limitTime(\"5s\"); // to avoid never ending loop\n",
    "model.getSolver().solve(); // look for the first improving solution"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Using LDS\n",
    "Limited-Discrepancy Search bets that the enumeration strategy (variable selection + value selection) is quite enough.\n",
    "So it tries not to move too much away from it (see \"W.D. Harvey and M.L.Ginsberg, *Limited Discrepancy Search*, IJCAI-95\" for more details).\n",
    "This approach requires to declare an enumeration strategy based on the solution."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import org.chocosolver.solver.search.strategy.Search;\n",
    "import org.chocosolver.solver.search.strategy.selectors.variables.InputOrder;\n",
    "\n",
    "import java.util.Arrays;\n",
    "import java.util.Map;\n",
    "import java.util.stream.Collectors;\n",
    "\n",
    "model.getSolver().hardReset(); // required for notebook \n",
    "\n",
    "Map<IntVar, Integer> map = IntStream.range(0,m).boxed().collect(Collectors.toMap(i->ticks[i], i -> good[i]));\n",
    "model.getSolver().setSearch(Search.intVarSearch(\n",
    "        new InputOrder<>(model), // variable selection: from ticks[0] to ticks[m-1]\n",
    "        var -> { // value selection, choose value from solution if possible\n",
    "            if(var.contains(map.get(var))){\n",
    "                return map.get(var);\n",
    "            }\n",
    "            return var.getLB(); // otherwise, select the current lower bound\n",
    "        },\n",
    "        ticks\n",
    "));\n",
    "model.getSolver().setLDS(12); // discrepancy is set to 12\n",
    "model.getSolver().showSolutions(() -> Arrays.toString(ticks));\n",
    "model.getSolver().limitTime(\"5s\");\n",
    "model.getSolver().solve();"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solution-based phase saving approach\n",
    "This approach is a kind of compromise between LNS and LDS. It requires a solution to be applied (most of the time, found by the solver) and then when a value selection is called, it tries first the value in the last solution found (for more details, see \"E. Demirović, G. Chu and P.J. Stuckey, *Solution-based phase saving for CP: A value-selection heuristic to simulate local search behavior in complete solvers*, CP18\")."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import org.chocosolver.solver.search.strategy.Search;\n",
    "import org.chocosolver.solver.search.strategy.selectors.variables.InputOrder;\n",
    "import org.chocosolver.solver.search.strategy.selectors.values.IntDomainLast;\n",
    "import org.chocosolver.solver.search.strategy.selectors.values.IntDomainMin;\n",
    "\n",
    "model.getSolver().hardReset(); // required for notebook\n",
    "\n",
    "model.getSolver().setSearch(Search.intVarSearch(\n",
    "    new InputOrder<>(model), // variable selection: from ticks[0] to ticks[m-1]\n",
    "    new IntDomainLast(sol, new IntDomainMin()), // value selection, and default one if value from solution is forbidden\n",
    "    ticks\n",
    "));\n",
    "model.getSolver().showSolutions(() -> Arrays.toString(ticks));\n",
    "model.getSolver().limitTime(\"5s\");\n",
    "model.getSolver().solve();"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Java",
   "language": "java",
   "name": "java"
  },
  "language_info": {
   "codemirror_mode": "java",
   "file_extension": ".java",
   "mimetype": "text/x-java-source",
   "name": "Java",
   "pygments_lexer": "java",
   "version": "11+28"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}