knapsack

Mochila

El problema de la mochila es un problema de optimización bien conocido. Se encuentra, por ejemplo, al embalar contenedores de transporte. Un contenedor de envío tiene una capacidad de peso que puede contener. Dada una colección de artículos a enviar, donde cada artículo tiene un valor y un peso, el problema es seleccionar los artículos óptimos para empacar en el contenedor de envío. Este problema de optimización se puede definir como un objetivo con una restricción:

• Objetivo: Maximizar el valor del flete (suma de valores de los artículos seleccionados).
• Restricción: El peso total de la carga (suma de los pesos de los artículos seleccionados) debe ser menor o igual a la capacidad del contenedor.

Este ejemplo resuelve dicho problema de mochila reformulándolo como un modelo cuadrático restringido (CQM) y enviándolo a un solucionador CQM híbrido de Leap.

Uso

Para ejecutar la demostración predeterminada, ingrese el comando:

python knapsack.py

Para ver las opciones disponibles, ingrese el comando:

python knapsack.py --help

Los argumentos de la línea de comandos le permiten seleccionar uno de varios conjuntos de datos (en la carpeta /data ) y establecer la capacidad de carga. Los archivos de datos se formulan como filas de elementos, cada uno definido como un par de peso y valor.

Descripción general del código

El código en knapsack.py incluye tres funciones principales:

• build_knapsack_cqm() crea un CQM estableciendo un objetivo y una restricción de la siguiente manera:

  • Objetivo: Se crean variables binarias para cada artículo y se les asigna un sesgo lineal igual al valor negativo del valor del artículo. Minimizar este objetivo, seleccionando un conjunto óptimo de artículos, equivale a maximizar el valor total del flete. Las soluciones establecen un valor de 1 para los elementos seleccionados y 0 para los elementos no seleccionados.
  • Restricción: Se crea un modelo cuadrático con las variables binarias creadas previamente, donde los sesgos lineales se igualan al peso de cada artículo, con el requisito de que el peso total no debe exceder la capacidad del contenedor.

• parse_inputs() es una función de utilidad que lee datos de los archivos de ejemplo.

• parse_solution() analiza y muestra los resultados devueltos por el solucionador.

Licencia

Publicado bajo la licencia Apache 2.0. Ver archivo de LICENCIA.