使用约束java设置分区

Question

那是什么

我正在尝试为锦标赛制作一套最佳的方括号(最佳约束条件).

问题

我不知道如何处理这个问题. 该论文是相当高的水平,但讨论解决与约束编程集分割问题的可能性.它还指出大多数集合分区问题都是通过整数编程解决的.我主要是在寻找一个模仿的例子.问题类似于这个问题.我见过的大多数约束示例都定义了特定的分区总数.是否可以建模一个系统,其中分区将由约束和参与者集动态确定？我会链接示例,但由于我的声誉,我仅限于2.

一个更具体的例子

已知值

• 参加人数为N.
• 每个参与者具有与他们相关联的权重W.

约束

• 支架(组)由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

这是主要方法:

• 大小为1..N的数组("x")用于将人(x [i])分配给哪个括号.对称性打破"x":

  • 必须在括号2之前使用括号1(约束value_precede_chain)

• 1..N div 2的另一个数组("set_size")包含每个括号中的人数.

  "set_size"上的对称性破坏:

  • "set_size"中的值必须按递减顺序排列.

• 然后有三个帮助数组("分钟","最大","差异")大小为1..N div 2(即与"set_size"相同),其中包括每个括号的最小值,最大值,以及maxs [s] -mins [s]之间的差异(diff [s]).该差异必须在15%以内(计算为"10000*diffs [s] div maxs [s] <= 1500").

  这15%的要求使得模型有点混乱,但很有趣.

• 通过最大化4号和8号托架的数量来实现4和8尺寸托架的偏好(两者都具有重量1,其他托架尺寸具有重量0); 这是"z"变量.另一种方法是将支架尺寸的重量减少8乘2和尺寸4的1(以及所有其他重量0),因此优选8个尺寸的支架超过4个尺寸的支架.

注意: - 还有一些其他约束 - 隐式约束和对称性破坏 - 这往往会加速模型,例如:

 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]

Gecode通过约0.7秒解决了这个问题.