social golfer
Social golfer is one of the famous problems in the CSPLib
(prob010). We have m social golfers, n weeks and k groups
of l size. Each golfer plays once a week in groups of l
golfers. The problem is to build a schedule of play for all
golfers over the n weeks such that no golfer plays in the
same group as any other golfer more than one time.
The model-oracle can be built by two constraints ( m_ct1
and m_ct2 ), the first one to specify that each group has
exactly l golfers (group size). The second one to say that
each pair of golfers meets only at most once.
- The model-oracle can after be improved using static symmetry breaking. The symmetry can be broken by selective assignment. We get a model with five constraints, we inject in each constraint a fault to get at the end five faulty CPUTs (CPUT1 to CPUT5).
- CPUT1
- CPUT2
- CPUT3
- CPUT4
- CPUT5
tab3. Fault detection and localization of social golfer problem.
| TEST | LOCALIZATION | ||||
|---|---|---|---|---|---|
| G.rulers | #_constr. | fault_injected | non.conf._detected | fault localization | time |
| CPUT1 | 5 | p1_ct1 | sol(CPUT1)=emptyset | (rev(p1_ct1),emptyset) | 1.04s |
| CPUT2 | 5 | p2_ct2 | [4 6 3 1 5 2 3 5 4 6] | (rev(P2), (m_ct2)) | 0.18s |
| CPUT3 | 5 | p3_ct3 | sol(CPUT3)=emptyset | (rev(p3_ct3),emptyset) | 1.05s |
| CPUT4 | 5 | p4_ct4 | sol(CPUT4)=emptyset | (rev(p4_ct4,p4_ct5),emptyset) | 1.03s |
| CPUT5 | 5 | p5_ct5 |
sol(CPUT5)=emptyset | (rev(p5_ct5),emptyset) | 1.15s |
nc1= [[1 1 1 1][1 2 2 2][1 3 3 3]
[2 1 3 3][2 2 2 1][2 2 1 1][3 3 3 2][3 1 1 2][3 3 2 3]] |
|||||
Correction:
- Mutant1 ==> (ct1, 58 EC)
- Mutant2==> (Emptyset, 75 EC)
- Mutant3==> (ct3, 58 EC)
- Mutant4==> (ct4, 58 EC)
- ______-==> (ct5, 58 EC )
- Mutant5==> (ct5 , 58 EC)
All our experiments were performed on Intel Core2 Duo CPU 2.40Ghz machine with 2.00 GB of RAM.
