Dagster: Parallel Structured Search

Mark Alexander Burgess; Charles Gretton; Josh Milthorpe; Luke Croak; Thomas Willingham; Alwen Tiu

Dagster: Parallel Structured Search

Mark Alexander Burgess, Charles Gretton, Josh Milthorpe, Luke Croak, Thomas Willingham, Alwen Tiu

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › peer-review

Abstract

We demonstrate DAGSTER, a system that implements a new approach to scheduling interdependent (Boolean) SAT search activities in high-performance computing (HPC) environments. Our system takes as input a set of disjunctive clauses (i.e., DIMACS CNF) and a labelled directed acyclic graph (DAG) structure describing how the clauses are decomposed into a set of interrelated problems. Component problems are solved using standard systematic backtracking search, which may optionally be coupled to (stochastic dynamic) local search and/or clause-strengthening processes. We demonstrate DAGSTER using a new Graph Maximal Determinant combinatorial case study. This demonstration paper presents a new case study, and is adjunct to the longer accepted manuscript at the Pacific Rim International Conference on Artificial Intelligence (2022).

Original language	English
Title of host publication	AAAI-23 Special Programs, IAAI-23, EAAI-23, Student Papers and Demonstrations
Editors	Brian Williams, Yiling Chen, Jennifer Neville
Publisher	AAAI Press
Pages	16404-16406
Number of pages	3
ISBN (Electronic)	9781577358800
Publication status	Published - 27 Jun 2023
Event	37th AAAI Conference on Artificial Intelligence, AAAI 2023 - Washington, United States Duration: 7 Feb 2023 → 14 Feb 2023

Publication series

Name	Proceedings of the 37th AAAI Conference on Artificial Intelligence, AAAI 2023
Volume	37

Conference

Conference	37th AAAI Conference on Artificial Intelligence, AAAI 2023
Country/Territory	United States
City	Washington
Period	7/02/23 → 14/02/23

Cite this

Burgess, M. A., Gretton, C., Milthorpe, J., Croak, L., Willingham, T., & Tiu, A. (2023). Dagster: Parallel Structured Search. In B. Williams, Y. Chen, & J. Neville (Eds.), AAAI-23 Special Programs, IAAI-23, EAAI-23, Student Papers and Demonstrations (pp. 16404-16406). (Proceedings of the 37th AAAI Conference on Artificial Intelligence, AAAI 2023; Vol. 37). AAAI Press.

@inproceedings{d0651809bde641bda75c619f0cc4f5ca,

title = "Dagster: Parallel Structured Search",

abstract = "We demonstrate DAGSTER, a system that implements a new approach to scheduling interdependent (Boolean) SAT search activities in high-performance computing (HPC) environments. Our system takes as input a set of disjunctive clauses (i.e., DIMACS CNF) and a labelled directed acyclic graph (DAG) structure describing how the clauses are decomposed into a set of interrelated problems. Component problems are solved using standard systematic backtracking search, which may optionally be coupled to (stochastic dynamic) local search and/or clause-strengthening processes. We demonstrate DAGSTER using a new Graph Maximal Determinant combinatorial case study. This demonstration paper presents a new case study, and is adjunct to the longer accepted manuscript at the Pacific Rim International Conference on Artificial Intelligence (2022).",

author = "Burgess, \{Mark Alexander\} and Charles Gretton and Josh Milthorpe and Luke Croak and Thomas Willingham and Alwen Tiu",

note = "Publisher Copyright: Copyright {\textcopyright} 2023, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.; 37th AAAI Conference on Artificial Intelligence, AAAI 2023 ; Conference date: 07-02-2023 Through 14-02-2023",

year = "2023",

month = jun,

day = "27",

language = "English",

series = "Proceedings of the 37th AAAI Conference on Artificial Intelligence, AAAI 2023",

publisher = "AAAI Press",

pages = "16404--16406",

editor = "Brian Williams and Yiling Chen and Jennifer Neville",

booktitle = "AAAI-23 Special Programs, IAAI-23, EAAI-23, Student Papers and Demonstrations",

}

Burgess, MA, Gretton, C, Milthorpe, J, Croak, L, Willingham, T & Tiu, A 2023, Dagster: Parallel Structured Search. in B Williams, Y Chen & J Neville (eds), AAAI-23 Special Programs, IAAI-23, EAAI-23, Student Papers and Demonstrations. Proceedings of the 37th AAAI Conference on Artificial Intelligence, AAAI 2023, vol. 37, AAAI Press, pp. 16404-16406, 37th AAAI Conference on Artificial Intelligence, AAAI 2023, Washington, United States, 7/02/23.

Dagster: Parallel Structured Search. / Burgess, Mark Alexander; Gretton, Charles; Milthorpe, Josh et al.
AAAI-23 Special Programs, IAAI-23, EAAI-23, Student Papers and Demonstrations. ed. / Brian Williams; Yiling Chen; Jennifer Neville. AAAI Press, 2023. p. 16404-16406 (Proceedings of the 37th AAAI Conference on Artificial Intelligence, AAAI 2023; Vol. 37).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › peer-review

TY - GEN

T1 - Dagster

T2 - 37th AAAI Conference on Artificial Intelligence, AAAI 2023

AU - Burgess, Mark Alexander

AU - Gretton, Charles

AU - Milthorpe, Josh

AU - Croak, Luke

AU - Willingham, Thomas

AU - Tiu, Alwen

PY - 2023/6/27

Y1 - 2023/6/27

N2 - We demonstrate DAGSTER, a system that implements a new approach to scheduling interdependent (Boolean) SAT search activities in high-performance computing (HPC) environments. Our system takes as input a set of disjunctive clauses (i.e., DIMACS CNF) and a labelled directed acyclic graph (DAG) structure describing how the clauses are decomposed into a set of interrelated problems. Component problems are solved using standard systematic backtracking search, which may optionally be coupled to (stochastic dynamic) local search and/or clause-strengthening processes. We demonstrate DAGSTER using a new Graph Maximal Determinant combinatorial case study. This demonstration paper presents a new case study, and is adjunct to the longer accepted manuscript at the Pacific Rim International Conference on Artificial Intelligence (2022).

AB - We demonstrate DAGSTER, a system that implements a new approach to scheduling interdependent (Boolean) SAT search activities in high-performance computing (HPC) environments. Our system takes as input a set of disjunctive clauses (i.e., DIMACS CNF) and a labelled directed acyclic graph (DAG) structure describing how the clauses are decomposed into a set of interrelated problems. Component problems are solved using standard systematic backtracking search, which may optionally be coupled to (stochastic dynamic) local search and/or clause-strengthening processes. We demonstrate DAGSTER using a new Graph Maximal Determinant combinatorial case study. This demonstration paper presents a new case study, and is adjunct to the longer accepted manuscript at the Pacific Rim International Conference on Artificial Intelligence (2022).

UR - https://www.scopus.com/pages/publications/85168255369

M3 - Conference Paper

T3 - Proceedings of the 37th AAAI Conference on Artificial Intelligence, AAAI 2023

SP - 16404

EP - 16406

BT - AAAI-23 Special Programs, IAAI-23, EAAI-23, Student Papers and Demonstrations

A2 - Williams, Brian

A2 - Chen, Yiling

A2 - Neville, Jennifer

PB - AAAI Press

Y2 - 7 February 2023 through 14 February 2023

ER -

Dagster: Parallel Structured Search

Abstract

Publication series

Conference

Other files and links

Fingerprint

Cite this