Categoria: Metaheurística

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.

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