|
Department
of |
|
Susan L. EpsteinThe CUNY Graduate School, Department
of Computer Science and Hunter College, Department
of Computer Science
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Home Publications Collaborators Courses Media Appearances Contact
|
|
COMPOSED PROBLEMS (CSP)A composed problem consists of a random central component <n ,k, d ,t> and s smaller random satellites in <n’ ,k’ ,d’ t’>. Links with density d’’ and tightness t’’ join the central component and the satellites, but there are no links between satellites. Many classes of composed problems confound traditional heuristics. A composed problem is described here as <n ,k, d ,t> s <n’ ,k’ ,d’ t’> <d’’, t’’>. The results below come from experiments using ACE with variable-ordering heuristic mean domain/dynamic degree. Results using a mixture of heuristics (Advisors) will be reported soon. Results reported were averaged over ACE runs on the first 100 problems in each file. #PROBLEMS indicates how many problems are available on file CONSTRAINT CHECKS indicates the average number of constraint checks. VISITED NODES indicates the average number of nodes visited during search.
|
