dynamic programming - Set partitioning with constraints java -

the what

i'm attempting produce optimum set of brackets (optimum defined constraints) tournament.

the problem

i don't know how approach problem. this paper pretty high level discusses possibility of solving set partitioning problems constraint programming. states majority of set partitioning problems solved via integer programming. looking example emulate. question similar so question. majority of constraint examples i've seen defined specific partition total. possible model system partitions determined dynamically constraints , participant set? link examples limited 2 due reputation.

a more concrete example

known values

• the number of participants n.
• each participant has weight w associated them.

constraints

• a bracket (set) made of 2,3,4,6,7, or 8 participants.
• each participant in single bracket.
• the must not more 15% difference between lowest weighted participant , highest weighted participant in bracket.
• favor creating brackets of size 8 , 4 on other bracket sizes.

so example there 8 participants.

{ {1, w=100}, {2, w=103}, {3, w=105}, {4, w=106}, {5, w=110}, {6, w=114}, {7, w=120}, {8, w=125} }

one possible solution be: {1, 2, 3}, {4, 5}, {6, 7, 8}

a more optimum solution be: {1, 2, 3, 4}, {5, 6, 7, 8} since favors 4, 8 sized sets on previous solution.

is possible partition set dynamic number of child sets?

thanks again time!

here's proof-of-concept of constraint programming approach. it's done in minizinc, (as usual when prototyping csp problems). haven't implemented in java system hope it's of use anyway.

the minizinc model here: http://www.hakank.org/minizinc/bracket_partitioning.mzn

here's the principal approach:

• the array ("x") of size 1..n assigning person (x[i]) bracket. symmetry breaking on "x":

  • bracket 1 must used before bracket 2 (the constraint value_precede_chain)

• another array ("set_size") of 1..n div 2 contains number of person in each bracket.

  symmetry breaking on "set_size":

  • the values in "set_size" must in decreasing order.

• then there 3 arrays ("mins", "maxs","diffs") of size 1..n div 2 (i.e. same same "set_size") includes minimum, maximum values of each bracket, , difference (diff[s]) between maxs[s]-mins[s]. difference must within 15% (calculated "10000*diffs[s] div maxs[s] <= 1500").

  this 15% requirement makes model bit messy, interesting.

• the preference of 4 , 8 size brackets has been implemented maximizing number of brackets of size 4 , 8 (both have weight 1, other bracket sizes have weight 0); "z" variable. alternative weight bracket size of 8 2 , size 4 of 1 (and other weight 0) prefer 8 size brackets on 4 size brackets.

notes: - there other constraints - implicit constraints , symmetry breaking - tend speed model, such as:

 sum(set_size) = n % implicit constraint   x[1] = 1 % assign first person bracket 1 

• the code includes stuff randomized testing such rand_int_array (minizinc don't have built-in). can ignored.

• i don't know how large n can in real life. perhaps it's large, 1 have add more symmetry breaking etc or using approach.

here's output running example given:

w: [100, 103, 105, 106, 110, 114, 120, 125] z: 2 x: [1, 1, 1, 1, 2, 2, 2, 2] set_size: [4, 4, 0, 0] diffs: [6, 15, 0, 0] mins: [100, 110, 0, 0] maxs: [106, 125, 0, 0] bracket 1: [100, 103, 105, 106] bracket 2: [110, 114, 120, 125] 

here see 2 brackets of size 4 have optimal value (z=2 since there 2 size 4) expected.

for example n=28, model give results ("w" array of 'random' weights).

w: [111, 109, 112, 146, 115, 103, 130, 145, 128, 127, 144, 114, 133, 126, 134, 133, 114, 134, 143, 116, 106, 104, 147, 110, 114, 102, 118, 130] z: 7 x: [1, 1, 1, 2, 1, 3, 2, 2, 2, 4, 4, 3, 4, 4, 5, 6, 3, 5, 5, 3, 7, 7, 5, 7, 6, 7, 6, 6] set_size: [4, 4, 4, 4, 4, 4, 4, 0, 0, 0, 0, 0, 0, 0] diffs: [6, 18, 13, 18, 13, 19, 8, 0, 0, 0, 0, 0, 0, 0] mins: [109, 128, 103, 126, 134, 114, 102, 0, 0, 0, 0, 0, 0, 0] maxs: [115, 146, 116, 144, 147, 133, 110, 0, 0, 0, 0, 0, 0, 0] bracket 1: [111, 109, 112, 115] bracket 2: [146, 130, 145, 128] bracket 3: [103, 114, 114, 116] bracket 4: [127, 144, 133, 126] bracket 5: [134, 134, 143, 147] bracket 6: [133, 114, 118, 130] bracket 7: [106, 104, 110, 102] 

this solved in 0.7s gecode.