\n", " The following problem was formulated by Tomas C. (ND '09) who was \n", " working with the Jesuit Volunteer Corp in 2009-2010. Here was his \n", " problem:\n", "
\n", "\n", " There are 7 of us in the house. We have broken down the chores into 4 \n", " major sections: 1) Kitchen, 2) Bathroom, 3) Common Area, 4) Trash. The \n", " trash is the only task that needs only one person to accomplish, the \n", " other 3 tasks have 2 people assigned to them. Each person needs to rotate\n", " through each task twice and the trash only once. The assignments rotate \n", " each week. Each person needs to have a new partner each week and no \n", " person can have more than one task in a week.\n", "\n", "
\n", " In the formulation below we require every possible pair to do at least\n", " one task together. This is different that requiring a new partner each \n", " week, but Tomas said later that this would meet their needs.\n", "
\n", "\n", " This a challenging computation, depending\n", " on your computer this may take a few seconds to a few minutes.\n", "
\n" ] }, { "cell_type": "heading", "level": 2, "metadata": {}, "source": [ "Solution" ] }, { "cell_type": "code", "collapsed": false, "input": [ "%%script glpsol -m /dev/stdin \n", "\n", "# Example: JesuitVols.mod\n", "\n", "/* Number of weeks to schedule */\n", "param T := 7;\n", "\n", "/* Numeric labels for volunteers facilitate creating non-replicated pairs */\n", "set VOLS := 1..7;\n", "set TASKS := {'Kitchen', 'Bathroom', 'Commons', 'Trash'};\n", "set WEEKS := 1..T;\n", "\n", "/* Compute all pairs of volunteers */\n", "set PAIRS := setof{u in VOLS, v in VOLS: u < v} (u,v);\n", "\n", "/* x[v,t,w] = 1 if volunteer v is assigned task t in week w */\n", "var x{v in VOLS, t in TASKS, w in WEEKS} binary;\n", "\n", "/* p[u,v,t,w] = 1 if volunteers u and v are paired together on t in week w */\n", "var p{(u,v) in PAIRS, t in TASKS, w in WEEKS} binary;\n", "\n", "/* The objective will be the number of times anyone has to do the trash */\n", "var z integer;\n", "\n", "minimize obj: z;\n", "\n", "/* Each volunteer each week must be assigned one task */\n", "s.t. fa{v in VOLS, w in WEEKS}: sum {t in TASKS} x[v,t,w] = 1;\n", "\n", "/* Except for Trash, each task each week must be assigned two volunteers */\n", "s.t. fb{w in WEEKS}: sum {v in VOLS} x[v,'Trash',w] = 1;\n", "s.t. fc{t in TASKS, w in WEEKS : t <> 'Trash'}: sum {v in VOLS} x[v,t,w] = 2;\n", "\n", "/* Each volunteer must cycle through each task twice (except trash) */\n", "s.t. fd{t in TASKS, v in VOLS : t <> 'Trash'}: sum {w in WEEKS} x[v,t,w] >= 2;\n", "\n", "/* Minimize number of times anyone has to do trash */\n", "s.t. fz{v in VOLS}: sum {w in WEEKS} x[v,'Trash',w] <= z;\n", "\n", "/* Pair p(u,v,t,w) is 1 if u and v worked together on Week w and Task t */\n", "s.t. ga{t in TASKS, w in WEEKS, (u,v) in PAIRS}: p[u,v,t,w] <= x[u,t,w];\n", "s.t. gb{t in TASKS, w in WEEKS, (u,v) in PAIRS}: p[u,v,t,w] <= x[v,t,w];\n", "s.t. gc{t in TASKS, w in WEEKS, (u,v) in PAIRS}: \n", " p[u,v,t,w] >= x[u,t,w] + x[v,t,w] - 1;\n", "\n", "/* Each possible pair must do at least one task together. */\n", "s.t. gd{(u,v) in PAIRS}: sum{t in TASKS, w in WEEKS} p[u,v,t,w] >= 1;\n", "\n", "solve;\n", "\n", "printf \"Volunteer Assignments by Weeks\";\n", "for {w in WEEKS}{\n", " printf \"\\n\\nWeek: %2s\\n\",w;\n", " printf \"Volunteer:\";\n", " printf {v in VOLS} \"%3s\",v;\n", " for {t in TASKS}{\n", " printf \"\\n%9s:\",t;\n", " printf {v in VOLS} \"%3s\", if x[v,t,w]=1 then \"X\" else \"-\";\n", " }\n", "}\n", "\n", "printf \"\\n\\n\\n Analysis of Volunteer Pairs\";\n", "for{(u,v) in PAIRS}{\n", " printf \"\\n\\nPair: (%s,%s)\\n\",u,v;\n", " printf \" Week:\";\n", " printf {w in WEEKS} \"%3s\",w;\n", " for {t in TASKS}{\n", " printf \"\\n%9s:\",t;\n", " printf {w in WEEKS} \"%3s\", if p[u,v,t,w]=1 then \"X\" else \"-\";\n", " }\n", "}\n", "\n", "end;\n" ], "language": "python", "metadata": {}, "outputs": [ { "output_type": "stream", "stream": "stdout", "text": [ "GLPSOL: GLPK LP/MIP Solver, v4.52\n", "Parameter(s) specified in the command line:\n", " -m /dev/stdin\n", "Reading model section from /dev/stdin...\n", "/dev/stdin:72: warning: final NL missing before end of file\n", "72 lines were read\n", "Generating obj...\n", "Generating fa...\n", "Generating fb...\n", "Generating fc...\n", "Generating fd...\n", "Generating fz...\n", "Generating ga...\n", "Generating gb...\n", "Generating gc...\n", "Generating gd...\n", "Model has been successfully generated\n", "GLPK Integer Optimizer, v4.52\n", "1891 rows, 785 columns, 5300 non-zeros\n", "785 integer variables, 784 of which are binary\n", "Preprocessing...\n", "1890 rows, 785 columns, 5299 non-zeros\n", "785 integer variables, 784 of which are binary\n", "Scaling...\n", " A: min|aij| = 1.000e+00 max|aij| = 1.000e+00 ratio = 1.000e+00\n", "Problem data seem to be well scaled\n", "Constructing initial basis...\n", "Size of triangular part is 1883\n", "Solving LP relaxation...\n", "GLPK Simplex Optimizer, v4.52\n", "1890 rows, 785 columns, 5299 non-zeros\n", " 0: obj = 0.000000000e+00 infeas = 5.960e+02 (7)\n", " 500: obj = 1.000000000e+00 infeas = 2.125e+01 (7)\n", "* 717: obj = 1.000000000e+00 infeas = 2.748e-15 (7)\n", "* 718: obj = 1.000000000e+00 infeas = 3.446e-15 (7)\n", "OPTIMAL LP SOLUTION FOUND\n", "Integer optimization begins...\n", "+ 718: mip = not found yet >= -inf (1; 0)\n", "+ 17067: >>>>> 1.000000000e+00 >= 1.000000000e+00 0.0% (49; 116)\n", "+ 17067: mip = 1.000000000e+00 >= tree is empty 0.0% (0; 247)\n", "INTEGER OPTIMAL SOLUTION FOUND\n", "Time used: 3.1 secs\n", "Memory used: 4.0 Mb (4168594 bytes)\n", "Volunteer Assignments by Weeks\n", "\n", "Week: 1\n", "Volunteer: 1 2 3 4 5 6 7\n", " Kitchen: - - - X - X -\n", " Bathroom: - X X - - - -\n", " Commons: X - - - - - X\n", " Trash: - - - - X - -\n", "\n", "Week: 2\n", "Volunteer: 1 2 3 4 5 6 7\n", " Kitchen: X - - - X - -\n", " Bathroom: - - X - - - X\n", " Commons: - X - - - X -\n", " Trash: - - - X - - -\n", "\n", "Week: 3\n", "Volunteer: 1 2 3 4 5 6 7\n", " Kitchen: - - - - X - X\n", " Bathroom: X - - - - X -\n", " Commons: - - X X - - -\n", " Trash: - X - - - - -\n", "\n", "Week: 4\n", "Volunteer: 1 2 3 4 5 6 7\n", " Kitchen: - X - X - - -\n", " Bathroom: - - - - - X X\n", " Commons: - - X - X - -\n", " Trash: X - - - - - -\n", "\n", "Week: 5\n", "Volunteer: 1 2 3 4 5 6 7\n", " Kitchen: X - X - - - -\n", " Bathroom: - X - - X - -\n", " Commons: - - - X - - X\n", " Trash: - - - - - X -\n", "\n", "Week: 6\n", "Volunteer: 1 2 3 4 5 6 7\n", " Kitchen: - X - - - - X\n", " Bathroom: X - - X - - -\n", " Commons: - - - - X X -\n", " Trash: - - X - - - -\n", "\n", "Week: 7\n", "Volunteer: 1 2 3 4 5 6 7\n", " Kitchen: - - X - - X -\n", " Bathroom: - - - X X - -\n", " Commons: X X - - - - -\n", " Trash: - - - - - - X\n", "\n", "\n", " Analysis of Volunteer Pairs\n", "\n", "Pair: (1,2)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - - -\n", " Bathroom: - - - - - - -\n", " Commons: - - - - - - X\n", " Trash: - - - - - - -\n", "\n", "Pair: (1,3)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - X - -\n", " Bathroom: - - - - - - -\n", " Commons: - - - - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (1,4)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - - -\n", " Bathroom: - - - - - X -\n", " Commons: - - - - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (1,5)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - X - - - - -\n", " Bathroom: - - - - - - -\n", " Commons: - - - - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (1,6)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - - -\n", " Bathroom: - - X - - - -\n", " Commons: - - - - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (1,7)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - - -\n", " Bathroom: - - - - - - -\n", " Commons: X - - - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (2,3)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - - -\n", " Bathroom: X - - - - - -\n", " Commons: - - - - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (2,4)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - X - - -\n", " Bathroom: - - - - - - -\n", " Commons: - - - - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (2,5)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - - -\n", " Bathroom: - - - - X - -\n", " Commons: - - - - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (2,6)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - - -\n", " Bathroom: - - - - - - -\n", " Commons: - X - - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (2,7)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - X -\n", " Bathroom: - - - - - - -\n", " Commons: - - - - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (3,4)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - - -\n", " Bathroom: - - - - - - -\n", " Commons: - - X - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (3,5)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - - -\n", " Bathroom: - - - - - - -\n", " Commons: - - - X - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (3,6)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - - X\n", " Bathroom: - - - - - - -\n", " Commons: - - - - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (3,7)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - - -\n", " Bathroom: - X - - - - -\n", " Commons: - - - - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (4,5)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - - -\n", " Bathroom: - - - - - - X\n", " Commons: - - - - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (4,6)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: X - - - - - -\n", " Bathroom: - - - - - - -\n", " Commons: - - - - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (4,7)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - - -\n", " Bathroom: - - - - - - -\n", " Commons: - - - - X - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (5,6)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - - -\n", " Bathroom: - - - - - - -\n", " Commons: - - - - - X -\n", " Trash: - - - - - - -\n", "\n", "Pair: (5,7)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - X - - - -\n", " Bathroom: - - - - - - -\n", " Commons: - - - - - - -\n", " Trash: - - - - - - -\n", "\n", "Pair: (6,7)\n", " Week: 1 2 3 4 5 6 7\n", " Kitchen: - - - - - - -\n", " Bathroom: - - - X - - -\n", " Commons: - - - - - - -\n", " Trash: - - - - - - -Model has been successfully processed\n" ] } ], "prompt_number": 2 }, { "cell_type": "code", "collapsed": false, "input": [], "language": "python", "metadata": {}, "outputs": [] } ], "metadata": {} } ] }