Solving combined configuration problems: A heuristic approach

Research output: Contribution to journalConference articleScientificpeer-review

Researchers

  • Martin Gebser
  • Anna Ryabokon
  • Gottfried Schenner

Research units

  • University of Klagenfurt
  • Siemens

Abstract

This paper describes an abstract problem derived from a combination of Siemens product configuration problems encountered in practice. Often isolated parts of configuration problems can be solved by mapping them to well-studied problems for which efficient heuristics exist (graph coloring, bin-packing, etc.). Unfortunately, these heuristics may fail to work when applied to a problem that combines two or more subproblems. In the paper we show how to formulate a combined configuration problem in Answer Set Programming (ASP) and to solve it using heuristics a la hclasp. The latter stands for heuristic clasp that is nowadays integrated in clasp and enables the declaration of domain-specific heuristics in ASP. In addition, we present a novel method for heuristic generation based on a combination of greedy search with ASP that allows to improve the performance of clasp.

Details

Original languageEnglish
Pages (from-to)55-60
Number of pages6
JournalCEUR Workshop Proceedings
Volume1453
Publication statusPublished - 2015
MoE publication typeA4 Article in a conference publication
Event International Configuration Workshop - Vienna, Austria
Duration: 10 Sep 201511 Sep 2015
Conference number: 17

ID: 17249091