Classification of Network Optimization Software Packages

Background

During the last decades several advances have emerged in the field of network and combinatorial optimization (Cook, 2010). Nowadays, optimization software packages are required for the efficient solution of complex network optimization problems, even of moderate dimensions, due to their computational difficulty. Briefly speaking, an optimization software package is a software package specifically designed to be used for optimization problems. Such network optimization software packages have various differences in their characteristics, technology, and scope (Maros & Khaliq, 2002). The most well-known types of optimization software packages include optimization solvers, problem generators, performance analyzers/profilers, and educational software packages using visualization/animation techniques. An optimization solver is an optimization software package including efficient implementations of optimization algorithms specifically designed for the solution of optimization problems. Furthermore, a network generator is an optimization software package designed for random generating instances of network optimization problems with specific structure and dimension. Moreover, modern performance analyzer/profilers are now available to analyze the efficiency of the source code of an optimization algorithm, identify the bottlenecks in its performance, and suggest ways of computational improvements.

Benchmark collections for mathematical programming problems are also very important for comparing the computational efficiency of network optimization solvers. Roughly speaking, a benchmark collection constitutes a set of computationally difficult problems, either from real-world applications (e.g., real data from railway networks for robust train timetabling problems) or randomly generated. Such sets of benchmark problem instances allow researchers to compare the efficiency of their optimization solvers in common, usually publicly available, problem sets.