Project: HYPAR - Hybrid Parameterized Problem Solving in Practice
(funded by the Austrian Science Fund (FWF) under grant P 32830)
Contents
News
Runner-Up for Best Student Paper at ICAPS'23
2023-07Our publication on Grounding and Planning using Tree Decompositions was the runner-up for the Best Student Paper award at ICAPS 2023. The publication is a follow-up work on body-decoupled grounding and provides insights on how to efficiently utilize structure for planning.
ICAPS'23 and ICGCA'23 Competition Awards
2023-07Recently, team member Markus Hecher co-won the International Planning Competition (ICAPS 2023, satisficing track) as well as the International Path Counting Competition (ICGCA 2023) for their excellent solvers. Both competition awards were possible because of follow-up techniques that were developed from recent findings of the project.
Recent Awards for Markus Hecher
2022-09Recently, Markus Hecher has won the EurAI dissertation award 2021, as well as the GI Dissertationspreis 2021 for his excellent PhD thesis. Further, for his contributions in KR and AI so far, he received the KR Early Career Award 2022.
Erwin Schrödinger Research Funding
2022-03An Erwin Schrödinger Research Funding was granted to team member Markus Hecher. He will work on his project "QuantASP - Quantitatives Schlussfolgern und Zählen für ASP" (translation: quantitative reasoning and counting for ASP) at the "Computer Science and Artificial Intelligence Laboratory" at M.I.T. (Massachusetts Institute of Technology).
Dissertation Award of excellence
2021-12Team member Markus Hecher defended his PhD thesis "Advanced tools and methods for treewidth-based problem solving" and received the award of excellence from the Austrian ministry of education, science, and research.
Accepted Papers at CP and KR
2021-10We are happy to announce that two papers by team members have been accepted to this year's International Conference on Principles and Practice of Constraint Programming (CP 2021) and another two papers (one long, one short) at the International Conference on Principles of Knowledge Representation and Reasoning (KR 2021).
Best Paper Awards at ICLP'21
2021-09
We are pleased to announce that team members Viktor Besin and Markus Hecher and PI Stefan Woltran won the Best Paper Award and Best Student Paper Award with their paper Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic Programs at the International Conference on Logic Programming ICLP 2021.
Bachelor and Master Theses of Team Members
2021-04
Team member Viktor Besin successfully defended his bachelor thesis, and team member Matthias König successfully defended his
master thesis.
Congratulations!
Winner of the Marco Cadoli Best Student Paper Award 2020
2020-10
We are pleased to announce that team member Markus Hecher won the prestigious
Marco Cadoli Best Student Paper Award at KR 2020.
A detailed news report in German can be found at the website of TU Wien.
Co-Organization of ASPOCP 2020
2020-07The 13th edition of the Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP 2020) will be co-organized by project member Markus Hecher. Information of the workshop is available at the ASPOCP 2020 website.
CP 2020 and KR 2020: Accepted Papers
2020-07We are grateful to announce that in total we got three accepted papers for CP 2020. Further, our work entitled "Treewidth-Aware Reductions of normal ASP to SAT – Is normal ASP harder than SAT after all?" got accepted for publication at the KR conference in Rhodes.
Co-Organization of MC 2020 and MCW 2020
2020-07We are delighted to report that the first international competition on model counting (MC 2020) as well as the first international workshop on model counting (MCW 2020) were a success! Details of the results can be found online at mccompetition.org. Both events were co-organized by project member Markus Hecher.
LICS 2020 and SAT 2020: Published Papers
2020-07We gladly announce that our recent study on Lower Bounds for QBFs of Bounded Treewidth got accepted for publication at the virtual conference LICS 2020. Further, we were able to present our work on "Taming High Treewidth with Abstraction, Nested Dynamic Programming, and Database Technology" at the SAT 2020 conference.
Recent Journal Publications
2020-07We are proud to announce that this project resulted in two recent journal publications. Both works "Complexity of abstract argumentation under a claim-centric view" and "Solving Advanced Argumentation Problems with Answer Set Programming" provide new insights for abstract argumentation.
Research Visit in Bergen
2020-02
We were able to pay our project partner Jan Arne Telle and Martin Vatshelle
a visit in Bergen.
Thanks for the fruitful cooperation!
AAAI 2020: Accepted Papers
2020-01We are delighted to announce that our work on Structural Decompositions of Epistemic Logic Programs has been accepted for presentation at this year's AAAI conference in New York.
Project started
2019-10The project officially started on October 1, 2019 and will have a duration of three years.
TopGoal of the Project
Solving computationally hard problems is a key challenge in computer science. One approach towards efficient solutions relies on decomposing the problem instances into smaller parts and solving the problem step-by-step by solving parts (subproblems) via a dedicated algorithm. This dedicated algorithm then suitably combines solutions of the single parts into a solution of the problem. One particular form of this method is known as dynamic programming over tree decompositions. The runtime of this approach mainly depends on a certain parameter, namely the size of the largest subproblem, which can be obtained via tree decompositions satisfying certain criteria. The common hypothesis for this approach is that the smaller the parts obtained by the decomposition are, the faster the problem at hand can be solved. However, practical experiments have shown that this theoretical rule of thumb does not necessarily apply in practice.
Our working hypothesis is that decompositions with larger subproblems might be beneficial in practice, in particular if dedicated algorithms are used to solve subproblems. Therefore, we call this approach hybrid since it relies on both standard approaches for the subproblems and the dedicated dynamic programming machinery for combining solutions to subproblems. In this project, we aim to better understand which "shapes" of decompositions provide the best results in practice, and to study methods on how to find these decompositions. In the course of the project, we will focus on several prominent problems in computer science, ranging from Boolean satisfiability (SAT) and extensions thereof, Satisfiability on Quantified Boolean Formulas (QSAT) as well as Answer Set Programming (ASP, also known as disjunctive datalog).
TopProject Team
National project partners
International project partners
Systems and Tools
Systems delivered and extended in course of the project are publicly available.
Software
- dpdb: Dpdb is a flexible framework allowing for rapid prototyping of dynamic programming algorithms over tree decompositions making use of database technology. The tree decomposition is generated via heuristics and the developer specifies the dynamic programming algorithm by means of providing an SQL generator in Python.
- nesthdb: Nesthdb is an extension of dpdb that allows to formulate algorithms by means of nested dynamic programming. Thereby, abstractions are decomposed and subsequently refined and solved using standard problem solving tools like SAT solvers.
- newground: Newground is an alternative grounding technique that is capable of grounding rules with large bodies efficiently. It benefits from the interplay with standard grounders (e.g., gringo or idlv), thereby providing an efficient combination of grounding strategies that aims at the best of both worlds.
Publications
Here, we provide a list of all project publications.2023
- On the Structural Complexity of Grounding - Tackling the ASP Grounding Bottleneck via Epistemic Programs and Treewidth In 26th European Conference on Artificial Intelligence (ECAI), pages 247-254, 2023.
[ BibTeX ] - Foundations for Projecting Away the Irrelevant in ASP Programs In 20th International Conference on Principles of Knowledge Representation and Reasoning, KR 2023, pages 614-624, 2023.
[ BibTeX | doi ] - The Impact of Structure in Answer Set Counting: Fighting Cycles and its Limits In 20th International Conference on Principles of Knowledge Representation and Reasoning (KR), pages 344-254, 2023.
[ BibTeX ] - Quantitative Reasoning and Structural Complexity for Claim-Centric Argumentation In 32nd International Joint Conference on Artificial Intelligence (IJCAI), pages 3212-3220, ijcai.org, 2023.
[ BibTeX ] - Treewidth-Aware Complexity for Evaluating Epistemic Logic Programs In 32nd International Joint Conference on Artificial Intelligence (IJCAI), pages 6312-6320, ijcai.org, 2023.
[ BibTeX ] - Structure-Aware Lower Bounds and Broadening the Horizon of Tractability for QBF In 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1-14, 2023.
[ BibTeX ] - Grounding Planning Tasks Using Tree Decompositions and Iterated Solving In 33rd International Conference on Automated Planning and Scheduling, pages 100-108, 2023.
[ BibTeX ] - Inconsistent Cores for ASP: The Perks and Perils of Non-Monotonicity In 37th AAAI Conference on Artificial Intelligence, pages 6363-6371, 2023.
[ BibTeX ] - The Effect of Preferences in Abstract Argumentation under a Claim-Centric View In 37th AAAI Conference on Artificial Intelligence, pages 6253-6261, AAAI Press, 2023.
[ BibTeX | doi ] - Characterizing Structural Hardness of Logic Programs: What makes Cycles and Reachability Hard for Treewidth? In 37th AAAI Conference on Artificial Intelligence, pages 6407-6415, 2023.
[ BibTeX ] - Expressiveness of SETAFs and support-free ADFs under 3-valued semantics In J. Appl. Non Class. Logics, 33 (3-4): 298-327, 2023.
[ BibTeX | doi ] - A claim-centric perspective on abstract argumentation semantics: Claim-defeat, principles, and expressiveness In Artif. Intell., 324: 104011, 2023.
[ BibTeX | doi ] - The complexity landscape of claim-augmented argumentation frameworks In Artif. Intell., 317: 103873, 2023.
[ BibTeX | doi ] - Solving Projected Model Counting by Utilizing Treewidth and its Limits In Artif. Intell., 314: 103810, 2023.
[ BibTeX ]
2022
- Advanced Tools and Methods for Treewidth-Based Problem Solving IOS Press, Frontiers in Artificial Intelligence and Applications 359, 2022.
Available at IOS Press
[ BibTeX | www ] - Rediscovering Argumentation Principles Utilizing Collective Attacks In Proceedings of the 19th International Conference on Principles of Knowledge Representation and Reasoning, KR 2022, Haifa, Israel. July 31 - August 5, 2022, 2022.
[ BibTeX ] - Just a Matter of Perspective In Computational Models of Argument - Proceedings of COMMA 2022, Cardiff, Wales, UK, 14-16 September 2022, Volume 353 of Frontiers in Artificial Intelligence and Applications, pages 212-223, IOS Press, 2022.
[ BibTeX | doi ] - Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic Programs (Extended Abstract) In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, pages 5264-5268, ijcai.org, 2022.
[ BibTeX | doi ] - Body-Decoupled Grounding via Solving: A Novel Approach on the ASP Bottleneck In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, pages 2546-2552, ijcai.org, 2022.
[ BibTeX | doi ] - Tractable Abstract Argumentation via Backdoor-Treewidth In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22 - March 1, 2022, pages 5608-5615, AAAI Press, 2022.
[ BibTeX ] - Recursion in Abstract Argumentation is Hard - On the Complexity of Semantics Based on Weak Admissibility In J. Artif. Intell. Res., 74: 1403-1447, 2022.
[ BibTeX | doi ] - Deletion-Backdoors for Argumentation Frameworks with Collective Attacks In Proceedings of the Fourth International Workshop on Systems and Algorithms for Formal Argumentation co-located with the 9th International Conference on Computational Models of Argument (COMMA 2022), Cardiff, Wales, United Kingdom, September 13, 2022, Volume 3236 of CEUR Workshop Proceedings, pages 98-110, CEUR-WS.org, 2022.
[ BibTeX ] - Treewidth for Argumentation Frameworks with Collective Attacks In Computational Models of Argument - Proceedings of COMMA 2022, Cardiff, Wales, UK, 14-16 September 2022, Volume 353 of Frontiers in Artificial Intelligence and Applications, pages 140-151, IOS Press, 2022.
[ BibTeX | doi ] - Plausibility Reasoning via Projected Answer Set Counting - A Hybrid Approach In Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, pages 2620-2626, ijcai.org, 2022.
[ BibTeX | doi ] - Default logic and bounded treewidth In Inf. Comput., 283: 104675, 2022.
[ BibTeX | doi ] - IASCAR: Incremental Answer Set Counting by Anytime Refinement In Logic Programming and Nonmonotonic Reasoning - 16th International Conference, LPNMR 2022, Genova, Italy, September 5-9, 2022, Proceedings, Volume 13416 of Lecture Notes in Computer Science, pages 217-230, Springer, 2022.
[ BibTeX | doi ] - A Practical Account into Counting Dung's Extensions by Dynamic Programming In Logic Programming and Nonmonotonic Reasoning - 16th International Conference, LPNMR 2022, Genova, Italy, September 5-9, 2022, Proceedings, Volume 13416 of Lecture Notes in Computer Science, pages 387-400, Springer, 2022.
[ BibTeX | doi ] - Proofs for Propositional Model Counting In 25th International Conference on Theory and Applications of Satisfiability Testing, SAT 2022, August 2-5, 2022, Haifa, Israel, Volume 236 of LIPIcs, pages 30:1-30:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.
[ BibTeX | doi ] - Exploiting Database Management Systems and Treewidth for Counting In Theory Pract. Log. Program., 22 (1): 128-157, 2022.
[ BibTeX | doi ] - ApproxASP - a Scalable Approximate Answer Set Counter In Thirty-Sixth AAAI Conference on Artificial Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intelligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, EAAI 2022 Virtual Event, February 22 - March 1, 2022, pages 5755-5764, AAAI Press, 2022.
[ BibTeX ] - Advanced Tools and Methods for Treewidth-Based Problem Solving IOS Press, Frontiers in Artificial Intelligence and Applications 359, 2022.
[ BibTeX | www ] - Treewidth-aware reductions of normal ASP to SAT - Is normal ASP harder than SAT after all? In Artif. Intell., 304: 103651, 2022.
[ BibTeX | doi ]
2021
- The Model Counting Competition 2020 In ACM Journal of Experimental Algorithmics, 26 (1), 2021.
[ BibTeX ] - Utilizing Treewidth for Quantitative Reasoning on Epistemic Logic Programs In Theory and Practice of Logic Programming, 21 (5): 575-592, 2021.
[ BibTeX | doi ] - On the Complexity of Preferred Semantics in Argumentation Frameworks with Bounded Cycle Length In Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning, KR 2021, Online event, November 3-12, 2021, pages 671-675, 2021.
[ BibTeX | doi ] - Treewidth-Aware Cycle Breaking for Algebraic Answer Set Counting In Proceedings of the 18th International Conference on Principles of Knowledge Representation and Reasoning, KR 2021, Online event, November 3-12, 2021, pages 269-279, 2021.
[ BibTeX | doi ] - aspmc: An Algebraic Answer Set Counter In Proceedings of the International Conference on Logic Programming 2021 Workshops co-located with the 37th International Conference on Logic Programming (ICLP 2021), Porto, Portugal (virtual), September 20th-21st, 2021, Volume 2970 of CEUR Workshop Proceedings, CEUR-WS.org, 2021.
[ BibTeX ] - Parallel Model Counting with CUDA: Algorithm Engineering for Efficient Hardware Utilization In 27th International Conference on Principles and Practice of Constraint Programming, CP 2021, Montpellier, France (Virtual Conference), October 25-29, 2021, Volume 210 of LIPIcs, pages 24:1-24:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
[ BibTeX | doi ] - Complications for Computational Experiments from Modern Processors In 27th International Conference on Principles and Practice of Constraint Programming, CP 2021, Montpellier, France (Virtual Conference), October 25-29, 2021, Volume 210 of LIPIcs, pages 25:1-25:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
[ BibTeX | doi ] - Decomposition-Guided Reductions for Argumentation and Treewidth In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual Event / Montreal, Canada, 19-27 August 2021, pages 1880-1886, ijcai.org, 2021.
[ BibTeX | doi ] - Knowledge-Base Degrees of Inconsistency: Complexity and Counting In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pages 6349-6357, AAAI Press, 2021.
[ BibTeX ] - Treewidth-Aware Complexity in ASP: Not all Positive Cycles are Equally Hard In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pages 6312-6320, AAAI Press, 2021.
[ BibTeX ] - The Complexity Landscape of Claim-Augmented Argumentation Frameworks In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pages 6296-6303, AAAI Press, 2021.
[ BibTeX ] - DynASP2.5: Dynamic Programming on Tree Decompositions in Action In Algorithms, 14 (3): 81, 2021.
[ BibTeX | doi ] - Graph-Classes of Argumentation Frameworks with Collective Attacks In Logics in Artificial Intelligence - 17th European Conference, JELIA 2021, Virtual Event, May 17-20, 2021, Proceedings, Volume 12678 of Lecture Notes in Computer Science, pages 3-17, Springer, 2021.
[ BibTeX | doi ]
2020
- Solving the Steiner Tree Problem with few Terminals In 32nd IEEE International Conference on Tools with Artificial Intelligence, ICTAI 2020, Baltimore, MD, USA, November 9-11, 2020, pages 293-300, IEEE, 2020.
[ BibTeX | doi ] - lpopt: A Rule Optimization Tool for Answer Set Programming In Fundam. Informaticae, 177 (3-4): 275-296, 2020.
[ BibTeX | doi ] - Computational Argumentation - Formal Models and Complexity Results (invited talk) In Proceedings of the 35th Italian Conference on Computational Logic - CILC 2020, Rende, Italy, October 13-15, 2020, Volume 2710 of CEUR Workshop Proceedings, pages 2, CEUR-WS.org, 2020.
[ BibTeX ] - Treewidth-aware Reductions of Normal ASP to SAT - Is Normal ASP Harder than SAT after All? In Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning (KR 2020), pages 485-495, 2020.
[ BibTeX | doi ] - A Time Leap Challenge for SAT-Solving In Principles and Practice of Constraint Programming - 26th International Conference, CP 2020, Louvain-la-Neuve, Belgium, September 7-11, 2020, Proceedings, Volume 12333 of Lecture Notes in Computer Science, pages 267-285, Springer, 2020.
[ BibTeX | doi ] - Breaking Symmetries with RootClique and LexTopSort In Principles and Practice of Constraint Programming - 26th International Conference, CP 2020, Louvain-la-Neuve, Belgium, September 7-11, 2020, Proceedings, Volume 12333 of Lecture Notes in Computer Science, pages 286-303, Springer, 2020.
[ BibTeX | doi ] - Treewidth-Aware Quantifier Elimination and Expansion for QCSP In Principles and Practice of Constraint Programming - 26th International Conference, CP 2020, Louvain-la-Neuve, Belgium, September 7-11, 2020, Proceedings, Volume 12333 of Lecture Notes in Computer Science, pages 248-266, Springer, 2020.
[ BibTeX | doi ] - selp: A Single-Shot Epistemic Logic Program Solver In Theory Pract. Log. Program., 20 (4): 435-455, 2020.
[ BibTeX | doi ] - Lower Bounds for QBFs of Bounded Treewidth In LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, Saarbrücken, Germany, July 8-11, 2020, pages 410-424, 2020.
[ BibTeX | doi ] - Taming High Treewidth with Abstraction, Nested Dynamic Programming, and Database Technology In Theory and Applications of Satisfiability Testing - SAT 2020 - 23rd International Conference, Alghero, Italy, July 3-10, 2020, Proceedings, pages 343-360, 2020.
[ BibTeX | doi ] - Solving Advanced Argumentation Problems with Answer Set Programming In Theory Pract. Log. Program., 20 (3): 391-431, 2020.
[ BibTeX | doi ] - Complexity of abstract argumentation under a claim-centric view In Artif. Intell., 285: 103290, 2020.
[ BibTeX | doi ] - The Impact of Treewidth on Grounding and Solving of Answer Set Programs In J. Artif. Intell. Res., 67: 35-80, 2020.
[ BibTeX | doi ] - Exploiting Database Management Systems and Treewidth for Counting In 22nd Symposium on Practical Aspects of Declarative Languages (PADL), Volume 12007 of Lecture Notes in Computer Science, pages 151-167, Springer, 2020.
[ BibTeX ] - Structural Decompositions of Epistemic Logic Programs In The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pages 2830-2837, AAAI Press, 2020.
[ BibTeX ]
Last updated: 2024-04-11 18:16