EUVIMEDEUVIMED entdecken
Crossref

Efficient and Reliable Hitting-Set Computations for the Implicit Hitting Set Approach

Hannes Ihalainen, Dieter Vandesande, André Schidler, Jeremias Berg, Bart Bogaerts, Matti Järvisalo

Proceedings of the AAAI Conference on Artificial Intelligence · 14.03.2026 · 40 (17) · 14251-14260

DOI: 10.1609/aaai.v40i17.38439 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Proceedings of the AAAI Conference on Artificial Intelligence, online erschienen am 14.03.2026. Verfasst von Hannes Ihalainen und 5 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The implicit hitting set (IHS) approach offers a general framework for solving computationally hard combinatorial optimization problems declaratively. IHS iterates between a decision oracle used for extracting sources of inconsistency and an optimizer for computing so-called hitting sets (HSs) over the accumulated sources of inconsistency. While the decision oracle is language-specific, the optimizers is usually instantiated through integer programming. We explore alternative algorithmic techniques for hitting set optimization based on different ways of employing pseudo-Boolean (PB) reasoning as well as stochastic local search. We extensively evaluate the practical feasibility of the alternatives in particular in the context of pseudo-Boolean (0-1 IP) optimization as one of the most recent instantiations of IHS. Highlighting a trade-off between efficiency and reliability, while a commercial IP solver turns out to remain the most effective way to instantiate HS computations, it can cause correctness issues due to numerical instability; in fact, we show that exact HS computations instantiated via PB reasoning can be made competitive with a numerically exact IP solver. Furthermore, the use of PB reasoning as a basis for HS computations allows for obtaining certificates for the correctness of IHS computations, generally applicable to any IHS instantiation in which reasoning in the declarative language at hand can be captured in the PB-based proof format we employ.

Zitieren

APA

Ihalainen, H., Vandesande, D., Schidler, A., Berg, J., Bogaerts, B., & Järvisalo, M. (2026). Efficient and Reliable Hitting-Set Computations for the Implicit Hitting Set Approach. Proceedings of the AAAI Conference on Artificial Intelligence, 40(17), 14251-14260. https://doi.org/10.1609/aaai.v40i17.38439

Vancouver

Ihalainen H, Vandesande D, Schidler A, Berg J, Bogaerts B, Järvisalo M. Efficient and Reliable Hitting-Set Computations for the Implicit Hitting Set Approach. Proceedings of the AAAI Conference on Artificial Intelligence. 2026;40(17):14251-14260. doi:10.1609/aaai.v40i17.38439

BibTeX
@article{Ihalainen2026,
  author = {Ihalainen, Hannes and Vandesande, Dieter and Schidler, André and Berg, Jeremias and Bogaerts, Bart and Järvisalo, Matti},
  title = {Efficient and Reliable Hitting-Set Computations for the Implicit Hitting Set Approach},
  journal = {Proceedings of the AAAI Conference on Artificial Intelligence},
  year = {2026},
  volume = {40},
  number = {17},
  pages = {14251--14260},
  doi = {10.1609/aaai.v40i17.38439}
}
Kostenlos starten →