Markus Aschinger
Heribert Vollmer
Skip Abstract Section
Abstract
In this work, we present LoCo, a fragment of classical first-order logic carefully tailored for expressing technical product configuration problems. The core feature of LoCo is that the number of components used in configurations does not have to be finitely bounded explicitly, but instead is bounded implicitly through the axioms. Computing configurations is equivalent to the task of model finding. We present the language, related algorithms, and complexity results as well as a prototypical implementation via answer set programming.
- J. Amilhastre, H. Fargier, and P. Marquis. 2002. Consistency restoration and explanations in dynamic CSPs—application to configuration. Artif. Intell. 135, 1--2 (2002), 199--234. Google Scholar
Digital Library
- H. R. Andersen, T. Hadzic, and D. Pisinger. 2010. Interactive cost configuration over decision diagrams. J. Artif. Intell. Res. (JAIR) 37 (2010), 99--139. Google ScholarDigital Library
- M. Aschinger, C. Drescher, and G. Gottlob. 2011. Introducing LoCo, a logic for configuration problems. In Proceedings of the 2nd Workshop on Logics for Component Configuration (LoCoCo'11). EPTCS, 36--45.Google Scholar
- M. Aschinger, C. Drescher, G. Gottlob, G. Friedrich, P. Jeavons, A. Ryabokon, and E. Thorstensen. 2011. Optimization methods for the partner units problem. In Proceedings of the 8th International Conference on the Integration of Artificial Intelligence and Operations Research Techniques into Constraint Programming for Combinatorial Optimization Problems (CPAIOR). Springer, Berlin, 4--19. Google ScholarDigital Library
- M. Aschinger, C. Drescher, and H. Vollmer. 2012. LoCo—A logic for configuration problems. In Proceedings of the 20th European Conference on Artificial Intelligence (ECAI'12). IOS Press, 73--78.Google Scholar
- ASP Competition. 2011. Third International Answer Set Programming Competition. Available at https://www.mat.unical.it/aspcomp2011/.Google Scholar
- M. Bettex, A. Falkner, W. Mayer, and M. Stumptner. 2009. On solving complex rack configuration problems using CSP methods. In Proceedings of the Configuration Workshop at the 21st International Conference on Artificial Intelligence (IJCAI). AAAI Press, 53--60.Google Scholar
- M. Buchheit, R. Klein, and W. Nutt. 1995. Constructive Problem Solving: A Model Construction Approach Towards Configuration. Technical Report TM-95-01. DFKI. 34 pages.Google Scholar
- A. K. Chandra, D. C. Kozen, and L. J. Stockmeyer. 1981. Alternation. J. ACM 28, 1 (1981), 114--133. Google ScholarDigital Library
- E. Dantsin, T. Eiter, G. Gottlob, and A. Voronkov. 2001. Complexity and expressive power of logic programming. Comput. Surveys 33, 3 (Sept. 2001), 374--425. Google ScholarDigital Library
- W. F. Dowling and J. H. Gallier. 1984. Linear-time algorithms for testing the satisfiability of propositional horn formulae. J. Logic Program. 1, 3 (1984), 267--284.Google ScholarCross Ref
- H. B. Enderton. 1972. A Mathematical introduction to logic. Academic Press, New York.Google Scholar
- A. Falkner, I. Feinerer, G. Salzer, and G. Schenner. 2010. Computing product configurations via UML and integer linear programming. J. Mass Customisation 3, 4 (2010), 351--367.Google ScholarCross Ref
- A. Falkner, A. Haselböck, G. Schenner, and H. Schreiner. 2011. Modeling and solving technical product configuration problems. AI EDAM 25, 2 (2011), 115--129. Google ScholarDigital Library
- I. Feinerer. 2013. Efficient large-scale configuration via integer linear programming. AI EDAM 27, 1 (2013), 37--49. Google ScholarDigital Library
- G. Fleischanderl, G. Friedrich, A. Haselböck, H. Schreiner, and M. Stumptner. 1998. Configuring large systems using generative constraint satisfaction. IEEE Intell. Syst. 13, 4 (1998), 59--68. Google ScholarDigital Library
- G. Friedrich, A. Ryabokon, A. Falkner, A. Haselböck, G. Schenner, and H. Schreiner. 2011. (Re)configuration based on model generation. In Proceedings of the Second Workshop on Logics for Component Configuration, (LoCoCo), Perugia, Italy. EPTCS, 26--35.Google Scholar
- G. Friedrich and M. Stumptner. 1999. Consistency-based configuration. In Configuration Workshop at the 16th National Conference on Artificial Intelligence (AAAI). AAAI Press, 35--40.Google Scholar
- M. R. Garey and D. S. Johnson. 1979. Computers and Intractability. W.H. Freeman and Co., New York. Google ScholarDigital Library
- M. Gebser, R. Kaminski, B. Kaufmann, M. Ostrowski, T. Schaub, and M. Schneider. 2011. Potassco: The potsdam answer set solving collection. AI Commun. 24, 2 (2011), 105--124. Google ScholarDigital Library
- M. Gebser, R. Kaminski, B. Kaufmann, M. Ostrowski, T. Schaub, and S. Thiele. 2008. Engineering an incremental ASP solver. In Logic Programming, 24th International Conference, ICLP (Lecture Notes in Computer Science), Maria Garcia de la Banda and Enrico Pontelli (Eds.), Vol. 5366. Springer, 190--205. Google ScholarDigital Library
- M. Gelfond. 2008. Answer sets. In Handbook of Knowledge Representation, F. van Harmelen, V. Lifschitz, and B. Porter (Eds.). Elsevier, 285--316.Google Scholar
- M. Gelfond and V. Lifschitz. 1991. Classical negation in logic programs and disjunctive databases. New Generation Computing 9, 3/4 (1991), 365--386.Google ScholarDigital Library
- G. Gottlob, G. Greco, and T. Mancini. 2007. Conditional constraint satisfaction: Logical foundations and complexity. In Proceedings of the 20th International Conference on Artificial Intelligence (IJCAI). Morgan Kaufmann, 88--93. Google ScholarDigital Library
- P. Van Hentenryck. 1999. The OPL Optimization Programming Language. MIT Press, Cambridge, MA. Google ScholarDigital Library
- M. Hermann and B. Sertkaya. 2008. On the complexity of computing generators of closed sets. In Proceedings of the 6th International Conference on Formal Concept Analysis ICFCA'08. Springer, Montreal, Canada, 158--168. Google ScholarDigital Library
- A. Hubaux, D. Jannach, C. Drescher, L. Murta, T. Mannisto, K. Czarnecki, P. Heymans, T. Nguyen, and M. Zanker. 2012. Unifying software and product configuration: A researchl roadmap. In Proceedings of the ECAI 2012 Workshop on Configuration. CEUR-WS, 31--35.Google Scholar
- D. S. Johnson, M. Yannakakis, and C. H. Papadimitriou. 1988. On generating all maximal independent sets. Inform. Process. Lett. 27 (1988), 119--123. Google ScholarDigital Library
- U. Junker. 2004. QUICKXPLAIN: Preferred explanations and relaxations for over-constrained problems. In Proceedings of the 19th National Conference on Artificial Intelligence (AAAI'04). AAAI Press/MIT Press, 167--172. Google ScholarDigital Library
- U. Junker. 2006. Configuration. In Handbook of constraint programming, F. Rossi, P. van Beek, and T. Walsh (Eds.). Elsevier, 837--874.Google Scholar
- A. S. Karatas, H. Oguztüzün, and A. H. Dogru. 2010. Global constraints on feature models. In Proceedings of the 16th International Conference on Principles and Practice of Constraint Programming (CP'10). Springer, 537--551. Google ScholarDigital Library
- M. Lenzerini and P. Nobili. 1990. On the satisfiability of dependency constraints in entity-relationship schemata. Information Systems 15, 4 (1990), 453--461. Google ScholarDigital Library
- C. L. Lucchesi and S. L. Osborn. 1978. Candidate keys for relations. J. Comput. System Sci. 17, 2 (Oct. 1978), 270--279.Google ScholarCross Ref
- D. Mailharro. 1998. A classification and constraint-based framework for configuration. AI EDAM 12, 4 (1998), 383--397. Google ScholarDigital Library
- J. McDermott. 1982. R1: A rule-based configurer of computer systems. Artif. Intell. 19 (1982), 39--88.Google ScholarDigital Library
- D. L. McGuinness and J. R. Wright. 1998. Conceptual modelling for configuration: A description logic-based approach. AI EDAM 12, 4 (1998), 333--344. Google ScholarDigital Library
- S. Mittal and B. Falkenhainer. 1990. Dynamic constraint satisfaction problems. In Proceedings of the 8th National Conference on Artificial Intelligence (AAAI). AAAI Press/MIT Press, Boston, MA, 25--32. Google ScholarDigital Library
- S. Mittal and F. Frayman. 1989. Towards a generic model of configuration tasks. In Proceedings of the 11th International Conference on Artificial Intelligence (IJCAI). Morgan Kaufmann, 1395--1401. Google ScholarDigital Library
- N. Nethercote, P. J. Stuckey, R. Becket, S. Brand, G. J. Duck, and G. Tack. 2007. MiniZinc: Towards a standard CP modelling language. In Proceedings of the 13th International Conference on Principles and Practice of Constraint Programming (CP'07). Springer, 529--543. Google ScholarDigital Library
- D. Sabin and E. C. Freuder. 1996. Configuration as composite constraint satisfaction. In Proceedings of the Artificial Intelligence and Manufacturing Research Planning Workshop (AIMRP). AAAI Press, 153--161.Google Scholar
- D. Sabin and R. Weigel. 1998. Product configuration frameworks—A survey. IEEE Intelligent Systems 13, 4 (1998), 42--49. Google ScholarDigital Library
- P. Simons, I. Niemelä, and T. Soininen. 2002. Extending and implementing the stable model semantics. Artificial Intelligence 138, 1--2 (2002), 181--234. Google ScholarDigital Library
- C. Sinz, A. Kaiser, and W. Küchlin. 2003. Formal methods for the validation of automotive product configuration data. AI EDAM 17, 1 (2003), 75--97. Google ScholarDigital Library
- M. Stumptner, A. Haselböck, and G. Friedrich. 1998. Generative constraint-based configuration of large technical systems. AI EDAM 12, 4 (1998), 307--320. Google ScholarDigital Library
- E. Thorstensen. 2010. Capturing configuration. In Doctoral Program at the 16th International Conference on Principles and Practice of Constraint Programming (CP). Springer, 115--120.Google Scholar
Index Terms
- LoCo—A Logic for Configuration Problems
Recommendations
LoCo — a logic for configuration problems
ECAI'12: Proceedings of the 20th European Conference on Artificial IntelligenceLoCo is a fragment of classical first order logic tailored for expressing configuration problems. The core feature of LoCo is that the number of components used in configurations does not have to be finitely bounded explicitly, but instead is bounded ...
SCL(EQ): SCL for First-Order Logic with Equality
Automated ReasoningAbstractWe propose a new calculus SCL(EQ) for first-order logic with equality that only learns non-redundant clauses. Following the idea of CDCL (Conflict Driven Clause Learning) and SCL (Clause Learning from Simple Models) a ground literal model ...
Kolmogorov's logic of problems and a provability interpretation of intuitionistic logic
TARK '90: Proceedings of the 3rd conference on Theoretical aspects of reasoning about knowledgeIn 1932 A. N. Kolmogorov suggested an interpretation of intuitionistic logic <b>Int</b> as a "logic of problems". Then K. Gödel in 1933 offered a "provability" understanding of problems, thus, providing an abstract "provability" interpretation for <b>...
Comments