Toward a Programming Environment for Combinatorial Optimization: A Case Study Oriented to Max-Flow Computations

In this paper, we try to move a few steps toward the definition of a programming environment oriented to the production and updating of algorithms for combinatorial optimization problems. Such an environment contains a certain number of basic blocks (data structures and routines) together with a set of rules for their use, which allow us to assemble the blocks into large and complex algorithmic architectures. The max-flow problem has been chosen for a case study which illustrates the main issues arising in the design of the programming environment. In order to develop such a study, a new general algorithm paradigm for the max-flow problem is proposed, from which most of the known algorithms can be derived by instantiation.

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.