212 lines
6.7 KiB
Plaintext
212 lines
6.7 KiB
Plaintext
{
|
|
"cells": [
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "google",
|
|
"metadata": {},
|
|
"source": [
|
|
"##### Copyright 2025 Google LLC."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "apache",
|
|
"metadata": {},
|
|
"source": [
|
|
"Licensed under the Apache License, Version 2.0 (the \"License\");\n",
|
|
"you may not use this file except in compliance with the License.\n",
|
|
"You may obtain a copy of the License at\n",
|
|
"\n",
|
|
" http://www.apache.org/licenses/LICENSE-2.0\n",
|
|
"\n",
|
|
"Unless required by applicable law or agreed to in writing, software\n",
|
|
"distributed under the License is distributed on an \"AS IS\" BASIS,\n",
|
|
"WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
|
|
"See the License for the specific language governing permissions and\n",
|
|
"limitations under the License.\n"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "basename",
|
|
"metadata": {},
|
|
"source": [
|
|
"# set_covering_deployment"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "link",
|
|
"metadata": {},
|
|
"source": [
|
|
"<table align=\"left\">\n",
|
|
"<td>\n",
|
|
"<a href=\"https://colab.research.google.com/github/google/or-tools/blob/main/examples/notebook/contrib/set_covering_deployment.ipynb\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/colab_32px.png\"/>Run in Google Colab</a>\n",
|
|
"</td>\n",
|
|
"<td>\n",
|
|
"<a href=\"https://github.com/google/or-tools/blob/main/examples/contrib/set_covering_deployment.py\"><img src=\"https://raw.githubusercontent.com/google/or-tools/main/tools/github_32px.png\"/>View source on GitHub</a>\n",
|
|
"</td>\n",
|
|
"</table>"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "doc",
|
|
"metadata": {},
|
|
"source": [
|
|
"First, you must install [ortools](https://pypi.org/project/ortools/) package in this colab."
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": null,
|
|
"id": "install",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"%pip install ortools"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "markdown",
|
|
"id": "description",
|
|
"metadata": {},
|
|
"source": [
|
|
"\n",
|
|
"\n",
|
|
" Set covering deployment in Google CP Solver\n",
|
|
"\n",
|
|
" From http://mathworld.wolfram.com/SetCoveringDeployment.html\n",
|
|
" '''\n",
|
|
" Set covering deployment (sometimes written 'set-covering deployment'\n",
|
|
" and abbreviated SCDP for 'set covering deployment problem') seeks\n",
|
|
" an optimal stationing of troops in a set of regions so that a\n",
|
|
" relatively small number of troop units can control a large\n",
|
|
" geographic region. ReVelle and Rosing (2000) first described\n",
|
|
" this in a study of Emperor Constantine the Great's mobile field\n",
|
|
" army placements to secure the Roman Empire.\n",
|
|
" '''\n",
|
|
"\n",
|
|
" Compare with the following models:\n",
|
|
" * MiniZinc: http://www.hakank.org/minizinc/set_covering_deployment.mzn\n",
|
|
" * Comet : http://www.hakank.org/comet/set_covering_deployment.co\n",
|
|
" * Gecode : http://www.hakank.org/gecode/set_covering_deployment.cpp\n",
|
|
" * ECLiPSe : http://www.hakank.org/eclipse/set_covering_deployment.ecl\n",
|
|
" * SICStus : http://hakank.org/sicstus/set_covering_deployment.pl\n",
|
|
"\n",
|
|
" This model was created by Hakan Kjellerstrand (hakank@gmail.com)\n",
|
|
" Also see my other Google CP Solver models:\n",
|
|
" http://www.hakank.org/google_or_tools/\n",
|
|
"\n"
|
|
]
|
|
},
|
|
{
|
|
"cell_type": "code",
|
|
"execution_count": null,
|
|
"id": "code",
|
|
"metadata": {},
|
|
"outputs": [],
|
|
"source": [
|
|
"from ortools.constraint_solver import pywrapcp\n",
|
|
"\n",
|
|
"\n",
|
|
"def main():\n",
|
|
"\n",
|
|
" # Create the solver.\n",
|
|
" solver = pywrapcp.Solver(\"Set covering deployment\")\n",
|
|
"\n",
|
|
" #\n",
|
|
" # data\n",
|
|
" #\n",
|
|
"\n",
|
|
" countries = [\n",
|
|
" \"Alexandria\", \"Asia Minor\", \"Britain\", \"Byzantium\", \"Gaul\", \"Iberia\",\n",
|
|
" \"Rome\", \"Tunis\"\n",
|
|
" ]\n",
|
|
" n = len(countries)\n",
|
|
"\n",
|
|
" # the incidence matrix (neighbours)\n",
|
|
" mat = [[0, 1, 0, 1, 0, 0, 1, 1], [1, 0, 0, 1, 0, 0, 0, 0],\n",
|
|
" [0, 0, 0, 0, 1, 1, 0, 0], [1, 1, 0, 0, 0, 0, 1, 0],\n",
|
|
" [0, 0, 1, 0, 0, 1, 1, 0], [0, 0, 1, 0, 1, 0, 1, 1],\n",
|
|
" [1, 0, 0, 1, 1, 1, 0, 1], [1, 0, 0, 0, 0, 1, 1, 0]]\n",
|
|
"\n",
|
|
" #\n",
|
|
" # declare variables\n",
|
|
" #\n",
|
|
"\n",
|
|
" # First army\n",
|
|
" X = [solver.IntVar(0, 1, \"X[%i]\" % i) for i in range(n)]\n",
|
|
"\n",
|
|
" # Second (reserv) army\n",
|
|
" Y = [solver.IntVar(0, 1, \"Y[%i]\" % i) for i in range(n)]\n",
|
|
"\n",
|
|
" #\n",
|
|
" # constraints\n",
|
|
" #\n",
|
|
"\n",
|
|
" # total number of armies\n",
|
|
" num_armies = solver.Sum([X[i] + Y[i] for i in range(n)])\n",
|
|
"\n",
|
|
" #\n",
|
|
" # Constraint 1: There is always an army in a city\n",
|
|
" # (+ maybe a backup)\n",
|
|
" # Or rather: Is there a backup, there\n",
|
|
" # must be an an army\n",
|
|
" #\n",
|
|
" [solver.Add(X[i] >= Y[i]) for i in range(n)]\n",
|
|
"\n",
|
|
" #\n",
|
|
" # Constraint 2: There should always be an backup army near every city\n",
|
|
" #\n",
|
|
" for i in range(n):\n",
|
|
" neighbors = solver.Sum([Y[j] for j in range(n) if mat[i][j] == 1])\n",
|
|
" solver.Add(X[i] + neighbors >= 1)\n",
|
|
"\n",
|
|
" objective = solver.Minimize(num_armies, 1)\n",
|
|
"\n",
|
|
" #\n",
|
|
" # solution and search\n",
|
|
" #\n",
|
|
" solution = solver.Assignment()\n",
|
|
" solution.Add(X)\n",
|
|
" solution.Add(Y)\n",
|
|
" solution.Add(num_armies)\n",
|
|
" solution.AddObjective(num_armies)\n",
|
|
"\n",
|
|
" collector = solver.LastSolutionCollector(solution)\n",
|
|
" solver.Solve(\n",
|
|
" solver.Phase(X + Y, solver.INT_VAR_DEFAULT, solver.INT_VALUE_DEFAULT),\n",
|
|
" [collector, objective])\n",
|
|
"\n",
|
|
" print(\"num_armies:\", collector.ObjectiveValue(0))\n",
|
|
" print(\"X:\", [collector.Value(0, X[i]) for i in range(n)])\n",
|
|
" print(\"Y:\", [collector.Value(0, Y[i]) for i in range(n)])\n",
|
|
"\n",
|
|
" for i in range(n):\n",
|
|
" if collector.Value(0, X[i]) == 1:\n",
|
|
" print(\"army:\", countries[i], end=\" \")\n",
|
|
" if collector.Value(0, Y[i]) == 1:\n",
|
|
" print(\"reserv army:\", countries[i], \" \")\n",
|
|
" print()\n",
|
|
"\n",
|
|
" print()\n",
|
|
" print(\"failures:\", solver.Failures())\n",
|
|
" print(\"branches:\", solver.Branches())\n",
|
|
" print(\"WallTime:\", solver.WallTime())\n",
|
|
"\n",
|
|
"\n",
|
|
"main()\n",
|
|
"\n"
|
|
]
|
|
}
|
|
],
|
|
"metadata": {
|
|
"language_info": {
|
|
"name": "python"
|
|
}
|
|
},
|
|
"nbformat": 4,
|
|
"nbformat_minor": 5
|
|
}
|