Caracterizacin de instancias difciles del problema de Bin Packing orientada a la mejora de algoritmos metaheursticos

Adriana Mexicano Santoyo¹, Joaqun Prez Ortega², Gerardo Reyes Salgado²,
Nelva Nely Almanza Ortega²

¹ Instituto Tecnolgico de Cd. Victoria,
Mxico

² Centro Nacional de Investigacin y Desarrollo Tecnolgico, Cuernavaca,
Mxico

mexicanoa@gmail.com, jpo_cenidet@yahoo.com.mx, nelvanely@cenidet.edu.mx

Resumen. En este trabajo se presenta una metodologa para la caracterizacin de instancias difciles del problema de Bin Packing usando Minera de Datos. El objetivo es que las caractersticas de las instancias proporcionen ideas para desarrollar nuevas estrategias para encontrar soluciones ptimas mediante la mejora de los algoritmos de solucin actuales o mediante el desarrollo de nuevos. De acuerdo a la literatura especializada, en general, la caracterizacin de instancias ha sido utilizada para predecir qu algoritmo resuelve mejor una instancia o para mejorar el algoritmo asociando las caractersticas de la instancia con el desempeo de dicho algoritmo. A diferencia de los trabajos anteriores, este trabajo propone que el desarrollo de algoritmos de solucin eficientes puede ser guiado por una previa identificacin de las caractersticas que representan un alto impacto en la dificultad para obtener su solucin. Para validar nuestro enfoque se utiliz un conjunto de 1,615 instancias, 6 algoritmos bien conocidos del problema de Bin Packing y 27 mtricas iniciales. Despus de aplicar tcnicas de agrupamiento de Minera de Datos para la caracterizacin de las instancias, se encontraron 5 mtricas que ayudaron a caracterizar 4 grupos con las instancias que no fueron resueltas por ninguno de los algoritmos usados en este trabajo. En base al conocimiento obtenido de la caracterizacin de las instancias, se propuso un nuevo mtodo de reduccin de instancias que contribuye a reducir el espacio de bsqueda de un algoritmo metaheurstico. Los resultados experimentales muestran que aplicando el mtodo de reduccin es posible encontrar ms soluciones ptimas que las reportadas en el estado del arte por las mejores metaheursticas.

Palabras clave. Metaheuristicas, bin paking, caracterizacin, agrupamiento, reduccin, descubrimiento de conocimiento.

Characterization of Difficult Bin Packing Problem Instances Oriented to Improve Metaheuristic Algorithms

Abstract. This work presents a methodology for characterizing difficult instances of the Bin Packing Problem using Data Mining. Characteristics of such instances help to provide ideas for developing new strategies to find optimal solutions by improving the current solution algorithms or developing new ones. According to related work, in general, instance characterization has been used to make prediction of the algorithm that best solves an instance, or to improve one by associating the instance characteristics and performance of the algorithm that solves it. However, this work proposes the development of efficient solution algorithms guided by previous identification of characteristics that represent a greater impact on the difficulty of the instances. To validate our approach, we used a set of 1,615 instances, 6 well-known algorithms of the Bin Packing Problem, and 27 initial metrics. After applying our approach, 5 metrics were found relevant; these metrics helped to characterize 4 groups containing instances that could not be solved by any of the algorithms used in this work. Based on the gained knowledge from instance characterization, a new reduction method that helps to reduce the search space of a metaheuristic algorithm was proposed. Experimental results show that application of the reduction method allows finding more optimal solutions than those of best metaheuristics reported in the specialized literature.

Keywords. Characterization, clustering, metaheuristics, bin packing problem, reduction, knowledge discovery.

1. Introduccin

En el rea de la computacin, uno de los problemas abiertos y vigentes es encontrar algoritmos eficientes y eficaces para resolver problemas de optimizacin discreta del tipo NP-hard [18, 24], como lo son Bin Packing, el Agente viajero, y el de la Mochila, entre otros, dichos problemas son comnmente encontrados en situaciones prcticas como la planeacin de la produccin y logstica. Este tipo de problemas son considerados de alta complejidad computacional ya que a la fecha no se conocen algoritmos que los puedan resolver en un tiempo polinomial. Con la finalidad de extraer conocimiento relevante que posibilite la generacin de nuevas estrategias que sean *incorporadas en los algoritmos de solucin actuales o que permitan la generacin de nuevos algoritmos, en este trabajo se aborda el problema de la caracterizacin de instancias difciles de resolver del problema de Bin Packing, cuya entrada es una secuencia de objetos de diferentes tamaos. El objetivo es colocar los objetos en el mnimo nmero de contendores de capacidad uniforme c, donde [23]. El trabajo propone un enfoque basado en la hiptesis: el desarrollo de algoritmos de solucin eficientes, puede ser guiado por una previa identificacin de las caractersticas que representan un alto impacto en la dificultad de las instancias. En este sentido, se utilizaron tcnicas de Minera de Datos con el propsito de caracterizar las instancias representativas del problema de Bin Packing que contribuyen en la obtencin de patrones que pueden ser utilizados en el desarrollo de estrategias para la mejora del desempeo de los algoritmos de solucin.

Para probar la hiptesis propuesta, se seleccionaron 1,615 instancias del problema de Bin Packing. Cada instancia fue resuelta con 6 algoritmos bien conocidos y caracterizada con 27 mtricas iniciales. Al aplicar la Minera de Datos se obtuvieron los siguientes resultados:

a)     identificacin de 5 caractersticas relevantes que permiten describir las instancias difciles de resolver,

b)    identificacin de cuatro patrones que contribuyen a la caracterizacin de 22 instancias cuya solucin ptima no fue alcanzada por ninguno de los 6 algoritmos utilizados,

c)     Tres soluciones ptimas que no han sido reportadas por las mejores metaheursticas de la literatura especializada.

Lo que resta del documento est estructurado de la siguiente forma: la Seccin 2 muestra los trabajos relacionados con esta investigacin, la Seccin 3 presenta la metodologa propuesta para la caracterizacin de instancias difciles de resolver del problema de Bin Packing donde a manera de ejemplo se presenta la interpretacin del conocimiento adquirido mediante el desarrollo un procedimiento de reduccin de instancias el cual es generado a partir de la caracterizacin de las mismas y su incorporacin sobre un algoritmo metaheurstico inspirado en HGGA_BP [33]. En la Seccin 4 se presentan los resultados experimentales de ejecutar nuestro algoritmo sobre un conjunto de instancias difciles de resolver, se destaca que fue posible encontrar ms soluciones ptimas que las obtenidas inicialmente. Finalmente, la Seccin 5 muestra las conclusiones obtenidas y los trabajos futuros.

2. Trabajos relacionados

A continuacin se describen algunos de los trabajos, donde la caracterizacin de instancias es de gran importancia para obtener soluciones ptimas de instancias difciles de resolver, en problemas NP. Los trabajos relacionados se dividieron en problemas NP y Bin Packing para mayor claridad del documento.

2.1. Problemas NP

De acuerdo al teorema No free lunch [42], no existe un algoritmo que domine la solucin de todas las instancias de un problema NP-duro. Trabajos como los desarrollados en [20, 31] sugieren que es indispensable el conocimiento de las caractersticas de las instancias a resolver para desarrollar algoritmos que sean eficientes en el clculo de soluciones. As por ejemplo, en el ao 2000 Merz [31] analiz la trayectoria de los algoritmos memticos aplicados a la solucin de instancias del problema de particin de grafos. Concluy que el agregar las caractersticas de las instancias, puede ayudar en el desarrollo de mtodos heursticos altamente eficientes. En el ao 2004 Hoos [20], mientras estudiaba el desempeo de un algoritmo de bsqueda local para el problema de MAX-SAT, incorpor un conjunto de mtricas que le permitieron valorar la dificultad de las instancias y con ello mejorar el desempeo del algoritmo.

2.2. Problema de Bin Packing

El problema de Bin Packing ha sido ampliamente estudiado; en trabajos como [1, 4, 7, 10, 11, 12,15, 16, 17, 19, 21, 25, 26, 27, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41] se han desarrollado diferentes algoritmos con el objetivo de encontrar procedimientos eficientes que contribuyan a resolver dicho problema, sin embargo, slo investigaciones como [9, 10, 32, 33, 34, 37] se han enfocado en la identificacin de las caractersticas que representan alto impacto en la dificultad de resolver instancias. Dicha caracterizacin ha sido utilizada para hacer predicciones sobre el algoritmo que puede resolver mejor un conjunto particular de instancias, o bien para mejorar un algoritmo dado, donde la caracterizacin se realiza a partir del desempeo del algoritmo sobre la instancia. El trabajo ms relevante en cuanto a caracterizacin de instancias del problema de Bin Packing es el desarrollado por Schwerin y Wscher en 1997 [37]. En ese trabajo se expres que el intervalo de donde son extrados los valores de los pesos de los objetos puede tener efectos severos en el tiempo de cmputo y la calidad de la solucin de los algoritmos. Se reportan como indicadores de dificultad para el algoritmo Fist Fit Decreasing (FFD): a) el peso de los objetos; b) la variabilidad y c) el efecto de multiplicidad. Cruz en 2004 [9] propuso un procedimiento sistemtico, basado en aprendizaje automtico y estadstica. En dicho trabajo se incorporaron y relacionaron caractersticas crticas del problema de Bin Packing que ayudaron a seleccionar el algoritmo que mejor resuelve un caso dado. Otro de los trabajos destacables es el desarrollado por Quiroz en los aos 2009-2013 [33, 34], en el cual se presenta la mejora del algoritmo HGGA-BP propuesto por primera vez en [10, 32]. Dicho trabajo presenta un anlisis exploratorio sobre el desempeo del algoritmo y un anlisis de las caractersticas de las instancias difciles de resolver y haciendo uso de relaciones obtiene informacin que permite realizar la mejora de un algoritmo de solucin.

Los trabajos anteriores sugieren dos factores clave en cuanto a la solucin de las instancias difciles de un problema, uno es la caracterizacin del tipo de instancia y el otro es el conocimiento que se tenga sobre el algoritmo que mejor resuelve ese tipo de instancias. En este trabajo, lo que se aborda es la caracterizacin de las instancias con el objetivo de encontrar los patrones que las hacen difciles de resolver.

3. Caracterizacin de instancias difciles mediante agrupamiento

La metodologa desarrollada para la caracterizacin de instancias difciles del problema de Bin Packing est basada en el modelo de referencia para Minera de Datos CRISP-DM [8] cuyas fases son: entendimiento del negocio y de los datos, preparacin de los datos, modelado, evaluacin y despliegue de resultados. La Figura 1 muestra el enfoque de solucin propuesto que incluye desde el preprocesado de los datos hasta la aplicacin del conocimiento que se extrae para la mejora o generacin de los algoritmos de solucin.

Se muestra adems que dado un conjunto de algoritmos, un conjunto de instancias y un conjunto de mtricas; la caracterizacin de las instancias se realiza a travs de la aplicacin de tcnicas de Minera de Datos donde como parte de la preparacin de datos: se extraen las soluciones de las instancias al aplicar diferentes algoritmos, esto con la finalidad de identificar las instancias ms difciles de resolver; a partir de un conjunto de mtricas se extraen los valores correspondientes a cada instancia y se selecciona un conjunto de mtricas que sean relevantes para caracterizar las instancias ms difciles de resolver. En la fase de modelado como su nombre lo indica, se modela la informacin, en este caso mediante agrupamiento y se obtienen los patrones que posibilitan describir las instancias difciles de resolver. Durante la fase de evaluacin, se analizan los patrones para extraer conocimiento.

Finalmente en la fase de despliegue de resultados, el conocimiento proporcionado por los patrones se incorpora como estrategia que al combinarse con los algoritmos de solucin actuales, permite obtener soluciones ptimas que previamente no han sido encontradas. Otra posibilidad de uso del conocimiento obtenido es la generacin de nuevos algoritmos para la solucin de problemas reales. Las Secciones 3.1-3.6 describen cada una de las fases.

3.1. Entendimiento del negocio

Durante esta fase se determin la siguiente hiptesis: el desarrollo de algoritmos de solucin eficientes puede ser guiado por una previa identificacin de las caractersticas que representan un mayor impacto en la dificultad de las instancias. Dada la hiptesis la caracterizacin de las instancias fue planteada en trminos de determinar cules son las instancias que son difciles de resolver por los algoritmos de solucin actuales, encontrar las caractersticas que mejor las describen, aplicar el conocimiento adquirido para la generacin de estrategias que redunden en la mejora y/o desarrollo de nuevos algoritmos de solucin. Para alcanzar el objetivo se generaron los siguientes objetivos particulares:

a)     Seleccionar un conjunto de instancias de prueba I = {i₁, ..., i_n}, un conjunto de algoritmos A = {a₁, ..., a_j} y un conjunto de mtricas M = {m₁, ...,m_l} que permitan la caracterizacin de las instancias.

b)    Calcular las soluciones de las instancias en I con los algoritmos en A, para obtener el conjunto de soluciones R = {r_1,1, ..., r_n,j} que permitan identificar cules son las instancias ms difciles de resolver.

c)     Reducir el conjunto inicial de mtricas M a partir de los valores obtenidos al aplicarlas sobre I y encontrar las que describan mejor a las instancias difciles de resolver.

d)    Modelar los datos mediante agrupamiento para encontrar un conjunto de patrones P = {p₁, ..., p_x}, que aporten informacin sobre las caractersticas de los conjuntos de instancias difciles de resolver del problema de Bin Packing.

e)     Interpretar el conocimiento extrado a partir de los patrones relacionados con las instancias difciles de resolver.

f)     Mediante el conocimiento adquirido, implementar al menos una estrategia que permita obtener mayor nmero de soluciones ptimas.

3.2. Entendimiento de los datos

En esta etapa se recopil y analiz la informacin que contribuy para caracterizar las instancias difciles de resolver del problema de Bin Packing de una dimensin. Los datos recopilados fueron los siguientes:

a)     un conjunto I de 1,615 instancias del problema de Bin Packing, ampliamente utilizadas para probar algoritmos de solucin por la comunidad cientfica: Triplets (80 instancias), uniform (80 instancias), gau_1 (17 instancias), set_1 (720 instancias), set_2 (480 instancias), set_3 (10 instancias), was_1

(100 instancias), was_2 (100 instancias) y Hard28 (28 instancias), cuyas soluciones ptimas fueron reportadas en [5, 6, 13,14], utilizando programacin lineal en algunos casos,

b)    un conjunto A de 6 algoritmos bien conocidos que son utilizados para resolver instancias del problema de Bin Packing, entre ellos cuatro algoritmos exactos: First Fit [22], Best Fit [22], Worst Fit [22] y Best3 Fit Decreasing [3] y dos algoritmos metaheursticos: HGGA-BP[11] y HI_BP [4] hasta el momento considerados de los ms robustos,

c)     un conjunto de 27 mtricas propuestas en la literatura especializada para la caracterizacin de instancias de Bin Packing [2, 9, 33], las cuales se listan a continuacin: tamao de la instancia (p), capacidad ocupada por un objeto promedio (t), dispersin del tamao del objeto (d), factores (f), uso de contenedores (b), media aritmtica (avg), media geomtrica (avg_g), media armnica (avg_a), mediana (M_e), moda (M_o). rango (r), desviacin media (D_m), varianza (σ²), desviacin estndar (σ), coeficiente de variacin de Pearson (C_v), coeficiente de asimetra de Pearson (A_p), asimetra de Pearson mediana (A_m), asimetra de Pearson moda (A_mo), coeficiente de asimetra de Bowley (A_B), curtosis (Cu), variacin entre cuartiles (V_Q), variacin entre deciles (V_D), objeto menor (min), objeto mayor (max), multiplicidad (λ), frecuencia de repeticin mxima (ν), uniformidad (U).

Durante el anlisis de los datos, se consider la posibilidad de extraer las caractersticas propias de las instancias difciles de resolver con la finalidad de obtener informacin que contribuyera a la generacin de estrategias de solucin de dichas instancias.

3.3. Preparacin de datos

Esta fase bsicamente consisti en preparar los datos para identificar las instancias difciles de resolver, en particular por los 6 algoritmos de prueba, adems se calcularon los valores de las 27 mtricas para las 1,615 instancias y mediante seleccin de caractersticas, se identificaron las mtricas que ayudaron a caracterizar dichas instancias.

Extraccin de soluciones

Para la identificacin de las instancias difciles de resolver se ejecutaron los 6 algoritmos (FirstFit, BestFit, WorstFit, Best3Fit Decreasing, HGGA-BP y HI_BP) con las 1,615 instancias. Como resultado se obtuvo un conjunto D con 22 instancias para las cuales ninguno de los algoritmos alcanz la solucin ptima. D = {TEST0082, TEST0014, TEST0030, TEST0058, TEST0005, BPP60, BPP832, BPP13, BPP709, BPP785, BPP144, BPP561, BPP781, BPP900, BPP195, BPP40, BPP645, BPP766, BPP181, BPP485, BPP419, BPP178}.

Extraccin de valores de mtricas

En esta fase para cada instancia de prueba se calcul cada una de las 27 mtricas con la finalidad de aplicar reduccin de caractersticas.

Seleccin de mtricas relevantes

Para encontrar las mtricas que mejor describen a las instancias difciles de resolver, se llev a cabo la fase de reduccin de caractersticas del proceso de minera de datos, donde 27 mtricas fueron utilizadas inicialmente (ver Seccin 3.2 inciso c), para realizar la reduccin, se calcul el valor de cada mtrica utilizando las 1,615 instancias, posteriormente se extrajo una muestra estratificada representativa de la informacin correspondiente a los valores calculados con un nivel de confianza del 95% y considerando un error de clculo del 5% con lo cual se obtuvo una muestra de 198 instancias a las cuales posteriormente se les aplic un anlisis de correlaciones para eliminar la redundancia de informacin. Como resultado se obtuvieron 8 mtricas relevantes, las cuales se describen a continuacin.

Para la descripcin de las mtricas considere que: n es el nmero de objetos en una instancia, w_i es el peso del objeto i, c es la capacidad del contenedor, es la suma total de los pesos de los objetos en una instancia y para toda i la funcin factor(c, w_i) identifica si un objeto es factor o no del contenedor c

.

1.     Tamao de la instancia. Expresa la relacin entre el tamao de una instancia y el tamao mximo resuelto. El valor de n_max se asign a 1,000, ya que corresponde con el nmero de objetos de la instancia mayor en I (ver expresin 1):

2.     Factores. Expresa la proporcin de objetos cuyos tamaos son factores de la capacidad del contenedor; un objeto i es un factor cuando la capacidad del contenedor c es mltiplo de su correspondiente tamao de objeto w_i. En general, las instancias con muchos factores se consideran fciles de resolver (ver expresin 2):

3.     Uso de contenedores. Cuantifica la proporcin de la suma de los tamaos de los objetos que pueden asignarse en un contenedor de capacidad c, y expresa la cantidad ideal de contenedores requeridos en la solucin. Cuando este cociente toma un valor mayor o igual a 1 significa que todos los objetos caben en un contenedor y se le asigna un valor de 1 a la mtrica (ver expresin 3):

4.     Media aritmtica. Expresa el promedio de los pesos de los objetos (ver expresin 4):

5.     Rango. Expresa la diferencia entre el peso mayor y el peso menor de los objetos en la instancia respecto de c (ver expresin 5):

6.     Coeficiente de asimetra de Pearson. Expresa la comparacin entre la media y los pesos de los objetos de la instancia para observar que tan simtricos son los datos (ver expresin 6):

donde σ es la desviacin estndar de los pesos de los objetos.

7.     Menor. Expresa el peso del objeto ms pequeo en la instancia, en relacin al tamao del contenedor y permite ubicar el inicio de la distribucin de pesos (ver expresin 7):

8.     Frecuencia de repeticin mxima. Expresa la frecuencia mxima con la que un peso se repite en el conjunto de objetos de la instancia (ver expresin 8). f_i es el nmero de veces en que w_i aparece en w_i, . . . ,w_n, V = {v₁, . . . , v_k} es el conjunto de valores diferentes en {f_i, . . . , f_n}:

La informacin relacionada con: instancias, resultados obtenidos al ejecutar los algoritmos y valores de las mtricas por instancia, fue almacenada en una base de datos para su posterior modelado.

3.4. Modelado

Para el modelado de los datos se utiliz la tcnica de agrupamiento, en particular el algoritmo k-means [29]. Durante la construccin del modelo fue necesario experimentar con varios valores iniciales de k hasta encontrar subconjuntos formados por las instancias difciles de resolver (D) y separados lo ms posible de las instancias que se pudieron resolver de forma ptima (I\D).

Despus de obtener una buena separacin de las instancias difciles de resolver, de manera emprica se busc reducir las mtricas que permitieran mantener los grupos generados.

El procedimiento de bsqueda del nmero de grupos tiene como objetivo encontrar (D∩I\D) = 0 o lo ms cercano a 0, y adems permite reducir el nmero de mtricas de manera emprica. Dicho procedimiento es representado por el Algoritmo 1, el cual recibe como parmetros de entrada un conjunto inicial de l*n valores, obtenidos al aplicar las l = 8 mtricas sobre las n = 1, 615 instancias en I, k₀ es el valor inicial de k y Δ corresponde a las unidades que se incrementar k en cada iteracin. La lnea 1 indica la inicializacin del nmero de grupos k a utilizar con k-means k₀ = 30, la lnea 2 indica el clculo de los k grupos utilizando k-means y los valores de las mtricas calculadas para cada instancia .

El agrupamiento se repite mientras no sean separados los conjuntos I y I\D o el siguiente incremento de k no mejore la separacin de los conjuntos (ver lnea 3). La lnea 4 indica el incremento al nmero de grupos a calcular por k-means y Δ corresponde a incrementos de 5 unidades por iteracin (lnea 5).

Durante la experimentacin se utilizaron valores de k =30, 35, 40, 45 y 50; se utiliz como criterio de seleccin del nmero de grupos, el nmero de grupos que separara de manera conveniente las instancias en D del resto, es decir, cuando los grupos que reunieran las instancias que no se pudieron resolver contuvieran el menor nmero de instancias resueltas por los algoritmos probados en este trabajo.

3.5. Evaluacin de resultados

Extraccin de patrones

Grupo	avg	m	ν	r	p
A	(0.280	0.01	0.06	0.73	.900)
B	(0.231	0.006	0.05	0.48	.890)
C	(0.370	0.008	0.018	0.691	.183)
D	(0.398	0.008	0.014	0.788	.180)

El mejor resultado se obtuvo al generar 45 grupos con k-means utilizando 5 mtricas (avg, m, ν, r, p) debido a que esta configuracin permiti una buena separacin de las instancias de D en 4 grupos denominados A, B, C y D los cuales se muestran a continuacin: A={TEST0082}; B={TEST0014, TEST0030, TEST0058, TEST0005, TEST0022, TEST0065, TEST0084}; C={BPP60, BPP832, BPP13, BPP709, BPP785, BPP144, BPP561, BPP781, BPP900, BPP195, BPP14, BPP119} y D={BPP40, BPP645, BPP766, BPP181, BPP485, BPP419, BPP178, BPP360, BPP47, BPP640, BPP814, BPP742, BPP531, BPP359, BPP716, BPP175}. Los grupos B, C y D contienen algunas instancias en letra cursiva que fueron resueltas previamente por los algoritmos utilizados.

En particular, los grupos A y B contienen 5 instancias del conjunto gau_1 que no fueron resueltas de forma ptima por los algoritmos de prueba y los grupos C y D contienen las 17 instancias no resueltas de forma ptima del conjuntoHard28. Los patrones correspondientes a cada uno de los grupos se muestran en la Tabla 1.

Extraccin de conocimiento

Dados los patrones mostrados en la Tabla 1 se puede observar que la instancia en el grupo A contiene objetos en promedio del 28% del tamao del contenedor c, el objeto menor es del 1% de c, en promedio los objetos se repiten el 6%, el rango entre los tamaos de los objetos es del 73% de c, lo que significa que hay objetos muy pequeos y muy grandes y adems la instancia es pequea, slo 90 objetos. En el caso del grupo B el promedio del tamao de las instancias es de 23% respecto de c, el objeto pequeo es del 0.6% respecto de c, slo el 5% de los objetos se repiten, el rango de los tamaos de los objetos es del 48% respecto de c y la instancia tambin es pequea, 89 objetos. El grupo C muestra que el promedio de los tamaos de los objetos es del 37% respecto de c, el objeto menor representa el 0.8% de c, slo se repite el 1.8% de los objetos, el rango entre el tamao de los objetos es del 69% respecto de c y la instancia es pequea, 183 objetos. El grupo D muestra que en promedio el tamao de los objetos es del 39.8% respecto de c, el objeto menor utiliza el 0.8% de c, slo el 14% de los pesos de los objetos se repiten, el rango de los pesos de objetos es del 78.8% lo cual indica que hay un rango amplio en el peso de los objetos y las instancias tambin son pequeas, 180 objetos en promedio.

De acuerdo a las caractersticas antes mencionadas y dado que el grupo D contiene el mayor nmero de instancias difciles de resolver, se determin que a manera de pre procesado de la instancia, era posible que algunos contenedores se pudieran llenar totalmente o a un alto porcentaje de su capacidad utilizando 2 objetos. Lo anterior con el objetivo de reducir el tamao de la instancia y el espacio de bsqueda del algoritmo metaheurstico que se le aplicar.

3.6. Despliegue de resultados: Incorporacin del conocimiento adquirido para la mejora de algoritmos

Con la finalidad de aplicar el conocimiento adquirido sobre llenar contenedores en un alto porcentaje utilizando dos objetos, se implement un procedimiento de reduccin denominado Γ que fue incorporado a una metaheurstica como parte del preprocesamiento de la instancia, dicho procedimiento es llamado de forma iterativa mientras no se alcance el valor ptimo o mientras la capacidad residual de la instancia lo permita. El objetivo de aplicar el procedimiento fue reducir el espacio de bsqueda del algoritmo metaheurstico.

La Figura 2 muestra cmo se aplica el enfoque de solucin, donde la parte superior de la figura corresponde a la instancia que ser resuelta, 1) representa la ejecucin del procedimiento de reduccin sobre I de lo cual se obtiene la solucin parcial s₁ y una nueva instancia reducida , 2) corresponde a solucin parcial s₂, producto de aplicar el algoritmo metaheurstico; 3) corresponde a la solucin final . Si el nmero de contenedores obtenidos por S no corresponde al lmite terico preestablecido (L₂ propuesto por Martello y Toth en [30]), se vuelve a repetir el procedimiento desde 1) actualizando y aumentando la capacidad residual del contenedor en una unidad.

Procedimiento de reduccin Γ

De acuerdo a las caractersticas de las instancias en el grupo D, el mecanismo para reducir instancias consisti en llenar los contenedores con capacidad c usando un par de objetos (w_a and w_b) tales que w_a + w_b = (c−umbral), donde a ≠ b. La variable umbral es un parmetro adaptable, en esta experimentacin, fue inicializado en 0 e incrementado en una unidad por iteracin, el umbral desempea la labor de administrador de la capacidad residual que le es permitida a un contenedor utilizando slo dos objetos en una iteracin dada. Bsicamente encuentra todos los pares de objetos que llenen la capacidad c del contenedor tanto como sea posible con el objetivo de reducir el espacio de bsqueda de los algoritmos de solucin del problema de Bin Packing.

El procedimiento de reduccin Γ est presentado por el Algoritmo 2, el cual recibe como parmetros de entrada la instancia I con los objetos ordenados de forma decreciente, el valor de la variable umbral inicializada en 0 en la primera iteracin del algoritmo que llamar a Γ, la capacidad del contenedor c y el nmero de contenedores a los que se les asignan objetos en la iteracin actual nBin. Para ubicar los pares de objetos, se colocan dos apuntadores, uno apunta al objeto con el peso mayor de la instancia (max) y el otro apunta al objeto con el peso menor de la instancia (min) (lneas 1 y 2). Mientras existan objetos que no han sido evaluados en la instancia y mientras los ndices de los apuntadores sean diferentes, el proceso de combinar objetos se repite (lnea 3). Si la suma de los pesos de los objetos del conjunto par actuales igual a c−umbral, el par de objetos es extrado de I y los objetos son asignados al contenedor nBin en la solucin y agregados a la instancia I′ (lneas 4, 5, 6 y 7). En caso contrario, si la suma es menor que c−umbral, el apuntador min apunta al siguiente objeto menor ms cercano (lneas 8 y 9). Para el caso del apuntador mayor (max), si la suma es mayor que c−umbral el apuntador max cambia de posicin y apunta al siguiente objeto menor (lneas 10 y 11). Al terminar el procedimiento de reduccin, la variable nBin contiene el nmero de contenedores a los cuales se les asignaron objetos y regresa el subconjunto I′que corresponde a una solucin parcial S₁ de la instancia I (lnea 14).

El procedimiento fue implementado de tal forma que evita iterar ms de lo necesario ya que cada par de objetos es evaluado como mximo una vez.

4. Experimentacin computacional

En esta seccin se muestran los resultados obtenidos al aplicar el procedimiento de reduccin propuesto en este trabajo, producto de la caracterizacin de las instancias difciles de resolver. El enfoque utilizado consisti en aplicar Γ seguido de una metaheurstica para solucionar instancias de Bin Packing de una dimensin. El enfoque se aplic sobre el grupo de instancias D, el cual contiene 7 instancias difciles de resolverse (BPP40, BPP645, BPP766, BPP181, BPP485, BPP419, BPP178). Para la realizacin de los experimentos computacionales el procedimiento de reduccin y la metaheurstica de solucin para Bin Packing de una dimensin fueron implementadas en lenguaje C. Se utiliz un equipo con procesador Intel core i7, 2GHz, 4GB en RAM, 32 bits y el sistema operativo Windows 7.

La metaheurstica utilizada durante la experimentacin fue inspirada en el algoritmo de solucin HGGA-BP [33], en lo sucesivo nos referiremos a ella como Η. El enfoque de solucin de instancias consisti en aplicar de forma alternativa el procedimiento Γ y la metaheurstica Η. Despus de aplicar el enfoque de solucin sobre las instancias del grupo D fue posible obtener los valores ptimos alcanzados por los algoritmos de prueba y adicionalmente se encontraron las soluciones ptimas para las instancias BPP181, BPP485 yBPP178, dichas soluciones no han sido reportadas en la literatura por ninguna de las metaheursticas conocidas. El tiempo en encontrar dichos valores fue de 15.53, 6.98 y 6.34 segundos respectivamente.

La Tabla 2 presenta una comparativa entre las soluciones obtenidas por los mejores algoritmos metaheursticos reportados en la literatura (HI_BP [4], Pert-SAWMBS [16] y HGGA-BP [11]) y los resultados obtenidos despus de aplicar nuestro enfoque. Los resultados corresponden a las instancias del grupo D. En la Tabla 2 la columna Inst corresponde al nombre de la instancia, la columna opt corresponde al valor ptimo conocido y las columnas HI_BP, Pert, HGGA−BP y EsteTrabajo corresponden a cada uno de los algoritmos que se comparan. En la columna EsteTrabajo los asteriscos (*) indican las instancias para las cuales slo nuestro algoritmo alcanz los valores ptimos (remarcado en gris) y el signo positivo (+) sirve de identificador para aquellas instancias que ms de un algoritmo alcanza los valores ptimos.

Las soluciones ptimas encontradas son presentadas a continuacin. Por cada instancia se muestra el nombre de la misma, separado por un guin, el nmero de contenedores utilizados en la solucin, el valor hasta el cual lleg la variable (umbral) y el tiempo consumido en obtener la solucin. Posteriormente se muestran los contenedores que fueron llenados al utilizar el procedimiento de reduccin Γ y los contenedores utilizados al aplicar el algoritmo metaheurstico Η.

Solucin de la instancia BPP178 - 80, umbral = 1, tiempo = 6.34 seg.

Procedimiento de reduccin Γ:

(790 210) (786 214) (743 257) (724 276) (646 354) (640360) (637 363) (635 365) (629 371) (613 387) (605 395) (541 459) (531 469) (518 482) (515 485) (506 494) (724275) (678 321) (662 337) (644 355) (583 416) (580 419)(568 431) (523 476) (512 487)

Algoritmo metaheurstico Η:

(723 174 103) (704 292 4) (691 168 141) (189 709 102)(223 673 104) (423 518 59) (164 278 558) (519 408 72 1)(699 240 61) (436 157 407) (667 328) (116 184 700) (147347 506) (793 146 61) (732 266) (213 179 608) (602 396)(196 608 196) (504 446 50) (658 93 249) (119 415 466)(595 400) (212 443 345) (736 220 44) (94 170 736) (518232 250) (772 226) (756 242) (471 468 61) (628 370) (45278 677) (713 221 66) (662 336) (764 233) (535 462) (740209 51) (692 185 123) (133 250 617) (712 233 55) (517447 36) (185 21 794) (517 171 312) (703 181 116) (659334 7) (622 369 9) (572 423) (742 254) (509 487) (633 246120) (612 346 41) (740 252) (691 208 99) (625 370) (595399) (521 313 166)

Solucin de la instancia BPP485 - 71, umbral = 1, tiempo = 6.89 seg.

Procedimiento de reduccin Γ:

(800 200) (782 218) (756 244) (751 249) (747 253) (742258) (713 287) (693 307) (645 355) (621 379) (600 400) (594 406) (586 414) (584 416) (579 421) (577 423) (548452) (777 222) (759 240) (717 282) (694 305) (661 338)(657 342) (654 345) (607 392)

Algoritmo metaheurstico Η:

(540 14 446) (569 28 403) (570 54 376) (784 188 28) (42256 702) (138 276 586) (627 316 55) (335 574 91) (780117 103) (765 226 9) (688 263 47) (59 654 286 1) (758240) (633 10 357) (126 631 243) (559 317 124) (581 237182) (127 606 267) (351 644 5) (159 782 59) (505 482 13)(790 208) (612 380 8) (77 272 651) (116 765 119) (574277 149) (128 132 740) (788 141 70) (705 58 237) (103264 633) (639 359) (77 224 697) (405 405 190) (17 444539) (161 444 395) (752 245) (675 322) (541 455) (529467) (600 396) (796 197) (523 450 27) (90 404 506) (224706 68) (504 450 43) (445 289 266)

Solucin de la instancia BPP181 - 72, umbral = 4, tiempo = 15.53 seg.

Procedimiento de reduccin Γ:

(799 201) (745 255) (733 267) (721 279) (713 287) (703 297) (673 327) (660 340) (648 352) (646 354) (603 397) (545 455) (532 468) (523 477) (797 202) (770 229) (651 348) (641 358) (623 376) (548 451) (503 496) (706 292) (702 296) (680 318) (597 401) (758 239) (684 313) (629 368) (610 387) (561 436) (525 472) (679 317) (603 393) (525 471)

Algoritmo metaheurstico Η:

(32 659 309) (158 66 776) (699 278 23) (572 363 65) (45 372 583) (118 127 755) (51 750 199) (305 30 665) (39 407 554) (103 183 714) (144 755 101) (458 200 342) (214 120 666) (307 171 522) (276 109 615) (79 711 210) (120 128 752) (172 399 429) (697 281 22) (201 494 305) (661 276 63) (183 776 41) (391 197 412) (108 793 99) (328 215 457) (536 434 30) (457 278 265) (714 219 66) (531 432 36) (639 326 34) (51 372 577) (736 169 94) (610 307 82) (666 326 7) (620 257 123) (583 411) (572 407 20) (513 481)

5. Conclusiones y trabajos futuros

En este trabajo se muestra que la metodologa propuesta para la caracterizacin de instancias difciles del problema de Bin Packing de una dimensin contribuye a la generacin de estrategias para la mejora de los algoritmos de solucin actuales.

Despus de aplicar la metodologa propuesta sobre un conjunto de 1,615 instancias y un conjunto inicial de 27 mtricas para el problema de Bin Packing, se encontraron 5 mtricas relevantes (promedio de los pesos de los objetos avg, peso del objeto menor m, frecuencia de repeticin de los objetos ν, rango entre el cual se encuentran los pesos de los objetos r y tamao de la instancia p) que permitieron caracterizar las instancias difciles de resolver por 6 algoritmos bien conocidos del estado del arte, dos de ellos considerados de los ms robustos. Con las 5 mtricas relevantes fue posible identificar 4 patrones correspondientes a las instancias difciles de resolver. Las caractersticas de uno de los grupos sugirieron la posibilidad de desarrollar un nuevo procedimiento de reduccin del tamao de las instancias al cual denominamos Γ. Al aplicar el procedimiento de reduccin Γ con un algoritmo metaheuristico Η sobre uno de los grupos con instancias difciles de resolver fue posible encontrar las soluciones ptimas previamente reportadas y 3 adicionales que no han sido reportadas por ninguno de los algoritmos metaheursticos conocidos.

Consideramos que el enfoque utilizado para la caracterizacin de instancias, tambin puede ser til en la caracterizacin de instancias difciles de otros problemas NP. Como trabajo futuro se propone realizar un anlisis ms profundo sobre las caractersticas especficas de los patrones encontrados para los grupos de instancias C y D, con el objetivo de generar estrategias que permitan encontrar los valores ptimos para las instancias cuyo valor ptimo no se alcanz.

Referencias

1.     Afza, N., Zulkipli, F., Sarah, S., & Radiah, S. (2014). An Alternative Heuristics for Bin Packing Problem. Proceedings of the 2014 International Conference on Industrial Engineering and Operations Management, Bali, Indonesia, January 79.

2.     lvarez, V. (2006). Modelo para representar la complejidad del problema y el desempeo de algoritmos. Tesis de maestra, Instituto Tecnolgico de Cd. Madero, Mxico.

3.     Alvim, A. (2003). Uma heurstica hbrida de melhoria para o problema de Bin Packing e sua aplicao ao problema de escalonamento de tarefas. Tesis de doctorado, Pontificia Universidad Catlica de Rio de Janeiro, Brasil.

4.     Alvim, A., Glover, F., Ribeiro, C., & Aloise, D. (2004). A hybrid improvement heuristic for the one-dimensional Bin Packing problem. Journal of Heuristics, Vol. 10, pp. 205229. DOI: 10.1023/B:HEUR.0000026267.44673.ed

5.     Beasley, J. (2015). The operational research library, http://people.brunel.ac.uk/~mastjjb/jeb/orlib/binpackinfo.html, ltima visita: enero de 2015.

6.     Belov, G. (2004). Problems, models and algorithms in one and two dimensional cutting. Tesis de doctorado, Fakultt Mathematik und Naturwissenschaftender Technischen Universitt Dresden, Alemania.

7.     Bhatia, A. & Basu, S. (2004). Packing bins using multi-chromosomal genetic representation and better-fit heuristic. Neural Information in Processing, Springer, pp. 181186. DOI: 10.1007/978-3-540-30499-9_26

8.     Chapman, P., Clinton, J., Kerber, R., Khabaza, T., Reinartz, T, Shearer, C., & Wirth, R. (2000). Cross industry standard process for datamining version 1.0 step by step datamining guide, ftp://ftp.software.ibm.com/software/analytics/spss/support/Modeler/Documentation/14/UserManual/ CRISPDM.pdf, ltima visita: enero de 2015.

9.     Cruz, L. (2004). Clasificacin de algoritmos heursticos para la solucin de problemas de BinPacking. Tesis de doctorado, Centro Nacional de Investigacin y Desarrollo Tecnolgico, Mxico.

10.   Cruz, L., Nieto, Y., Toms, S., & Castilla, V. (2007). Solving Bin Packing problem with a hybridization of hard computing and soft computing. Innovations in Hybrid Intelligent Systems, Springer, pp. 223230. DO:10.1007/978-3-540-74972-1_30

11.   Cruz, L., Quiroz, M., Alvim, A., Fraire, H. Gmez, S., & Torres, J. (2012). Heursticas de agrupacin hbridas eficientes para el problema de empacado de objetos en contenedores. Computacin y Sistemas, Vol. 16, No. 3, pp. 349360.

12.   Ducatelle, F. & Levine, J. (2004). Ant colony optimization and local search for Bin Packing and Cutting Stock problems. Journal of the Operational Research Society, Vol. 55, pp. 705716. DOI:10.1109/ICSPC.2007.4728416

13.   Dresden University. (2015). Cutting and packing, http://www.math.tudresden.de_capad/cpd-ti.html#pmp, ltima visita: enero de 2015.

14.   ESICUP. (2015). Euro especial interest group on cutting and packing (esicup), http://paginas.fe.up.pt /_esicup/tikilist_file_gallery.php?galleryId=1, ltima visita: enero de 2015.

15.   Falkenauer, E. (1999). A hybrid grouping genetic algorithm for Bin Packing. Journal of Heuristics, Vol. 2, pp. 530. DOI: 10.1007/BF00226291

16.   Fleszar, K. & Charalambous, C. (2011). Average-weight-controlled bin oriented heuristics for the one-dimensional Bin-Packing problem. Discrete Optimization, Vol. 210, pp. 176184. DOI:10.1016/j.ejor.2010.11.004

17.   Fleszar, K. & Hindi, K. (2002). New heuristics for one-dimensional Bin-Packing. Computers & Operations Research, Vol. 29, pp. 821839. DOI:10.1016/S0305-0548(00)00082-4

18.   Garey, M.R., & Johnson, D.S. (1979). Computers and Intractability: a Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York.

19.   Gmez, M. & Randall, M. (2009). A hybrid extremal optimization approach for the Bin Packing problem. Artificial Intelligence, Springer, pp. 242251. DOI:10.1007/978-3-642-10427-5_24

20.   Hoos, H. Smyth, K., & Stutzle, T. (2004). Search space features underlying the performance of stochastic local search algorithms for MAX-SAT. Parallel Problem Solving from Nature, Springer, pp. 5160. DOI:10.1007/978-3-540-30217-9_6

21.   Jing, X., Zhou, X., & Xu, Y. (2006). A hybrid genetic algorithm for Bin Packing problem based on item sequencing. Journal of Information and Computing Science, Vol. 1, pp. 6164.

22.   Johnson, D. (1973). Near-optimal Bin Packing algorithms. PhD Thesis, Massachusetts Institute of Technology, Massachusetts.

23.   Kamali, S. & Lpez, A. (2015). Efficient Online Strategies for Renting Servers in the Cloud. SOFSEM 2015, LNCS, Vol. 8939, Springer, pp. 277288. DOI:10.1007/978-3-662-46078-8_23

24.   Kacprzak, Ł., Rudy, J., & Żelazny, D. (2015). Multicriteria 3-dimension Bin packing Problem. Research in logistics and production, Vol. 5, pp. 8594.

25.   Kasap, N. & Agarwal, A. (2004). Augmented-neural networks approach for the Bin Packing problem, Proceedings of the 4th International Symposium on Intelligent Manufacturing Systems, pp. 348358.

26.   Layeb, A. & Chenche, S. (2012). A Novel GRASP Algorithm for Solving the Bin Packing Problem. I.J. Information Engineering and Electronic Business, Vol. 2, pp. 814.

27.   Loh, K., Golden, B., & Wasil, E. (2008). Solving the one-dimensional Bin Packing problem with a weight annealing heuristic, Computers & Operations Research, Vol. 35, No. 7, pp. 22832291. DOI:10.1109/ICSPC.2007.4728416

28.   Lpez, E., Terashima, H., Ross, P., Ochoa, G. (2014). A unified hyper-heuristic framework for solving bin packing problems. Expert Systems with Applications, Vol. 41, pp. 68766868. DOI:10.1016/j.eswa.2014.04.043 89

29.   MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the fifteenth Berkeley Symposium on Mathematical Statistics and Probability, pp. 281298.

30.   Martello, S. & Toth, P. (1990). Lower bounds and reduction procedures for the Bin Packing problem. Discrete Applied Mathematics, Vol. 28, pp. 5970. DOI:10.1016/0166-218X(90)90094-S

31.   Merz, P. & Freisleben, B. (2000). Fitness landscapes, memetic algorithms and greedy operators for graph bi-partitioning. Evolutionary Computation, Vol. 8, pp. 6191. DOI:10.1162/106365600568103

32.   Nieto, D. (2007). Hibridacin de algoritmos metaheursticos para problemas de Bin Packing. Tesis de Maestra, Instituto Tecnolgico de Cd. Madero, Mxico.

33.   Quiroz, M. (2009). Caracterizacin de factores de desempeo de algoritmos de solucin de Bin Packing. Tesis de maestra, Instituto Tecnolgico de Cd. Madero, Mxico.

34.   Quiroz, M. Cruz, L., Torres, J., Gmez, C., Fraire, H., & Alvim A. (2015). A grouping genetic algorithm with controlled gene transmission for the bin packing problem. Computers & Operations Research, Vol. 55, pp. 5264.

35.   Quiroz, M., Cruz, L., J. Torres, Gmez, C.G., Fraire, H.J., & Melin, P. (2013). Improving the Performance of Heuristic Algorithms Based on Exploratory Data Analysis. Recent Advances on Hybrid Intelligent Systems, Vol. 451, pp. 361375. DOI:10.1007/978-3-642-33021-6_29

36.   Scholl, A., Klein, R., & Jrgens, C. (1997). Bison: a fast hybrid procedure for exactly solving the one-dimensional Bin Packing problem. Computers & Operations Research, Vol. 24, No. 7, pp. 627645. DOI:10.1016/S0305-0548(96)00082-2

37.   Schwerin, P. & Wscher. G. (1997).The Bin-Packing problem: a problem generator and some numerical experiments with FFD packing and MTP. International Transactions in Operational Research, Vol. 4, No. 5-6, pp. 337389. DOI: 10.1111/j.1475-3995.1997.tb00093.x

38.   Sim, K., Hart, E., & Paechter.B. (2013). Learning to Solve Bin Packing Problems with an Immune Inspired Hyper-heuristic. Artificial Immune Systems ICARIS, pp. 856863. DOI: 10.7551/978-0-262-31709-2-ch126

39.   Singh, A. & Gupta. A. (2007). Two heuristics for the one-dimensional Bin-Packing problem. OR Spectrum, Vol. 29, No. 4, pp. 765781. DOI:10.1007/s00291-006-0071-2

40.   Stawowy. A. (2008). Evolutionary based heuristic for Bin Packing problem. Computers & Industrial Engineering, Vol. 55, No. 2, pp. 465474. DOI:10.1016/j.cie.2008.01.007

41.   lker, O., Korkmaz, E., & zcan. E. (2008). A grouping genetic algorithm using linear linkage encoding for Bin Packing. Parallel Problem Solving from Nature, Springer, pp. 11401149. DOI:10.1007/978-3-540-87700-4_113

42.   Wolpert, D., & Macready, W. (1996). No free lunch theorems for optimizations. IEEE Transactions on Evolutionary Computation, Vol. 1, pp. 6782. DOI:10.1109/4235.585893

Adriana Mexicano Santoyo recibi el grado de Doctora por el Centro Nacional de Investigacin y Desarrollo Tecnolgico. Actualmente es profesora en el Instituto Tecnolgico de Cd. Victoria. Sus intereses de investigacin incluyen anlisis de algoritmos y optimizacin combinatoria entre otros.

Joaqun Prez Ortega recibi el grado de Doctor por el Tecnolgico de Monterrey. Es profesor investigador en el Centro Nacional de Investigacin y Desarrollo Tecnolgico. Actualmente pertenece al Sistema Nacional de Investigadores (SNI), es miembro Senior del IEEE y autor de ms de 100 publicaciones en bases de datos, heursticas y optimizacin.

Gerardo Reyes Salgado recibi el grado de Doctor por el Instituto Nacional Politcnico de Grenoble (Francia). Es profesor-investigador en el Centro Nacional de Investigacin y Desarrollo Tecnolgico. Autor de ms de 60 publicaciones en temas de prediccin y optimizacin con diferentes tcnicas de machine learning e inteligencia artificial.

Nelva Nely Almanza Ortega recibi el grado de Maestra en Ciencias por el Centro Nacional de Investigacin y Desarrollo Tecnolgico. Actualmente estudia el Doctorado en la misma institucin. Sus intereses de investigacin incluyen Ingeniera de Software, Anlisis de Algoritmos y Minera de Datos. 

Artculo recibido el 26/08/2013; aceptado el 21/04/2015.
Autor de correspondencia es Adriana Mexicano Santoyo.