Correct predictions are in blue. If we detect only a subset of a labelled sentence, we highlight the caught part as blue, the missing part light blue. False positives are in green and false negatives are in red.

Problem 015 (Schur's Lemma) — Constraint detection

The problem is to put $ n $ balls labelled $ -LCB- 1 , - , n -RCB- $ into 3 boxes so that for any triplet of balls $ -LRB- x , y , z -RRB- $ with $ x + y = z $ , not all are in the same box . This has a solution iff $ n > 14 $ . The problem can be formulated as a 0-1 problem using the variables , $ M _ -LCB- ij -RCB- $ for $ i \ in -LCB- 1 , - , n -RCB- , j \ in -LCB- 1,2,3 -RCB- $ with $ M _ -LCB- ij -RCB- $ true iff ball $ i $ is in box $ j $ . The constraints are that a ball must be in exactly one box , $ M _ -LCB- i1 -RCB- + M _ -LCB- i2 -RCB- + M _ -LCB- i3 -RCB- = 1 $ for all $ i \ in -LCB- 1 , - , n -RCB- $ . And for each $ x + y = z $ and $ j \ in -LCB- 1,2,3 -RCB- $ , not $ -LRB- M _ -LCB- xj -RCB- \ wedge M _ -LCB- yj -RCB- \ wedge M _ -LCB- zj -RCB- $ -RRB- . This converts to , $ -LRB- 1-M _ -LCB- xj -RCB- -RRB- + -LRB- 1-M _ -LCB- yj -RCB- -RRB- + -LRB- 1-M _ -LCB- zj -RCB- -RRB- \ geq 1 $ or , $ M _ -LCB- xj -RCB- + M _ -LCB- yj -RCB- + M _ -LCB- zj -RCB- \ leq 2 $ .

Problem 015 (Schur's Lemma) — Detection of the decisions and objects to be modeled

The problem is to put $ n $ balls labelled $ -LCB- 1 , - , n -RCB- $ into 3 boxes so that for any triplet of balls $ -LRB- x , y , z -RRB- $ with $ x + y = z $ , not all are in the same box . This has a solution iff $ n > 14 $ . The problem can be formulated as a 0-1 problem using the variables , $ M _ -LCB- ij -RCB- $ for $ i \ in -LCB- 1 , - , n -RCB- , j \ in -LCB- 1,2,3 -RCB- $ with $ M _ -LCB- ij -RCB- $ true iff ball $ i $ is in box $ j $ . The constraints are that a ball must be in exactly one box , $ M _ -LCB- i1 -RCB- + M _ -LCB- i2 -RCB- + M _ -LCB- i3 -RCB- = 1 $ for all $ i \ in -LCB- 1 , - , n -RCB- $ . And for each $ x + y = z $ and $ j \ in -LCB- 1,2,3 -RCB- $ , not $ -LRB- M _ -LCB- xj -RCB- \ wedge M _ -LCB- yj -RCB- \ wedge M _ -LCB- zj -RCB- $ -RRB- . This converts to , $ -LRB- 1-M _ -LCB- xj -RCB- -RRB- + -LRB- 1-M _ -LCB- yj -RCB- -RRB- + -LRB- 1-M _ -LCB- zj -RCB- -RRB- \ geq 1 $ or , $ M _ -LCB- xj -RCB- + M _ -LCB- yj -RCB- + M _ -LCB- zj -RCB- \ leq 2 $ .

Back to list