Cunjing Dr. Ge, Armin Biere,
"Decomposition Strategies to Count Integer Solutions over Linear Constraints"
: Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21), ijcai.org 2021, Seite(n) 1389-1395, 1-2021
Original Titel:
Decomposition Strategies to Count Integer Solutions over Linear Constraints
Sprache des Titels:
Englisch
Original Buchtitel:
Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence (IJCAI-21)
Original Kurzfassung:
Counting integer solutions of linear constraints hasfound interesting applications in various fields. Itis equivalent to the problem of counting integerpoints inside a polytope. However, state-of-the-artalgorithms for this problem become too slow foreven a modest number of variables. In this paper,we propose new decomposition techniques whichtarget both the elimination of variables as well asinequalities using structural properties of countingproblems. Experiments on extensive benchmarksshow that our algorithm improves the performanceof state-of-the-art counting algorithms, while theoverhead is usually negligible compared to the run-ning time of integer counting.
Forschungs-