aula-12-fluxo-rede.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Fluxos de rede\n",
    "\n",
    "Muitos problemas computacionais podem ser representados por um grafo que consiste em nós e arcos entre eles. Um exemplo muito importante são problemas de fluxo de rede, que envolvem o transporte de mercadorias ou materiais através de uma rede, como um sistema ferroviário. \n",
    "\n",
    "Você pode representar um fluxo de rede por um gráfico cujos nós são cidades e cujos arcos são linhas ferroviárias entre eles. (Eles são chamados de fluxos porque suas propriedades são semelhantes às da água fluindo através de uma rede de tubos.)\n",
    "\n",
    "Uma restrição importante nos fluxos de rede é que cada arco tem uma **capacidade** - a quantidade máxima que pode ser transportada através do arco em um período de tempo fixo. \n",
    "\n",
    "## Fluxos Máximos\n",
    "\n",
    "O problema de fluxo máximo é determinar a quantidade total máxima que pode ser transportada por todos os arcos da rede, sujeita às restrições de capacidade.\n",
    "\n",
    "A seguir, veremos um exemplo de problema de fluxo máximo. O problema é definido pelo seguinte grafo, que representa uma rede de transporte:\n",
    "\n",
    "<img src=\"./img/fluxo-maximo.png\" width=\"50%\">\n",
    "\n",
    "Queremos transportar material do nó 0 (a fonte) para o nó 4 (o sumidouro). \n",
    "\n",
    "Os números próximos aos arcos são suas capacidades - a capacidade de um arco é a quantidade máxima que pode ser transportada por ele em um período de tempo fixo. As capacidades são as restrições para o problema.\n",
    "\n",
    "Um fluxo é uma atribuição de um número não negativo a cada arco (a quantidade de fluxo) que satisfaz a seguinte regra de conservação de fluxo:\n",
    "\n",
    "    Em cada nó, que não seja a fonte ou o sumidouro, o fluxo total de todos os arcos que levam ao nó é igual ao fluxo total de todos os arcos que saem dele.\n",
    "    \n",
    "O problema do fluxo máximo é encontrar um fluxo para o qual a soma dos valores de fluxo para toda a rede seja a maior possível.\n",
    "\n",
    "A seguir veremos um programa em C++ para encontrar o fluxo máximo da fonte (nó 0) para o sumidouro (nó 4)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <iostream>\n",
    "#include <iomanip>\n",
    "#include \"setup.h\"\n",
    "#include \"ortools/graph/max_flow.h\"\n",
    "\n",
    "using namespace operations_research;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Defina os dados\n",
    "\n",
    "Você pode representar o grafo para o problema com três vetores, para os nós iniciais, nós finais e capacidades dos arcos. O comprimento de cada vetor é igual ao número de arcos no grafo. Para cada $i$, arco $i$ vai de start_nodes[i] a end_nodes[i], e sua capacidade é dada por capacities[i]. \n",
    "\n",
    "A próxima seção mostra como criar os arcos usando esses dados."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "int numNodes = 5;\n",
    "int numArcs = 9;\n",
    "int start_nodes[] = {0, 0, 0, 1, 1, 2, 2, 3, 3};\n",
    "int end_nodes[] = {1, 2, 3, 2, 4, 3, 4, 2, 4};\n",
    "int capacities[] = {20, 30, 10, 40, 30, 10, 20, 5, 20};"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Declare o solucionador e adicione os arcos\n",
    "\n",
    "Para resolver o problema, usamos o solucionador [SimpleMaxFlow](https://developers.google.com/optimization/reference/graph/max_flow/SimpleMaxFlow).\n",
    "\n",
    "Para cada o nó inicial e nó final, criamos um arco do nó inicial ao nó final com a capacidade fornecida, usando o método AddArcWithCapacity. As capacidades são as restrições para o problema."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "SimpleMaxFlow maxFlow;\n",
    "\n",
    "for (int i = 0; i < numArcs; ++i)\n",
    "{\n",
    "  int arc = maxFlow.AddArcWithCapacity(start_nodes[i], end_nodes[i], capacities[i]);\n",
    "}\n",
    "int source = 0;\n",
    "int sink = numNodes - 1;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Chame o solucionador e exiba os resultados\n",
    "\n",
    "Agora que todos os arcos foram definidos, tudo o que resta é invocar o solucionador e exibir os resultados. Invocamos o método Solve(), fornecendo a fonte (0) e o sumidouro (4) e, a seguir, exibimos o fluxo em cada arco."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solving max flow with 5 nodes, and 9 arcs, source=0, sink=4\n",
      "Max. flow: 60\n",
      "  Arc     Flow / Capacity\n",
      "0 -> 1    20  /  20\n",
      "0 -> 2    30  /  30\n",
      "0 -> 3    10  /  10\n",
      "1 -> 2    0  /  40\n",
      "1 -> 4    20  /  30\n",
      "2 -> 3    10  /  10\n",
      "2 -> 4    20  /  20\n",
      "3 -> 2    0  /  5\n",
      "3 -> 4    20  /  20\n"
     ]
    }
   ],
   "source": [
    "std::cout << \"Solving max flow with \" << numNodes << \" nodes, and \" \n",
    "    << numArcs << \" arcs, source=\" << source << \", sink=\" << sink << std::endl;\n",
    "\n",
    "// Find the maximum flow between node 0 and node 4.\n",
    "int solveStatus = maxFlow.Solve(source, sink);\n",
    "if (solveStatus == SimpleMaxFlow::OPTIMAL) {\n",
    "  std::cout << \"Max. flow: \" << maxFlow.OptimalFlow() << std::endl;\n",
    "  std::cout << \"  Arc     Flow / Capacity\" << std::endl;\n",
    "  for (int i = 0; i < numArcs; ++i) {\n",
    "    std::cout << maxFlow.Tail(i) << \" -> \" <<\n",
    "                      maxFlow.Head(i) << \"    \" <<\n",
    "                      maxFlow.Flow(i) << \"  /  \" <<\n",
    "                      maxFlow.Capacity(i) << std::endl;\n",
    "  }\n",
    "}\n",
    "else {\n",
    "  std::cout << \"Solving the max flow problem failed. Solver status: \" << solveStatus;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fluxos de Custo Mínimo\n",
    "\n",
    "O problema de fluxo de custo mínimo está intimamente relacionado ao problema de fluxo máximo com a diferença que cada arco no gráfico tem um custo unitário para transportar material através dele. O problema é encontrar um fluxo com o menor custo total.\n",
    "\n",
    "O problema de fluxo de custo mínimo também possui nós especiais, chamados de nós de suprimento ou nós de demanda, que são semelhantes à origem e ao sumidouro no problema de fluxo máximo. O material é transportado de nós de suprimento para nós de demanda.\n",
    "\n",
    "- Em um nó de suprimento, uma quantidade positiva - o suprimento - é adicionado ao fluxo. Um suprimento pode representar a produção naquele nó, por exemplo.\n",
    "\n",
    "- Em um nó de demanda, uma quantidade negativa - a demanda - é retirada do fluxo. Uma demanda pode representar o consumo naquele nó, por exemplo.\n",
    "\n",
    "Por conveniência, assumiremos que todos os nós, exceto os nós de suprimento ou demanda, têm suprimento (e demanda) zero.\n",
    "\n",
    "Para o problema de fluxo de custo mínimo, temos a seguinte regra de conservação de fluxo, que leva em consideração os suprimentos e as demandas:\n",
    "\n",
    "    Em cada nó, o fluxo total que sai do nó menos o fluxo total que chega ao nó é igual ao suprimento (ou demanda) nesse nó.\n",
    "    \n",
    "O grafo abaixo mostra um problema de fluxo de custo mínimo. Os arcos são rotulados com pares de números: \n",
    "- o primeiro número é a capacidade e o segundo número é o custo. \n",
    "- os números entre parênteses próximos aos nós representam suprimentos ou demandas. \n",
    "\n",
    "O nó 0 é um nó de suprimento com fornecimento 20, enquanto os nós 3 e 4 são nós de demanda, com demandas -5 e -15, respectivamente.\n",
    "\n",
    "<img src=\"./img/fluxo-custo-min.png\" width=\"50%\">\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "#include <iostream>\n",
    "#include <iomanip>\n",
    "#include \"setup.h\"\n",
    "#include \"ortools/graph/min_cost_flow.h\"\n",
    "\n",
    "using namespace operations_research;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Defina os dados\n",
    "\n",
    "O código a seguir define os dados para o problema. Nesse caso, há quatro matrizes para os nós iniciais, nós finais, capacidades e custos unitários. Novamente, o comprimento das matrizes é o número de arcos no grafo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "int numNodes = 5;\n",
    "int numArcs = 9;\n",
    "\n",
    "int startNodes[] = {0, 0, 1, 1, 1, 2, 2, 3, 4};\n",
    "int endNodes[] = {1, 2, 2, 3, 4, 3, 4, 4, 2};\n",
    "int capacities[] = {15, 8, 20, 4, 10, 15, 4, 20, 5};\n",
    "int unitCosts[] = {4, 4, 2, 2, 6, 1, 3, 2, 3};\n",
    "\n",
    "// Define an array of supplies at each node.\n",
    "int supplies[] = {20, 0, 0, -5, -15};"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Declare o solucionador e adicione os arcos\n",
    "\n",
    "Para resolver o problema, usamos o solucionador [SimpleMinCostFlow](https://developers.google.com/optimization/reference/graph/min_cost_flow/SimpleMinCostFlow).\n",
    "\n",
    "Para cada nó inicial e nó final, criamos um arco do nó inicial ao nó final com a capacidade e custo unitário dados, usando o método **AddArcWithCapacityAndUnitCost**.\n",
    "\n",
    "O método **SetNodeSupply** do solucionador cria um vetor de suprimentos para os nós."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "SimpleMinCostFlow minCostFlow;\n",
    "\n",
    "// Add each arc.\n",
    "for (int i = 0; i < numArcs; ++i) {\n",
    "  int arc = minCostFlow.AddArcWithCapacityAndUnitCost(startNodes[i], endNodes[i],\n",
    "                                       capacities[i], unitCosts[i]);\n",
    "}\n",
    "\n",
    " // Add node supplies.\n",
    "for (int i = 0; i < numNodes; ++i) {\n",
    "  minCostFlow.SetNodeSupply(i, supplies[i]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Chame o solucionador e exiba os resultados\n",
    "\n",
    "Agora que todos os arcos foram definidos, tudo o que resta é invocar o solucionador e exibir os resultados. Chamamos o método Solve () e, em seguida, exibimos o fluxo e o custo em cada arco."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Minimum cost: 150\n",
      " Edge   Flow / Capacity  Cost\n",
      "0 -> 1  12  / 15       48\n",
      "0 -> 2  8  / 8       32\n",
      "1 -> 2  8  / 20       16\n",
      "1 -> 3  4  / 4       8\n",
      "1 -> 4  0  / 10       0\n",
      "2 -> 3  12  / 15       12\n",
      "2 -> 4  4  / 4       12\n",
      "3 -> 4  11  / 20       22\n",
      "4 -> 2  0  / 5       0\n"
     ]
    }
   ],
   "source": [
    "int solveStatus = minCostFlow.Solve();\n",
    "if (solveStatus == MinCostFlow::OPTIMAL) {\n",
    "  auto optimalCost = minCostFlow.OptimalCost();\n",
    "  std::cout << \"Minimum cost: \" << optimalCost << std::endl;\n",
    "\n",
    "  std::cout << \" Edge   Flow / Capacity  Cost\" << std::endl;\n",
    "  for (int i = 0; i < numArcs; ++i) {\n",
    "    auto cost = minCostFlow.Flow(i) * minCostFlow.UnitCost(i);\n",
    "    std::cout << minCostFlow.Tail(i) << \" -> \" <<\n",
    "                      minCostFlow.Head(i) << \"  \" <<\n",
    "                      minCostFlow.Flow(i) << \"  / \" <<\n",
    "                      minCostFlow.Capacity(i) << \"       \" <<\n",
    "                      cost << std::endl;\n",
    "  }\n",
    "}\n",
    "else {\n",
    "  std::cout << \"Solving the min cost flow problem failed. Solver status: \" << solveStatus;\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++14",
   "language": "C++14",
   "name": "xcpp14"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
   "version": "14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}