GAPCYCLE: LEARNING FROM RESIDUAL CYCLES FOR MINIMUM-COST FLOW

Decision-focused learning aims to predict costs that induce good downstream decisions, but training can require repeated solves of the downstream optimization problem. For minimum-cost flow (MCF), GapCycle instead exploits the classical residual-cycle optimality condition: an optimal flow has no improving residual cycle. GapCycle defines a length-normalized hinge over residual cycles and penalizes the cycle that most violates this condition under the predicted costs. When separation is invoked, the most violated cycle is found exactly by a minimum-mean-cycle computation; a bounded working set then reuses discovered cycles between separator calls. This removes downstream MCF solves from the training signal while retaining efficient graph-based separation. For the full, uncached cycle hinge, we prove a pointwise upper bound on decision regret; for a positive margin parameter $\kappa$, zero full hinge implies zero regret for any flow that is optimal under the predicted costs. On a held-out 24-topology NETGEN panel, GapCycle achieves aggregate normalized regret of $0.020800$, the lowest among the evaluated methods, compared with $0.023338$ for the next-lowest method, MOM, while using zero downstream MCF training solves. Additional shortest-path experiments test robustness across misspecification and noise. Together, these results show how MCF structure can replace repeated downstream solves with a decision-aware training signal.