Linear programming x Heuristics x Metaheuristics

A didactic example of some optimization techniques.

See file to play a bit.

Problem: there are 3 sources of material (blocks of wood, for example) and 3 destinations (mills, for example).

cid:image001.png@01D589BE.D5DD9D80

The distances are given below.

I want to do the distribution source->destination, minimizing the total distance.

cid:image002.png@01D589BE.D5DD9D80

Method 1: Solver (linear programming).

The formulation is straightforward and it will reach optimal solution.

In this case, FO is 106.700.

2 – Method 2: Heuristics.

A heuristic is a simple and easy rule of thumb.

For example, begin from the first source, distribute it to the first destination, till there is no more volume to distribute.

It is easy, computationally cheap (only O(N) interactions), but gives a bad solution: 113.400 vs 106.700.

(take a look on the VBA code).

3 – Method 3: Meta heuristics.

This method uses the heuristics as a basis, but the rule involves probabilities.

For example, I can toss a die to decide which source and which destination I want to distribute.

Do this probabilistic distribution for the whole sets, and calculate results.

Then, repeat it several times, say T, and keep the best solution.

The more trials, the better the solution (and worst the computational time ~ T*O(N)).

Each time I run, it will give a different result.

Ex. With 4 trials, it gave a FO of 115.200, worse than the pure heuristics.

With 10 trials, it gave 107.100, better than the heuristic, but still worse than the linear programming.

With 100 trials, it reaches the optimal solution.    

Some advantages of metaheuristics against linear programming:

Do not need license (Aimms can cost US$ 50.000)

It’s possible to model non-linear constraints  

Some disadvantages of metaheuristics against linear programming:

It needs people with knowledge to deal with code

Does not guarantee the global optimum, but a good solution    

As every other tool, the application depends on several constraints and the real process. There’s a best tool for each case.      


Ideias técnicas com uma pitada de filosofia: https://ideiasesquecidas.com