Quadraturas do retângulo

Aqui, uma macro que lida com o problema da “quadratura do retângulo”.

Dado um retângulo, digamos de tamanho 11 x 10, como eu decomponho a mesma no menor número de quadrados menores?

A macro utiliza um algoritmo recursivo. Basicamente, esta vai testando todas as combinações possíveis em duas dimensões, até chegar ao final, e compara o número de quadrados gerados. É o chamado método da força-bruta.

Mesmo incluindo alguns truques, como eliminando quem tem mais quadrados que o mínimo até então, o algoritmo continua sendo força bruta – ou seja, demora muito quando aumenta o tamanho do problema.

Outro exemplo, um retângulo 13 x 11.

Uma utilidade possível é encaixar produtos em pallets, ou conjugar cargas em carregamentos, utilizando métodos adaptados.

Há um problema similar, porém com uma restrição muito mais forte: todos os quadrados menores devem ter tamanho diferente.

Esta restrição é tão forte que a maioria dos retângulos não vai ter solução. Porém, algumas que as têm geram resultados muito bonitos, como o seguinte (retângulo 33 x 32).

Houve uma série de matemáticos que estudou este problema, chegando em soluções bem legais (porém, muito mais matemáticas que computacionais).

Uma história desses é mostrada no livro “Mania de matemática”, de Ian Stewart.

Link para download: https://github.com/asgunzi/quadraturaVBA

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



O “barril mágico”

Forgotten Lore

O “barril mágico” da foto é um tipo de cubo mágico no formato de cilindro.

Fiquei um bom tempo analisando o mesmo, porque o tipo de movimento é bem diferente do cubo comum. Há uma série de simetrias possíveis (que podem facilitar ou atrapalhar a montagem).

A conclusão é de que o barril mágico é fácil de montar. Muito mais fácil do que o Rubik comum. Um pouco mais difícil que o tetraedro mágico (com movimento muito semelhante a este).

Basicamente, há um tipo de movimento apenas. O RLR’L’. Ou seja, girar à direita, esquerda, e voltar tudo.

E apenas variantes deste: RL’R’L, R’LRL’, etc…

Enfim, o barril mágico é muito fácil. As simetrias (ex. a peça do meio pode ser encaixada a 0 graus e 180 graus) não atrapalham o resultado final.

A seguir, várias fotos.

Antigamente, para conseguir coisas assim, tinha que importar da China, via AliExpress, e…

Ver o post original 31 mais palavras

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.

Open solver

A tip of a great tool.

Open solver is an Excel addin. It is very similar to the MS solver. The difference is that the default solver has a limit of around 5000 variables. Above this, the user has to purchase the Frontline solver (the name of the company).

Page: https://opensolver.org

To use opensolver, just download, unpack and add it to the Excel supplements.

A good evolution of openSolver is solverStudio, from the same developer. It allows a formulation of the problem using formulas, supports more optimization languages and is faster. But it is also a bit more complex to deal with.

Solver studio https://solverstudio.org

Both of these tools are able to use any solver. The package comes with CBC, the great open source solver from COIN-OR. https://www.coin-or.org/

Frontline solver:

https://www.solver.com/

Ideias técnicas com uma pitada de filosofia

https://ideiasesquecidas.com/

O “cubo torcido”

Forgotten Lore

O “cubo torcido” é o da foto abaixo. Não sei se este é o nome oficial do mesmo, mas é exatamente um Rubik torcido.

O mesmo, bagunçado, fica assim:

Um pouco assustador, mas quase todos os algoritmos são idênticos ao Rubik 3x3x3.

Pré-requisito: saber resolver o 3x3x3.

O primeiro passo é arrumar o primeiro layer, que pode ser feito sem grande dificuldade.

A seguir, arrumar as peças de centro. Esta é a única grande diferença. No Rubik normal, a peça de centro é flat. Aqui, ela é torcida, ou seja, uma rotação errada vai bagunçar a mesma.

A seguir, arrumar as laterais do segundo layer. Aqui, outra ressalva.

Como a peça lateral é indistinguível se está de pé ou de cabeça para baixo, podemos descobrir, no final, uma paridade insolúvel.

Aí, saberemos que há uma das peças laterais de cabeça para baixo – é necessário tirar a peça (qualquer lateral…

Ver o post original 264 mais palavras

Indicator variable

An indicator variable can be useful in several cases.

Suppose we have the situation below.

Three areas, two normal ones, and one emergency area.

To use this emergency area, we need to pay a penalty to activate this area, besides the unitary cost.

Suppose we need a min value of 100.000 tons.

The question. How to model this in Linear integer programming?

Easy. With an indicator variable.

We model everything as usual.

But we add a binary variable (in B17), and a “Big M” calculation in B18.

The “big M” is a number great enough to our purposes.

If indicator is zero, 0*100000 = 0

If indicator is one, 1*100000 = 100000 > 40.000 (bigger than the emergency area).

In the constraints,

B17 = binary

B18 > B17, to force the indicator to be one if emergency area is used.

In Objective Function, we multiply the indicator and the penalty – if indicator is zero, no penalty, if it is one, add penalty.

For example, if the minimum volume is 100.000, then we do need the emergency area:

If the minimum volume is 74000, we don’t need to activate the emergency area.



File to download.

Ideias técnicas com uma pitada de filosofia:

https://ideiasesquecidas.com/