O Problema da Mochila na Computação Quântica

Definição do problema

Um problema de otimização combinatória tem como objetivo encontrar dentro de um conjunto finito de objetos, um subconjunto ótimo, dadas algumas condições. O Problema da Mochila (Knapsack Problem) é um tipo de problema de otimização combinatória, nele todos os objetos disponíveis que fazem parte do conjunto maior possuem um peso e um valor, e o subconjunto ótimo será aquele cujo valor é o maior possível enquanto o peso não ultrapassa um limite pré-estabelecido.

Suponha que exista um total de N objetos que podem ser escolhidos para formar um subconjunto. Sendo i o índice de cada um desses objetos, temos c_i e v_i como o peso e valor de cada objeto, respectivamente. Utilizamos uma variável de decisão q que indica se um objeto pertence ou não ao subconjunto que estamos calculando. Caso o objeto i pertença a esse subconjunto, q_i=1 . Caso contrário, q_i=0 . Sendo W a capacidade de peso máximo que a mochila pode suportar, então a formulação do problema da mochila em termos matemáticos é a seguinte.

Onde desejamos maximizar o Valor Total, obedecendo à restrição de que a soma dos pesos seja menor do que o limite máximo que a mochila pode carregar.

Essa formulação leva o nome de Problema da Mochila 0/1 (Knapsack Problem 0/1), pois cada objeto pode ser escolhido nenhuma, ou apenas uma vez. Existem variações desse problema onde a variável  pode assumir valores inteiros maiores do que 1. O caso em que um objeto pode ser escolhido mais de uma vez havendo um limite máximo, é chamado de Problema da Mochila com Repetição Limitado (Bounded Knapsack Problem). No caso em que um objeto pode ser escolhido infinitas vezes, ou seja ele pode ser escolhido quantas vezes for desejado sem limite algum, então o nome dado é Problema da Mochila com Repetição Ilimitado (Unbounded Knapsack Problem).

Existem outras variações do Problema da Mochila, como por exemplo o Problema da Mochila Limitado por Prioridade em Múltiplos Períodos (Multi-period Precedence Constrained Knapsack) no qual o subconjunto ótimo é escolhido para diferentes períodos do tempo, de forma sequencial, de forma que o valor de cada item e a capacidade máxima da mochila variam de período para período.

Aplicações no Mercado

A formulação do problema da mochila pode ser adaptada para solucionar diversos tipos de problemas reais na indústria. O primeiro, e mais óbvio problema que se pode solucionar é chamado de Picking and Packing (Separar e Embalar) no qual o objetivo é otimizar o fluxo de matéria-prima ou bens de consumo de um lugar para outro. Nesse exemplo pode-se imaginar que existe um container com um limite de peso que pode ser carregado, e diversos itens que precisam ser distribuídos dentro desse container, cada um com uma prioridade (ou valor). O objetivo seria encontrar qual a combinação de itens pode ser colocada dentro desse container de forma que o peso máximo não seja excedido e os itens de maior prioridade sejam enviados.

Esse problema pode ser encarado por outro ponto de vista, no qual a limitação não é mais o peso e sim o volume do container. Nesse caso os itens disponíveis possuiriam volumes diferentes e certa prioridade, ou valor. Dessa forma, o objetivo seria ocupar o volume do container com itens que possuem maior prioridade, ou valor, otimizando assim o custo de transportar esse container de um local para outro.

Outro problema real que pode ser formulado utilizando o conceito do Problema da Mochila é o Open Pit Mining Production Scheduling Problem (Planejamento de Extração para Mina Aberta). Suponha que uma empresa de mineração deseja explorar uma região onde exista alta concentração de minérios preciosos. Essa região pode ser dividida em blocos desde a superfície até as camadas mais profundas onde existam esses minérios. O problema consiste então em definir quais blocos serão explorados em que ordem, de forma a otimizar o lucro total da exploração dessa mina por toda sua vida útil. Para isso, deve-se levar em conta que os blocos só podem ser explorados caso todos os blocos acima dele já tenham sido retirados, de forma a não colapsar a mina, e também deve-se considerar que o valor dessa commodity irá variar conforme o tempo passa. Apesar de complexas, essas restrições podem ser introduzidas na formulação do Problema da Mochila e assim encontrar o planejamento que melhor otimiza o lucro da operação.

Um exemplo da aplicação do Problema da Mochila com Repetição Limitada é na indústria de fundição, na qual uma quantidade determinada de liga metálica é produzida e pode ser utilizada para produzir diversos itens diferentes. O objetivo então é encontrar quantas unidades de cada produto serão feitas, de forma que não sejam produzidos mais itens do que o mercado demanda, que o lucro da operação seja o máximo e que a menor quantidade possível da liga seja desperdiçada. Nesse caso, a solução do problema auxiliará no planejamento da operação dessa indústria, permitindo que ela atenda às demandas maximizando lucro e diminuindo os resíduos.

Além disso são possíveis outras aplicações, como por exemplo na escolha de um portifólio, em que os recursos para a aquisição de ativos são limitados e deve-se escolher dentre diversas alternativas, aquela que maximize os lucros futuros. Ou então como distribuir a entrega de certo volume de produtos dentro de uma frota de veículos com capacidades diferentes, de forma que o custo de transporte seja minimizado. Notamos que o Problema da Mochila pode ser adaptado para diversas necessidades do mercado, basta compreender quais as limitações e os objetivos que se deseja alcançar.

Métodos Clássicos

O Problema da Mochila é considerado um problema NP-completo devido à dificuldade em se encontrar a melhor solução, portanto foram desenvolvidas diversas maneiras de buscar pelo melhor resultado, com a menor ordem de complexidade possível. Dentre os métodos desenvolvidos, estão algoritmos de programação dinâmica, métodos de relação de dominância e algoritmos de aproximação. Cada um deles pode apresentar diferentes resultados para um mesmo conjunto de dados de entrada, uma vez que possuem maneiras diferentes de selecionar quais itens farão parte de sua solução.

Os algoritmos de programação dinâmica são utilizados para otimizar diversos problemas onde há recursividade com o mesmo conjunto de dados de entrada. Nesses casos ele armazena o resultado de subproblemas para utilizá-los posteriormente, reduzindo o número de operações necessárias para se encontrar a melhor solução. Na maioria dos casos, os algoritmos de programação dinâmica conseguem reduzir problemas de complexidade exponencial a problemas com complexidade polinomial, ou pseudo-polinomial.

Já os métodos de relação de dominância se baseiam na comparação dos valores entre um item e um conjunto de mesmo peso, descartando esse item sempre que houver um conjunto que possua maior valor com o mesmo peso. Dessa forma o método busca substituir itens que não irão compor a melhor solução para o problema. Existem diferentes maneiras de realizar essas operações de dominância, cada uma adequada para um conjunto de dados com características específicas. Entretanto, esses métodos não se aplicam a problemas da mochila limitados, uma vez que é possível que um item já tenha sido utilizado e ainda faça parte desse novo conjunto que substituiria outro item menos valioso.

Como o próprio nome já diz, os algoritmos de aproximação são aqueles que abrem mão da precisão em troca de um processamento mais rápido. O resultado obtido por esses algoritmos possuirá uma margem de erro que pode ser ajustada dependendo da necessidade. Cada algoritmo desses se baseia em alguma propriedade matemática diferente para garantir a diferença entre o valor ótimo possível e o resultado que será encontrado, portanto cada um deles pode ser mais adequado dependendo do problema que se deseja solucionar.

Formulação Quântica

Apesar de os métodos clássicos serem atualmente os mais eficientes para solucionar o Problema da Mochila, eles possuem uma grande limitação quando se trata de problemas realmente grandes. Uma alternativa que pode contornar esses limites são os algoritmos quânticos.

O primeiro passo para resolver o Problema da Mochila em um Computador Quântico Adiabático é modelar esse problema em um formato específico chamado QUBO (Quadratic Unconstrained Binary Optimization). Nesse formato, cada uma das variáveis de decisão q_i pode se ligar com apenas uma outra variável de decisão q_j por vez. Além disso, nesse formato deve-se inserir penalidades que refletem as limitações e parâmetros do problema, como o peso máximo W. Dessa forma, o Problema da Mochila 0/1 pode ser descrito pela seguinte expressão

Onde  e  são multiplicadores de Lagrange, que irão calibrar as penalidades impostas pelo problema. A variável n assume todos os valores inteiros possíveis de peso da mochila, ou seja, n vai de 1 até W. E a variável y_n é uma variável de decisão auxiliar, que aponta para o peso final da mochila e ajuda a garantir que esse peso seja menor do que o limite máximo permitido.

Essa formulação permite que o problema seja solucionado pelo computador quântico adiabático, que irá realizar diversos processos de annealing quântico e obter um padrão de resultados. Esses resultados mostram qual a configuração do sistema que minimiza o valor da função H descrita acima, essa configuração ótima pode ser traduzida posteriormente no conjunto que apresenta o maior valor para aquele problema.

Assim como os métodos clássicos, o algoritmo quântico também possui uma limitação. Atualmente os computadores quânticos adiabáticos permitem acoplamentos diretos entre uma quantidade limitada de qubits físicos devido à sua arquitetura. Entretanto, o modelo descrito requer um acoplamento de todos os qubits uns com os outros o que seria impossível de realizar diretamente nos computadores existentes. Uma forma de contornar isso é a utilização de mais de um qubit físico do computador quântico para representar um mesmo qubit lógico descrito no problema. Isso limita ainda mais a dimensão dos problemas que podem ser solucionados, pois os qubits físicos são rapidamente consumidos.

Com os investimentos constantes na área e o interesse cada vez maior nas tecnologias quânticas, é de se esperar que nos próximos anos surjam computadores quânticos adiabáticos cada vez melhores e com mais acoplamentos entre os qubits. Portanto não deve demorar para que os métodos clássicos sejam ultrapassados pelos algoritmos quânticos tanto em precisão quanto em velocidade.