{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "### CS/ECE/ISyE 524 — Introduction to Optimization — Spring 2018 ###\n", "\n", "# Pay Me Maybe : Settle Group Bills #\n", "\n", "#### Om Bathija (bathija@wisc.edu)\n", "\n", "*****\n", "\n", "### Table of Contents\n", "\n", "1. [Introduction](#intro)\n", " 1. [Problem Statement](#problem_statement)\n", " 1. [Problem Complexity](#problem_complexity)\n", " 1. [Data](#data)\n", "1. [Mathematical Model](#math_model)\n", "1. [Solution](#solution)\n", " 1. [Minimal Working Solution](#min_solution)\n", " 1. [Implementation](#implementation)\n", " 1. [Base Implementation](#base_implementation)\n", " 1. [Circular Transanctions](#circular)\n", " 1. [Multiple Groups](#multigroup)\n", " 1. [Determining the Upper Bound](#opti)\n", "1. [Results and Future Work](#results)\n", "1. [Interactive Mode](#interactive)\n", "1. [References](#refs)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "# 1. Introduction # \n", "\n", "\n", "## 1.1 Problem Statement ##\n", "\n", "This project draws inspiration from a specific aspect of a popular application called SplitWise. SplitWise basically helps people settle expenses among different people in a group in an efficient manner. It's easiest to understand with an example, so here's a minimal example (which we will actually get working later) : \n", "\n", "> * Bob pays \\$20 for gas, split between him and Alice. (Alice owes Bob \\$10) \n", "> * Charles pays \\\\$20 for lunch, split between him and Bob. (Bob owes Charles \\$10) \n", "\n", "How can they settle their debts? Of course, the simplest option is :\n", "\n", "> * Alice pays Bob the \\$10 she owes him \n", "> * Bob pays Charles the \\$10 he owes him.\n", "\n", "If Alice, Bob and Charles are friends (we'll say they're in the same group from here on) then of course, it's easy for us to understand that intuitively, the most effective way to settle their debts would just be : \n", "\n", "> * Alice pays Charles the \\$10 that Bob owes him.\n", "\n", "This reduces the total number of transanctions required for the group to reach a **settled state** from 2 to 1.\n", "\n", "The utility of such an application is obvious. However, what's interesting is that this problem of finding the minimum number of transanctions that will lead to a group reaching a \"settled\" state, is actually **NP-Complete**. Also, it can actually be modelled in some interesting ways, including as an **integer programming problem**! \n", "\n", "Over the course of this notebook, we will see one possible formulations of this problem, and also explore some extensions of the problem statement.\n", "\n", "\n", "## 1.2 Problem Complexity ##\n", "\n", "This seemingly straightforward problem can actually be reduced to the well known **subset-sum** problem, which is NP-Complete. \n", "\n", "The subset-sum problem is defined as follows : \n", "\n", "> *Given a set of Integers$S$, determine the existence of a non-empty subset who's elements add up to a given integer$n$*\n", "\n", "One possible transformation of our problem into the subset-sum problem is as follows : \n", "\n", "> Initialize the subset$S$with all amounts of money owed \n", "Set each integer$n$to the amount of money owed to each individual \n", "\n", "This means that finding an optimal solution to this problem for large sets of transanctions is computationally intractable, and interestingly enough, [according to the founder of the actual SplitWise app](https://www.quora.com/What-algorithm-or-solution-do-the-people-at-Splitwise-use-for-its-debt-simplification-feature) they use a greedy solution (which, as greedy algorithms often go, isn't always optimal but run in reasonable time).\n", "\n", "\n", "## 1.3 Data ##\n", "\n", "The data used in this notebook is synthetically generated by a Python script that writes to a CSV file. The CSV file is in the format : \n", "\n", "> (owed by), (owed to), (amount owed)\n", "\n", "This format was chosen because even though real transanctions most likely occur in the format : \n", "\n", "> (person who paid), (amount paid), (people splitting the expense)\n", "\n", "Transforming from that format to the one used by this notebook is simple, and therefore does not affect the modelling in any way. It would be simple to add some pre-processing to convert data between these two formats." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "# 2. Mathematical Model#\n", "\n", "To understand the integer programming problem, let's go back to our minimal example and try and solve that. \n", "\n", "We can represent the transanctions in terms of a matrix$T$such that :\n", "\n", "> each element$T_{ij}$of the matrix is the amount of money (in dollars) **person$i$owes person$j$.**\n", "\n", "Here's a quick recap of the transanctions we had, simplified down : \n", "\n", "> Alice owes Bob \\$10 \n", "> Bob owes Charles \\$10\n", "\n", "So based on our above formulation of the$T$matrix: \n", "\n", ">$T_{alice, bob} = 10$\n", ">$T_{bob, charles} = 10$\n", "\n", "For convenience, let's assign integer indices to Alice, Bob and Charles as follows : \n", "\n", "> Alice = 1 \n", "Bob = 2 \n", "Charles = 3 \n", "\n", "We can now form our$T$matrix : \n", "\n", ">$T = \\begin{bmatrix} 0 & 10 & 0 \\\\ 0 & 0 & 10 \\\\ 0 & 0 & 0 \\end{bmatrix}$\n", "\n", "Note here that$T_{i,i}$will always be zero (as you can't owe yourself any money).\n", "\n", "Similarly, we can construct a **settlement matrix$S$** which represents the optimal solution.\n", "\n", "Let's define each element of$S$, **$S_{i,j}$as they money that person$i$needs to pay person$j$** in order for all debts to be settled. In our simple case, we can construct this by observation as : \n", "\n", ">$S = \\begin{bmatrix} 0 & 0 & 10 \\\\ 0 & 0 & 0 \\\\ 0 & 0 & 0 \\end{bmatrix}$\n", "\n", "So our settlement matrix tells us that Alice must pay Charles \\$10, which is what we want. This is in some sense, our \"target\" matrix.\n", "\n", "Intepreted in a different way, our $S$ matrix is also an *alternate to our $T$ matrix*, because it's just telling us who owes who, and how much, which is exactly what the $T$ matrix too. In other words, it basically says \"Alice finally owes charles \\$10.\"\n", "\n", "***\n", "\n", "The important thing to understand here, is that **we don't really care who pays who**, as long as everyone receives or pays what they're supposed to. We can express this as : \n", "\n", "> Net Amount for person$i$= Amount owed to$i$- Amount owed by$i$\n", "\n", "How do we represent that using the matrices we've constructed? \n", "\n", "> Net amount owed by$i$=$\\sum_{j} T_{ij}$_(sum along row$i$)_ \n", "> Net amount owed to$i$=$\\sum_{j} T_{ji}$_(sum along column$i$)_\n", "\n", "Since the net amount owed to or by each person must be the same in the the$S$and$T$matrices we arrive at this important **constraint** : \n", "\n", ">$\\sum_{j} T_{ji} - \\sum_{j} T_{ij} = \\sum_{j} S_{ji} - \\sum_{j} S_{ij}$\n", "\n", "Therefore, as long as this constraint holds,$S$and$T$are basically equivalent in the manner we require.\n", "\n", "Our task has now reduced to finding a sparisified version of$T$that satisifies the above constraint!\n", "\n", "---\n", "\n", "How do we actually sparisfy$T$though? \n", "\n", "One simple way of doing this is to express this as our objective: \n", "\n", ">Minimize the number of elements of$S$that are not 0.\n", "\n", "And to do this, we can turn to integer programming, by simply using a binary indicator variable to determine if an element of$Sis zero or nonzero.\n", "\n", "Therefore, our final formulation is as follows : \n", "\n", "> \n", "\\begin{aligned}\n", "\\underset{I \\in \\mathbb{R^{n x n}}}{\\text{minimize}}\\qquad& \\sum_{i, j} I_{ij} && i,j = 1,\\dots,n \\\\\n", "\\text{subject to:}\\qquad& S_{i,j} \\ge 0 && i,j = 1,\\dots,n\\\\\n", "& S_{i,j} \\le MI_{i,j} && i,j = 1,\\dots,n\\\\\n", "& \\sum_{j} S_{ji} - \\sum_{j} S_{ij} = \\sum_{j} T_{ji} - \\sum_{j} T_{ij} && i = 1,\\dots,n\\\\\n", "\\end{aligned}\n", "\n", "\n", "whereM$is an upper-bound on the values$S_{i,j}$can take.\n", "\n", "We can now solve an MWE of our problem." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "# 3. Solution" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "## 3.1 Minimal Working Solution" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "using JuMP, NamedArrays, Cbc" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's reuse our example from above." ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3×3 Array{Int64,2}:\n", " 0 10 0\n", " 0 0 10\n", " 0 0 0" ] }, "execution_count": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "T = [0 10 0; 0 0 10; 0 0 0 ]" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ ":Optimal" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "m = Model(solver = CbcSolver())\n", "\n", "@variable(m, s[1:3, 1:3])\n", "@variable(m, indicator[1:3, 1:3], Bin)\n", "\n", "# while some possible formulations of this problem might allow \n", "# for a negative S(i,j) value in the sense that a negative \n", "# amount of money owed can be construed as money lent, but the \n", "# formulation described above does not allow for negative values of S.\n", "@constraint(m, s .>= 0)\n", "\n", "@expression(m, rowsums[i in 1:3], sum(s[i,j] for j in 1:3))\n", "@expression(m, colsums[i in 1:3], sum(s[j,i] for j in 1:3))\n", "\n", "# This is the constraint that forces equivalence between \n", "# the S matrix and the T matrix.\n", "@constraint(m, rowsumc[i in 1:3], \n", " (colsums[i] - rowsums[i]) == (sum(T[j,i] for j in 1:3) - sum(T[i,j] for j in 1:3)))\n", "\n", "# This constraint forces the indicator variables to be set to 1 \n", "# if a transanction occurs i.e. if any element of the S matrix is non-zero\n", "# we're just going to use an arbitrarily large number for the upper-bound for now\n", "# more on this later.\n", "@constraint(m, s .<= indicator*10000)\n", "\n", "@objective(m, Min, sum(indicator))\n", "\n", "status = solve(m)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's examine the value of our S matrix : " ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "3×3 Array{Float64,2}:\n", " 0.0 0.0 10.0\n", " 0.0 0.0 0.0\n", " 0.0 0.0 0.0" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "s_opt = getvalue(s)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This matches what we were expecting, which is great. Now that we have a simple working model, we can extend it to more realistic examples, with several transanctions. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "## 3.2 Implementation" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now that we have a minimum working example, let's test it out with a larger data set. \n", "\n", "\n", "### 3.2.1 Base Implementation\n", "\n", "We will use a random set of 20 transanctions among 5 people. First, let's just parse the CSV file." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "get_T_from_csv (generic function with 1 method)" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function get_T_from_csv(datafile)\n", " transanctions = []\n", " all_users = []\n", " f = open(datafile)\n", " lines = readlines(f)\n", " for line in lines\n", " owed_by, owed_to, amount = split(line, \",\")\n", " push!(transanctions, [owed_by, owed_to, parse(Int, amount)])\n", " push!(all_users, owed_by)\n", " push!(all_users, owed_to)\n", " end\n", "\n", " # Set up some variables we'll need for later\n", " unique_users = sort(unique(all_users))\n", " n = length(unique_users)\n", "\n", " # Initialize the T Matrix\n", " T = NamedArray(zeros(n,n), (unique_users, unique_users), (\"OWED BY\", \"OWED TO\"));\n", "\n", " # Fill in the T Matrix\n", " # T[i,j] => i owes j T[i,j]\n", " for transanction in transanctions\n", " owed_by, owed_to, amount = transanction\n", " T[owed_by, owed_to] = amount\n", " end\n", " \n", " return T, n, unique_users\n", "end" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "5×5 Named Array{Float64,2}\n", "OWED BY ╲ OWED TO │ \"Albert\" \"Anthony\" … \"Tyler\" \"Victoria\"\n", "──────────────────┼──────────────────────────────────────────────────────\n", "\"Albert\" │ 0.0 435.0 … 435.0 180.0\n", "\"Anthony\" │ 65.0 0.0 185.0 185.0\n", "\"Elizabeth\" │ 170.0 185.0 180.0 65.0\n", "\"Tyler\" │ 185.0 290.0 0.0 15.0\n", "\"Victoria\" │ 185.0 280.0 … 185.0 0.0\n" ] } ], "source": [ "T, n, unique_users = get_T_from_csv(\"dense.csv\")\n", "println(T)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Here, we have a total of 20 transanctions that occured. Let's examine them. " ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Albert owes Anthony$435.0\n", "Albert owes Elizabeth $65.0\n", "Albert owes Tyler$435.0\n", "Albert owes Victoria $180.0\n", "Anthony owes Albert$65.0\n", "Anthony owes Elizabeth $210.0\n", "Anthony owes Tyler$185.0\n", "Anthony owes Victoria $185.0\n", "Elizabeth owes Albert$170.0\n", "Elizabeth owes Anthony $185.0\n", "Elizabeth owes Tyler$180.0\n", "Elizabeth owes Victoria $65.0\n", "Tyler owes Albert$185.0\n", "Tyler owes Anthony $290.0\n", "Tyler owes Elizabeth$290.0\n", "Tyler owes Victoria $15.0\n", "Victoria owes Albert$185.0\n", "Victoria owes Anthony $280.0\n", "Victoria owes Elizabeth$290.0\n", "Victoria owes Tyler $185.0\n" ] } ], "source": [ "for i in unique_users\n", " for j in unique_users\n", " if T[i,j] != 0\n", " println(\"$i owes $j \\$$(T[i,j])\")\n", " end\n", " end\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Here's a graph showing us just how messy these debts are right now : \n", "\n", " " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's see how many transanctions we can reduce this down to." ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "find_S_matrix (generic function with 1 method)" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function find_S_matrix(T, n, unique_users)\n", " m = Model(solver = CbcSolver())\n", "\n", " @variable(m, s[1:n, 1:n])\n", " @variable(m, indicator[1:n, 1:n], Bin)\n", "\n", " @constraint(m, s .>= 0)\n", "\n", " @expression(m, rowsums[i in 1:n], sum(s[i,j] for j in 1:n))\n", " @expression(m, colsums[i in 1:n], sum(s[j,i] for j in 1:n))\n", "\n", " @constraint(m, rowsumc[i in 1:n], \n", " (colsums[i] - rowsums[i]) == (sum(T[j,i] for j in 1:n) - sum(T[i,j] for j in 1:n)))\n", "\n", " @constraint(m, s .<= indicator*10000)\n", "\n", " @objective(m, Min, sum(indicator))\n", "\n", " status = solve(m)\n", " println(status)\n", " \n", " s_opt = getvalue(s)\n", " S = NamedArray(s_opt, (unique_users, unique_users), (\"OWED BY\", \"OWED TO\"));\n", " return S\n", "end" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Optimal\n" ] }, { "data": { "text/plain": [ "5×5 Named Array{Float64,2}\n", "OWED BY ╲ OWED TO │ \"Albert\" \"Anthony\" … \"Tyler\" \"Victoria\"\n", "──────────────────┼──────────────────────────────────────────────────────\n", "\"Albert\" │ 0.0 255.0 … 0.0 0.0\n", "\"Anthony\" │ 0.0 0.0 0.0 0.0\n", "\"Elizabeth\" │ 0.0 0.0 0.0 0.0\n", "\"Tyler\" │ 0.0 0.0 0.0 0.0\n", "\"Victoria\" │ 0.0 290.0 … 205.0 0.0" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "S = find_S_matrix(T, n, unique_users)" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Albert owes Anthony 255.0\n", "Albert owes Elizabeth 255.0\n", "Victoria owes Anthony 290.0\n", "Victoria owes Tyler 205.0\n" ] } ], "source": [ "for i in unique_users\n", " for j in unique_users\n", " if S[i,j] != 0\n", " println(\"i owes j \\$$(S[i,j])\")\n", " #println(\"\\\"$i,$j,$(S[i,j])\\\",\")\n", " end\n", " end\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "And here's our new, simplified graph : \n", "\n", " " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Just 4 transanctions! Let's verify that this result ensures everyone is getting what they deserve." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "First, let's see what everyone's receiving (we know that this is the sum along columns) : " ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Albert => 0.0\n", "Anthony => 545.0\n", "Elizabeth => 255.0\n", "Tyler => 205.0\n", "Victoria => 0.0\n" ] } ], "source": [ "colsums = []\n", "for i in 1:n\n", " colsum = sum(S[j,i] for j in 1:n)\n", " # we'll also save the colsum for later\n", " push!(colsums, colsum)\n", " println( \"$(unique_users[i]) =>$colsum\" )\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Next, let's see what everyone's paying (sum along the rows):" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Albert => 510.0\n", "Anthony => 0.0\n", "Elizabeth => 0.0\n", "Tyler => 0.0\n", "Victoria => 495.0\n" ] } ], "source": [ "rowsums = []\n", "for i in 1:n\n", " rowsum = sum(S[i,j] for j in 1:n)\n", " push!(rowsums, rowsum)\n", " println( \"$(unique_users[i]) =>$rowsum\" )\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Finally, let's see the net amount everyone receives or gets. This is just what they're getting minus what they owe." ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Albert => -510.0\n", "Anthony => 545.0\n", "Elizabeth => 255.0\n", "Tyler => 205.0\n", "Victoria => -495.0\n" ] } ], "source": [ "net = colsums - rowsums\n", "for i in 1:n\n", " println( \"$(unique_users[i]) =>$(net[i])\" )\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "No surprises there. Let's repeat this process for the $T$ matrix we started off with. If we end up at the same thing, we know for sure that we're being fair to everyone." ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Albert => -510.0\n", "Anthony => 545.0\n", "Elizabeth => 255.0\n", "Tyler => 205.0\n", "Victoria => -495.0\n" ] } ], "source": [ "colsums = []\n", "for i in 1:n\n", " colsum = sum(T[j,i] for j in 1:n)\n", " push!(colsums, colsum)\n", "end\n", "\n", "rowsums = []\n", "for i in 1:n\n", " rowsum = sum(T[i,j] for j in 1:n)\n", " push!(rowsums, rowsum)\n", "end\n", "\n", "net = colsums - rowsums\n", "for i in 1:n\n", " println( \"$(unique_users[i]) =>$(net[i])\" )\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Great, it matches our values from the $S$ matrix. \n", "\n", "So now we know that our model works, as no one is paying more than they owe, or receiving less than they should." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "### 3.2.2 Circular Transanctions" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "An interesting case to try out would be to have many circular transanctions. \n", "\n", "Basically, something along the lines of : \n", "\n", "> Alice owes Bob \\$10 \n", "Bob owes Charles \\$10 \n", "Charles owes Dick \\$10 \n", "Dick owes Alice \\$10 \n", "\n", "We can of course tell that in this case, there's no transanctions needed as the group is already in a settled state. But let's see if our model realizes that." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's get our data first" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "(10×10 Named Array{Float64,2}\n", "OWED BY ╲ OWED TO │ \"Adam\" \"Amanda\" … \"Noah\" \"Roger\"\n", "──────────────────┼──────────────────────────────────────────────────\n", "\"Adam\" │ 0.0 0.0 … 100.0 0.0\n", "\"Amanda\" │ 0.0 0.0 0.0 0.0\n", "\"Carolyn\" │ 0.0 0.0 0.0 0.0\n", "\"Cheryl\" │ 0.0 0.0 0.0 0.0\n", "\"Jonathan\" │ 0.0 0.0 0.0 0.0\n", "\"Joshua\" │ 0.0 0.0 0.0 100.0\n", "\"Juan\" │ 100.0 0.0 0.0 0.0\n", "\"Nancy\" │ 0.0 0.0 0.0 0.0\n", "\"Noah\" │ 0.0 100.0 0.0 0.0\n", "\"Roger\" │ 0.0 0.0 … 0.0 0.0, 10, SubString{String}[\"Adam\", \"Amanda\", \"Carolyn\", \"Cheryl\", \"Jonathan\", \"Joshua\", \"Juan\", \"Nancy\", \"Noah\", \"Roger\"])" ] }, "execution_count": 17, "metadata": {}, "output_type": "execute_result" } ], "source": [ "T, n, unique_users = get_T_from_csv(\"circular.csv\")" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Adam owes Noah $100.0\n", "Amanda owes Carolyn$100.0\n", "Carolyn owes Nancy $100.0\n", "Cheryl owes Joshua$100.0\n", "Jonathan owes Juan $100.0\n", "Joshua owes Roger$100.0\n", "Juan owes Adam $100.0\n", "Nancy owes Cheryl$100.0\n", "Noah owes Amanda $100.0\n", "Roger owes Jonathan$100.0\n" ] } ], "source": [ "for i in unique_users\n", " for j in unique_users\n", " if T[i,j] != 0\n", " println(\"$i owes$j \\$$(T[i,j])\")\n", " end\n", " end\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "If we were to graph these, it becomes clear why I keep calling them \"circular transanctions\" : \n", "\n", " " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's give them to our solver and see what it comes up with." ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Optimal\n" ] } ], "source": [ "S = find_S_matrix(T, n, unique_users);" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "10×10 Array{Float64,2}:\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0\n", " 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0" ] }, "execution_count": 20, "metadata": {}, "output_type": "execute_result" } ], "source": [ "S.array" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It works as we expected it to. Now we can get more complex." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "### 3.2.3 Multiple Groups" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### 3.2.3.1 Motivation\n", "\n", "In a more realistic situation, there isn't going to be just one group of people on the app. There are going to exist multiple groups. Let's define what a group is exactly : \n", "\n", "* A user can belong to multiple groups. \n", "* An input transanction will only occur among members of one group.\n", "* A settlement transanction can be across groups only if it's between two people who belong to both groups.\n", "* The contrapositive to the above is that if money is flowing between two people, they must belong to at least one group together.\n", "\n", "Here's a simple example to illustrate why this is important : \n", "\n", "**Example 1**\n", "\n", "**Group 1** (Alice, Bob and Charles)\n", ">Alice owes Bob \\10 \n", ">Bob owes Charles \\10\n", "\n", "**Group 2** (Alice, Dick, and Charles)\n", ">Charles owes Dick \\20 \n", ">Dick owes Alice \\20\n", "\n", "If we just treated them as individual groups, we'd end up with these 2 transanctions to stabilize each group :\n", "\n", "> Alice owes Charles \\10 \n", "> Charles owes Alice \\20\n", "\n", "Whereas what we really want is : \n", "\n", "> Charles owes Alice \\10\n", "\n", "---\n", "\n", "So how do we approach this problem? We definitely can't combine everything into one big T matrix. Consider the following example to understand why : \n", "\n", "**Example 2**\n", "\n", "**Group 1** (Alice, Bob and Charles)\n", ">Alice owes Bob \\10 \n", ">Bob owes Charles \\10\n", "\n", "**Group 2** (Dick and Charles)\n", ">Charles owes Dick \\10 \n", "\n", "Here, we _wouldn't_ want to end up with an answer that looks like : \n", "\n", ">Alice owes Dick \\10\n", "\n", "Because Alice and Dick aren't in the same group together. This time, we do want our solver to give us two separate transanctions that respect the group structuring. Or in other words : \n", "\n", ">Alice owes Charles \\10 \n", ">Charles owes Dick \\10" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "#### 3.2.3.2 Implementation\n", "\n", "It turns out, all we have to do is tell our solver who money can't move between. This is just an additional (set of) constraints that we need to derive based on the group information." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "But first off, we need this group information, which we will generate another CSV file for, in the format : \n", "\n", "> Group Number, User1, User2...\n", "\n", "For simplicity, we will assume the group numbers start at 1 and increase by 1 with each line. \n", "\n", "Let's parse our group information CSV file." ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [], "source": [ "function get_group_info(groupfile)\n", " groups = []\n", " all_users = []\n", " f = open(groupfile)\n", " lines = readlines(f)\n", " for line in lines\n", " this_group = split(line, \",\")\n", " users_only = this_group[2:end]\n", " push!(groups, users_only)\n", " for user in users_only\n", " push!(all_users, user)\n", " end\n", " end\n", " return groups, sort(unique(all_users))\n", "end\n", "\n", "groups, unique_users = get_group_info(\"groups.csv\");" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Here's our groups : " ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Group 1 : \n", "Alice, Bob, Charles, Evan, \n", "\n", "Group 2 : \n", "Charles, Dick, Ron, Alice, \n", "\n", "Group 3 : \n", "Evan, Dick, Ingrid, \n", "\n" ] } ], "source": [ "group_number = 1\n", "for group in groups\n", " println(\"Group group_number : \")\n", " for name in group\n", " print(\"name, \")\n", " end\n", " println(\"\\n\")\n", " group_number+=1\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now, we need to construct a list of disallowed transanctions. This is basically a list of (user1, user2) pairs that money cannot flow between. Basically, if two users are never in the same group, then money can't flow between them." ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [], "source": [ "function get_disallowed_transanctions(groups, unique_users)\n", " disallowed = []\n", " n = length(unique_users)\n", " for i in 1:n-1\n", " for j in i:n\n", " first_user = unique_users[i]\n", " second_user = unique_users[j]\n", " allowed = false\n", " for k in 1:3\n", " is_first_in_group_k = first_user in groups[k]\n", " is_second_in_group_k = second_user in groups[k]\n", " are_both_in_group_k = is_first_in_group_k & is_second_in_group_k\n", " if are_both_in_group_k\n", " allowed=true\n", " # no need to check the other groups as \n", " # we found at least one group in common they share\n", " break \n", " end\n", " end\n", " if allowed == false\n", " # money can't flow in either direction\n", " # for disallowed users\n", " push!(disallowed, (i,j))\n", " push!(disallowed, (j,i))\n", " end\n", " end\n", " end\n", " return disallowed\n", "end\n", "\n", "disallowed_transanctions = get_disallowed_transanctions(groups, unique_users);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now that we have that, let's load up their transanctions as usual. The trasnanction file has the same structure as before." ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [], "source": [ "T, n, unique_users = get_T_from_csv(\"group_transanctions.csv\");" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We need to change our model to include the additional constraint that now, money can't flow between certain people." ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [], "source": [ "function find_S_matrix_grouped(T, n, unique_users)\n", " m = Model(solver = CbcSolver())\n", "\n", " # first, all the same variables and constraints as before.\n", " @variable(m, s[1:n, 1:n])\n", " @variable(m, indicator[1:n, 1:n], Bin)\n", "\n", " @constraint(m, s .>= 0)\n", "\n", " @expression(m, rowsums[i in 1:n], sum(s[i,j] for j in 1:n))\n", " @expression(m, colsums[i in 1:n], sum(s[j,i] for j in 1:n))\n", "\n", " @constraint(m, rowsumc[i in 1:n], \n", " (colsums[i] - rowsums[i]) == (sum(T[j,i] for j in 1:n) - sum(T[i,j] for j in 1:n)))\n", "\n", " @constraint(m, s .<= indicator*10000)\n", " \n", " # and now, the additional constraint of disallowed transanctions\n", " for user_tuple in disallowed_transanctions\n", " # we can actually define a constraint either on indicator, or S itself.\n", " i = user_tuple\n", " j = user_tuple\n", " @constraint(m, s[i,j] == 0)\n", " end\n", " \n", " # objective doesn't change either\n", " @objective(m, Min, sum(indicator))\n", "\n", " status = solve(m)\n", " println(status)\n", " \n", " s_opt = getvalue(s)\n", " S = NamedArray(s_opt, (unique_users, unique_users), (\"OWED BY\", \"OWED TO\"));\n", " return S\n", "end;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's run this updated model." ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Optimal\n" ] } ], "source": [ "S = find_S_matrix_grouped(T, n, unique_users);" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Charles owes Alice 350.0\n", "Charles owes Ron 215.0\n", "Evan owes Alice 205.0\n", "Evan owes Bob 80.0\n", "Evan owes Dick 230.0\n", "Ingrid owes Dick 300.0\n" ] } ], "source": [ "for i in unique_users\n", " for j in unique_users\n", " if S[i,j] != 0\n", " println(\"i owes j \\$$(S[i,j])\")\n", " end\n", " end\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "If we examine the results, we can actually see that none of the transanctions occur between two people who are never in the same group at least once. This is exactly what we wanted. Here's the groups again just so you can look for yourself : " ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Group 1 : \n", "Alice, Bob, Charles, Evan, \n", "\n", "Group 2 : \n", "Charles, Dick, Ron, Alice, \n", "\n", "Group 3 : \n", "Evan, Dick, Ingrid, \n", "\n" ] } ], "source": [ "group_number = 1\n", "for group in groups\n", " println(\"Group $group_number : \")\n", " for name in group\n", " print(\"$name, \")\n", " end\n", " println(\"\\n\")\n", " group_number+=1\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's re-run this for the example we constructed by hand above, and compare it against our earlier model\n", "\n", "Just to recap, here's the earlier example : \n", "\n", "**Group 1** (Alice, Bob and Charles)\n", ">Alice owes Bob \\$10 \n", ">Bob owes Charles \\$10\n", "\n", "**Group 2** (Dick and Charles)\n", ">Charles owes Dick \\$10 " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let's set up the$T$and disallowed_transanction matrices manually." ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [], "source": [ "T = [\n", " 0 10 0 0;\n", " 0 0 10 0;\n", " 0 0 0 10;\n", " 0 0 0 0;\n", "];\n", "\n", "unique_users = [\"Alice\", \"Bob\", \"Charles\", \"Dick\"]\n", "n = 4\n", "\n", "# Dick can't transanct with either Bob or Alice\n", "disallowed_transanctions = [\n", " (1,4)\n", " (4,1)\n", " (2,4)\n", " (4,2)\n", "];" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Optimal\n", "Alice owes Charles$10.0\n", "Charles owes Dick $10.0\n" ] } ], "source": [ "S = find_S_matrix_grouped(T, n, unique_users)\n", "for i in unique_users\n", " for j in unique_users\n", " if S[i,j] != 0\n", " println(\"$i owes $j \\$$(S[i,j])\")\n", " end\n", " end\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This is what we expected, but now let's just compare it to what we would get if we just used our earlier solver." ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Optimal\n", "Alice owes Dick 10.0\n" ] } ], "source": [ "S = find_S_matrix(T, n, unique_users)\n", "for i in unique_users\n", " for j in unique_users\n", " if S[i,j] != 0\n", " println(\"i owes j \\$$(S[i,j])\")\n", " end\n", " end\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Of course, it doesn't know anything about groups, so it just (wrongly) suggests Alice should pay Dick." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "### 3.3 Determining the Upper Bound" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Till now, we've been using an arbitrarily large value for the upper bound on the problem, but we can actually determine this by just looking at the raw transanctions. \n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The upper bound in our case is essentially the largest single transanction that could occur in the settlement phase. \n", "\n", "This can also be thought of as the maximum amount of money that a single person has to receive. We don't have to worry about the maximum amount of money a single person owes, because even if it's greater than the maximum someone has to receive, that particular value will never occur in the settlement phase because the amount owed would be split between at least two people." ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "find_upper_bound (generic function with 1 method)" ] }, "execution_count": 34, "metadata": {}, "output_type": "execute_result" } ], "source": [ "function find_upper_bound(T, n)\n", " colsums = []\n", " for i in 1:n\n", " colsum = sum(T[j,i] for j in 1:n)\n", " push!(colsums, colsum)\n", " end\n", " return maximum(colsums)\n", "end" ] }, { "cell_type": "code", "execution_count": 35, "metadata": {}, "outputs": [], "source": [ "T, n, unique_users = get_T_from_csv(\"dense.csv\");" ] }, { "cell_type": "code", "execution_count": 36, "metadata": {}, "outputs": [ { "data": { "text/html": [ "1190.0" ], "text/plain": [ "1190.0" ] }, "execution_count": 36, "metadata": {}, "output_type": "execute_result" } ], "source": [ "find_upper_bound(T, n)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "It's trivial to integrate this reasonining into our function that actually solves the problem, so for brevity, it's not done here." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "## 4. Results and Future Work ##\n", "\n", "So we looked at how we can use integer programming in order to simplify debts across multiple groups. This can make a big difference in the number of transnactions required to get to a settled state. \n", "\n", "There's many different aspects of this problem that can be explored further : \n", "\n", "* **Are there other, simpler methods of modelling this problem?** The number of variables we use is of the order$n^2$for every$n$users. Therefore this approach will not scale to hundreds or thousands of transanctions. I had initially explored the possibility of modelling this as a flow problem, which would simplify the model greatly. I think this is something definitely worth purusing. \n", "\n", "\n", "* **Zero diagonal.** One of the characteristics of the problem we could make use of is the fact that the main diagonal of both the$T$and$S$matrix have to always be zero. This would require changing the model quite a bit, but it would reduce the problem to requiring *n(n-1)* variables, which on paper doesn't seem like a big difference, but it can make a difference for large values for$n$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "## 5. Interactive Mode ##\n", "\n", "Do you have debts you need simplified? Go ahead and put your transanctions in and run the cell after that to find the quickest way to get to a settled state with your friends!" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [], "source": [ "my_transanctions = [\n", " # format : \"owed by,owed to,amount\",\n", " # don't forget the , at the end\n", " # sample : \n", " \"Tony,Bob,10\",\n", "];" ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Optimal\n", "Tony owes Bob$10.0\n" ] } ], "source": [ "function get_T_manual()\n", " transanctions = []\n", " all_users = []\n", " lines = my_transanctions\n", " for line in lines\n", " owed_by, owed_to, amount = split(line, \",\")\n", " push!(transanctions, [owed_by, owed_to, parse(Int, amount)])\n", " push!(all_users, owed_by)\n", " push!(all_users, owed_to)\n", " end\n", " unique_users = sort(unique(all_users))\n", " n = length(unique_users)\n", " T = NamedArray(zeros(n,n), (unique_users, unique_users), (\"OWED BY\", \"OWED TO\"));\n", " for transanction in transanctions\n", " owed_by, owed_to, amount = transanction\n", " T[owed_by, owed_to] = amount\n", " end \n", " return T, n, unique_users\n", "end\n", "T, n, unique_users = get_T_manual()\n", "S = find_S_matrix(T, n, unique_users)\n", "for i in unique_users\n", " for j in unique_users\n", " if S[i,j] != 0\n", " println(\"$i owes$j \\(S[i,j])\")\n", " #println(\"\\\"$i,$j,\$(S[i,j])\\\",\")\n", " end\n", " end\n", "end" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "# 6. References" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "* http://publications.lib.chalmers.se/records/fulltext/218949/218949.pdf\n", "* https://www.juliabloggers.com/solving-the-group-expenses-headache-with-graphs/\n", "* https://www.alexirpan.com/2016/05/10/may-10.html\n", "* https://miguelbiron.github.io/2018/02/09/simplifying-payments-with-linear-programming/" ] } ], "metadata": { "kernelspec": { "display_name": "Julia 0.6.4", "language": "julia", "name": "julia-0.6" }, "language_info": { "file_extension": ".jl", "mimetype": "application/julia", "name": "julia", "version": "0.6.4" } }, "nbformat": 4, "nbformat_minor": 2 }