A Class Of Bilevel Programming Charactered By Topological Structure Optimization And Applications

The bilevel programming characted by topological struture optimiza- tion is ofen encountered in the process of production and management. For example, road net designment, heat exchange net design and optimization, truss structure design, the layout of workshops, assembly line design and the layout occured in satellite cables all belong to this type problems. since the problems are NP-hard, there lacks optimality theory , so the current so- lution procedures often turn to heuristic methods. The paper applies graph theory, group theroy, convex analysis, non-smooth optimization to study the problems and obtained the following results: 1 A bilelel programming model is constructed on the basis of point-valued mapping, set-valued mapping, and seperation theorem for the first time (BP) mm F(ai~,y) s.t. xEX ~ Arg min{F(x,y)Iy E ~2(a~)} where the upper level is about topological structure optimization(a~ is a topological structure varable), and the lower level is a constrained programming about continuous variable y. 2 Apply graph, the action of permutation group on a graph, equiva- lent class, orbit etc. for the first time to study topological structure optimization. Divide the domain into finite number of sub-domain, such overcome the on-off nature disturbing topological structure opti- niization, which also founds the theory basis for acheving the global optiniization solution for the problems. 3 Develop an improve generic algorithm and LCABS algorithm according to the above theories, by which an algorithm for (BP) is constructed. 4 Apply convex scperation theorem, the action of pcrmutaion group on a graph. stability set, orbit ~o study the layout of satellite cables, and 111 obtain an equivalent explicit form for the non-overlap and capacity constraints for the first time, and construct a bilevl programming for the problem. 5 Construct a bilevel programming charactered by topological structure for heat exchange net for the first time, and some conditions for global. solutions are also studied. 6 Construct for the first time a bilevel programming charactered by topo- logical structure fOr job-shop scheduling problems and the new model integrates the main three factors occured in the problem: scheduling, lot and start-time.