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 à la hclasp. 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 an ASP solver.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The instances were taken from: http://www.wiwi.uni-jena.de/Entscheidung/binpp/index.htm.
- 2.
The evaluation was performed using clingo version 4.3.0 from the Potassco ASP collection [7] on a system with Intel i7-3030K CPU (3.20 GHz) and 64 GB of RAM, running Ubuntu 11.10.
- 3.
The instances are available at: http://isbi.aau.at/hint/problems.
References
Aschinger, M., Drescher, C., Friedrich, G., Gottlob, G., Jeavons, P., Ryabokon, A., Thorstensen, E.: Optimization methods for the partner units problem. In: Achterberg, T., Beck, J.C. (eds.) CPAIOR 2011. LNCS, vol. 6697, pp. 4–19. Springer, Heidelberg (2011)
Aschinger, M., Drescher, C., Gottlob, G., Jeavons, P., Thorstensen, E.: Tackling the partner units configuration problem. In: Proceedings of IJCAI, pp. 497–503 (2011)
Balduccini, M.: Learning and using domain-specific heuristics in ASP solvers. AI Commun. 24(2), 147–164 (2011)
Cipriano, R., Di Gaspero, L., Dovier, A.: A hybrid solver for large neighborhood search: mixing gecode and easylocal++. In: Hybrid Metaheuristics, pp. 141–155 (2009)
Friedrich, G., Ryabokon, A., Falkner, A.A., Haselböck, A., Schenner, G., Schreiner, H.: (Re) configuration based on model generation. In: LoCoCo Workshop, pp. 26–35 (2011)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)
Gebser, M., Kaminski, R., Kaufmann, B., Schaub, T.: Answer Set Solving in Practice. Morgan & Claypool Publishers, San Rafael (2012)
Gebser, M., Kaufmann, B., Romero, J., Otero, R., Schaub, T., Wanko, P.: Domain-specific heuristics in answer set programming. In: Proceedings of AAAI (2013)
Haselböck, A., Schenner, G.: S’UPREME. In: Knowledge-Based Configuration: From Research to Business Cases, pp. 263–269 (2014)
Hotz, L., Felfernig, A., Stumptner, M., Ryabokon, A., Bagley, C., Wolter, K.: Configuration knowledge representation and reasoning. In: Knowledge-Based Configuration: From Research to Business Cases, pp. 41–72 (2014)
Madigan, C., Malik, S., Moskewicz, M., Zhang, L., Zhao, Y.: Chaff: engineering an efficient SAT solver. In: Proceedings of DAC (2001)
Mayer, W., Bettex, M., Stumptner, M., Falkner, A.: On solving complex rack configuration problems using CSP methods. In: Proceedings of the IJCAI Workshop on Configuration (2009)
McDermott, J.: R1: a rule-based configurer of computer systems. Artif. Intell. 19(1), 39–88 (1982)
Ryabokon, A., Friedrich, G., Falkner, A.A.: Conflict-based program rewriting for solving configuration problems. In: Cabalar, P., Son, T.C. (eds.) LPNMR 2013. LNCS, vol. 8148, pp. 465–478. Springer, Heidelberg (2013)
Schenner, G., Falkner, A., Ryabokon, A., Friedrich, G.: Solving object-oriented configuration scenarios with ASP. In: Proceedings of the Configuration Workshop, pp. 55–62 (2013)
Schrijvers, T., Tack, G., Wuille, P., Samulowitz, H., Stuckey, P.J.: Search combinators. Constraints 18(2), 269–305 (2013)
Sinz, C., Haag, A.: Configuration. IEEE Intell. Syst. 22(1), 78–90 (2007)
Soininen, T., Niemelä, I., Tiihonen, J., Sulonen, R.: Representing configuration knowledge with weight constraint rules. In: Proceedings of the Workshop on ASP, pp. 195–201 (2001)
Stumptner, M.: An overview of knowledge-based configuration. AI Commun. 10(2), 111–125 (1997)
Teppan, E.C., Friedrich, G., Falkner, A.A.: QuickPup: a heuristic backtracking algorithm for the partner units configuration problem. In: Proceedings of IAAI, pp. 2329–2334 (2012)
Tiihonen, J., Heiskala, M., Anderson, A., Soininen, T.: WeCoTin - a practical logic-based sales configurator. AI Commun. 26(1), 99–131 (2013)
Tomita, E., Kameda, T.: An efficient branch-and-bound algorithm for finding a maximum clique with computational experiments. J. Global Optim. 37(1), 95–111 (2007)
Acknowledgments
This work was funded by COIN and AoF under grant 251170 as well as by FFG under grant 840242. The authors would like to thank all anonymous reviewers for their comments and Konstantin Schekotihin for helpful discussions on the subject of this paper.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Gebser, M., Ryabokon, A., Schenner, G. (2015). Combining Heuristics for Configuration Problems Using Answer Set Programming. In: Calimeri, F., Ianni, G., Truszczynski, M. (eds) Logic Programming and Nonmonotonic Reasoning. LPNMR 2015. Lecture Notes in Computer Science(), vol 9345. Springer, Cham. https://doi.org/10.1007/978-3-319-23264-5_32
Download citation
DOI: https://doi.org/10.1007/978-3-319-23264-5_32
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-23263-8
Online ISBN: 978-3-319-23264-5
eBook Packages: Computer ScienceComputer Science (R0)