Descrição do problema – Kaggle Papai Noel 2019

O Desafio Kaggle está em https://www.kaggle.com/c/santa-workshop-tour-2019/overview/prizes

Sua tarefa é agendar a entrega de presentes para as famílias de forma a minimizar as penalidades.

Cada família listou suas top 10 preferências de entrega.

Por exemplo, a família 0 prefere entregas no dia 52, depois 38, 12, 82, etc…

family_id,choice_0,choice_1,choice_2,choice_3,choice_4,choice_5,choice_6,choice_7,choice_8,choice_9,n_people
0,52,38,12,82,33,75,64,76,10,28,4

(arquivo Family_data.csv)

As datas são valores inteiros representando dias antes de Natal. Dia 0 = Natal.  

Cada família tem um número de pessoas, n_people (no caso da família 0, há 4 pessoas).

Cada família deve ser agendada para um único dia.

Restrições:

  1. O número de pessoas agendadas deve estar entre 125 e 300.  Atenção: é o número de pessoas, e não de famílias. Se tiver um único dia fora desta faixa, a nota será zero (ou seja, é restrição hard).
  2. O ideal é agendar na data que a família quer, mas há prêmios de consolação se o agendamento não for o ideal – o preferencecost
  • choice_0: no consolation gifts
  • choice_1: one $50 gift card to Santa’s Gift Shop
  • choice_2: one $50 gift card, and 25% off Santa’s Buffet (value $9) for each family member
  • choice_3: one $100 gift card, and 25% off Santa’s Buffet (value $9) for each family member
  • choice_4: one $200 gift card, and 25% off Santa’s Buffet (value $9) for each family member
  • choice_5: one $200 gift card, and 50% off Santa’s Buffet (value $18) for each family member
  • choice_6: one $300 gift card, and 50% off Santa’s Buffet (value $18) for each family member
  • choice_7: one $300 gift card, and free Santa’s Buffet (value $36) for each family member
  • choice_8: one $400 gift card, and free Santa’s Buffet (value $36) for each family member
  • choice_9: one $500 gift card, and free Santa’s Buffet (value $36) for each family member, and 50% off North Pole Helicopter Ride tickets (value $199) for each family member
  • otherwise: one $500 gift card, and free Santa’s Buffet (value $36) for each family member, and free North Pole Helicopter Ride tickets (value $398) for each family member

Para ficar mais claro, transcrevi a tabela no excel.

3 – Há uma restrição adicional, referente à flutuação de pessoas entre os dias.

Onde Nd é a ocupação do dia corrente, e Nd+1 refere-se ao dia anterior, já que a contagem é de trás para frente em relação ao Natal. Atenção, é o dia anterior, não posterior. Para a condição inicial d=100, considerar N101 = N100.

O Kaggle coloca algumas restrições não-lineares estranhas assim de propósito, para evitar que as pessoas usem puramente um solver comercial como CPLEX ou Gurobi.

Score final (a ser minimizado):

score=preferencecost+accountingpenalty

O Kaggle fornece um Jupyter Notebook básico, para começar:

https://www.kaggle.com/inversion/santa-s-2019-starter-notebook

Arquivo de submissão de respostas deve ser no formato

family_id,assigned_day

0,100

1,99

2,98

etc.

Esta competição vai até o dia 20/jan.

Como estratégia, há duas abordagens:

– Solução inicial via Programação inteira e melhorias via metaheurística.

– Solução metaheurística pura (mas há infinitas variantes possíveis).

Para enviar solução, há um campo específico.

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