acceptodds
Withdrawn from ICLR 2027

GAPCYCLE: LEARNING FROM RESIDUAL CYCLES FOR MINIMUM-COST FLOW

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

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 , 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 , the lowest among the evaluated methods, compared with 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.

Primary area:
optimization
Keywords:
decision-focused learning, predict-then-optimize, minimum-cost flow, solver-free learning, separation oracle, working-set methods

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_qfoLOpenReview ↗
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
  1. 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.
  2. “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.
  3. The evaluation is restricted to synthetic NETGEN-style networks.
Questions for authors
  1. 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?
  2. Please report the exact performance of the decision-only variant and clarify whether any meaningful regret guarantee can be obtained in that setting.
Reviewer_NhijOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper considers the problem of learning the costs of a minimum-cost flow problem in a contextual predict-then-optimize setting.

It proposes a new decision-focused training loss based on the classical residual-cycle optimality condition. They show that this loss can be computed exactly using minimum-mean-cycle separation. To reduce computational cost of this loss (and avoid solving the separation problem every training step), they introduce an approximation of it that uses only a small subset of cached cycles.

It then conducts numerical experiments comparing GapCycle with existing decision-focused learning methods, reporting lower decision regret on NETGEN instances.

Critical strengths
  • The idea of the loss and its cached approximation is nice.
Critical weaknesses

Although I am very familiar with the subject, I found the paper difficult to read, mainly because of its poor exposition. The manuscript frequently introduces concepts and terminology before properly defining or explaining them, uses vague or imprecise language, and uses unnecessarily dense statements.

A few examples (among many others):

  • “GapCycle builds...”: Before discussing what GapCycle builds on, the authors should first clearly introduce it as their proposed method and explain, at least intuitively, what it does and what problem it addresses.
  • “For the full hinge”: What does “full hinge” mean at this point? The terminology has not yet been introduced or explained.
  • “On the held-out NETGEN panel”: What is NETGEN, and why refer to “the” panel when it has never been introduced? I happen to know NETGEN because I have worked with it before, but readers unfamiliar with it would have no idea that it is a synthetic network-flow problem generator.
  • “For MOM”: What is MOM? The acronym should be expanded and the method briefly introduced.
  • “Bounded working-set training together with a certificate connecting the cached and full hinges and pointwise regret control”: This sentence is extremely dense and difficult to interpret, especially before the underlying concepts have been properly explained.
  • “Each context has dimension p”: At this point, the authors have not clearly explained what a “context” represents in their problem setting.
  • “The forward copy represents increasing x_e”: This explanation is too terse to be informative. The authors should first provide an intuitive explanation of a residual graph, clarifying that a forward residual arc represents the possibility of increasing the flow along an original arc, with residual capacity indicating how much additional flow can be sent in that direction. The reverse residual arcs should be explained similarly.

These are only a few examples; similar issues occur throughout the manuscript. In its current form, the exposition makes the paper unnecessarily difficult to follow, even for readers familiar with the subject.

Questions for authors
  • One of the main motivations of GapCycle is to avoid the repeated minimum-cost-flow solves required by several existing decision-focused learning methods. However, GapCycle periodically solves minimum-mean-cycle separation problems, which can also be computationally expensive. Could the authors clarify how the computational cost of separation compares with that of solving MCF? In particular, how much of the observed efficiency gain comes from caching rather than from the separation algorithm itself?

  • Aren't the choices of ϵc=10−8\epsilon_c = 10^{-8} in Equation (11) and τ=10−7\tau = 10^{-7} in Equation (24) implementation details that would be more appropriately specified in the numerical experiments section rather than in the methodological development? The same applies to the choice of b=16b=16 in Equation (21), ϵa=10−12\epsilon_a = 10^{-12} in Equation (25), and other numerical parameter values introduced throughout the paper.

  • Why do the main experiments compare GapCycle against single-basis LAVA rather than full LAVA? Furthermore, what exactly do the authors mean by the statement "Single-basis LAVA in the locked comparison and full LAVA with Transition Node Pivoting belong to separate campaigns and are not substituted for one another"? Does this mean that experiments with full LAVA were conducted but their results were not included in the paper? If so, why were these results omitted?

  • What does pp represent in the experimental tables (e.g., Table 13)? Presumably, these are p-values from statistical hypothesis tests, but this is not explicitly stated. If so, all the reported p-values in Table 13 exceed 0.05, meaning that none of the ablation comparisons is statistically significant at the 5% level. Could the authors comment on this and explain to what extent these experiments support their design choices?

  • A pseudocode for GapCycle would improve clarity, as the algorithmic details are scattered across several sections.

Reviewer_d2obOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper studies decision-focused learning for the min-cost flow problem, where a machine learning model is used to predict the arc costs on a directed graph which is then used by an optimization solver to identify the min-cost flows. Traditional decision-focused learning method requires repeatedly calling an optimization solver to derive the gradients during training, which can be computationally expensive. In response, this paper propose to leverage the graph structure embedded in min-cost flow problem to train the ML model in a solver-free manner. Empirical results demonstrate the effectiveness of the proposed approach in reducing the out-of-sample regret and training time.

Critical strengths
  • I like the idea of using problem structures to accelerate decision-focused learning of which the computational tractability is a major barrier to wider adoption.
Critical weaknesses
  • First and foremost, the technical content of this paper is very difficult to follow due to the abuse of notation and lack of organization. I'd really encourage the authors to improve their writing in order to help readers to better appreciate their work.
  • The focus on min-cost problem narrows the scope of the proposed contribution. I'm not sure if this is of sufficient interest to the broader ICLR community. I'd encourage the authors to draw connection to modern AI applications to make their work more appealing to this specific community.
  • The empirical results deserve more detailed discussion. Specifically, why did the proposed method achieve lower regret despite the fact that much of the methodological development is focused on improving the tractability of decision-focused training? Is this finding generalizable across problem contexts, sample sizes, and machine learning models?
Questions for authors

See above.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Discussion (0)

Sign in to comment.