The Research On Bilevel Integer Programming Algorithm Based On Plant Growth Simulation

Multilevel programming is an effective way to solve the dispersedecision-making problem, in which believel programming is the most common andimportant research field. Fruther more, solving believel integer programming is themost diffcult in believel programming. Because solving integer programming is muchmore difficult than solving normal programmings, no general and effective integerprogramming algorithm is found for both linear and non-linear programmings duringalmost a half century from 1960's. The difficulty in solving single-level integerprogramming is what makes multilevel integer programming one of the difficultmultilevel programming problems.Among tradition algorithms, discrete searching algorithm for non-linear integerprogramming and filling function algorithm are the commonly effective methods tosolve a global optimization for integer programming. Plant growth simulationalgorithm is first proposed herein for solving integer programming. This Algorithm isa kind of bionics random algorithm which occurs in nature. Bionics algorithms havemade great progress in recent years. The algorithms including simulated annealingalgorithm, genetic algorithm and aunt algorithm, simulate the self-adapted mode ofdifferent biomes for environment in nature, set up random, positive feedback,harmony dynamics models that can make solution to escape from the local minimum.In the numerous bionics models most of them simulate animals and insects. Littleattention is paid to the natural optimization models simulating plant growth, forexample the plant phototropism mechanism. Among the limited plant models, theplant configuration occurrence model proposed by Turing, and the plant branchingmodel proposed by A. Lindenmager and P. Prusinkiewca, are aiming at computerfigures and fractal theory. It is a new research field for plant growth dynamicsmechanism to be used to solve integer programming. The plant growth simulationalgorithm simulates the plant phototropism mechanism, regards the feasible region ofinteger programming as plant growth environment, decides the plant growthinformation according to the changes of feasible solutions to the objective functions,and sets up the dynamics mechanism of branches and leaves growing rapidly towardslights. The non-linear integer programming problems of several global optimalsolutions with both un-constraint and constraint are easily solved by the plant growthsimulation algorithm proposed herein, with the solutions satisfied and the algorithmwell verified. Based on the work above, the plant growth simulation algorithm isdeveloped to bilevel integer programming field in this dissertation. The algorithm isused to solve the price control problem, the personal resource planning problem, themachines and equipments distribution problem, etc. Therefore, the establishment andapplication of bilevel integer programming theory and model are accomplished withthe plant growth simulation algorithm, so that a new research orientation of bionicsalgorithms is found in this dissertation.The research in this dissertation was surpported by National Natural ScienceFoundation of China in 2003. (No:70371051)...