knapsack

Mochila

O problema da mochila é um problema de otimização bem conhecido. É encontrado, por exemplo, na embalagem de contêineres. Um contêiner de transporte tem uma capacidade de peso que pode suportar. Dada uma coleção de itens a serem despachados, onde cada item possui um valor e um peso, o problema é selecionar os itens ideais para embalar no contêiner de transporte. Este problema de otimização pode ser definido como um objetivo com uma restrição:

• Objetivo: Maximizar o valor do frete (soma dos valores dos itens selecionados).
• Restrição: O peso total da carga (soma dos pesos dos itens selecionados) deve ser menor ou igual à capacidade do contêiner.

Este exemplo resolve esse problema de mochila reformulando-o como um modelo quadrático restrito (CQM) e submetendo-o a um solucionador CQM híbrido Leap.

Uso

Para executar a demonstração padrão, digite o comando:

python knapsack.py

Para visualizar as opções disponíveis, digite o comando:

python knapsack.py --help

Os argumentos de linha de comando permitem selecionar um dos vários conjuntos de dados (na pasta /data ) e definir a capacidade de frete. Os arquivos de dados são formulados como linhas de itens, cada um definido como um par de peso e valor.

Visão geral do código

O código em knapsack.py inclui três funções principais:

• build_knapsack_cqm() cria um CQM definindo um objetivo e uma restrição como segue:

  • Objetivo: São criadas variáveis ​​binárias para cada item, às quais é atribuído um viés linear igual ao valor negativo do valor do item. Minimizar esse objetivo, selecionando um conjunto ótimo de itens, equivale a maximizar o valor total do frete. As soluções definem um valor de 1 para itens selecionados e 0 para itens não selecionados.
  • Restrição: Um modelo quadrático com as variáveis ​​binárias criadas anteriormente, onde os vieses lineares são definidos iguais ao peso de cada item, é criado com a exigência de que o peso total não exceda a capacidade do contêiner.

• parse_inputs() é uma função utilitária que lê dados dos arquivos de exemplo.

• parse_solution() analisa e exibe os resultados retornados do solucionador.

Licença

Lançado sob a licença Apache 2.0. Consulte o arquivo LICENÇA.