A note on Rudi Mathon
From BICA (12) 1994
by John van Rees
Rudi Mathon
Professor, University of Toronto
We are always looking for new methods to tackle our favourite intractable problems. Those of us who know the hill-climbing and simulated annealing techniques realize that these are wonderful algorithms for finding various combinatorial objects. But often these algorithms are not powerful enough to do the job. So it is with great interest that we learn from Rudi Mathon, via his talk at the Vermont Summer Workshop, that there is a new variation to the search algorithms developed by the optimization people that may help us all.
Rudi was examining Steiner Systems, S(t,k,v), exact packings of k-sets from a v-set with the property that each t-set occurs exactly once. For t≥5, there are only 9 orders known to S(5,6,168). Rudi assumed the design had PSL2(23) as an automorphism group, obtained the 5-set and 6-set orbit representatives, and found which 6-set orbit representative covered which 5-set orbit representative.
Then the problem reduced to finding a subset of a list of singletons, doubletons, and tripletons. The subset must include every element used in the list exactly once. It would seem a good set up for hill-climbing or simulated annealing but these techniques were tried and did not work. However, Tabu Search did the trick. In short, Tabu Search means that a list of the last n attempts are kept to prevent searching the same vectors over and over again.
Rudi's achievement is doubly interesting. It is impressive to have a new Steiner System S(5,6,v) and we now have a new algorithm that may serve in attacks on our favourite problems.
by John van Rees
Rudi Mathon
Professor, University of Toronto
We are always looking for new methods to tackle our favourite intractable problems. Those of us who know the hill-climbing and simulated annealing techniques realize that these are wonderful algorithms for finding various combinatorial objects. But often these algorithms are not powerful enough to do the job. So it is with great interest that we learn from Rudi Mathon, via his talk at the Vermont Summer Workshop, that there is a new variation to the search algorithms developed by the optimization people that may help us all.
Rudi was examining Steiner Systems, S(t,k,v), exact packings of k-sets from a v-set with the property that each t-set occurs exactly once. For t≥5, there are only 9 orders known to S(5,6,168). Rudi assumed the design had PSL2(23) as an automorphism group, obtained the 5-set and 6-set orbit representatives, and found which 6-set orbit representative covered which 5-set orbit representative.
Then the problem reduced to finding a subset of a list of singletons, doubletons, and tripletons. The subset must include every element used in the list exactly once. It would seem a good set up for hill-climbing or simulated annealing but these techniques were tried and did not work. However, Tabu Search did the trick. In short, Tabu Search means that a list of the last n attempts are kept to prevent searching the same vectors over and over again.
Rudi's achievement is doubly interesting. It is impressive to have a new Steiner System S(5,6,v) and we now have a new algorithm that may serve in attacks on our favourite problems.
Comments
Post a Comment