A HEURISTIC FOR FINDING EMBEDDED NETWORK STRUCTURE IN MATHEMATICAL PROGRAMS

An intuitive description is given of how to recognise when a mathemati cal programme can be converted to a network flow problem. In practice, it is more likely that a mathematical programme with a high degree of network structure will have additional complicating constraints. Thus , a heuristic is presented for identifying a maximal subset of the con straints which can be converted to a network flow problem. Computation al results show that the heuristic is highly effective, and that much larger networks are identified by seeking a general network structure, rather than limiting the search to a subset of rows giving at most on e + 1 and one - 1 in each column, as has been done previously.