Solving Integer Quadratic Programming via Explicit and Structural Restrictions

Eduard Eiben, Robert Ganian, Dusan Knop, Sebastian Ordyniak

AAAI 2019 pp. 1477-1484

doi:10.1609/AAAI.V33I01.33011477 /aaai/2019/eiben2019aaai-solving/

Abstract

We study the parameterized complexity of Integer Quadratic Programming under two kinds of restrictions: explicit restrictions on the domain or coefficients, and structural restrictions on variable interactions. We argue that both kinds of restrictions are necessary to achieve tractability for Integer Quadratic Programming, and obtain four new algorithms for the problem that are tuned to possible explicit restrictions of instances that we may wish to solve. The presented algorithms are exact, deterministic, and complemented by appropriate lower bounds.

PDF AAAI Semantic Scholar

Cite

Text

Eiben et al. "Solving Integer Quadratic Programming via Explicit and Structural Restrictions." AAAI Conference on Artificial Intelligence, 2019. doi:10.1609/AAAI.V33I01.33011477

Markdown

[Eiben et al. "Solving Integer Quadratic Programming via Explicit and Structural Restrictions." AAAI Conference on Artificial Intelligence, 2019.](https://mlanthology.org/aaai/2019/eiben2019aaai-solving/) doi:10.1609/AAAI.V33I01.33011477

BibTeX

@inproceedings{eiben2019aaai-solving,
  title     = {{Solving Integer Quadratic Programming via Explicit and Structural Restrictions}},
  author    = {Eiben, Eduard and Ganian, Robert and Knop, Dusan and Ordyniak, Sebastian},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2019},
  pages     = {1477-1484},
  doi       = {10.1609/AAAI.V33I01.33011477},
  url       = {https://mlanthology.org/aaai/2019/eiben2019aaai-solving/}
}