Convergence of Two Optimization Methods in Integer Programming: An Empirical Analysis

2個整數規劃之收斂最佳化模式－實驗分析

吳怡德(Yi-Te Wu)

《興國學報》 7期 (2007/01) Pp. 251-262

https://doi.org/10.29950/JHKUM.200701.0016

並列摘要

In this paper, we investigate the convergence properties of two very different optimization methods, Lagrangean relaxation and decomposition technique and Genetic Algorithm optimization, in integer programming. Using ANSI C codes designed by us, we applied these two methods on the famous facility location problem for optimality. We find that these two methods can perform quite differently, either in terms of convergence rates, or in terms of their final solutions. We also confirmed that initial population used in Genetic Algorithm optimization should be chosen carefully, as different initial population can give out quite different outcomes. As a result, there is no general result guaranteeing the convergence of a genetic algorithm to the global optimum.

並列關鍵字

optimization ； integer programming ； Lagrangean Relaxation and Decomposition Technique ； Genetic Algorithm Optimization

參考文獻

Aarts, E.(Ed.),Lenstra, J.(Ed.)(1997).Local Search in Combinatorial Optimization.Wiley.

Avriel, M.(Ed.),Golany, B.(Ed.)(1996).Mathematical Programming for Industrial Engineers.Marcel Dekker.

Bertsekas, D. P.(1995).Nonlinear Programming.Athena Scientific.

Fourer, R.,Gay, D.,Kernighan, B.(2003).AMPL: A Modeling Language for athematical Programming.Pacific Grove:Brooks/Cole-Thompson Learning.

Wolsey, L.(1998).Integer Programming.John Wiley.