M/611

Geometric branch-and-bound techniques like the ``big-square-small-square method`` are popular solution algorithms for continuous and non-convex global optimization problems. The idea is to partition the continuous solution space into boxes and to approximate the problem on any of them. By calculating bounds some of the boxes can be discarded, while the remaining ones are split into sub-boxes. This is repeated until a certain accuracy is obtained. The most important task throughout this branch-and-bound algorithm is the calculation of good lower bounds on the objective function. Several techniques to do so exist. This geometric branch & bound approach has been applied so far for pure continuous objective functions. The aim of this paper is to extend geometric branch-and-bound methods to mixed continuous and combinatorial optimization problems, i.e. to objective functions containing continuous and integer variables. The idea is to do a geometric branching for the continuous variables and to approximate the remaining discrete problem in order to obtain the required bounds on the boxes. This is in contrast to the classical integer branch-and-bound in which branching is done on the discrete variables. We formulate this new approach and extend known bounding operations from the continuous case to mixed-integer problems. We are able to derive theoretical results about their rate of convergence. Moreover, we discuss an extension of the method which leads to exact optimal solutions under certain conditions. We also implemented our approach and applied it to some facility location problems with combinatorial decisions. Our numerical results show that we succeeded in finding exact optimal solutions in relatively low computational time.

Anita Schöbel

Universität Göttingen