## When the “Optimal” Solution Isn’t the “Best” Solution

By Robert Hickingbotham, Monash University

Suppose you are organising a conference at Melbourne Uni featuring some world-class mathematicians. People from all across Melbourne are interested in coming along to this event in order to hear the latest research that will be presented by these great mathematicians. However, most of the guests aren’t able to drive there and will need to be picked up by somebody else. The question the organisers want answered is this: is how do we best allocate passenger to the different cars in order to minimise the overall driving time? Questions like these, where we have something we want to either minimise or maximise as a function of integer variables (here, total time of drivers on the road) while satisfying a set of constraints (here, we need to ensure that each passengers is able to get to the conference) are classified as Integer-Programming (IP) problems. Now IP problems are NP-Hard; that is, the computational time to determine the optimal solution to the problem increases exponentially with the size of the problem. This means that for large scale IP problems, it may take a computer and an infeasibly long period of time to actually determine the optimal solution.

What mathematicians do to get around this is to instead settle for an approximation of the optimal solution by solving a simplified version of the problem. This allows them to obtain a “good” solution to the original problem within a more reasonable computational time. My research project involved studying and improving one of these methods, called Lagrangian Relaxation. This was done by using principles from Graph Theory to try and “intelligently” automate a difficult step within the method.

Now during my project, I was quite intrigued by the underlying principle behind methods used to solve IP problems. That is, that is better to go with a good solution to a problem than to go with the “optimal” solution. I believe this principle is relevant and can be invoked in our own personal decision-making. The way I see this principle playing out in our decision making is as follow – often, we can have a tendency to want to wait until we can make the perfect decision to a problem. However, this leads to delay and an inability to execute, which can actually be more costly than having made the perfect decision over a good one. As such, it can often be better for us to act decisively and make the best decisions that we can based off the limited information we do have in order to boost our productivity than to be paralysed, waiting for the perfect solution to come. Of course, there are occasions where it is best to be patient, but in general, I think we should seek to make our decisions quickly and effectively.

Robert Hickinbotham was one of the recipients of a 2017/18 AMSI Vacation Research Scholarship.