Solving Integer Quadratic Programming via Explicit and Structural Restrictions

Eduard Eiben; Robert Ganian; Dusan Knop; Sebastian Ordyniak

doi:10.1609/aaai.v33i01.33011477

Solving Integer Quadratic Programming via Explicit and Structural Restrictions

Eduard Eiben, Robert Ganian, Dusan Knop, Sebastian Ordyniak

Research output: Contribution to conference › Paper › peer-review

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.

Original language	English
Pages	1477-1484
Number of pages	8
DOIs	https://doi.org/10.1609/aaai.v33i01.33011477
Publication status	Published - 17 Jul 2019
Event	The Thirty-Third AAAI Conference on Artificial Intelligence - Honolulu, United States Duration: 27 Jan 2019 → 1 Feb 2019 https://aaai.org/Conferences/AAAI-19/

Conference

Conference	The Thirty-Third AAAI Conference on Artificial Intelligence
Abbreviated title	AAAI 2019
Country/Territory	United States
City	Honolulu
Period	27/01/19 → 1/02/19
Internet address	https://aaai.org/Conferences/AAAI-19/

Access to Document

10.1609/aaai.v33i01.33011477

Cite this

@conference{cc4bd6cc3156460493373d05070fef56,

title = "Solving Integer Quadratic Programming via Explicit and Structural Restrictions",

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.",

author = "Eduard Eiben and Robert Ganian and Dusan Knop and Sebastian Ordyniak",

year = "2019",

month = jul,

day = "17",

doi = "10.1609/aaai.v33i01.33011477",

language = "English",

pages = "1477--1484",

note = "The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019 ; Conference date: 27-01-2019 Through 01-02-2019",

url = "https://aaai.org/Conferences/AAAI-19/",

}

TY - CONF

T1 - Solving Integer Quadratic Programming via Explicit and Structural Restrictions

AU - Eiben, Eduard

AU - Ganian, Robert

AU - Knop, Dusan

AU - Ordyniak, Sebastian

PY - 2019/7/17

Y1 - 2019/7/17

N2 - 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.

AB - 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.

U2 - 10.1609/aaai.v33i01.33011477

DO - 10.1609/aaai.v33i01.33011477

M3 - Paper

SP - 1477

EP - 1484

T2 - The Thirty-Third AAAI Conference on Artificial Intelligence

Y2 - 27 January 2019 through 1 February 2019

ER -