Backtracking search heuristics for solving the all-partition array problem

Bemman, Brian; Meredith, David

Abstract

Recent efforts to model the compositional processes of Milton Babbitt have yielded a number of computationally challenging problems. One of these problems, known as the \textit{all-partition array problem}, is 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. We present here 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.

Citation

Bemman, B., & Meredith, D. (2019, November). Backtracking search heuristics for solving the all-partition array problem. Presented at ISMIR 2019: International Society for Music Information Retrieval Conference, Delft University of Technology, Delft, Netherlands

• Presentation Conference Type: Conference Paper (published)
• Conference Name: ISMIR 2019: International Society for Music Information Retrieval Conference
• Start Date: Nov 4, 2019
• End Date: Nov 8, 2019
• Online Publication Date: Nov 4, 2019
• Publication Date: Nov 4, 2019
• Deposit Date: Jan 20, 2025
• Peer Reviewed: Peer Reviewed
• Pages: 391-397
• Public URL: https://durham-repository.worktribe.com/output/2954578
• Publisher URL: https://zenodo.org/records/3527826