{ "cells": [ { "cell_type": "markdown", "id": "f2d7b3c9", "metadata": {}, "source": [ "# Multi-commodity Network Flows\n", "\n", "Multi-commodity network flows are a mathematical model used to optimize the simultaneous routing of multiple resources through a single network. These models can be applied in various fields, including logistics, telecommunications, and urban planning to improve efficiency and resource allocation. In our example, we will explore the application of this model using a small network consisting of nodes **A, B, C, D,** and **E**, connected by directed edges with specific capacities: **A->B**, **A->D**, **B->C**, **B->D**, **C->E**, **D->C**, and **D->E**. The network includes two commodities, with the first aiming to maximize flow from node **A** to node **C**, and the second from node **A** to node **E**. Transporting each commodity through the network has a different profit per edge, and the objective is to maximize the total profit while respecting the capacity constraints of each edge." ] }, { "cell_type": "code", "execution_count": 1, "id": "a1684e94", "metadata": {}, "outputs": [ { "data": { "text/html": [ "\n", " \n", " \n", " \n", " \n", " \n", "
\n", " \n", " \n", " \n", " \n", "
Installed version:v1.0.0-alpha.0 (latest: v0.9.1-alpha.6)
Available backends:CVXPY v1.4.2, PICOS v2.4.17
Default backend (corneto.K):CVXPY
Installed solvers:CLARABEL, CVXOPT, ECOS, ECOS_BB, GLPK, GLPK_MI, OSQP, SCIP, SCIPY, SCS
Graphviz version:v0.20.1
Repository:https://github.com/saezlab/corneto
\n", "
" ], "text/plain": [ "" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "import numpy as np\n", "import pandas as pd\n", "\n", "import corneto as cn\n", "\n", "cn.info()" ] }, { "cell_type": "code", "execution_count": 2, "id": "4512c595", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "A\n", "\n", "A\n", "\n", "\n", "\n", "B\n", "\n", "B\n", "\n", "\n", "\n", "A->B\n", "\n", "\n", "\n", "\n", "\n", "D\n", "\n", "D\n", "\n", "\n", "\n", "A->D\n", "\n", "\n", "\n", "\n", "\n", "B->D\n", "\n", "\n", "\n", "\n", "\n", "C\n", "\n", "C\n", "\n", "\n", "\n", "B->C\n", "\n", "\n", "\n", "\n", "\n", "D->C\n", "\n", "\n", "\n", "\n", "\n", "E\n", "\n", "E\n", "\n", "\n", "\n", "D->E\n", "\n", "\n", "\n", "\n", "\n", "C->E\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "G = cn.Graph()\n", "# We create the transportation network, and we add attributes to the edges.\n", "# These attributes are the capacity of the edge, and the profit of the edge for the two commodities.\n", "G.add_edge(\"A\", \"B\", capacity=10, profit_c1=4, profit_c2=1)\n", "G.add_edge(\"A\", \"D\", capacity=15, profit_c1=3, profit_c2=2)\n", "G.add_edge(\"B\", \"C\", capacity=12, profit_c1=2, profit_c2=3)\n", "G.add_edge(\"B\", \"D\", capacity=5, profit_c1=1, profit_c2=4)\n", "G.add_edge(\"C\", \"E\", capacity=10, profit_c1=5, profit_c2=5)\n", "G.add_edge(\"D\", \"C\", capacity=4, profit_c1=2, profit_c2=6)\n", "G.add_edge(\"D\", \"E\", capacity=8, profit_c1=3, profit_c2=4)\n", "G.plot()" ] }, { "cell_type": "markdown", "id": "f731f972", "metadata": {}, "source": [ "Now we will manually create a flow graph by adding incoming edges for flow through the input vertices and outgoing flow edges for the output vertices." ] }, { "cell_type": "code", "execution_count": 3, "id": "16658b82", "metadata": {}, "outputs": [ { "data": { "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "A\n", "\n", "A\n", "\n", "\n", "\n", "B\n", "\n", "B\n", "\n", "\n", "\n", "A->B\n", "\n", "\n", "\n", "\n", "\n", "D\n", "\n", "D\n", "\n", "\n", "\n", "A->D\n", "\n", "\n", "\n", "\n", "\n", "B->D\n", "\n", "\n", "\n", "\n", "\n", "C\n", "\n", "C\n", "\n", "\n", "\n", "B->C\n", "\n", "\n", "\n", "\n", "\n", "D->C\n", "\n", "\n", "\n", "\n", "\n", "E\n", "\n", "E\n", "\n", "\n", "\n", "D->E\n", "\n", "\n", "\n", "\n", "\n", "C->E\n", "\n", "\n", "\n", "\n", "\n", "e_8_target\n", "\n", "\n", "\n", "\n", "C->e_8_target\n", "\n", "\n", "\n", "\n", "\n", "e_9_target\n", "\n", "\n", "\n", "\n", "E->e_9_target\n", "\n", "\n", "\n", "\n", "\n", "e_7_source\n", "\n", "\n", "\n", "\n", "e_7_source->A\n", "\n", "\n", "\n", "\n", "\n" ], "text/plain": [ "" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# First commodity, routing from A to C\n", "G.add_edge((), \"A\", capacity=1000)\n", "G.add_edge(\"C\", (), capacity=1000)\n", "\n", "# Second commodity, routing from A to E.\n", "G.add_edge(\"E\", (), capacity=1000)\n", "\n", "G.plot()" ] }, { "cell_type": "code", "execution_count": 4, "id": "3e456484", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[10, 15, 12, 5, 10, 4, 8, 1000, 1000, 1000]" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "G.get_attr_from_edges(\"capacity\")" ] }, { "cell_type": "code", "execution_count": 5, "id": "3359283c", "metadata": {}, "outputs": [], "source": [ "# P.expr.flow.sum(axis=0).shape" ] }, { "cell_type": "code", "execution_count": 18, "id": "efb4a139", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "{'_flow': Variable((10, 2), _flow), 'flow': Variable((10, 2), _flow)}" ] }, "execution_count": 18, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# We create a flow problem with 2 flows, one per commodity\n", "P = cn.K.Flow(G, ub=G.get_attr_from_edges(\"capacity\"), n_flows=2, shared_bounds=True)\n", "# NOTE: Using shared bounds links shares the capacity of the edges across flows. It is equivalent to adding this constraint here:\n", "# P += P.expressions.flow[:, 0] + P.expressions.flow[:, 1] <= G.get_attr_from_edges('capacity')\n", "P.expressions" ] }, { "cell_type": "code", "execution_count": 20, "id": "f5ce234b", "metadata": {}, "outputs": [], "source": [ "c1 = np.array(G.get_attr_from_edges(\"profit_c1\", 0))\n", "c2 = np.array(G.get_attr_from_edges(\"profit_c2\", 0))" ] }, { "cell_type": "code", "execution_count": 21, "id": "6c8445f5", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(CORNETO) Apr 23 04:42:36 PM - WARNING : Directly calling function 'multiply' on the backend engine may lead to incompatibility issues with other computational backends. It's recommended to use compatible abstraction methods to ensure backend-agnostic operation.\n", "(CORNETO) Apr 23 04:42:36 PM - WARNING : Directly calling function 'multiply' on the backend engine may lead to incompatibility issues with other computational backends. It's recommended to use compatible abstraction methods to ensure backend-agnostic operation.\n", "===============================================================================\n", " CVXPY \n", " v1.4.2 \n", "===============================================================================\n", "(CVXPY) Apr 23 04:42:36 PM: Your problem has 20 variables, 4 constraints, and 0 parameters.\n", "(CVXPY) Apr 23 04:42:36 PM: It is compliant with the following grammars: DCP, DQCP\n", "(CVXPY) Apr 23 04:42:36 PM: (If you need to solve this problem multiple times, but with different data, consider using parameters.)\n", "(CVXPY) Apr 23 04:42:36 PM: CVXPY will first compile your problem; then, it will invoke a numerical solver to obtain a solution.\n", "(CVXPY) Apr 23 04:42:36 PM: Your problem is compiled with the CPP canonicalization backend.\n", "-------------------------------------------------------------------------------\n", " Compilation \n", "-------------------------------------------------------------------------------\n", "(CVXPY) Apr 23 04:42:36 PM: Compiling problem (target solver=SCIP).\n", "(CVXPY) Apr 23 04:42:36 PM: Reduction chain: Dcp2Cone -> CvxAttr2Constr -> ConeMatrixStuffing -> SCIP\n", "(CVXPY) Apr 23 04:42:36 PM: Applying reduction Dcp2Cone\n", "(CVXPY) Apr 23 04:42:36 PM: Applying reduction CvxAttr2Constr\n", "(CVXPY) Apr 23 04:42:36 PM: Applying reduction ConeMatrixStuffing\n", "(CVXPY) Apr 23 04:42:36 PM: Applying reduction SCIP\n", "(CVXPY) Apr 23 04:42:36 PM: Finished problem compilation (took 7.972e-02 seconds).\n", "-------------------------------------------------------------------------------\n", " Numerical solver \n", "-------------------------------------------------------------------------------\n", "(CVXPY) Apr 23 04:42:36 PM: Invoking solver SCIP to obtain a solution.\n", "-------------------------------------------------------------------------------\n", " Summary \n", "-------------------------------------------------------------------------------\n", "(CVXPY) Apr 23 04:42:36 PM: Problem status: optimal\n", "(CVXPY) Apr 23 04:42:36 PM: Optimal value: -1.900e+02\n", "(CVXPY) Apr 23 04:42:36 PM: Compilation took 7.972e-02 seconds\n", "(CVXPY) Apr 23 04:42:36 PM: Solver (including time spent in interface) took 2.704e-02 seconds\n" ] }, { "data": { "text/plain": [ "Problem(Minimize(Expression(AFFINE, UNKNOWN, ())), [Inequality(Constant(CONSTANT, ZERO, (10, 2))), Inequality(Variable((10, 2), _flow)), Equality(Expression(AFFINE, UNKNOWN, (5, 2)), Constant(CONSTANT, ZERO, ())), Inequality(Expression(AFFINE, UNKNOWN, (10,)))])" ] }, "execution_count": 21, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Finally, we add the objective function: maximize the amount of flow per commodity, taking into account the profit\n", "# of transporting each commodity through each edge.\n", "P.add_objectives(sum(P.expressions.flow[:, 0].multiply(c1)), weights=-1)\n", "P.add_objectives(sum(P.expressions.flow[:, 1].multiply(c2)), weights=-1)\n", "P.solve(verbosity=1)" ] }, { "cell_type": "code", "execution_count": 22, "id": "df3a320d", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(90.0, 100.0)" ] }, "execution_count": 22, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P.objectives[0].value, P.objectives[1].value" ] }, { "cell_type": "code", "execution_count": 24, "id": "eedc57ad", "metadata": {}, "outputs": [ { "data": { "text/html": [ "
\n", "\n", "\n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", " \n", "
Commodity 1Commodity 2totalcapacityProfit c1Profit c2Total profit
(A)(B)10.00.010.01040.00.040.0
(D)0.012.012.0150.024.024.0
(B)(C)10.00.010.01220.00.020.0
(D)0.00.00.050.00.00.0
(C)(E)6.04.010.01030.020.050.0
(D)(C)0.04.04.040.024.024.0
(E)0.08.08.080.032.032.0
()(A)10.012.022.010000.00.00.0
(C)()4.00.04.010000.00.00.0
(E)()6.012.018.010000.00.00.0
\n", "
" ], "text/plain": [ " Commodity 1 Commodity 2 total capacity Profit c1 Profit c2 \\\n", "(A) (B) 10.0 0.0 10.0 10 40.0 0.0 \n", " (D) 0.0 12.0 12.0 15 0.0 24.0 \n", "(B) (C) 10.0 0.0 10.0 12 20.0 0.0 \n", " (D) 0.0 0.0 0.0 5 0.0 0.0 \n", "(C) (E) 6.0 4.0 10.0 10 30.0 20.0 \n", "(D) (C) 0.0 4.0 4.0 4 0.0 24.0 \n", " (E) 0.0 8.0 8.0 8 0.0 32.0 \n", "() (A) 10.0 12.0 22.0 1000 0.0 0.0 \n", "(C) () 4.0 0.0 4.0 1000 0.0 0.0 \n", "(E) () 6.0 12.0 18.0 1000 0.0 0.0 \n", "\n", " Total profit \n", "(A) (B) 40.0 \n", " (D) 24.0 \n", "(B) (C) 20.0 \n", " (D) 0.0 \n", "(C) (E) 50.0 \n", "(D) (C) 24.0 \n", " (E) 32.0 \n", "() (A) 0.0 \n", "(C) () 0.0 \n", "(E) () 0.0 " ] }, "execution_count": 24, "metadata": {}, "output_type": "execute_result" } ], "source": [ "df_result = pd.DataFrame(\n", " P.expressions.flow.value, index=G.E, columns=[\"Commodity 1\", \"Commodity 2\"]\n", ")\n", "df_result[\"total\"] = df_result.sum(axis=1)\n", "df_result[\"capacity\"] = G.get_attr_from_edges(\"capacity\")\n", "df_result[\"Profit c1\"] = df_result[\"Commodity 1\"] * c1\n", "df_result[\"Profit c2\"] = df_result[\"Commodity 2\"] * c2\n", "df_result[\"Total profit\"] = df_result[\"Profit c1\"] + df_result[\"Profit c2\"]\n", "df_result" ] }, { "cell_type": "code", "execution_count": 25, "id": "3a31f2f1", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "190.0" ] }, "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ "df_result[\"Total profit\"].sum()" ] }, { "cell_type": "code", "execution_count": 26, "id": "759f76d0", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "190.0" ] }, "execution_count": 26, "metadata": {}, "output_type": "execute_result" } ], "source": [ "P.objectives[0].value + P.objectives[1].value" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.9.13" }, "toc": { "base_numbering": 1, "nav_menu": {}, "number_sections": true, "sideBar": true, "skip_h1_title": false, "title_cell": "Table of Contents", "title_sidebar": "Contents", "toc_cell": false, "toc_position": {}, "toc_section_display": true, "toc_window_display": false } }, "nbformat": 4, "nbformat_minor": 5 }