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).


The distances are given below.

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


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:

Shadow price

The excel solver has a feature of sensibility analysis.

For example, we want to maximize a linear programming like this.

Run solver, and select the reports you want to see:

The sensibility will be in another spreadsheet.

What does a shadow price means?

For example, the shadow price for constraint2 is equal to 4.

It means that if I increase the right hand size of constraint2 in one unit, the objective function will increase 4 units.

Lets test it:

If I increase constraint2, from 166 to 167, and run solver again, the results will be as below.

The FO was previously 709. Now, it is 713, because the shadow price for this constraint is 4.

If shadow price is zero, it means this constraint is not restricting the problem.

One detail. If I increase too much the value of the RHS of the restriction, it can give another optimal solution.

The maximum I can increase is 14, according to the column “Permitido aumentar” in the Excel report.

Take a look in the file.