Mochila cuadratica

[pic 1]

Integrantes: José Humberto Mendoza Alfaro - 1535422

Materia: Tópicos Selectos de Optimización

Hora: V3- V6

Maestro/a: M Angélica Salazar Aguilar

Fecha: 09/09/2014

Tema: Quadratic Knapsack Problem

(Problema de la mochila cuadrática)

Introducción

Knapsack problem: “Empacado de objetos dentro de la mochila”

El problema se define con la siguiente descripción:

Se tiene una determinada instancia de KP con un conjunto de objetos N, que consiste de n objetos j con ganancia pj y peso wj, y una capacidad c. (Usualmente, los valores toman números enteros positivos). El objetivo es seleccionar un subconjunto de N tal que la ganancia total de esos objetos seleccionados es maximizado y el total de los pesos no excede a c.

[pic 2]

Esta sería la descripción sencilla de comprender de cómo funciona el problema básico de optimización combinatoria representado en el problema de la mochila, el reporte hará uso de estas bases integrándose en un tema de más complejidad, pues nos referimos a una variante extra en este problema que lo denomina Mochila cuadrática.

Existen muchos ejemplos sobre este tipo de problemas lineales (Knapsack problema), donde se considera solo el beneficio de elegir un determinado artículo de los demás elementos seleccionados y estos problemas tienen gran aplicación en la vida real.

En un problema de raíces de la teoría de grafos, es natural el suponer que el beneficio de un embalaje (empacado) también debe reflejar lo bien que los elementos dados encajan, una posible formulación de una interdependencia tal es el problema de la mochila cuadrática (QKP) en el que un elemento tiene un beneficio correspondiente y un beneficio adicional es redimido si el elemento está seleccionado junto con otro elemento, por lo que ahora cada elemento depende del contenido actual de la mochila, y esta característica eleva las posibilidades de una mejor solución al problema de la mochila simple.

Esta teoría o aplicación fue ideada por Gallo, Hammer y Simeone, y es estudiado actualmente con intensidad debido a su simple estructura y dificultad elevada.

Para definir formalmente el problema asumamos que nos dan n elementos, j elementos y con un peso entero positivo Wj, y un límite en el total del peso que representa la capacidad de la mochila (c), además se nos da una matriz n x n entera no negativa P =  (Pij) , donde (Pjj) representa la ganancia alcanzad si se alcanza el punto j y Pij + Pji es un beneficio logrado si los dos elementos i y j se seleccionan.

QKP (Quadratic Knapsack Problem) llama a seleccionar un subconjunto de elementos cuyo peso total no sobre pace el limite c , a fin de maximizar los beneficios , recordemos que el conjunto de artículos en N := {1,…,n}.

Mediante la introducción de una variable binaria Xj igual a 1 si se selecciona el punto j y 0 en caso contrario, el problema tiene la formulación de programación entera siguiente:

[pic 3]

Entonces …

[pic 4]

Entonces los beneficios en la matriz son simétricos, es decir Pij = Pji, para toda i, i E N, Pero si los valores del peso son negativos wj < 0 es posible que lanzamos variable xj de 1 - xj. Si W}> c podemos arreglar Xj = 0, y si wj = c entonces podemos descomponer el problema. Por lo tanto, normalmente 0 <= que wj < c. Si Pij > 0 para todos los coeficientes i f. j se denota la supermodular el problema de la mochila. Nos apoyaremos en la hipótesis más fuerte de que todos los coeficientes pij > 0, lo que no se hace sin pérdida de generalidad. Dónde límites superiores y otros resultados son válidos por un modelo más general, que se harán constar en el texto.

Uno mismo puede dar varias interpretaciones en la teoría de grafos para QKP, Dada un grafo no dirigido en conjunto de nodos N, donde cada nodo j tiene ganancias Pij y el peso Wj y cada arista (i, j) tiene un beneficio Pij + Pj i, seleccionar un subconjunto nodo S => N cuya global peso no exceda c a fin de maximizar el beneficio global, dado por la suma de las ganancias de los nodos en S y de los bordes con ambos extremos en S.

[pic 5]

Una aplicación al problema de la mochila cuadrática aparece en las telecomunicaciones, cuando una serie de sitios para las estaciones de satélite han de ser seleccionado, de manera que el tráfico global entre estas estaciones se maximiza y se respeta una restricción presupuestaria.

Aunque existe una variedad amplia de métodos de solución para este tipo de problemas cuadráticos de optimización, nos enfocaremos solo en heurísticas de aproximación y comentaremos sobre la existencia de algunas otras soluciones.

Métodos de solución

Heurística

Podemos dividir la heurística para (QKP) en dos clases: El primal, que mantener la viabilidad a lo largo de la construcción, y el dual que parten de un solución factible y se esfuerzan por lograr una solución factible.

Gallo, Hammer y Simeone presentaron una familia de heurísticas primarias correspondientes a los límites en base en planos superiores.

[pic 6]

Se puede obtener una solución factible por truncando las variables fraccionarios.

Gallo, Hammer y Simeone proponen para avanzar mejorar una solución factible, a través de una secuencia de relleno y las operaciones de cambio según lo propuesto por Peterson. Hammer y Rader presentan una heurística primal diferente, llamado LEX, basado en el mejor L2-aproximación lineal de (QKP) tal como se presenta en Hammer y Holzman.

Algoritmos de Aproximación

Dado que QKP es un problema de gran dificultad se recurren a soluciones parciales que pueden ser una solución factible que no requiere tanto esfuerzo / tiempo en llegar a ella.

...