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.
Last updated: 2024-04-11 18:16