Graph-theoretic Representation of Linear Programming Problems: Applications in Network Flow and Resource Optimization

In the research work, the combination of the graph representation formulation and the traditional LP formulation was taken into account for the further development of the optimization methodology within the environment of the network. In fact, the major part of the networks such as energy transmission networks, transport networks, telecommunication networks, and resource distribution networks is made up of the graph representation by the nature itself, whereas the traditional LP formulation methodology is not appropriate for the improvement of the efficiency of the result within the environment. The proposal of the research work was to apply the constraints of the traditional LP formulation within the graph representation by the help of the graph representation with capacity-constrained flow within the environment of graph representation. The verification of the proposal was carried out within the environment of the traditional simplex methodology, the network simplex methodology, within the environment of the min-cost flow problem, which was later confirmed by the GNN. Meanwhile, in the case of the PowerGraph dataset, the network simplex algorithm obtained a speedup of 5.9 times with a 93.6% reduction in iterations compared to the traditional simplex algorithm. In depth analyses of flow patterns and congestion pointed to essential lines with maximal congestion, underutilized transmission paths, as well as comprehensible patterns of resource allocation in the network. Sensitivity analyses also highlighted changes in the cost structure and network topology as major factors in shifting optimal flow patterns. Overall, this integrated LP & graph approach enables a computationally effective and interpretable analysis paradigm for such networks. This work thus serves as an exemplary foundation in elucidating network flow problems by integrating LP algorithms with graph structures in more advanced network paradigms involving dynamics, stochasticity, or multi-layers.