Un programa de enteros típico: el problema de la mochila

Presenta el modelo y los archivos de datos.

Un ejemplo típico del programa de enteros es el problema de la mochila, que se puede entender intuitivamente de la siguiente manera. Tenemos una mochila con una capacidad física (un entero) y un número de artículos. Cada artículo tiene un peso asociado (un entero) y un valor asociado (otro entero). El problema consiste en llenar la mochila sin exceder su capacidad al tiempo que se maximiza el valor total de su contenido. El problema de la mochila múltiple es parecido al problema de la mochila, excepto en que hay múltiples características del objeto (por ejemplo, peso y volumen) y múltiples restricciones de capacidad. El siguiente ejemplo, ' knapsack.mod, representa un modelo para el problema de la mochila múltiple, mientras que Data for the multi-knapsack problem (knapsack.dat) describe una instancia del problema.

int NbItems = ...;
int NbResources = ...;
range Items = 1..NbItems;
range Resources = 1..NbResources;
int Capacity[Resources] = ...;
int Value[Items] = ...;
int Use[Resources][Items] = ...;
int MaxValue = max(r in Resources) Capacity[r];


dvar int Take[Items] in 0..MaxValue;

maximize
  sum(i in Items) Value[i] * Take[i];
  
subject to {
  forall( r in Resources )
    ct:
      sum( i in Items ) 
        Use[r][i] * Take[i] <= Capacity[r];
}

Este modelo tiene diversas características novedosas. Representa artículos y recursos no por conjuntos de cadenas sino por enteros. En otras palabras, los elementos (respectivamente, los recursos) están representados por números enteros sucesivos que empiezan por 1. Las instrucciones

int NbItems = ...;
int NbResources = ...;
range Items = 1..NbItems;
range Resources = 1..NbResources;

declaran el número de artículos y el número de recursos, además de los dos rangos, Items y Resources, que representan el conjunto de artículos y el conjunto de recursos.

Las siguientes tres instrucciones

int Capacity[Resources] = ...;
int Value[Items] = ...;
int Use[Resources][Items] = ...;

son similares a las declaraciones de datos presentadas en Declaraciones de datos y las secciones posteriores. La matriz Capacity representa la capacidad de los recursos, la matriz Value el valor de cada elemento y Use[r][i] el uso de recurso r por artículo i.

La siguiente instrucción

int MaxValue = max(r in Resources) Capacity[r];

es más interesante. Declara un entero MaxValue cuyo valor viene dado por una expresión. OPL e IBM ILOG Script tienen muchas funciones de cálculo y preproceso de datos, puesto que es fundamental simplificar y mejorar la eficiencia de muchos modelos.

La instrucción

dvar int Take[Items] in 0..MaxValue;

declara las variables del problema : take[Items] representa el número de veces que el artículo i se selecciona en la solución. La variable es de tipo entero y está restringida al rango en 0..MaxValue.

El resto de la sentencia es bastante estándar y no debería representar ninguna dificultad. Los datos del problema de la mochila múltiple (knapsack.dat) describen una instancia del problema.

NbResources = 7;
NbItems = 12;
Capacity = [ 18209, 7692, 1333, 924, 26638, 61188, 13360 ];
Value = [ 96, 76, 56, 11, 86, 10, 66, 86, 83, 12, 9, 81 ];
Use = [
      [ 19,   1,  10,  1,   1,  14, 152, 11,  1,   1, 1, 1 ],
      [  0,   4,  53,  0,   0,  80,   0,  4,  5,   0, 0, 0 ],
      [  4, 660,   3,  0,  30,   0,   3,  0,  4,  90, 0, 0],
      [  7,   0,  18,  6, 770, 330,   7,  0,  0,   6, 0, 0],
      [  0,  20,   0,  4,  52,   3,   0,  0,  0,   5, 4, 0],
      [  0,   0,  40, 70,   4,  63,   0,  0, 60,   0, 4, 0],
      [  0,  32,   0,  0,   0,   5,   0,  3,  0, 660, 0, 9]];

Feasible solution with objective 261890.0000:
  take = [0 0 0 154 0 0 0 912 333 0 6505 1180];

Feasible solution with objective 261916.0000:
  take = [0 0 0 153 0 0 0 912 333 0 6499 1180];

Final solution with objective 261916.0000:
  take = [0 0 0 154 0 0 0 913 333 0 6499 1180];