SAMK researchers set a new world record in mathematical optimization

SAMK researchers Cimmo Nurmi and Nico Kyngäs set a new record in mathematical optimization. The target of the optimization was a data set of the 47 most difficult instances of the so-called SMPTSP problem. Top scientists have been trying to solve and find superior solutions for the instances. The problem was published in 2001. Earlier this year, a Belgian research team published a matheuristic method, which was able to find the optimal solutions to 42 instances. The earlier record of 40 solutions was published in 2014. The novel metaheuristic method of SAMK researchers was able to find the optimal solutions to 44 instances.

The results of SAMK researchers were reached as a by-product when solving a much more complicated real-world optimization problem. In this practical problem the workers visit the clients to carry out tasks with specific time windows. The workers have specific skill sets, transportation types and availability intervals. Examples of such work include cleaning, home care, guarding, manufacturing, installation services, waste management and delivery of goods. SMPTSP is a scientific special case of these practical problems – even thousands of tasks need to be assigned to hundreds of workers in such a way that minimizes the number of workers to be used.

World record by cooperation between two computational intelligence algorithms

The world record was set by cooperation between two computational intelligence algorithms. The first one is a variation of the R&R algorithm developed by Nico Kyngäs in his ongoing Ph.D. studies. The second one is the PEASTP algorithm, the basis of which was created on the Ph.D. thesis of Cimmo Nurmi, and which was further developed by Jari Kyngäs in his own Ph.D. thesis. The researchers have earlier published excellent scientific and practical optimization results in workforce scheduling, professional sports league scheduling (e.g. the Finnish Major Ice-Hockey League and the Australian Football League) and several theoretical combinatorial problems.

Computational Intelligence is a type of Artificial Intelligence which applies computational methods inspired by Nature, such as evolutionary algorithms, ant algorithms and swarm intelligence. This type of AI focuses on solving extremely complicated problems which require massive computer power. The generated solutions for these problems are way beyond the reach of human intelligence.

Another type of AI solves problems which require cognitive skills, such as pattern recognition, machine vision, speech recognition, decision-making and learning. These type of problems are solved using neural networks.

For more information:
Cimmo Nurmi,
Vice President for Research, Satakunta University of Applied Sciences
cimmo.nurmi@samk.fi
tel. +358 44 710 3371