Programação Inteira Mista: Um Guia para Tomada de Decisão Computacional

A pesquisa operacional, a ciência de usar computadores para tomar decisões ótimas, tem sido usada e aplicada em muitas áreas de software. Para dar alguns exemplos, as empresas de logística o usam para determinar a rota ideal para ir do ponto A ao ponto B, as empresas de energia o usam para determinar os cronogramas de produção de energia e as empresas de manufatura o usam para encontrar padrões ideais de pessoal para suas fábricas.

Hoje, vamos explorar o poder da pesquisa operacional, abordando um problema hipotético. Especificamente, usaremos programação inteira mista (MIP) para determinar o padrão de equipe ideal para uma fábrica hipotética.

Algoritmos de Pesquisa Operacional

Antes de mergulharmos em nosso problema de exemplo, é útil revisar alguns conceitos básicos em pesquisa operacional e entender um pouco das ferramentas que usaremos hoje.

Algoritmos de Programação Linear

A programação linear é uma técnica de pesquisa operacional usada para determinar o melhor resultado em um modelo matemático onde o objetivo e as restrições são expressos como um sistema de equações lineares. Um exemplo de modelo de programação linear pode ser assim:

 Maximize a + b (objective) Subject to: a <= 2 (constraint 1) b <= 3 (constraint 2)

Em nosso exemplo muito simples, podemos ver que o resultado ideal é 5, com a = 2 e b = 3. Embora este seja um exemplo bastante trivial, você provavelmente pode imaginar um modelo de programação linear que utiliza milhares de variáveis ​​e centenas de restrições .

Um bom exemplo pode ser um problema de portfólio de investimentos, onde você pode acabar com algo como o abaixo, em pseudocódigo:

 Maximize <expected profit from all stock investments> Subject to: <investment in the technology sector must be between 10% - 20% of portfolio> <investment in the consumer staples must not exceed investment in financials> Etc. ...

O que seria bastante complexo e difícil de resolver manualmente ou por tentativa e erro. O software de pesquisa operacional usará vários algoritmos para resolver esses problemas rapidamente. Se você estiver interessado nos algoritmos subjacentes, recomendo aprender sobre o método simplex aqui e o método do ponto interior aqui.

Algoritmos de programação inteira

A programação inteira é como a programação linear com uma permissão adicional para que algumas ou todas as variáveis ​​sejam valores inteiros. Embora isso possa não parecer uma grande melhoria no início, nos permite resolver muitos problemas que poderiam ter permanecido sem solução usando apenas programação linear.

Um desses problemas é o problema da mochila, onde recebemos um conjunto de itens com valores e pesos atribuídos e somos solicitados a encontrar a combinação de itens de maior valor que podemos colocar em nossa mochila. Um modelo de programação linear não será capaz de resolver isso porque não há como expressar a ideia de que você pode colocar um item em sua mochila ou não, mas você não pode colocar parte de um item em sua mochila - toda variável é uma variável contínua. variável!

Um exemplo de problema de mochila pode ter os seguintes parâmetros:

E o modelo MIP ficará assim:

 Maximize 5a + 7b + 2c + 10d (objective: maximize value of items take) Subject to: 2a + 4b + 7c + 10d <= 15 (space constraint)

A solução ótima, neste caso, é a=0, b=1, c=0, d=1, sendo o valor do item total 17.

O problema que resolveremos hoje também exigirá programação inteira, já que um funcionário de uma fábrica pode ser agendado para um turno ou não - para simplificar, você não pode agendar um empregado para 2/3 de um turno nesta fábrica.

Para tornar a programação inteira possível, vários algoritmos matemáticos são usados. Se você estiver interessado nos algoritmos subjacentes, recomendo estudar o algoritmo de planos de corte e o algoritmo de ramificação e limite aqui.

Exemplo de problema: agendamento

Descrição do Problema

Hoje, vamos explorar o problema de pessoal de uma fábrica. Como gerentes da fábrica, queremos minimizar os custos de mão de obra, mas queremos garantir cobertura suficiente para cada turno para atender à demanda de produção.

Suponha que temos cinco turnos com as seguintes demandas de pessoal:

E, suponha que temos os seguintes trabalhadores:

Para simplificar o problema, vamos supor, por enquanto, que disponibilidade e custo são as únicas preocupações.

Nossas Ferramentas

Para o problema de hoje, usaremos um software de ramificação e corte de código aberto chamado CBC. Faremos interface com este software usando PuLP, que é uma biblioteca de modelagem de pesquisa operacional popular para Python. Você pode encontrar informações sobre isso aqui.

PuLP nos permite construir modelos MIP de uma forma muito Pythonic e se integra bem com o código Python existente. Isso é muito útil, pois algumas das ferramentas de manipulação e análise de dados mais populares são escritas em Python, e a maioria dos sistemas de pesquisa de operações comerciais exige processamento extensivo de dados antes e depois da otimização.

Para demonstrar a simplicidade e elegância do PuLP, aqui está o problema da mochila anterior e resolvido no PuLP:

 import pulp as pl # declare some variables # each variable is a binary variable that is either 0 or 1 # 1 means the item will go into the knapsack a = pl.LpVariable("a", 0, 1, pl.LpInteger) b = pl.LpVariable("b", 0, 1, pl.LpInteger) c = pl.LpVariable("c", 0, 1, pl.LpInteger) d = pl.LpVariable("d", 0, 1, pl.LpInteger) # define the problem prob = pl.LpProblem("knapsack", pl.LpMaximize) # objective function - maximize value of objects in knapsack prob += 5 * a + 7 * b + 2 * c + 10 * d # constraint - weight of objects cannot exceed 15 prob += 2 * a + 4 * b + 7 * c + 10 * d <= 15 status = prob.solve() # solve using the default solver, which is cbc print(pl.LpStatus[status]) # print the human-readable status # print the values print("a", pl.value(a)) print("b", pl.value(b)) print("c", pl.value(c)) print("d", pl.value(d))

Execute isso e você deve obter a saída:

 Optimal a 0.0 b 1.0 c 0.0 d 1.0

Agora vamos ao nosso problema de agendamento!

Codificando nossa solução

A codificação da nossa solução é bastante simples. Primeiro, vamos querer definir nossos dados:

 import pulp as pl import collections as cl # data shift_requirements = [1, 4, 3, 5, 2] workers = { "Melisandre": { "availability": [0, 1, 4], "cost": 20 }, "Bran": { "availability": [1, 2, 3, 4], "cost": 15 }, "Cersei": { "availability": [2, 3], "cost": 35 }, "Daenerys": { "availability": [3, 4], "cost": 35 }, "Theon": { "availability": [1, 3, 4], "cost": 10 }, "Jon": { "availability": [0, 2, 4], "cost": 25 }, "Tyrion": { "availability": [1, 3, 4], "cost": 30 }, "Jaime": { "availability": [1, 2, 4], "cost": 20 }, "Arya": { "availability": [0, 1, 3], "cost": 20 } }

Em seguida, vamos querer definir o modelo:

 # define the model: we want to minimize the cost prob = pl.LpProblem("scheduling", pl.LpMinimize) # some model variables cost = [] vars_by_shift = cl.defaultdict(list) for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable("%s_%s" % (worker, shift), 0, 1, pl.LpInteger) vars_by_shift[shift].append(worker_var) cost.append(worker_var * info['cost']) # set the objective to be the sum of cost prob += sum(cost) # set the shift requirements for shift, requirement in enumerate(shift_requirements): prob += sum(vars_by_shift[shift]) >= requirement

E agora é só pedir para resolver e imprimir os resultados!

 status = prob.solve() print("Result:", pl.LpStatus[status]) results = [] for shift, vars in vars_by_shift.items(): results.append({ "shift": shift, "workers": [var.name for var in vars if var.varValue == 1], }) for result in sorted(results, key=lambda x: x['shift']): print("Shift:", result['shift'], 'workers:', ', '.join(result['workers']))

Depois de executar o código, você deverá ver as seguintes saídas:

 Result: Optimal Shift: 0 workers: Arya_0 Shift: 1 workers: Melisandre_1, Bran_1, Theon_1, Arya_1 Shift: 2 workers: Bran_2, Jon_2, Jaime_2 Shift: 3 workers: Bran_3, Daenerys_3, Theon_3, Tyrion_3, Arya_3 Shift: 4 workers: Bran_4, Theon_4

Aumente um pouco a dificuldade: restrições adicionais

Embora o modelo anterior fosse interessante e útil, ele não demonstra totalmente o poder da programação inteira mista. Também poderíamos facilmente escrever um loop for para encontrar os x trabalhadores mais baratos para cada turno, onde x é o número de trabalhadores necessários para um turno. Para demonstrar como o MIP pode ser usado para resolver um problema que seria difícil de resolver de forma imperativa, vamos examinar o que aconteceria se adicionarmos algumas restrições extras.

Restrições Adicionais

Suponha que, devido às novas regulamentações trabalhistas, nenhum trabalhador possa ser alocado em mais de 2 turnos. Para explicar o aumento do trabalho, recrutamos a ajuda do Dothraki Staffing Group, que fornecerá até 10 trabalhadores Dothraki para cada turno a uma taxa de US$ 40 por turno.

Além disso, suponha que, devido a alguns conflitos interpessoais em andamento fora de nossa fábrica, Cersei e Jaime não possam trabalhar em nenhum turno ao lado de Daenerys ou Jon. Além disso, Jaime e Cersei não podem trabalhar em nenhum turno juntos. Finalmente, Arya, que tem relações interpessoais particularmente complexas, não consegue trabalhar no mesmo turno que Jaime, Cersei ou Melisandre.

A adição dessas duas novas restrições e recursos de forma alguma torna o problema insolúvel por meios imperativos, mas torna a solução muito mais difícil, pois será necessário levar em conta os custos de oportunidade de agendar um trabalhador para um turno específico.

Solução

Com programação inteira mista, no entanto, é muito mais fácil. Nós simplesmente precisamos alterar nosso código assim:

Defina a lista de banimentos e algumas restrições:

 ban_list = { ("Daenerys", "Jaime"), ("Daenerys", "Cersei"), ("Jon", "Jaime"), ("Jon", "Cersei"), ("Arya", "Jaime"), ("Arya", "Cersei"), ("Arya", "Melisandre"), ("Jaime", "Cersei") } DOTHRAKI_MAX = 10 DOTHRAKI_COST = 45

Preencha as variáveis ​​para implementar as restrições de ban e max shift:

 for worker, info in workers.items(): for shift in info['availability']: worker_var = pl.LpVariable("%s_%d" % (worker, shift), 0, 1, pl.LpInteger) # store some variable data so we can implement the ban constraint var_data = (worker,) vars_by_shift[shift].append((worker_var, var_data)) # store vars by variable so we can implement the max shift constraint vars_by_worker[worker].append(worker_var) cost.append(worker_var * info['cost'])

Adicione as variáveis ​​Dothraki:

 for shift in range(len(shift_requirements)): dothraki_var = pl.LpVariable('dothraki_%d' % shift, 0, DOTHRAKI_MAX, pl.LpInteger) cost.append(dothraki_var * DOTHRAKI_COST) dothrakis_by_shift[shift] = dothraki_var

Também precisaremos de um loop ligeiramente modificado para calcular os requisitos de mudança e proibição:

 # set the shift requirements for shift, requirement in enumerate(shift_requirements): prob += sum([var[0] for var in vars_by_shift[shift]]) + dothrakis_by_shift[shift] >= requirement # set the ban requirements for shift, vars in vars_by_shift.items(): for var1 in vars: for var2 in vars: worker_pair = var1[1][0], var2[1][0] if worker_pair in ban_list: prob += var1[0] + var2[0] <= 1 # set the labor standards: for worker, vars in vars_by_worker.items(): prob += sum(vars) <= 2

E, finalmente, para imprimir os resultados:

 status = prob.solve() print("Result:", pl.LpStatus[status]) results = [] for shift, vars in vars_by_shift.items(): results.append({ "shift": shift, "workers": [var[1][0] for var in vars if var[0].varValue == 1], "dothrakis": dothrakis_by_shift[shift].varValue }) for result in sorted(results, key=lambda x: x['shift']): print("Shift:", result['shift'], 'workers:', ', '.join(result['workers']), 'dothrakis hired:', int(result['dothrakis']))

E devemos estar prontos para ir. Execute o código e você deverá ver a saída como abaixo:

 Result: Optimal Shift: 0 workers: Arya dothrakis hired: 0 Shift: 1 workers: Melisandre, Theon, Tyrion, Jaime dothrakis hired: 0 Shift: 2 workers: Bran, Jon dothrakis hired: 1 Shift: 3 workers: Bran, Daenerys, Theon, Tyrion, Arya dothrakis hired: 0 Shift: 4 workers: Melisandre, Jaime dothrakis hired: 0

E aí está, um resultado que respeita a lista de trabalhadores proibidos, segue as normas trabalhistas e utiliza os trabalhadores dothraki criteriosamente.

Conclusão

Hoje, exploramos o uso de programação inteira mista para tomar melhores decisões. Discutimos os algoritmos e técnicas subjacentes usados ​​na pesquisa operacional e analisamos um exemplo de problema que é representativo de como a programação de inteiros mistos é usada no mundo real.

Espero que este artigo tenha inspirado você a aprender mais sobre pesquisa operacional e feito você pensar em como essa tecnologia pode ser aplicada em seus projetos. Nós realmente vimos apenas a ponta do iceberg quando se trata do excitante mundo dos algoritmos de otimização e pesquisa operacional.

Você pode encontrar todo o código relacionado a este artigo no GitHub. Se você quiser discutir mais, compartilhe seus comentários abaixo!