@article{Zhang2016106,
title = "Prediction-based relaxation solution approach for the fixed charge network flow problem",
journal = "Computers & Industrial Engineering",
volume = "99",
pages = "106 - 111",
year = "2016",
issn = "0360-8352",
doi = "http://dx.doi.org/10.1016/j.cie.2016.07.014",
url = "http://www.sciencedirect.com/science/article/pii/S036083521630239X",
author = "W. Zhang and C.D. Nicholson",
keywords = "Network optimization",
keywords = "Fixed charge network flow",
keywords = "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. "
}