The SHOT (Supporting Hyperplane Optimization Toolkit) software recently won the annual prize of the Computational Infrastructure for Operations Research (COIN-OR) Foundation. The software is developed by Docent Andreas Lundell, University Teacher Jan Kronqvist and Professor Emeritus Tapio Westerlund at Åbo Akademi University, Finland, and can be used for optimizing real-life problems, for instance within industry or artificial intelligence.
Officially released in June 2018, the SHOT solver will find the guaranteed optimal solution for a particular type of nonlinear integer problems known as convex MINLP (Mixed-Integer NonLinear Programming) problems. The source code is open and the application is based on the ESH (Extended Supporting Hyperplane) algorithm, developed by the same team.
Convex problems have certain properties that can be utilized by solution methods, such as the ESH algorithm. The properties include the fact that a weighted average of two valid points also is a valid point.
'With the methods we've developed, the solution can be captured between an upper and a lower limit. This gives a measure for the quality of the solution, and allows the methods to guarantee that the solution found is the absolutely best possible', says Andreas Lundell, Docent at ÅAU.
Nearly all real-life problems, for instance, in industry, are nonlinear.
'This means that the problem cannot be formulated linearly. To give a simple example: Cost per unit is perhaps not the same regardless of the number of units produced, nor does it decline linearly so that the cost per unit would decrease by a certain percentage per an additional unit produced', says Jan Kronqvist, University Teacher at ÅAU.
'The new algorithms developed by our group draw advantage from the special characteristics of convex problems. If we can efficiently solve convex MINLP problems, we will also be able to solve nonconvex problems. And that again will open new opportunities for solving optimization problems within industry and ways of tackling problems within, for example, machine learning that have been impossible to solve so far,' adds Lundell.
Extensive testing has shown that SHOT is a world-class optimization solver for this type of problems. It successfully competes with both commercially available software and applications developed at other universities.
'Even if SHOT is currently primarily intended to solve convex MINLP problems, we already have a plan for extending it to be applicable to more generic optimization problems, and, all in all, we have a lot of interesting initiatives underway', says Lundell.
'We will also look into a range of special application areas within, for example, AI and system identification', adds Kronqvist.
Since optimization problems exist all over in society, there is an infinite number of potential applications for MINLP. In particular, as methods are being further developed it will be possible to move on from simplified linear models to more advanced nonlinear (MINLP) models that correspond better to real-life systems. The efficiency of SHOT and other methods developed at Åbo Akademi University will then play a key role.
###
Andreas Lundell
Docent in Applied Mathematics, Mathematics and Statistics, Åbo Akademi University
Email: andreas.lundell@abo.fi
Tel. +358 50 026 1668
Foundation is based in the USA, and aims to promote the use of open-source software within optimization and operations research (OR). The majority of the optimization-related software released nowadays fall within the scope of the COIN-OR initiative. SHOT is currently one of more than 60 COIN-OR projects. The prize was awarded on 5 November 2018 in during the annual INFORMS conference in Phoenix, USA. INFORMS is one of the largest conferences in the field with more than 5500 attendees.