3.12.2018
Jan Kronqvist, Anders Lundell and Tapio Westerlund are the creators of SHOT, the world’s fastest optimization tool. The program makes it possible to solve problems within artificial intelligence that so far have been unsolvable.
Optimization is a special area within Mathematics and Engineering. The idea of optimization is to find the best possible – or a sufficiently good – solution to a problem given in the form of a mathematical description of a system or process.
‘Currently, there are several optimization methods that only provide a possible solution without giving any idea of its goodness as compared to the absolutely optimal one. In some cases, this is enough’, explains Jan Kronqvist, University Teacher in Process and Systems Engineering at Åbo Akademi University.
What is a sufficiently good solution is determined by the application or the user, but it may be difficult to decide it in advance.
‘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 the best possible solution will be found at a point where the upper and lower limits meet’, says Andreas Lundell, Docent at Åbo Akademi University.
Optimization problems may relate to practically any field in real life. For example, the problem may concern the drawing up of the best possible production plan for manufacturing goods; an optimized process will not only be more efficient but also cut down wastage and energy costs, increase profitability and reduce environmental load. Or, radiation therapy can be optimized to provide maximal effect with minimal risk while also saving time. Or, as a variation of a classic optimization problem explained below, the problem may be how to find the shortest route between two cities.
Travelling salesman problem
For computational optimization, it is necessary to describe the problem in mathematical terms for an analysis.
The travelling salesman problem is an example often used in teaching but it also has many practical implications. The problem is as follows: A travelling salesman is expected to visit a certain number of cities, and the task is to find the shortest route for visiting each city and returning to the original city.
It should be pointed out that this problem only concerns the shortest route, that is, only the distance is considered. It is, however, also possible to consider such aspects as the accessibility of different roads depending on the season, time of day or traffic, or what is the optimal vehicle.
A reasonable question: Why not simply test all routes in order to find the shortest way?
The answer: If the problem is simple or small, this would be a reasonable approach. For example, if the task is to find the quickest way of visiting four cities and finally return to the start, there are three different routes available. If there are five cities to visit, the number of alternative routes increases to 12, but if you increase the number of cities to 10, there will be 181,440 possible routes. For 15 cities, there are 43,589,145,600 possible routes and for 20 cities, the number rises to 60,822,550,204,416,000. When the number of variables increases, even supercomputers will be in trouble. In order to solve the optimization problem by using pure ‘brute-force’ computation, it is necessary to formulate the problem in a sufficiently uncomplicated form which, in reality, often calls for a crude simplification.
‘Mathematically speaking, optimization problems deal with finding either a minimum or a maximum of a function known as the ‘objective function’ within the context of certain given restrictions known as “constraints”’, says Jan Kronqvist.
‘An example of an objective function is how to obtain the greatest possible profit with a given constraint that describes resource-related restrictions, such as raw material costs.’
MILP and MINLP
Integer variables are characterized by that their values are always given as integers. A special case of integer variables are binary variables, which can only take the value of ‘yes’ or ‘no’ (or: ‘1’ or ‘0’). For example: How many cars is it profitable to manufacture? In terms of profitability, how many assembly lines can be in operation at the same time? The answers to these questions are given as integers – there is no point in producing one quarter of a car or building just a half of an assembly line. The simplest category of integer optimization problems with integer variables fall under the scope of MILP (Mixed-Integer Linear Programming) and can today be effectively solved by means of computational software.
‘MILP can also give answers to questions involving sequential orders, for example, what is the most profitable order for completing different processes when manufacturing a certain product, just to name one example’, explains Andreas Lundell.
However, MILP problems are limited by the requirement that all functions, both the objective functions and constraints, must be linear. The simplest form of the travelling salesman problem is a typical MILP type problem, but as soon as any constraints, such as fuel efficiency, are included, the problem becomes much more difficult to solve.
‘A fact is that nearly all real-life problems, for instance, in industry, are nonlinear. It means that the problem cannot be formulated linearly. To give a simple example: Cost per unit is 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.’
These considerably more complex problems fall within the scope of nonlinear integer optimization, MINLP (Mixed-Integer NonLinear Programming). Examples of this type of optimization problems are numerous. They may deal with the optimization of, among other things, cancer treatment, operation of nuclear reactors, design of heat exchanger networks, production or portfolio optimization, as well as diverse problems related to machine learning and artificial intelligence (AI). The common aspect for these is that they are extremely difficult optimization problems.
Convex problems
In recent years, the subjects of Process and Systems Engineering, Mathematics and Statistics at Åbo Akademi University have focused on developing methods related to a particular type of nonlinear integer problems known as convex MINLP problems.
Convex problems refer to nonlinear functions that have certain properties, including the fact that if you draw a line between two points on the function graph then the entire line lies above the graph. In practice, these problems are simpler but unfortunately it is extremely difficult to determine in advance if a problem is convex or not. To explain what exactly makes a problem convex would call for a two-hour lecture on Mathematics.
Many problems, however, can be formulated as convex problems.
‘The new algorithms developed by our group draw advantage from the special characteristics of convex problems. Moreover, we combine and utilize the advances made in other areas of optimization, within MILP, for example. 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 so far.’
SHOT
One important step in this evolution is the software known as SHOT (The Supporting Hyperplane Optimization Toolkit) developed by Lundell, Kronqvist and Professor emeritus Tapio Westerlund. Officially released in June 2018, the SHOT solver will find the guaranteed optimal solution for convex MINLP problems. The source code is open and the application is based on the ESH (Extended Supporting Hyperplane) algorithm, developed by the same team.
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 outstanding universities, including Carnegie Mellon University, MIT and Princeton.
‘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 indefinite number of potential applications for MINLP. In particular, as methods are being further developed it will be possible to move on from simplified MILP models to more advanced 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.
Advances in integer optimization from 1988 to 2017:
– Improved algorithms and methods: 147,650 times faster
– Improved computing power: 17,120 times faster
– Overall improvement: 2,527,768,000 times faster
In practice, this means that solving a typical MILP problem would have taken 80 years back in 1988, whereas today it only takes one second. However, while MILP problem solving is nowadays standard technology, MINLP problems still pose a challenge.This is motivating and inspiring researchers in the field.
Background
At Åbo Akademi University, the research within MINLP optimization started in the 1990s under the leadership of Professor Tapio Westerlund. A total of 16 doctoral candidates have earned their PhD in this area, most recently Jan Kronqvist.
The internationally renowned group has established a strong network and is closely collaborating with the globally leading researchers in the field. Among them are:
Prof. Ignacio Grossman at Carnegie Mellon University, USA, Doctor h.c. at Åbo Akademi University (h-index 114)
Prof. Nick Sahinidis at Carnegie Mellon University, USA
Prof. Leo Liberti at École Polytechnique, France
Over the years, the group collaborated with Professor Christodoulus Floudas at Princeton University and Texas A&M University, USA, and Doctor h.c. at ÅAU (h-index 96). Regrettably, Prof. Floudas passed away, too early, a couple of years ago. However, collaboration continues with one of his students, Doctor Ruth Misener who is currently working at Imperial College London, UK.