Abstract
An Integer Linear Programming problem (or ILP in short) consists of finding an integer point minimizing or maximizing a linear function within a set oflinear constraints. This deceptively simple setting is however capable of representing other problems, from economics to combinatorial, scheduling and
many more. A natural extension of the Linear Programming problem would be to minimize or maximize a function that is not linear anymore but a
polynomial of degree 2 over the same constraints. This leads to the Integer Quadratic Programming problem (IQP). While there is little hope to find
a polynomial time algorithm for solving the IQP problem, not much has been said for algorithms in fixed dimension. It has only recently been proved
that the problem is solvable in dimension 2. This project gives an alternative method for solving the problem in 2 dimensions and extends it to 3 dimensions, when the constraint matrix is bounded.
| Date of Award | 1 Feb 2023 |
|---|---|
| Original language | English |
| Supervisor | Friedrich Eisenbrand (Supervisor 1) |