Optimal network flow: A predictive analytics perspective on the fixed-charge network flow problem

• A predicative model is investigated to determine whether or not arcs are selected in an optimal solution of a FCNF problem.
• The accuracy of the predictive mode is very high.
• The model has useful explanatory power regarding the predictors defined.
• Component importance measure is developed to rank the arcs in the network.

The fixed charge network flow (FCNF) problem is a classical NP-hard combinatorial problem with wide spread applications. To the best of our knowledge, this is the first paper that employs a statistical learning technique to analyze and quantify the effect of various network characteristics relating to the optimal solution of the FCNF problem. In particular, we create a probabilistic classifier based on 18 network related variables to produce a quantitative measure that an arc in the network will have a non-zero flow in an optimal solution. The predictive model achieves 85% cross-validated accuracy. An application employing the predictive model is presented from the perspective of identifying critical network components based on the likelihood of an arc being used in an optimal solution.