AAAI

Association for the Advancement of Artificial Intelligence

Home > Proceedings / Proceedings of the AAAI Conference on Artificial Intelligence, 33 > No. 1: AAAI-19, IAAI-19, EAAI-20

Solving Integer Quadratic Programming via Explicit and Structural Restrictions

Authors

Eduard Eiben

University of Bergen


Robert Ganian

Vienna University of Technology


Dusan Knop

TU Berlin


Sebastian Ordyniak

University of Sheffield


Proceedings:

No. 1: AAAI-19, IAAI-19, EAAI-20

Volume

Issue:

Proceedings of the AAAI Conference on Artificial Intelligence, 33

Track:

AAAI Technical Track: Constraint Satisfaction and Optimization

Downloads:

Download PDF

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.

DOI:

10.1609/aaai.v33i01.33011477


AAAI

Proceedings of the AAAI Conference on Artificial Intelligence, 33