Backtracking search heuristics for solving the all-partition array problem

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

82 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationInternational Society for Music Information Retrieval Conference
Number of pages7
PublisherInternational Society for Music Information Retrieval
Publication date2019
Pages391-397
Article number46
Publication statusPublished - 2019
EventInternational Society for Music Information Retrieval Conference - Delft University of Technology, Delft, Netherlands
Duration: 4 Nov 20198 Nov 2019
Conference number: 20
https://ismir2019.ewi.tudelft.nl/

Conference

ConferenceInternational Society for Music Information Retrieval Conference
Number20
LocationDelft University of Technology
Country/TerritoryNetherlands
CityDelft
Period04/11/201908/11/2019
Internet address

Fingerprint

Dive into the research topics of 'Backtracking search heuristics for solving the all-partition array problem'. Together they form a unique fingerprint.

Cite this