IMDEA Software researcher Alessio Mansutti’s paper “Integer Linear-Exponential Programming in NP by Quantifier Elimination”, coauthored by Dmitry Chistikov and Mikhail Starchak, won the Track B Best Paper Award at the International Colloquium on Automata, Languages, and Programming (ICALP) 2024, which is a flagship research meeting.
Can you give
where
The problem above (which, by the way, has a solution:
where
ILP is a fundamental problem in computer science, and after many decades of research and engineering we now have efficient software to solve this problem. Finding the best route for a driver to bring a parcel at your address? That’s solved with ILP. Scheduling aircrafts, their routes, and their crew members? Airlines use ILP not only for these tasks, but also for optimising ticket pricing! How do banks quantify the risk involved when lending money to a borrower? They use ILP solvers. How are the available frequencies in GSM mobile networks distributed across antennas so that interference is minimised? ILP! Whenever companies need to solve a difficult planning problem, their rely on ILP.
There are problems that cannot be solved with ILP. Let us take for instance the following program
Input: an integer
Output: an integer
while
end while
return
This program takes as input a positive integer
where
Many techniques to prove that programs do not contain bugs require putting together several systems of constraints as the one above and check whether the resulting system has a solution. We face however a major problem: the exponential function cannot be expressed in ILP. How can we then check if the system has a solution? Is this even possible to check?
The above is an instance of the Integer Linear-Exponential Programming problem: is it possible to assign integer values to variables
where
Want to know more? Check out the paper!
The International Colloquium on Automata, Languages and Programming (ICALP) is the flagship conference and annual meeting of the European Association for Theoretical Computer Science (EATCS). The conference was launched in 1972, and this year was its 51st edition. It took place in Tallinn, Estonia, on the 8th to 12th of July 2024.