Designing better algorithms by testing them with hard problems
A new research project led by Luca Gambardella, professor at the Dalle Molle Institute for Artificial Intelligence IDSIA (USI-SUPSI) and Pro-Rector for Innovation and Corporate Relations, has been approved by the Swiss National Science Foundation (SNSF) . The study entitled 'Computational methods for integrality gaps analysis' approaches the optimisation of algorithms to deal with complex problems from an innovative and original perspective. The project, with a planned duration of four years, with one postdoctoral researcher and two PhD students, is conducted in collaboration with Professor Monaldo Mastrolilli of SUPSI, who is also a member of IDSIA (USI-SUPSI). The research is inspired by recent advances in algorithms that combine artificial intelligence techniques and approximate/exact methods. But instead of studying the algorithms, it changes the perspective because it aims to undermine them by generating systematically and mathematically sound problem-solving instances. Professor Gambardella, what is meant by complex problems? The 'complexity theory'', as defined by Oxford Languages, studies systems made up of a very large number of elements that interact through defined rules and are subject to certain constraints. The aim is to understand global behaviour and predict the evolution of these systems. In mathematics, one tries to determine the minimum number of operations required to solve such problems. A research topic in this area concerns the measurement of the complexity of a problem by evaluating it according to the number of operations required to solve an instance of it in relation to the amount of input data. A number of operations which I imagine could be very high.
