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