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.