Prediction-based relaxation solution approach for the fixed charge network flow problem

• Introduce a statistical learning approach to a traditional optimization problem.
• Problem is reformulated as a linear relaxation based on model predictions.
• Method can be part of an exact solution strategy and used as a primal heuristic.
• Empirical tests demonstrate improved solutions over leading commercial software.
• Incremental solution time is negligible for large problems.

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.