This thesis is concerned with developing a heuristic algorithm for solving a class of nonlinear integer programs(NLIP). Exact algorithms for solving a NLIP either may not exist, or may take an unrealistically large amount of computing time. This thesis develops a new heuristic, the Excursion Algorithm(EA), for solving a class of NLIP's. The proposed EA consists of three parts: 1) construction of an initial feasible solution, 2) excursions over a bounded region, and 3) stopping rules. It is the second part that distinguishes the EA from the other existing heuristic methods. It turns out that excursions over a bounded feasible and/or infeasible region is effective in alleviating the risks of being trapped at a local optimum.
The developed EA is applied to the constrained redudancy optimization problems in complex systems, and is compared with other existing heuristic methods. We also include simulated annealing (SA) method in the comparision experiment due to its popularity for solving complex combinatorial problems. Computational results indicate that the proposed EA performs consistently better than the others in terms of solution quality, with moderate increase in computing time.
The EA is also applied to the optimal experimental design problem under the cost constraint. Since this problem is formulated for the first time in this thesis, other heuristic algorithms do not exist. Therefore, global optimal solutions are obtained by complete enumeration for some cases, and the performance of the EA is evaluated in terms of solution quality. Computational results show that the proposed EA is effective in finding good(or, in many cases, global) solutions to the constrained optimal experimental design problems.