Intro to optimization

AI is just a fancy word for algorithms

AI, or artificial intelligence, encompasses a broad range of disciplines, including robotics, reasoning, optimization,
natural language processing (NLP), machine learning (ML), and vision.
Over the past ten years, machine learning has been a major focus of AI research, particularly after Google
Deepmind Google Deepmind introduced their AlphaGo algorithm, which outperformed the world's
top Go players.
This algorithm was developed using deep learning, a subset of machine learning based on neural networks, and it laid the
groundwork for large language models like ChatGPT.
Machine learning typically involves making predictions based on historical data, and the algorithms used are often seen
as black boxes that output results with a certain level of accuracy.

In contrast, optimization involves a model-based approach carried out by an expert. It can be split into two categories:
exact algorithms and heuristics. Exact algorithms can provide a mathematically proven optimal solution, but they don't
guarantee a quick solve time. Heuristics, on the other hand, can generate high-quality solutions in a reasonable
timeframe, but they can't guarantee that these solutions are optimal. At Solvice, we use heuristics.

The Traveling Salesman Problem (TSP)

One common application of decision optimization is the traveling salesman problem (TSP), which involves finding the shortest possible route that visits each city once. This problem has been the subject of extensive research, and it's now possible to
solve versions of the problem involving up to 100,000 cities. The Clay Mathematics Institute in America offers a $1
million prize for anyone who can efficiently find the optimal solution to this and six other incredibly challenging problems.

The solution space of NP-hard problems

Why is it hard? It is because there are so many combinations that you can make.

The difficulty of the TSP and similar problems lies in the vast number of possible combinations, or permutations, that can be made. For example, even a relatively small shift scheduling problem involving 50 employees and 200 shifts can have a staggering number of potential solutions. Despite this, algorithms have proven to be highly effective at solving such problems, often finding solutions that reduce total travel time by 30% or more while still meeting other constraints. This is largely because computers can perform hundreds of thousands of calculations per second, while humans might take several minutes to evaluate a single solution.

To put that into perspective, you have to compare it with other big numbers.

Algorithms have proven to be very consistent in solving scheduling problems with high quality. For example in routing,
algorithms can find solutions that require 30% or higher reduction in total travel time while keeping other constraints
in mind. That is mainly because of the fact that computers can do hundreds of thousands calculations per second while a
human might need
multiple minutes to evaluate the quality of single solution. It is true that algorithms will also investigate parts of
the search
space that intuitively feel unnecessary to human schedules.

How do solvers work?

Solvers work in three main steps. First, they construct an initial solution from scratch. Next, they modify this
solution based on its current state in a way that is likely to improve its quality. Finally, they score the solution to
determine its quality. If the solution is an improvement, it becomes the new solution, and this process is repeated many
times. The solver stops when it appears that no further improvements can be made, or when a predetermined time limit is
reached.

So you can visualise this process on this graph where the x-axis represents the solution space, meaning all the
potential solutions / permutations / combinations. And on the y-axis you can see the solution quality. So it’s our job
to search this space for the one with the global optimum (max or min, depending on the problem we’re
optimizing). So you can see this as a blind person going through this mountainous landscape, these mountains and
valleys, looking for the highest peak. And it can teleport, but unaware of where it will end up.

So after some time, it will have looked in the most promising regions of the solution space. That should be an analogy
to how the search algorithms work.