Skip to content

Instantly share code, notes, and snippets.

@oxinabox

oxinabox/convexbased.ipynb

Created May 18, 2020 20:55
Show Gist options
  • Save oxinabox/124dd3160ff970ec202283cf564524fc to your computer and use it in GitHub Desktop.
Save oxinabox/124dd3160ff970ec202283cf564524fc to your computer and use it in GitHub Desktop.
Download ZIP
Autoschedualling
Display the source blob
Display the rendered blob
Raw
convexbased.ipynb
{
"cells": [
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\u001b[32m\u001b[1m Status\u001b[22m\u001b[39m `~/Documents/JuliaEnvs/JuliaConProgramming2018/Project.toml`\n",
" \u001b[90m [9961bab8]\u001b[39m\u001b[92m + Cbc v0.4.4\u001b[39m\n",
" \u001b[90m [f65535da]\u001b[39m\u001b[92m + Convex v0.10.1\u001b[39m\n",
" \u001b[90m [31c24e10]\u001b[39m\u001b[92m + Distributions v0.16.4\u001b[39m\n",
" \u001b[90m [3c7084bd]\u001b[39m\u001b[92m + GLPKMathProgInterface v0.4.4\u001b[39m\n",
"\u001b[32m\u001b[1m Status\u001b[22m\u001b[39m `~/Documents/JuliaEnvs/JuliaConProgramming2018/Manifest.toml`\n",
" \u001b[90m [7d9fca2a]\u001b[39m\u001b[92m + Arpack v0.3.0\u001b[39m\n",
" \u001b[90m [9e28174c]\u001b[39m\u001b[92m + BinDeps v0.8.10\u001b[39m\n",
" \u001b[90m [b99e7846]\u001b[39m\u001b[92m + BinaryProvider v0.5.3\u001b[39m\n",
" \u001b[90m [e1450e63]\u001b[39m\u001b[92m + BufferedStreams v1.0.0\u001b[39m\n",
" \u001b[90m [34da2185]\u001b[39m\u001b[92m + Compat v1.4.0\u001b[39m\n",
" \u001b[90m [864edb3b]\u001b[39m\u001b[92m + DataStructures v0.14.0\u001b[39m\n",
" \u001b[90m [60bf3e95]\u001b[39m\u001b[92m + GLPK v0.9.1\u001b[39m\n",
" \u001b[90m [0862f596]\u001b[39m\u001b[92m + HTTPClient v0.2.1\u001b[39m\n",
" \u001b[90m [d9be37ee]\u001b[39m\u001b[92m + Homebrew v0.7.0\u001b[39m\n",
" \u001b[90m [682c06a0]\u001b[39m\u001b[92m + JSON v0.20.0\u001b[39m\n",
" \u001b[90m [b27032c2]\u001b[39m\u001b[92m + LibCURL v0.4.1\u001b[39m\n",
" \u001b[90m [522f3ed2]\u001b[39m\u001b[92m + LibExpat v0.5.0\u001b[39m\n",
" \u001b[90m [2ec943e9]\u001b[39m\u001b[92m + Libz v1.0.0\u001b[39m\n",
" \u001b[90m [f8899e07]\u001b[39m\u001b[92m + LinQuadOptInterface v0.6.0\u001b[39m\n",
" \u001b[90m [b8f27783]\u001b[39m\u001b[92m + MathOptInterface v0.8.0\u001b[39m\n",
" \u001b[90m [fdba3010]\u001b[39m\u001b[92m + MathProgBase v0.7.7\u001b[39m\n",
" \u001b[90m [e1d29d7a]\u001b[39m\u001b[92m + Missings v0.3.1\u001b[39m\n",
" \u001b[90m [bac558e1]\u001b[39m\u001b[92m + OrderedCollections v1.0.2\u001b[39m\n",
" \u001b[90m [90014a1f]\u001b[39m\u001b[92m + PDMats v0.9.6\u001b[39m\n",
" \u001b[90m [1fd47b50]\u001b[39m\u001b[92m + QuadGK v2.0.3\u001b[39m\n",
" \u001b[90m [79098fc4]\u001b[39m\u001b[92m + Rmath v0.5.0\u001b[39m\n",
" \u001b[90m [a2af1166]\u001b[39m\u001b[92m + SortingAlgorithms v0.3.1\u001b[39m\n",
" \u001b[90m [276daf66]\u001b[39m\u001b[92m + SpecialFunctions v0.7.2\u001b[39m\n",
" \u001b[90m [2913bbd2]\u001b[39m\u001b[92m + StatsBase v0.27.0\u001b[39m\n",
" \u001b[90m [4c63d2b9]\u001b[39m\u001b[92m + StatsFuns v0.7.0\u001b[39m\n",
" \u001b[90m [30578b45]\u001b[39m\u001b[92m + URIParser v0.4.0\u001b[39m\n",
" \u001b[90m [c17dfb99]\u001b[39m\u001b[92m + WinRPM v0.4.2\u001b[39m\n",
" \u001b[90m [2a0f44e3]\u001b[39m\u001b[92m + Base64 \u001b[39m\n",
" \u001b[90m [ade2ca70]\u001b[39m\u001b[92m + Dates \u001b[39m\n",
" \u001b[90m [8bb1440f]\u001b[39m\u001b[92m + DelimitedFiles \u001b[39m\n",
" \u001b[90m [8ba89e20]\u001b[39m\u001b[92m + Distributed \u001b[39m\n",
" \u001b[90m [b77e0a4c]\u001b[39m\u001b[92m + InteractiveUtils \u001b[39m\n",
" \u001b[90m [76f85450]\u001b[39m\u001b[92m + LibGit2 \u001b[39m\n",
" \u001b[90m [8f399da3]\u001b[39m\u001b[92m + Libdl \u001b[39m\n",
" \u001b[90m [37e2e46d]\u001b[39m\u001b[92m + LinearAlgebra \u001b[39m\n",
" \u001b[90m [56ddb016]\u001b[39m\u001b[92m + Logging \u001b[39m\n",
" \u001b[90m [d6f4376e]\u001b[39m\u001b[92m + Markdown \u001b[39m\n",
" \u001b[90m [a63ad114]\u001b[39m\u001b[92m + Mmap \u001b[39m\n",
" \u001b[90m [44cfe95a]\u001b[39m\u001b[92m + Pkg \u001b[39m\n",
" \u001b[90m [de0858da]\u001b[39m\u001b[92m + Printf \u001b[39m\n",
" \u001b[90m [3fa0cd96]\u001b[39m\u001b[92m + REPL \u001b[39m\n",
" \u001b[90m [9a3f8284]\u001b[39m\u001b[92m + Random \u001b[39m\n",
" \u001b[90m [ea8e919c]\u001b[39m\u001b[92m + SHA \u001b[39m\n",
" \u001b[90m [9e88b42a]\u001b[39m\u001b[92m + Serialization \u001b[39m\n",
" \u001b[90m [1a1011a3]\u001b[39m\u001b[92m + SharedArrays \u001b[39m\n",
" \u001b[90m [6462fe0b]\u001b[39m\u001b[92m + Sockets \u001b[39m\n",
" \u001b[90m [2f01184e]\u001b[39m\u001b[92m + SparseArrays \u001b[39m\n",
" \u001b[90m [10745b16]\u001b[39m\u001b[92m + Statistics \u001b[39m\n",
" \u001b[90m [4607b0f0]\u001b[39m\u001b[92m + SuiteSparse \u001b[39m\n",
" \u001b[90m [8dfed614]\u001b[39m\u001b[92m + Test \u001b[39m\n",
" \u001b[90m [cf7118a7]\u001b[39m\u001b[92m + UUIDs \u001b[39m\n",
" \u001b[90m [4ec0a83e]\u001b[39m\u001b[92m + Unicode \u001b[39m\n"
]
}
],
"source": [
"using Pkg: @pkg_str\n",
"pkg\"activate .\"\n",
"pkg\"status\""
]
},
{
"cell_type": "code",
"execution_count": 16,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"4 methods for generic function <b>ConicModel</b>:<ul><li> ConicModel(s::<b>CbcSolver</b>) in Cbc.CbcMathProgSolverInterface at <a href=\"file:///Users/oxinabox/.julia/packages/Cbc/vXG4G/src/MPB_wrapper.jl\" target=\"_blank\">/Users/oxinabox/.julia/packages/Cbc/vXG4G/src/MPB_wrapper.jl:35</a></li> <li> ConicModel(::<b>Int64</b>) in MathProgBase.SolverInterface at <a href=\"file:///Users/oxinabox/.julia/packages/MathProgBase/rVlFR/src/SolverInterface/SolverInterface.jl\" target=\"_blank\">/Users/oxinabox/.julia/packages/MathProgBase/rVlFR/src/SolverInterface/SolverInterface.jl:29</a></li> <li> ConicModel() in MathProgBase.SolverInterface at <a href=\"file:///Users/oxinabox/.julia/packages/MathProgBase/rVlFR/src/SolverInterface/SolverInterface.jl\" target=\"_blank\">/Users/oxinabox/.julia/packages/MathProgBase/rVlFR/src/SolverInterface/SolverInterface.jl:27</a></li> <li> ConicModel(s::<b>Union{GLPKSolverLP, GLPKSolverMIP}</b>) in GLPKMathProgInterface at <a href=\"file:///Users/oxinabox/.julia/packages/GLPKMathProgInterface/8q6jt/src/GLPKMathProgInterface.jl\" target=\"_blank\">/Users/oxinabox/.julia/packages/GLPKMathProgInterface/8q6jt/src/GLPKMathProgInterface.jl:19</a></li> </ul>"
],
"text/plain": [
"# 4 methods for generic function \"ConicModel\":\n",
"[1] ConicModel(s::CbcSolver) in Cbc.CbcMathProgSolverInterface at /Users/oxinabox/.julia/packages/Cbc/vXG4G/src/MPB_wrapper.jl:35\n",
"[2] ConicModel(::Int64) in MathProgBase.SolverInterface at /Users/oxinabox/.julia/packages/MathProgBase/rVlFR/src/SolverInterface/SolverInterface.jl:29\n",
"[3] ConicModel() in MathProgBase.SolverInterface at /Users/oxinabox/.julia/packages/MathProgBase/rVlFR/src/SolverInterface/SolverInterface.jl:27\n",
"[4] ConicModel(s::Union{GLPKSolverLP, GLPKSolverMIP}) in GLPKMathProgInterface at /Users/oxinabox/.julia/packages/GLPKMathProgInterface/8q6jt/src/GLPKMathProgInterface.jl:19"
]
},
"execution_count": 16,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"using Convex\n",
"using GLPKMathProgInterface\n",
"using Cbc\n",
"\n",
"using Random\n",
"\n",
"Convex.MathProgBase.ConicModel |> methods"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Setup the program\n",
" - `num_rooms` how many rooms\n",
" - `timeslots` is a list of all time slots\n",
" - `progam_items` is a list of all program items\n",
" - `people_votes` is a list of voting slips, where a voting slip is a list of things people are interested in."
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1:96"
]
},
"execution_count": 3,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"num_rooms = 4\n",
"timeslots = 1:8*3\n",
"\n",
"program_items = 1:(4*8*3)"
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {},
"outputs": [],
"source": [
"num_voters = 250\n",
"max_votes = 24\n",
"\n",
"people_votes = [rand(program_items, rand(1:max_votes)) for _ in 1:num_voters];"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# MIP Model\n",
"## Variables\n",
"\n",
"We have 1 varaiable, it is `A`.\n",
"It represents allocations.\n",
"It is a Boolean 3D array.\n",
"Where each cell is a particular room, timeslot and program item.\n",
"and a 1 indicates that at that room, in that time slot, that program item will occur."
]
},
{
"cell_type": "code",
"execution_count": 5,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"(24, 96)"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"A = Variable((length(timeslots), length(program_items)), :Int)\n",
"size(A)"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Objective\n",
"\n",
"We want to minimize the number of items that people voted to see that occur at the same time."
]
},
{
"cell_type": "code",
"execution_count": 44,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"count_clashes (generic function with 1 method)"
]
},
"execution_count": 44,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"function count_clashes(A, people_votes)\n",
" num_clashes = 0\n",
" for vote_slip in people_votes\n",
" for timeslot in timeslots\n",
" items_in_slot = sum(A[timeslot, vote_slip])\n",
" num_clashes += max(items_in_slot-1, 0) # Having 1 item is same as having none.\n",
" end\n",
" end;\n",
" return num_clashes\n",
"end\n",
"m = minimize(count_clashes(A, people_votes))"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Constraints\n",
" \n",
" - An item occurs or does not occurt. A is binary.\n",
" - Every program item must occur\n",
" - Never program more items in an hour than we have rooms for"
]
},
{
"cell_type": "code",
"execution_count": 7,
"metadata": {},
"outputs": [],
"source": [
"for x in A\n",
" # Negative items would break the model\n",
" m.constraints += 0 <= x\n",
" \n",
" # The below constraint to only use a 1 to make it occuring is redundant, since it will be minimized down to that\n",
" # But adding it makes things faster\n",
" m.constraints += x <=1\n",
"end\n",
"\n",
"for program_item in program_items\n",
" # Every program item must occur exactly once\n",
" m.constraints += sum(A[:,program_item]) == 1\n",
"end\n",
"\n",
"\n",
"for timeslot in timeslots\n",
" # In any given time slot at most there are a number of items equal to the number of rooms.\n",
" m.constraints += sum(A[timeslot, :]) <= num_rooms\n",
"end\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Solution\n",
"\n",
" - Column 1 is the timeslot ID\n",
" - Column 2 is the program item ID"
]
},
{
"cell_type": "code",
"execution_count": 8,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"CbcSolver(Base.Iterators.Pairs(:threads=>8,:logLevel=>1,:seconds=>7200))"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"solver = CbcSolver(; threads=8, logLevel=1, seconds=2*60*60)"
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Cgl0003I 0 fixed, 0 tightened bounds, 24 strengthened rows, 0 substitutions\n",
"Cgl0003I 0 fixed, 0 tightened bounds, 23 strengthened rows, 0 substitutions\n",
"Cgl0003I 0 fixed, 0 tightened bounds, 23 strengthened rows, 0 substitutions\n",
"Cgl0003I 0 fixed, 0 tightened bounds, 23 strengthened rows, 0 substitutions\n",
"Cgl0003I 0 fixed, 0 tightened bounds, 23 strengthened rows, 0 substitutions\n",
"Cgl0003I 0 fixed, 0 tightened bounds, 23 strengthened rows, 0 substitutions\n",
"Cgl0003I 0 fixed, 0 tightened bounds, 23 strengthened rows, 0 substitutions\n",
"Cgl0003I 0 fixed, 0 tightened bounds, 23 strengthened rows, 0 substitutions\n",
"Cgl0003I 0 fixed, 0 tightened bounds, 23 strengthened rows, 0 substitutions\n",
"Cgl0004I processed model has 5952 rows, 8136 columns (2304 integer (2303 of which binary)) and 79767 elements\n",
"Cutoff increment increased from 1e-05 to 0.9999\n",
"Cbc0038I Initial state - 1151 integers unsatisfied sum - 96.2673\n",
"Cbc0038I Pass 1: (38.02 seconds) suminf. 0.00000 (0) obj. 813 iterations 10079\n",
"Cbc0038I Solution found of 813\n",
"Cbc0038I Relaxing continuous gives 813\n",
"Cbc0038I Cleaned solution of 813\n",
"Cbc0038I Before mini branch and bound, 1105 integers at bound fixed and 5188 continuous\n",
"Cbc0038I Full problem 5952 rows 8136 columns, reduced to 5477 rows 1834 columns - 28 fixed gives 1949, 861 - ok now\n",
"Cbc0038I Full problem 5952 rows 8136 columns, reduced to 0 rows 0 columns\n",
"Cbc0038I Mini branch and bound did not improve solution (43.81 seconds)\n",
"Cbc0038I Round again with cutoff of 730.8\n",
"Cbc0038I Pass 2: (47.60 seconds) suminf. 23.15325 (71) obj. 730.8 iterations 437\n",
"Cbc0038I Pass 3: (49.83 seconds) suminf. 9.27562 (37) obj. 730.8 iterations 11286\n",
"Cbc0038I Pass 4: (51.85 seconds) suminf. 9.09512 (42) obj. 730.8 iterations 6651\n",
"Cbc0038I Pass 5: (56.09 seconds) suminf. 7.43333 (25) obj. 730.8 iterations 16301\n",
"Cbc0038I No solution found this major pass\n",
"Cbc0038I After 56.09 seconds - Feasibility pump exiting with objective of 813 - took 21.81 seconds\n",
"Cbc0012I Integer solution of 813 found by feasibility pump after 0 iterations and 0 nodes (56.10 seconds)\n",
"Cbc0038I Full problem 5952 rows 8136 columns, reduced to 5506 rows 6585 columns - 95 fixed gives 14, 14 - ok now\n",
"Cbc0031I 2928 added rows had average density of 3.5751366\n",
"Cbc0013I At root node, 2928 cuts changed objective from 0 to 227.45843 in 20 passes\n",
"Cbc0014I Cut generator 0 (Probing) - 5835 row cuts average 2.0 elements, 1 column cuts (1210 active) in 1.812 seconds - new frequency is 1\n",
"Cbc0014I Cut generator 1 (Gomory) - 369 row cuts average 244.6 elements, 0 column cuts (0 active) in 3.355 seconds - new frequency is -100\n",
"Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.396 seconds - new frequency is -100\n",
"Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.041 seconds - new frequency is -100\n",
"Cbc0014I Cut generator 4 (MixedIntegerRounding2) - 4962 row cuts average 2.6 elements, 0 column cuts (0 active) in 0.232 seconds - new frequency is 1\n",
"Cbc0014I Cut generator 5 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.332 seconds - new frequency is -100\n",
"Cbc0014I Cut generator 6 (TwoMirCuts) - 2304 row cuts average 15.7 elements, 0 column cuts (0 active) in 1.201 seconds - new frequency is 1\n",
"Cbc0010I After 0 nodes, 1 on tree, 813 best solution, best possible 227.45843 (800.68 seconds)\n",
"Cbc0010I After 100 nodes, 55 on tree, 813 best solution, best possible 227.46805 (2037.04 seconds)\n",
"Cbc0010I After 200 nodes, 110 on tree, 813 best solution, best possible 227.46805 (2536.89 seconds)\n",
"Cbc0010I After 300 nodes, 159 on tree, 813 best solution, best possible 227.46805 (2998.02 seconds)\n",
"Cbc0010I After 400 nodes, 209 on tree, 813 best solution, best possible 227.46805 (3484.29 seconds)\n",
"Cbc0010I After 500 nodes, 262 on tree, 813 best solution, best possible 227.46805 (3901.25 seconds)\n",
"Cbc0010I After 600 nodes, 313 on tree, 813 best solution, best possible 227.46805 (4382.15 seconds)\n",
"Cbc0010I After 700 nodes, 366 on tree, 813 best solution, best possible 227.46805 (4776.11 seconds)\n",
"Cbc0010I After 800 nodes, 415 on tree, 813 best solution, best possible 227.46805 (5207.82 seconds)\n",
"Cbc0010I After 900 nodes, 463 on tree, 813 best solution, best possible 227.46805 (5607.62 seconds)\n",
"Cbc0010I After 1000 nodes, 515 on tree, 813 best solution, best possible 227.46805 (6014.31 seconds)\n",
"Cbc0010I After 1100 nodes, 567 on tree, 813 best solution, best possible 227.46805 (6439.70 seconds)\n",
"Cbc0010I After 1200 nodes, 616 on tree, 813 best solution, best possible 227.46805 (6818.21 seconds)\n",
"1726.504320 seconds (28.68 M allocations: 30.669 GiB, 0.24% gc time)\n",
"Cbc0030I Thread 0 used 158 times, waiting to start 1.1648672, 839 locks, 0.24251294 locked, 0.00016546249 waiting for locks\n",
"Cbc0030I Thread 1 used 185 times, waiting to start 23.130435, 966 locks, 0.302356 locked, 0.0047955513 waiting for locks\n",
"Cbc0030I Thread 2 used 166 times, waiting to start 28.028183, 866 locks, 0.26084423 locked, 0.0015280247 waiting for locks\n",
"Cbc0030I Thread 3 used 159 times, waiting to start 32.415466, 825 locks, 0.25484896 locked, 0.0022418499 waiting for locks\n",
"Cbc0030I Thread 4 used 160 times, waiting to start 34.023923, 833 locks, 0.2451961 locked, 0.00072360039 waiting for locks\n",
"Cbc0030I Thread 5 used 158 times, waiting to start 34.610482, 819 locks, 0.25028682 locked, 0.00085830688 waiting for locks\n",
"Cbc0030I Thread 6 used 160 times, waiting to start 36.679925, 847 locks, 0.24719381 locked, 0.0008687973 waiting for locks\n",
"Cbc0030I Thread 7 used 156 times, waiting to start 39.306733, 814 locks, 0.25425935 locked, 0.00066351891 waiting for locks\n",
"Cbc0030I Main thread 888.87581 waiting for threads, 2621 locks, 0.0017046928 locked, 0.0054161549 waiting for locks\n",
"Cbc0020I Exiting on maximum time\n",
"Cbc0005I Partial search - best objective 813 (best possible 227.46805), took 4337962 iterations and 1295 nodes (7206.83 seconds)\n",
"Cbc0032I Strong branching done 16064 times (1498419 iterations), fathomed 0 nodes and fixed 0 variables\n",
"Cbc0035I Maximum depth 132, 0 variables fixed on reduced cost\n",
"Total time (CPU seconds): 7209.43 (Wallclock seconds): 1701.62\n",
"\n"
]
},
{
"name": "stderr",
"output_type": "stream",
"text": [
"┌ Warning: Problem status UserLimit; solution may be inaccurate.\n",
"└ @ Convex /Users/oxinabox/.julia/packages/Convex/Y3Bcx/src/solution.jl:48\n"
]
}
],
"source": [
"@time solve!(m, solver)"
]
},
{
"cell_type": "code",
"execution_count": 13,
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"m.optval = 813.0\n"
]
},
{
"data": {
"text/plain": [
"96×2 LinearAlgebra.Adjoint{Int64,Array{Int64,2}}:\n",
" 1 23\n",
" 1 62\n",
" 1 65\n",
" 1 69\n",
" 2 1\n",
" 2 30\n",
" 2 78\n",
" 2 86\n",
" 3 11\n",
" 3 34\n",
" 3 54\n",
" 3 64\n",
" 4 17\n",
" ⋮ \n",
" 22 14\n",
" 22 29\n",
" 22 50\n",
" 22 81\n",
" 23 46\n",
" 23 51\n",
" 23 74\n",
" 23 83\n",
" 24 5\n",
" 24 31\n",
" 24 73\n",
" 24 96"
]
},
"execution_count": 13,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"@show m.optval\n",
"allocations_raw = A.value\n",
"allocations_list = collect.(Tuple.(findall(allocations_raw .> 0)))\n",
"allocation_matrix = reduce(hcat, sort(allocations_list))'"
]
},
{
"cell_type": "code",
"execution_count": 12,
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"250-element Array{Array{Int64,1},1}:\n",
" [78, 89, 41, 34, 86, 82] \n",
" [19, 65, 21, 42, 22, 66, 14, 85, 79, 90 … 31, 52, 90, 4, 19, 70, 1, 61, 53, 9] \n",
" [53, 95, 43, 32, 80, 73, 66, 55, 35, 69, 40, 29, 93] \n",
" [56, 29, 87, 31, 31, 70, 29, 23, 88, 80 … 84, 81, 4, 72, 70, 55, 85, 81, 27, 69]\n",
" [65, 52, 48, 67, 67] \n",
" [25, 92, 64, 64, 95] \n",
" [11, 54, 42, 41, 80, 16, 11, 65, 10, 4, 2, 93, 77, 69, 55, 25, 17] \n",
" [66, 74, 84, 87, 13, 47, 25, 85, 72, 75, 26, 36, 3, 24, 94, 16, 41, 34, 18, 71] \n",
" [55, 2, 91, 66, 89, 35, 61, 9, 20, 27, 65, 94, 17, 2, 26] \n",
" [5, 8, 50, 11, 85, 64, 47, 35, 73, 25, 10, 49, 90] \n",
" [13, 74, 65, 5, 65, 92, 25, 13, 68, 28 … 55, 1, 90, 86, 49, 10, 12, 64, 72, 33] \n",
" [60, 81, 79, 47, 34, 21] \n",
" [31, 29, 7, 28] \n",
" ⋮ \n",
" [49, 12, 78, 73, 48, 28, 50, 93, 69, 42, 8, 49, 80, 4, 15, 59, 81, 45, 50] \n",
" [4, 72, 28, 94] \n",
" [40, 55, 30, 73, 64] \n",
" [79, 62, 38, 59, 56, 48, 28, 82, 79, 34, 4, 47] \n",
" [95, 34, 84, 58, 76, 69, 64, 16, 37, 17, 47, 50, 70] \n",
" [44, 94, 51, 44, 18, 2, 20, 49, 84] \n",
" [33, 51, 57, 77, 50, 64, 40] \n",
" [31, 34, 37, 92, 2, 50, 62, 79, 25] \n",
" [39, 56, 2, 53, 71, 16, 42, 12, 88, 58, 49, 72, 58, 8, 24, 21, 2, 36] \n",
" [68, 55, 43, 71, 92, 65, 6, 26, 51, 84 … 90, 15, 22, 41, 35, 22, 29, 34, 61, 67]\n",
" [50, 87, 4, 71, 75, 74] \n",
" [22, 93, 74, 55, 47, 45, 44, 25] "
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"people_votes"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Baseline\n",
"Just try different legal arrangements\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"function random_solution(num_rooms, num_timeslots, num_program_items)\n",
" A = zeros(Int, num_timeslots, num_program_items)\n",
" \n",
" program_items = shuffle(1:num_program_items)\n",
" for (ii,item) in enumerate(program_items)\n",
" timeslot = ceil(Int, ii/num_rooms)\n",
" A[timeslot, item] = 1\n",
" end\n",
" @assert all(isequal(1), sum(randA, dims=1)) # Everything occurs once\n",
" @assert all(sum(randA, dims=2) .<= num_rooms) # Don't double book rooms\n",
" return A\n",
"end\n",
"\n",
"\n",
"maximum(\n",
" Base.Generator(1:100_000) do ii\n",
" sol = random_solution(num_rooms, length(timeslots), length(program_items))\n",
" score = count_clashes(sol, people_votes)\n",
" return (score, rand(), sol) # the rand is to break ties so it never compares last arg\n",
" end\n",
")"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": []
}
],
"metadata": {
"kernelspec": {
"display_name": "Julia 1.0.2",
"language": "julia",
"name": "julia-1.0"
},
"language_info": {
"file_extension": ".jl",
"mimetype": "application/julia",
"name": "julia",
"version": "1.0.2"
}
},
"nbformat": 4,
"nbformat_minor": 2
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment