What is a solver? The Mathematical Engine that Solves Complex Problems

  • Post author:
  • Post category:Code
Image of Max Fischer on pexels

Many Complex Problems are Tackled With poor Tools

In Industry 4.0 context and, in general, the 4.0 world, appear products and services whose organisation poses extremely complex problems. Dealing with them well or badly can be the difference between a profitable business and an unprofitable one.

Designing our supply network, organising last-mile routes, planning production, pricing our products, allocating staff shifts, etc. are just a few examples. However, despite the importance of tackling these problems well, many companies’ approach is not the most appropriate. In many cases, behind every problem, there is a person or a team that explores some solutions generally with the help of a huge spreadsheet.

This process is slow, does not allow for what-if analysis and does not guarantee that we will find the best solution or know how far we are from that best solution.

The Alternative: Mathematical Programming and a solver

But there is a better alternative, with an impact of 10-20% improvement: the use of mathematical programming and a type of software called solver.

In a last-mile delivery problem, a traditional approach is to add stops to a route “with common sense”: Stops are added sequentially to each vehicle so that each stop is “close to the previous ones”. Sometimes the solution will not be bad, but other times it will be necessary to backtrack and build the routes again until the result is sufficiently satisfactory.

The alternative is to build a mathematical model. If we want to visit some customers to make deliveries we have to decide whether for every two customers (A and B) the route passes through B immediately after A. If we have 10 customers, there are 181440 different routes. If the number of customers is 100 the number of routes is 4.6 x 10^155 (46000000… with 155 zeros).

To define the path, we define a variable x__{AB} that takes a value equal to 1 if we visit B immediately after B and 0 otherwise.

If going from customer A to customer B costs c__{{AB}^{1}}, the product {c__{AB}}{x__{AB}} represents the cost according to the route. If we visit customer B immediately after A, we pay the cost. Otherwise not.

In general, the formulation* would be as follows.

min. {c__{ij}}{x__{ij}}

(we minimise the total cost resulting from the chosen route)

Bound to:

    \begin{align*} \sum_{j}{x__{ij}}   = 1 \hspace{0.1cm} \forall i  \hspace{0.2cm}    \end{align*}

(it is necessary to exit from each client to some other client and only to one client)

    \begin{align*} \sum_{j}{x__{ij}}   = 1 \hspace{0.1cm} \forall j  \hspace{0.2cm}   \end{align*}

(each customer needs to be reached from some other customer and only from one)

    \begin{align*} {x__{ij}}, \hspace{0.1cm} \in \hspace{0.1cm} \left\{0,1 \right\},  \forall i,j  \hspace{0.2cm}     \end{align*}

(for each pair of customers i and j we can include or not the path from i to j or not in the final solution)

(* )The wording given is not complete. Restrictions preventing the formation of sub-cycles are missing. The following have been deliberately omitted. The explanation of such restrictions does not add essentially different aspects and introduces additional complexity to the explanation which is not strictly necessary.

With this mathematical problem or with the decomposition of this problem into several sub-problems, we can delegate the search for the best route to the solver. The algorithm discards both combinations of values of the variables that are not feasible and those where it is not worth searching because other areas certainly contain better solutions (cheaper routes).

Mathematical Programming is not Traditional Programming

Without a solver, finding the optimum (the best way to design or operate a system) is like looking for a tiny needle in a giant haystack.

And why do solvers find the needle? Because they don’t work like the human mind.

Although developing a mathematical model and the resolution using a solver requires code development, it is not traditional programming. It is not a set of instructions executed sequentially as the human mind would do.

The solver uses the mathematical properties of the equations with which the system is modelled and searches efficiently because they “realise” that there are combinations or values that are not worth exploring. They look for the needle in the haystack by eliminating areas where the needle is certainly not.

The Goal: To Make it Profitable

There are different alternatives with different costs, but for complex problems with an impact on the income statement, they are undoubtedly more profitable than having the best expert looking for solutions.

If you feel that you are wasting your time doing sudokus you are probably not only wasting time but also money because, with the help of a solver (and a good analytical formulation of your problem), you could find better solutions and in less time, with a direct impact on the income statement.