Evaluación Experimental del Problema de Flujo no Divisible de Costo Mínimo con única fuente mediante la aplicación de Algoritmos Genéticos

Resumen

Resumen: En este trabajo se considera el problema de encontrar un flujo que satisfaga la demanda de ciertos productos, en una red con capacidades y costos, de manera que cada demanda sea enviada por un único camino hacia su destino, el costo total sea mínimo y la capacidad de los arcos se viole por el menor factor posible. El problema expuesto es NP-difícil. El mejor algoritmo que se conoce, da una aproximación (3,1) para la congestión y costo respectivamente. Sin embargo, en el 2001 Goemans conjeturó que es posible encontrar una aproximación (2,1) para el problema. Partiendo de un grupo de instancias utilizadas en trabajos previos, proponemos realizar una evaluación exhaustiva de la conjetura de Goemans de acuerdo a un modelo de optimización de programación entera, generando nuevas instancias de prueba a través de un algoritmo genético. En este trabajo se tomaron siete instancias iniciales, y se obtuvieron 844 nuevas instancias de prueba. Para las 132 instancias factibles se verificó la conjetura de Goemans y se mejoró la población con 9 nuevos individuos.

Abstract: We consider the problem of finding an unsplittable flow that satisfies the demand of a given set of products on a capacitated network with arc costs, such that the total cost is minimum and arc capacities are violated by the lower possible factor. The stated problem is NP-hard. The best known algorithm for the problem gives a (3,1)-approximation for congestion and cost respectively. However, since 2001, there exists a conjecture by Goemans saying that it is possible to find a (2,1)-approximation for the problem.Here, taking a number of instances used previously in the literature, we propose a thorough evaluation of Goemans’ conjecture according to an integer programming model and genetic operators.This work starts with seven instances and 844 new instances were obtained. Goemans’ conjecture holds for all 132 feasible instances and nine better individuals in terms of congestion have been added to theinitial population.