Backtracking search heuristics for solving the all-partition array problem

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review

Resumé

Recent efforts to model the compositional processes of Milton Babbitt have yielded a number of computationally challenging problems. One of these, known as the all partition array problem, has been shown to be a particularly hard variant of set covering and several different approaches, including mathematical optimization, constraint satisfaction, and greedy backtracking, have been proposed for solving it. Of these previous approaches, only constraint programming has led to a successful solution. Unfortunately, this solution is expensive in terms of computation time. In this paper, we present two new search heuristics and a modification to a previously proposed heuristic, that, when applied to a greedy backtracking algorithm, allow the all-partition array problem to be solved in a practical running time. We demonstrate the success of our heuristics by solving for three different instances of the problem found in Babbitt’s music, including one previously solved with constraint programming and one Babbitt himself was unable to solve. Use of the new heuristics allows each instance of the problem to be solved more quickly than was possible with previous approaches.
OriginalsprogEngelsk
TitelInternational Society for Music Information Retrieval Conference
Antal sider7
ForlagInternational Society for Music Information Retrieval
Publikationsdato2019
Sider391-397
Artikelnummer46
StatusUdgivet - 2019
BegivenhedInternational Society for Music Information Retrieval Conference - Delft University of Technology, Delft, Holland
Varighed: 4 nov. 20198 nov. 2019
Konferencens nummer: 20
https://ismir2019.ewi.tudelft.nl/

Konference

KonferenceInternational Society for Music Information Retrieval Conference
Nummer20
LokationDelft University of Technology
LandHolland
ByDelft
Periode04/11/201908/11/2019
Internetadresse

Citer dette

Bemman, B., & Meredith, D. (2019). Backtracking search heuristics for solving the all-partition array problem. I International Society for Music Information Retrieval Conference (s. 391-397). [46] International Society for Music Information Retrieval.
Bemman, Brian ; Meredith, David. / Backtracking search heuristics for solving the all-partition array problem. International Society for Music Information Retrieval Conference. International Society for Music Information Retrieval, 2019. s. 391-397
@inproceedings{ff5bf057d7a047e38076a00d63036ea0,
title = "Backtracking search heuristics for solving the all-partition array problem",
abstract = "Recent efforts to model the compositional processes of Milton Babbitt have yielded a number of computationally challenging problems. One of these, known as the all partition array problem, has been shown to be a particularly hard variant of set covering and several different approaches, including mathematical optimization, constraint satisfaction, and greedy backtracking, have been proposed for solving it. Of these previous approaches, only constraint programming has led to a successful solution. Unfortunately, this solution is expensive in terms of computation time. In this paper, we present two new search heuristics and a modification to a previously proposed heuristic, that, when applied to a greedy backtracking algorithm, allow the all-partition array problem to be solved in a practical running time. We demonstrate the success of our heuristics by solving for three different instances of the problem found in Babbitt’s music, including one previously solved with constraint programming and one Babbitt himself was unable to solve. Use of the new heuristics allows each instance of the problem to be solved more quickly than was possible with previous approaches.",
author = "Brian Bemman and David Meredith",
year = "2019",
language = "English",
pages = "391--397",
booktitle = "International Society for Music Information Retrieval Conference",
publisher = "International Society for Music Information Retrieval",

}

Bemman, B & Meredith, D 2019, Backtracking search heuristics for solving the all-partition array problem. i International Society for Music Information Retrieval Conference., 46, International Society for Music Information Retrieval, s. 391-397, International Society for Music Information Retrieval Conference, Delft, Holland, 04/11/2019.

Backtracking search heuristics for solving the all-partition array problem. / Bemman, Brian; Meredith, David.

International Society for Music Information Retrieval Conference. International Society for Music Information Retrieval, 2019. s. 391-397 46.

Publikation: Bidrag til bog/antologi/rapport/konference proceedingKonferenceartikel i proceedingForskningpeer review

TY - GEN

T1 - Backtracking search heuristics for solving the all-partition array problem

AU - Bemman, Brian

AU - Meredith, David

PY - 2019

Y1 - 2019

N2 - Recent efforts to model the compositional processes of Milton Babbitt have yielded a number of computationally challenging problems. One of these, known as the all partition array problem, has been shown to be a particularly hard variant of set covering and several different approaches, including mathematical optimization, constraint satisfaction, and greedy backtracking, have been proposed for solving it. Of these previous approaches, only constraint programming has led to a successful solution. Unfortunately, this solution is expensive in terms of computation time. In this paper, we present two new search heuristics and a modification to a previously proposed heuristic, that, when applied to a greedy backtracking algorithm, allow the all-partition array problem to be solved in a practical running time. We demonstrate the success of our heuristics by solving for three different instances of the problem found in Babbitt’s music, including one previously solved with constraint programming and one Babbitt himself was unable to solve. Use of the new heuristics allows each instance of the problem to be solved more quickly than was possible with previous approaches.

AB - Recent efforts to model the compositional processes of Milton Babbitt have yielded a number of computationally challenging problems. One of these, known as the all partition array problem, has been shown to be a particularly hard variant of set covering and several different approaches, including mathematical optimization, constraint satisfaction, and greedy backtracking, have been proposed for solving it. Of these previous approaches, only constraint programming has led to a successful solution. Unfortunately, this solution is expensive in terms of computation time. In this paper, we present two new search heuristics and a modification to a previously proposed heuristic, that, when applied to a greedy backtracking algorithm, allow the all-partition array problem to be solved in a practical running time. We demonstrate the success of our heuristics by solving for three different instances of the problem found in Babbitt’s music, including one previously solved with constraint programming and one Babbitt himself was unable to solve. Use of the new heuristics allows each instance of the problem to be solved more quickly than was possible with previous approaches.

M3 - Article in proceeding

SP - 391

EP - 397

BT - International Society for Music Information Retrieval Conference

PB - International Society for Music Information Retrieval

ER -

Bemman B, Meredith D. Backtracking search heuristics for solving the all-partition array problem. I International Society for Music Information Retrieval Conference. International Society for Music Information Retrieval. 2019. s. 391-397. 46