Network problems. (English) Zbl 0832.90117

Guisewite, G. M.

Horst, Reiner et al., Handbook of global optimization. Dordrecht: Kluwer Academic Publishers. Nonconvex Optim. Appl. 2, 609-648 (1995).

Summary: Network problems arise naturally in many application areas. For the case of nonconvex network optimization, it is often necessary to exploit the network structure to develop efficient algorithms. This paper summarizes the application areas, complexity, and solution techniques for popular network problems. Network formulations for numerous application areas are provided. A summary of complexity results for concave and indefinite problems, as well as for specific network structures is discussed. Classes of algorithms that have been used to solve network problems are summarized along with any reported performance results.
For the entire collection see [Zbl 0805.00009].

MSC:

90C35	Programming involving graphs or networks
90C26	Nonconvex programming, global optimization
90-02	Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
90B10	Deterministic network models in operations research

Keywords:

nonconvex network optimization