- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper proposes GapCycle, a decision-focused learning surrogate for contextual minimum-cost flow. Given a reference optimal flow, it constructs the residual graph and penalizes the most violated residual cycle under predicted costs. The full hinge is separated exactly with a minimum-mean-cycle algorithm, while a bounded working set avoids repeated separation. The paper also provides a pointwise regret bound for the full hinge and a conditional certificate for the cached hinge. On 24 held-out NETGEN topologies, GapCycle obtains the best aggregate normalized regret among the evaluated methods, while using no downstream MCF solves in gradient-based training.
Critical strengths
The method makes good use of the residual-cycle optimality structure of minimum-cost flow. The resulting surrogate is more decision-aware than plain prediction loss while remaining computationally tractable.
Critical weaknesses
- The main method assumes access to both the true costs and an optimal reference flow during training. The decision-only variant is only briefly reported and is not covered by the regret theorem, so the practical scope of the strongest claims is limited.
- “Zero downstream MCF training solves” does not capture the full computational cost: reference optimum generation, residual-graph construction, minimum-mean-cycle separation, cache refreshes, and preprocessing remain necessary.
- The evaluation is restricted to synthetic NETGEN-style networks.
Questions for authors
- What is the exact end-to-end cost when reference-optimum generation, separator calls, cache maintenance, and preprocessing are included? How does this compare with MOM and PFYL under the same total wall-clock budget?
- Please report the exact performance of the decision-only variant and clarify whether any meaningful regret guarantee can be obtained in that setting.