{ "cells": [ { "cell_type": "markdown", "metadata": { "id": "uRtp1E6mSnM2" }, "source": [ "```{index} single: application; seating allocation\n", "```\n", "```{index} single: solver; cbc\n", "```\n", "```{index} single: AMPL; parameters\n", "```\n", "```{index} single: AMPL; sets\n", "```\n", "```{index} network optimization\n", "```\n", "```{index} max flow problem\n", "```\n", "```{index} networkx\n", "```\n", "```{index} feasibility problem\n", "```\n", "\n", "# Dinner seating arrangement" ] }, { "cell_type": "code", "execution_count": 1, "metadata": { "colab": { "base_uri": "https://localhost:8080/" }, "id": "5ssUqKOaPVaE", "outputId": "38c1005a-39f4-4307-e305-19a4c9819396" }, "outputs": [], "source": [ "# install dependencies and select solver\n", "%pip install -q amplpy pandas networkx\n", "\n", "SOLVER = \"cbc\"\n", "\n", "from amplpy import AMPL, ampl_notebook\n", "\n", "ampl = ampl_notebook(\n", " modules=[\"cbc\"], # modules to install\n", " license_uuid=\"default\", # license to use\n", ") # instantiate AMPL object and register magics" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "from IPython.display import display\n", "import networkx as nx\n", "import pandas as pd" ] }, { "cell_type": "markdown", "metadata": { "id": "uRtp1E6mSnM2" }, "source": [ "## Problem description\n", "\n", "Consider organizing a wedding dinner. Your objective is for guests from different families to mingle with each other. One way to encourage mingling is to seat people at the tables so that no more people than $k$ members of the same family take a seat at the same table. \n", "\n", "How could we solve a problem like this? First, we need the problem data -- for each family $f$ we need to know the number of its members $m_f$, and for each table $t$ we need to know its capacity $c_t$. Using this data and the tools we learned so far, we can formulate this problem as a linear optimization (LO).\n", "\n", "We can use variable $x_{ft}$ for the number of persons from family $f$ to be seated at table $t$. Since we were not provided with any objective function, we can focus on finding a feasible solution by setting the objective function to be constant, say $0$, which means that we do not differentiate between feasible solutions. \n", "\n", "The mathematical formulation of this seating problem is:\n", "\n", "$$\n", "\\begin{align*}\n", " \\min_{x_{ft}} \\quad & 0 \\label{ch4eq.Dina.problem.1}\\\\\n", " \\text{s.t.} \\quad & \\sum\\limits_{f} x_{ft} \\leq c_t & \\forall \\, t \\in T \\\\\n", " & \\sum\\limits_{t} x_{ft} = m_f & \\forall \\, f \\in F \\\\\n", " & 0 \\leq x_{ft} \\leq k.\n", "\\end{align*}\n", "$$\n", "\n", "The constraints ensure that the seating capacity for each table is not exceeded, that each family is fully seated, and that the number of elements of each family at each table does not exceed the threshold $k$." ] }, { "cell_type": "markdown", "metadata": { "id": "AqUu7i2kxV98" }, "source": [ "## Implementation\n", "\n", "The problem statement will be satisfied by finding a feasible solution, if one exists. Because no specific objective has been specified, the mathematical formulation uses a constant 0 as essentially a placeholder for the objective function. Some optimization solvers, however, issue warning messages if they detect a constant objective, and others will fail to execute at all. A simple work around for these cases is to replace the constant objective with a 'dummy' variable that doesn't appear elsewhere in the optimization problem. " ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Overwriting table_seat.mod\n" ] } ], "source": [ "%%writefile table_seat.mod\n", "\n", "set F;\n", "set T;\n", "\n", "param M{F};\n", "param C{T};\n", "\n", "param k;\n", "\n", "var x{F, T} >= 0, <= k;\n", "var dummy >= 0, <= 1, default 0;\n", "\n", "minimize goal: dummy;\n", "\n", "s.t. capacity {t in T}: sum{f in F} x[f, t] <= C[t];\n", "s.t. seat {f in F}: sum{t in T} x[f, t] == M[f];" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "id": "g3Jo-pwb4ltx" }, "outputs": [], "source": [ "def table_seat(members, capacity, k):\n", " m = AMPL()\n", " m.read(\"table_seat.mod\")\n", "\n", " m.set[\"F\"] = range(len(members))\n", " m.set[\"T\"] = range(len(capacity))\n", "\n", " m.param[\"M\"] = members\n", " m.param[\"C\"] = capacity\n", "\n", " m.param[\"k\"] = k\n", "\n", " m.option[\"solver\"] = SOLVER\n", "\n", " return m\n", "\n", "\n", "def get_solution(model):\n", " df = model.var[\"x\"].to_pandas()\n", " df.index.names = [\"family\", \"table\"]\n", " df = df.unstack()\n", " df.columns = df.columns.get_level_values(1)\n", "\n", " return df.round(5)\n", "\n", "\n", "def report(model, results, type=int):\n", " print(f\"Solve result: {model.solve_result}\")\n", " if model.solve_result == \"solved\":\n", " soln = get_solution(model).astype(type)\n", " display(soln)\n", " print(f'objective: {model.obj[\"goal\"].value()}')\n", " print(f\"places at table: {list(soln.sum(axis=0))}\")\n", " print(f\"members seated: {list(soln.sum(axis=1))}\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let us now consider and solve a specific instance of this problem with six families with sizes $m = (6, 8, 2, 9, 13, 1)$, five tables with capacities $c = (8, 8, 10, 4, 9)$, and a threshold $k=3$ for the number of members of each family that can be seated at the same table. " ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 337 }, "executionInfo": { "elapsed": 293, "status": "ok", "timestamp": 1623769075200, "user": { "displayName": "Joaquim Gromicho", "photoUrl": "", "userId": "14375950305363805729" }, "user_tz": -120 }, "id": "glauQ3YqSnM6", "outputId": "5d75d95c-4176-4d59-f4fa-4d1d27adbdf4" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "cbc 2.10.7: \b\b\b\b\b\b\b\b\b\b\b\bcbc 2.10.7: optimal solution; objective 0\n", "0 simplex iterations\n", "CPU times: user 0 ns, sys: 1.35 ms, total: 1.35 ms\n", "Wall time: 16.4 ms\n", "Solve result: solved\n" ] }, { "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", "
table01234
family
00.03.01.00.02.0
13.00.03.00.02.0
20.00.00.00.02.0
31.02.03.03.00.0
43.03.03.01.03.0
51.00.00.00.00.0
\n", "
" ], "text/plain": [ "table 0 1 2 3 4\n", "family \n", "0 0.0 3.0 1.0 0.0 2.0\n", "1 3.0 0.0 3.0 0.0 2.0\n", "2 0.0 0.0 0.0 0.0 2.0\n", "3 1.0 2.0 3.0 3.0 0.0\n", "4 3.0 3.0 3.0 1.0 3.0\n", "5 1.0 0.0 0.0 0.0 0.0" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "objective: 0.0\n", "places at table: [8.0, 8.0, 10.0, 4.0, 9.0]\n", "members seated: [6.0, 8.0, 2.0, 9.0, 13.0, 1.0]\n" ] } ], "source": [ "seatplan = table_seat(members=[6, 8, 2, 9, 13, 1], capacity=[8, 8, 10, 4, 9], k=3)\n", "%time results = seatplan.solve()\n", "assert seatplan.solve_result == \"solved\", seatplan.solve_result\n", "report(seatplan, results, type=float)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "A peculiar fact is that although we did not explicitly require that all variables $x_{ft}$ be integer, the optimal solution turned out to be integer anyway. This is no coincidence as it follows from a certain property of the problem we solve. This also means we can solve larger versions of this problem with LO instead of MILO solvers to find integer solutions, gaining a large computational advantage." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Minimize the maximum group size\n", "\n", "Our objective was that we make members of different families mingle as much as possible. Is $k = 3$ the lowest possible number for which a feasible table allocation exists or can we make the tables even more diverse by bringing this number down?\n", "\n", "In order to find out, we change the objective function and try to minimize $k$, obtaining the following problem:" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Overwriting table_seat_minimize_max_group_at_table.mod\n" ] } ], "source": [ "%%writefile table_seat_minimize_max_group_at_table.mod\n", "\n", "set F;\n", "set T;\n", "\n", "param M{F};\n", "param C{T};\n", "\n", "var x{F,T} >= 0;\n", "var k >= 0;\n", "\n", "minimize goal: k;\n", " \n", "s.t. capacity {t in T}: sum{f in F} x[f,t] <= C[t];\n", "s.t. seat {f in F}: sum{t in T} x[f,t] == M[f];\n", "s.t. bound {f in F, t in T}: x[f,t] <= k;" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "id": "GJxtvN9gS2xW" }, "outputs": [], "source": [ "def table_seat_minimize_max_group_at_table(members, capacity):\n", " m = AMPL()\n", " m.read(\"table_seat_minimize_max_group_at_table.mod\")\n", "\n", " m.set[\"F\"] = range(len(members))\n", " m.set[\"T\"] = range(len(capacity))\n", "\n", " m.param[\"M\"] = members\n", " m.param[\"C\"] = capacity\n", "\n", " m.option[\"solver\"] = SOLVER\n", "\n", " return m" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We now solve the same instance as before." ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 337 }, "executionInfo": { "elapsed": 269, "status": "ok", "timestamp": 1623768701481, "user": { "displayName": "Joaquim Gromicho", "photoUrl": "", "userId": "14375950305363805729" }, "user_tz": -120 }, "id": "amuwHXmGt_va", "outputId": "9056e7b0-1a7e-4017-e31b-ecbffa4a312b" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "cbc 2.10.7: \b\b\b\b\b\b\b\b\b\b\b\bcbc 2.10.7: optimal solution; objective 2.6\n", "0 simplex iterations\n", "CPU times: user 0 ns, sys: 1.47 ms, total: 1.47 ms\n", "Wall time: 16.3 ms\n", "Solve result: solved\n" ] }, { "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", "
table01234
family
00.02.60.80.02.6
12.60.22.60.02.6
20.00.00.80.01.2
32.62.62.41.40.0
42.62.62.62.62.6
50.20.00.80.00.0
\n", "
" ], "text/plain": [ "table 0 1 2 3 4\n", "family \n", "0 0.0 2.6 0.8 0.0 2.6\n", "1 2.6 0.2 2.6 0.0 2.6\n", "2 0.0 0.0 0.8 0.0 1.2\n", "3 2.6 2.6 2.4 1.4 0.0\n", "4 2.6 2.6 2.6 2.6 2.6\n", "5 0.2 0.0 0.8 0.0 0.0" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "objective: 2.6\n", "places at table: [8.0, 8.0, 10.0, 4.0, 9.0]\n", "members seated: [6.0, 8.0, 2.0, 9.0, 13.0, 1.0]\n" ] } ], "source": [ "seatplan = table_seat_minimize_max_group_at_table(\n", " members=[6, 8, 2, 9, 13, 1], capacity=[8, 8, 10, 4, 9]\n", ")\n", "%time results = seatplan.solve()\n", "report(seatplan, results, type=float)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Unfortunately, this solution is no longer integer. Mathematically, this is because the \"structure\" that previously ensured integer solutions at no extra cost has been lost as a result of making $k$ a decision variable. To find the solution to this problem we would need to impose that the variables are integers." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Minimize number of tables\n", "We now add an integer variable `y` to minimize the number of tables in our model. In order to better compare the diferences between a LO and a MILO implementation, we introduce the AMPL option `relax_integrality`. When the option `relax_integrality` is set to 1 all the integer variables in the model are treated as linear. Conversely, if `relax_integrality` is set to 0 the integrality restrictions are restored in the model." ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Overwriting table_seat_minimize_number_of_tables.mod\n" ] } ], "source": [ "%%writefile table_seat_minimize_number_of_tables.mod\n", "\n", "set F;\n", "set T;\n", "\n", "param M{F};\n", "param C{T};\n", "\n", "param k;\n", "\n", "var x{F,T} integer >= 0, <= k;\n", "var y{T} binary;\n", "\n", "minimize goal: sum{t in T} y[t];\n", "\n", "s.t. capacity{t in T}: sum{f in F} x[f,t] <= C[t] * y[t];\n", "s.t. seat{f in F}: sum{t in T} x[f,t] == M[f];" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "id": "9mHD-wjuuLg2" }, "outputs": [], "source": [ "def table_seat_minimize_number_of_tables(members, capacity, k, relax=False):\n", " m = AMPL()\n", " m.read(\"table_seat_minimize_number_of_tables.mod\")\n", "\n", " m.set[\"F\"] = range(len(members))\n", " m.set[\"T\"] = range(len(capacity))\n", "\n", " m.param[\"M\"] = members\n", " m.param[\"C\"] = capacity\n", " m.param[\"k\"] = k\n", "\n", " m.option[\"solver\"] = SOLVER\n", "\n", " if relax:\n", " m.option[\"relax_integrality\"] = 1\n", "\n", " return m" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "MILO problem\n", "\n", "cbc 2.10.7: \b\b\b\b\b\b\b\b\b\b\b\bcbc 2.10.7: optimal solution; objective 5\n", "0 simplex iterations\n", "CPU times: user 477 µs, sys: 78 µs, total: 555 µs\n", "Wall time: 17.3 ms\n", "Solve result: solved\n" ] }, { "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", "
table01234
family
020301
102303
200020
333111
433313
500001
\n", "
" ], "text/plain": [ "table 0 1 2 3 4\n", "family \n", "0 2 0 3 0 1\n", "1 0 2 3 0 3\n", "2 0 0 0 2 0\n", "3 3 3 1 1 1\n", "4 3 3 3 1 3\n", "5 0 0 0 0 1" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "objective: 5.0\n", "places at table: [8, 8, 10, 4, 9]\n", "members seated: [6, 8, 2, 9, 13, 1]\n", "\n", "Relaxed problem\n", "\n", "cbc 2.10.7: \b\b\b\b\b\b\b\b\b\b\b\bcbc 2.10.7: optimal solution; objective 5\n", "0 simplex iterations\n", "CPU times: user 464 µs, sys: 75 µs, total: 539 µs\n", "Wall time: 15.6 ms\n", "Solve result: solved\n" ] }, { "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", "
table01234
family
00.02.01.00.03.0
10.02.03.00.03.0
21.00.00.01.00.0
33.03.03.00.00.0
43.01.03.03.03.0
51.00.00.00.00.0
\n", "
" ], "text/plain": [ "table 0 1 2 3 4\n", "family \n", "0 0.0 2.0 1.0 0.0 3.0\n", "1 0.0 2.0 3.0 0.0 3.0\n", "2 1.0 0.0 0.0 1.0 0.0\n", "3 3.0 3.0 3.0 0.0 0.0\n", "4 3.0 1.0 3.0 3.0 3.0\n", "5 1.0 0.0 0.0 0.0 0.0" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "objective: 5.0\n", "places at table: [8.0, 8.0, 10.0, 4.0, 9.0]\n", "members seated: [6.0, 8.0, 2.0, 9.0, 13.0, 1.0]\n" ] } ], "source": [ "members = [6, 8, 2, 9, 13, 1]\n", "capacity = [8, 8, 10, 4, 9]\n", "k = 3\n", "\n", "print(\"\\nMILO problem\\n\")\n", "seatplan = table_seat_minimize_number_of_tables(members, capacity, k)\n", "%time results = seatplan.solve()\n", "report(seatplan, results, type=int)\n", "\n", "print(\"\\nRelaxed problem\\n\")\n", "seatplan = table_seat_minimize_number_of_tables(members, capacity, k, relax=True)\n", "%time results = seatplan.solve()\n", "report(seatplan, results, type=float)" ] }, { "cell_type": "markdown", "metadata": { "id": "5klBA6ebVDf3" }, "source": [ "# Reformulation as max flow problem" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "However, using an MILO solver is not necessarily the best approach for problems like this. Many real-life situations (assigning people to work/course groups) require solving really large problems. There are existing algorithms that can leverage the special **network structure** of the problem at hand and scale better than LO solvers. To see this we can visualize the seating problem using a graph where:\n", "\n", "* the nodes on the left-hand side stand for the families and the numbers next to them provide the family size\n", "* the nodes on the left-hand side stand for the tables and the numbers next to them provide the table size\n", "* each left-to-right arrow stand comes with a number denoting the capacity of arc $(f, t)$ -- how many people of family $f$ can be assigned to table $t$.\n", "\n", "![](dina_model_basic.png)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "If we see each family as a place of supply (people) and tables as places of demand (people), then we can see our original problem as literally sending people from families $f$ to tables $t$ so that everyone is assigned to some table, the tables' capacities are respected, and no table gets more than $k = 3$ members of the same family.\n", "\n", "An AMPL version of this model is given in the next cell. After that we will show how to reformulate the calculation using network algorithms." ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Overwriting table_seat_maximize_members_flow_to_tables.mod\n" ] } ], "source": [ "%%writefile table_seat_maximize_members_flow_to_tables.mod\n", "\n", "set F;\n", "set T;\n", "\n", "param M{F};\n", "param C{T};\n", "\n", "param k;\n", "\n", "var x{F,T} integer >= 0, <= k;\n", "\n", "maximize goal: sum{f in F, t in T} x[f, t];\n", "\n", "s.t. capacity {t in T}: sum{f in F} x[f,t] <= C[t];\n", "s.t. seat {f in F}: sum{t in T} x[f,t] == M[f];" ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n", "MILO problem\n", "\n", "cbc 2.10.7: \b\b\b\b\b\b\b\b\b\b\b\bcbc 2.10.7: optimal solution; objective 39\n", "0 simplex iterations\n", "CPU times: user 305 µs, sys: 51 µs, total: 356 µs\n", "Wall time: 17.3 ms\n", "Solve result: solved\n" ] }, { "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", "
table01234
family
012300
110313
202000
330123
433313
501000
\n", "
" ], "text/plain": [ "table 0 1 2 3 4\n", "family \n", "0 1 2 3 0 0\n", "1 1 0 3 1 3\n", "2 0 2 0 0 0\n", "3 3 0 1 2 3\n", "4 3 3 3 1 3\n", "5 0 1 0 0 0" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "objective: 39.0\n", "places at table: [8, 8, 10, 4, 9]\n", "members seated: [6, 8, 2, 9, 13, 1]\n", "\n", "Relaxed problem\n", "\n", "cbc 2.10.7: \b\b\b\b\b\b\b\b\b\b\b\bcbc 2.10.7: optimal solution; objective 39\n", "0 simplex iterations\n", "CPU times: user 398 µs, sys: 67 µs, total: 465 µs\n", "Wall time: 16 ms\n", "Solve result: solved\n" ] }, { "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", "
table01234
family
00.03.00.00.03.0
11.01.03.00.03.0
20.00.02.00.00.0
33.03.02.01.00.0
43.01.03.03.03.0
51.00.00.00.00.0
\n", "
" ], "text/plain": [ "table 0 1 2 3 4\n", "family \n", "0 0.0 3.0 0.0 0.0 3.0\n", "1 1.0 1.0 3.0 0.0 3.0\n", "2 0.0 0.0 2.0 0.0 0.0\n", "3 3.0 3.0 2.0 1.0 0.0\n", "4 3.0 1.0 3.0 3.0 3.0\n", "5 1.0 0.0 0.0 0.0 0.0" ] }, "metadata": {}, "output_type": "display_data" }, { "name": "stdout", "output_type": "stream", "text": [ "objective: 39.0\n", "places at table: [8.0, 8.0, 10.0, 4.0, 9.0]\n", "members seated: [6.0, 8.0, 2.0, 9.0, 13.0, 1.0]\n" ] } ], "source": [ "def table_seat_maximize_members_flow_to_tables(members, capacity, k, relax=False):\n", " m = AMPL()\n", " m.read(\"table_seat_maximize_members_flow_to_tables.mod\")\n", "\n", " m.set[\"F\"] = range(len(members))\n", " m.set[\"T\"] = range(len(capacity))\n", "\n", " m.param[\"M\"] = members\n", " m.param[\"C\"] = capacity\n", " m.param[\"k\"] = k\n", "\n", " m.option[\"solver\"] = SOLVER\n", "\n", " if relax:\n", " m.option[\"relax_integrality\"] = 1\n", "\n", " return m\n", "\n", "\n", "members = [6, 8, 2, 9, 13, 1]\n", "capacity = [8, 8, 10, 4, 9]\n", "k = 3\n", "\n", "print(\"\\nMILO problem\\n\")\n", "seatplan = table_seat_maximize_members_flow_to_tables(members, capacity, k)\n", "%time results = seatplan.solve()\n", "report(seatplan, results, type=int)\n", "\n", "print(\"\\nRelaxed problem\\n\")\n", "seatplan = table_seat_maximize_members_flow_to_tables(members, capacity, k, relax=True)\n", "%time results = seatplan.solve()\n", "report(seatplan, results, type=float)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "By adding two more nodes to the graph above, we can formulate the problem as a slightly different flow problem where all the data is formulated as the arc capacity, see figure below. In a network like this, we can imagine a problem of sending resources from the _root node_ \"door\" to the _sink node_ \"seat\", subject to the restriction that for any node apart from $s$ and $t$, the sum of incoming and outgoing flows are equal (_balance constraint_). If there exists a flow in this new graph that respects the arc capacities and the sum of outgoing flows at $s$ is equal to $\\sum_{f \\in F} m_f = 39$, it means that there exists a family-to-table assignment that meets our requirements.\n", "\n", "![](dina_model.png)" ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "id": "aSJ7UOokVfnu" }, "outputs": [], "source": [ "def model_as_network(members, capacity, k):\n", " # create lists of families and tables\n", " families = [f\"f{i}\" for i in range(len(members))]\n", " tables = [f\"t{j}\" for j in range(len(capacity))]\n", "\n", " # create digraphy object\n", " G = nx.DiGraph()\n", "\n", " # add edges\n", " G.add_edges_from([\"door\", f, {\"capacity\": n}] for f, n in zip(families, members))\n", " G.add_edges_from([(f, t) for f in families for t in tables], capacity=k)\n", " G.add_edges_from([t, \"seat\", {\"capacity\": n}] for t, n in zip(tables, capacity))\n", "\n", " return G" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [], "source": [ "members = [6, 8, 2, 9, 13, 1]\n", "capacity = [8, 8, 10, 4, 9]\n", "\n", "G = model_as_network(members, capacity=[8, 8, 10, 4, 9], k=3)\n", "\n", "labels = {(e[0], e[1]): e[2] for e in G.edges(data=\"capacity\")}" ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "id": "vRHT74fEV6KX" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "CPU times: user 3.37 ms, sys: 0 ns, total: 3.37 ms\n", "Wall time: 3.38 ms\n" ] } ], "source": [ "%time flow_value, flow_dict = nx.maximum_flow(G, 'door', 'seat')" ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "colab": { "base_uri": "https://localhost:8080/", "height": 206 }, "executionInfo": { "elapsed": 214, "status": "ok", "timestamp": 1643283766270, "user": { "displayName": "Joaquim Gromicho", "photoUrl": "https://lh3.googleusercontent.com/a/default-user=s64", "userId": "14375950305363805729" }, "user_tz": -60 }, "id": "JL9vgcULV-TG", "outputId": "15de4861-1a77-485e-e91f-c03f8d55a917", "tags": [] }, "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", "
f0f1f2f3f4f5
t0200231
t1011330
t2130330
t3010030
t4331110
\n", "
" ], "text/plain": [ " f0 f1 f2 f3 f4 f5\n", "t0 2 0 0 2 3 1\n", "t1 0 1 1 3 3 0\n", "t2 1 3 0 3 3 0\n", "t3 0 1 0 0 3 0\n", "t4 3 3 1 1 1 0" ] }, "execution_count": 16, "metadata": {}, "output_type": "execute_result" } ], "source": [ "families = [f\"f{i:.0f}\" for i in range(len(members))]\n", "tables = [f\"t{j:.0f}\" for j in range(len(capacity))]\n", "\n", "pd.DataFrame(flow_dict).loc[tables, families].astype(\"int\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Even for this very small example, we see that network algorithms generate a solution significantly faster." ] } ], "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.10.6" } }, "nbformat": 4, "nbformat_minor": 4 }