Set partitioning with java restrictions

Question

what

I am trying to create an optimal set of brackets (optimal, determined by restrictions) for the tournament.

Problem

I do not know how to approach the problem. This document is of a fairly high level, but discusses the possibility of solving given partitioning problems by programming constraints. It also indicates that most of the specified partitioning problems are solved using integer programming. I'm mostly looking for a role model. The question is similar to this SO question . Most of the examples of restrictions that I saw define a specific total amount of sections. Is it possible to simulate a system in which sections will be determined dynamically by restrictions and a set of participants? I would have linked examples, but I am limited to only 2 due to my reputation.

More specific example.

Known Values

• The number of participants is N.
• Each participant has a weight W associated with them.

Limitations

• () 2,3,4,6,7 8 .
• .
• 15% .
• 8 4 .

, , , 8 .

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

: {1, 2, 3}, {4, 5}, {6, 7, 8}

: {1, 2, 3, 4}, {5, 6, 7, 8}, 4, 8 .

?

!

Answer 1

. MiniZinc ( , CSP-). - Java, , - .

MiniZinc : http://www.hakank.org/minizinc/bracket_partitioning.mzn

:

• ( "x" ) 1..N (x [i]) . "x":

  • 1 2 ( _-)

• ( "set_size" ) 1..N div 2 .

  "set_size":

  • "set_size" .

• ( "mins", "maxs", "diffs" ) 1..N div 2 ( , "set_size" ), , , (diff [s]) maxs [s] -mins [s]. 15% ( "10000 * diffs [s] div maxs [s] <= 1500" ).

  15% , .

• 4 8 4 8 ( 1, 0); "z". 8 2 4 1 ( 0), , , 8 .

: - - - , , , :

 sum(set_size) = n % implicit constraint

 x[1] = 1 % assign the first person to bracket 1

• , rand_int_array ( MiniZinc ). .

• , N . , , .. .

:

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]

, 4 (z = 2, 2 4), .

N = 28 ( "w" - "" ).

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]

0,7 Gecode.

Answer 2

Java , Java, :

• OptaPlanner
• JaCop
• ECLiPSe CLP
• Choco
• JSR-331
• OR-tools ( , JVM)
• ...