- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
15
Social Golfers
32 golfers playing in groups of 4 each week Find a maximal schedule such that golfers don’t repeat partners 3 weeks solution:
{ 1 2 3 4} { 5 6 7 8} { 9 10 11 12} {13 14 15 16} {17 18 19 20} {21 22 23 24} {25 26 27 28} {29 30 31 32} { 1 5 9 13} { 2 6 10 14} { 3 7 11 15} { 4 8 12 16} {17 21 25 29} {18 22 26 30} {19 23 27 31} {20 24 28 32} { 1 6 11 16} { 2 5 12 15} { 3 8 9 14} { 4 7 10 13} {17 22 27 32} {18 21 28 31} {19 24 25 30} {20 23 26 29}
and
x1 + x 2 + x3 + x 4 = 2
Solution: x1=1, x4=1
12
Set Covering: A Sets Model
Find a set of 2 columns so that all lines are covered
Cols ⊆ {1,2,3,4}, #Cols=2, {1,4} ∩ Cols ≠ ∅ {1,2} ∩ Cols ≠ ∅ {3,4} ∩ Cols ≠ ∅ {2,4} ∩ Cols ≠ ∅ {1,3} ∩ Cols ≠ ∅
6
Set Relations
Relation R between 2 sets. R: P(U)2 B Equality and Difference (=, )
E.g. {n ∈ | n>0 ∧ n<3} = {1,2} {a,b} = {b,a} , {0} , {a} {a,b}
Containment (
{a, b} = {c, d }
8
Set Functions
Function F over one set F: P(U) ? (depends on the function) Cardinality #: P(U) 0 E.g. #{a,b} = 2 , # = 0 And others...
9
Problems / Applications
What if sets are not fully known a priori?
Partial information
Achieve a goal by finding appropriate set values subject to some constraints
empty: P(U) B (e.g. empty( ) = true) minimum: P( )\ (minimum({4.2, -1.5, 1}) = -1.5) max_length: P(Strings) 0 (max_length({“red”,”green”,”blue”}) = 5)
The optimum is 10 weeks Generalized to g groups of s golfers Also related to designs problems
5
Sets
A set is naturally used to collect distinct elements sharing some property {x | Property(x)} There is usually some associated universe U. E.g. Set of positive odd numbers less than 8: S = {n ∈ | (n mod 2 = 1) ∧ (n < 8)} = {1,3,5,7} Elements: 1 ∈ S, 3 ∈ S, 5 ∈ S, 7 ∈ S, 2 ∉ S, ... Empty set: {} or
10
Set Covering
Example: take 3 sets from {{1,2,5}, {2,4}, {3,5}, {1,3,4}} such that their union is {1,2,3,4,5} Optimization: Find the minimum number of sets that fully cover the domain. Solution: 2 sets, {1,2,5} and {1,3,4} Many real-life applications, with ‘servers’ (such as transportation, stores, etc) to serve all ‘clients’.
CP(Sets) as an alternative to ILP and other mathematical methods
Example: find 4 of 10 given sets, whose union is the same as the union of the 10 (Set Covering) Set Partitioning: find disjoint sets with full union Program Analysis
11
Set Covering: ILP Model
Take 2 sets from {{1,2,5}, {2,4}, {3,5}, {1,3,4}} such that their union is {1,2,3,4,5}
1 0 0 1 1 1 0 0 0 0 1 1. 0 1 0 1 1 0 1 0 x1 x2 x3 x4 1 1 ≥ 1 1 1
A particular case of Steiner systems or, more generally, Balanced Incomplete Block Designs (BIBD) A construction method is available on the internet: http://perso.wanadoo.fr/colin.barker/lpa/sts.htm
14
Steiner Triples
Steiner(n): find n.(n-1)/6 triples (of distinct elements) from 1...n, such that any two triples have at most one common element E.g. For Steiner(7): {{1,2,3}, {1,4,5}, {1,6,7}, {2,4,6}, {2,5,7}, {3,4,7}, {3,5,6}} Problem from combinatorial designs
6 x 2-hours lectures (in 2 weeks)
Mainly theoretical, partially practical 3 ECTS 70-90 hours student work
2
ቤተ መጻሕፍቲ ባይዱ
Bibliography
Constraint Solving over Multi-valued Logics – Application to Digital Circuits. IOS. Francisco Azevedo, 2003. Chapters 6 and 7 Interval Propagation to Reason about Sets: Definition and Implementation of a Practical Language, Constraints International Journal, Vol. 1, No. 3, KAP. C. Gervet, 1997, pp. 191 − 244 Set Domain Propagation Using ROBDDs. CP’04. Springer. V. Lagoon, & P.J. Stuckey, 2004, pp. 347−361 ECLiPSe user manual
Solution: Cols = {1,4}
Set Partitioning
For the same example: {{1,2,5}, {2,4}, {3,5}, {1,3,4}}, there is no solution. I.e. no set of disjoint sets have {1,2,3,4,5} as union. If it were {{1,2,4}, {2,5}, {3,5}, {1,3,4}} we could have 2 solutions {{1,2,4},{3,5}}, and {{2,5},{1,3,4}}
Course on Constraints over Sets and Optimization
Constraints Advanced Module of Master in Computational Logic (UNL)
2008
Francisco Azevedo, FCT/UNL
Organization
http://ssdi.di.fct.unl.pt/cso Lecturer: Francisco Azevedo
http://ssdi.di.fct.unl.pt/~fa fa@di.fct.unl.pt
Office hours
Office: P2/1. Tel. ext: 10730 Time: after lectures
Software: Cardinal
3
Outline
Sets, Domains and Tools
