Global Optimization Approaches to Combinatorial Optimization

Many questions in computer science, mathematics, and different applications can be expressed as or are strongly related to optimization problems. Among the most prominent classes of optimization problems we find the mixed integer nonlinear programming problems (denoted by MINLP). Applications of combinatorial optimization are found in such areas as VLSI routing, scheduling problems, network optimization problems, routing traffic in communications networks, economical allocation problems, multi-dimensional smoothing for pattern recognition, theorem proving, game theory, and artificial intelligence. The tremendous attention that combinatorial op-timization and MINLP particularly has received in the literature gives some indication of its im-portance in many research areas. Many real MINLP problems contain a huge number of variables and/or constraints that make the models intractable for currently available MINLP solvers. One of the promising approaches for solving MINLP problems is the construction of hybride methods based on combination and interaction of known methods in the framework of a new procedure. The aim of this project is to combine and use such combinatorial approaches like tree search, of which branch and bound is an important special case, a fundamental technique for solving combinatorial optimization problems; local decomposition algorithms using the special block matrix structure of constraints for solving block MINLP problems; nonserial dynamic programming algorithm consisting of elimination of variables and characterizing the structure of an optimization problem with an interaction graph; and continuous approaches. Each MINLP problem for which some of the variables have combinatorial (discrete) nature and the remaining ones are continuous can be considered as a global continuous optimization problem with additional constraints. A complete algorithm (exhaustive search) for solving global optimization problems uses a branch-and-bound scheme with interval analysis. The main aims of this work are: the analysis of possibilities how to combine continuous approaches from global optimization with combinatorial approaches like non-serial dynamic programming schemes, local decomposition algorithms to develop effective algorithms for solving MINLP problems. This research should have two distinct aspects: (1) developing and implementing new methodology using nonserial dynamic programming for solving large scale MINLP problems; and, (2) working with the COCONUT global optimization methodology on the solution of specific large scale MINLP problems using the COCONUT environment.

Many questions in computer science, mathematics, and different applications can be expressed as or are strongly related to optimization problems. Among the most prominent classes of optimization problems we find the mixed integer nonlinear programming problems (denoted by MINLP). Applications of combinatorial optimization are found in such areas as VLSI routing, scheduling problems, network optimization problems, routing traffic in communications networks, economical allocation problems, multi-dimensional smoothing for pattern recognition, theorem proving, game theory, and artificial intelligence. The tremendous attention that combinatorial op-timization and MINLP particularly has received in the literature gives some indication of its im-portance in many research areas. Many real MINLP problems contain a huge number of variables and/or constraints that make the models intractable for currently available MINLP solvers. One of the promising approaches for solving MINLP problems is the construction of hybride methods based on combination and interaction of known methods in the framework of a new procedure. The aim of this project is to combine and use such combinatorial approaches like tree search, of which branch and bound is an important special case, a fundamental technique for solving combinatorial optimization problems; local decomposition algorithms using the special block matrix structure of constraints for solving block MINLP problems; nonserial dynamic programming algorithm consisting of elimination of variables and characterizing the structure of an optimization problem with an interaction graph; and continuous approaches. Each MINLP problem for which some of the variables have combinatorial (discrete) nature and the remaining ones are continuous can be considered as a global continuous optimization problem with additional constraints. A complete algorithm (exhaustive search) for solving global optimization problems uses a branch-and-bound scheme with interval analysis. The main aims of this work are: the analysis of possibilities how to combine continuous approaches from global optimization with combinatorial approaches like non-serial dynamic programming schemes, local decomposition algorithms to develop effective algorithms for solving MINLP problems. This research should have two distinct aspects: (1) developing and implementing new methodology using nonserial dynamic programming for solving large scale MINLP problems; and, (2) working with the COCONUT global optimization methodology on the solution of specific large scale MINLP problems using the COCONUT environment.