Finding good structures for heat exchanger networks can be a very difficult task. Among others, the level of heat recovery, the size and type of the heat exchanger as well as the overall structure of the network need to be determined during the design phase. Different target procedures like the pinch analysis are widely used both in academia and industry. Another approach to find cost optimal network structures is to use mathematical programming methods. The advantage with mathematical programming methods is that a rigorous optimization of the structure, sizes of heat exchangers and utility usage is carried out, whereas the designer makes these decisions if purely pinch-based tools are used. The drawback, on the other hand, with almost every mathematical model in this field, is that only small and perhaps some medium sized problems are possible to solve at the moment. Large scale problems, with sometimes up to a hundred streams, are probably never to be solved directly with many common mathematical heat exchanger models. This paper presents a method, where large-scale heat exchanger problems can be solved with mathematical programming methods, even if the global optimum cannot be assured. The actual method combines deterministic and stochastic optimization methods and have successfully solved the problems tested so far.