We are happy to see two new papers accepted for publication in Computers and Industrial Engineering this Summer! These publications form a logical pair, with one introducing a new perspective that uses statistical learning to help study the Fixed-Charge Network Flow (FCNF) problem and the other develops a solution technique that hybridizes the new approach with classical techniques to improve on solution efficiency.
Zhang, W. and C.D. Nicholson. 2016. Prediction-based relaxation solution approach for the fixed charge network flow problem. Computers & Industrial Engineering, 99:106-111 http://dx.doi.org/10.1016/j.cie.2016.07.014.
Keywords: Network optimization; Fixed charge network flow; Heuristics
Abstract: A new heuristic procedure for the fixed charge network flow problem is proposed. The new method leverages a probabilistic model to create an informed reformulation and relaxation of the FCNF problem. The technique relies on probability estimates that an edge in a graph should be included in an optimal flow solution. These probability estimates, derived from a statistical learning technique, are used to reformulate the problem as a linear program which can be solved efficiently. This method can be used as an independent heuristic for the fixed charge network flow problem or as a primal heuristic. In rigorous testing, the solution quality of the new technique is evaluated and compared to results obtained from a commercial solver software. Testing demonstrates that the novel prediction-based relaxation outperforms linear programming relaxation in solution quality and that as a primal heuristic the method significantly improves the solutions found for large problem instances within a given time limit.
Nicholson, C.D. and W. Zhang. 2016. Optimal Network Flow: A Predictive Analytics Perspective on the Fixed-Charge Network Flow Problem. Computers & Industrial Engineering, 99:260-268 http://dx.doi.org/ 10.1016/j.cie.2016.07.030
Keywords:Network analysis, Fixed charge network flow, Predictive modeling, Critical components
Abstract: 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.
We have also just had a very good first round review from Sustainable and Resilient Infrastructure on a paper entitled “Defining Resilience Analytics for Interdependent Cyber-Physical-Social Networks” and expect a quick second round of reviews soon.
We have finally had the first round of reviews back from the Journal of Biomedical Informatics and a paper written in 2015 by Leslie Goodwin (MS ISE @ OU), Charles Nicholson (OU), and Corey Clark (SMU) entitled “Variable neighborhood search for reverse engineering of gene regulatory networks”. The first round review is very promising, and we are going to work hard to see this paper published in such a high quality journal!
Hopefully this fall we have 7 more submissons of papers that are close to wrapping up. These include two papers on data mining, one paper on network heuristics, and four papers relating to advancing the science of resilience.