Atomic Column Generation For Consensus Between Algorithms: Application to Path Computation

J\'er\'emie Leguay; Pierre Bauguion; S\'ebastien Martin; Youcef Magnouche

REVIEW 5 major objections 5 minor 41 references

Atomic Column Generation For Consensus Between Algorithms: Application to Path Computation

T0 review · 5 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Atomic Column Generation merges black-box solvers into an exact solver for the combined problem.

desk verdict A useful consensus-based Dantzig-Wolfe framework for combining black-box algorithms, but the optimality guarantee for heuristic pricing is not actually proven and one of the theoretical examples has a real error. read the letter →

arxiv 2501.13463 v1 pith:YRAV3ERS submitted 2025-01-23 cs.DM

Sébastien Martin , Pierre Bauguion , Youcef Magnouche , Jérémie Leguay This is my paper · ORCID

classification cs.DM MSC 90C1090C2790C3590C57

keywords combinatorialoptimizationcolumngenerationDantzig-Wolfedecompositionblack-boxbranch-and-priceresourceconstrainedshortestpathcomputationconsensus

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proposes Atomic Column Generation (ACG), a decomposition framework that lets several existing atomic optimization algorithms--each handling the same structural problem under a different subset of additional constraints--be combined into one solver for the full problem, with no dedicated algorithm written for the whole problem. ACG is based on a Dantzig-Wolfe reformulation of a consensus model in which variables and constraints are duplicated per additional constraint; the master problem enforces agreement among the atomic algorithms, and each pricing problem is delegated to one atomic algorithm. The paper claims that this decomposition strengthens the continuous relaxation of the original model and that the associated branch-and-price algorithm reaches an optimal global solution even when the atomic pricing problems are solved heuristically. This matters in practice because, for example, network operators can extend path-computation engines by plugging in existing black-box algorithms instead of reimplementing every combination of routing constraints.

What carries the argument

The central object is the consensus-based Dantzig-Wolfe reformulation: each atomic algorithm contributes a column family of its feasible sets, and the master problem enforces agreement through duplicated variables with equalities $x_e - \sum_{F\ni e} y^j_F = 0$, converted to inequalities for union-free problems, i.e. problems such as paths where two distinct feasible sets cannot union back into a feasible set. Branching is done only on the original arc variables $x_e$, and each pricing problem is solved by calling the corresponding atomic algorithm with dual values as arc costs. This makes the whole method agnostic to the internal form of each additional constraint.

What would settle it

Run ACG on a small resource-constrained shortest path instance with a known optimal path, give the atomic algorithms a very short time limit or a heuristic that cannot certify optimality, and record whether the bound $l$ ever exceeds the true cost of the best feasible completion in a branch that contains the optimum; if it does, that branch is pruned and the algorithm returns a suboptimal solution, which would disprove Proposition 8 as stated.

Watch

Extended reading notes

Core claim

The paper's central claim is that a collection of black-box atomic algorithms--each able to return a minimum-cost elementary path and to check whether a given path is feasible for the constraints it handles--can be assembled, through Atomic Column Generation, into an exact solver for the problem that imposes all of their constraints together. Formally, the compact model is reformulated by duplicating variables and constraints for each additional constraint and then applying Dantzig-Wolfe decomposition, giving a master problem with consensus equalities $x_e - \sum_{F\ni e} y^j_F = 0$ and one pricing problem per atomic algorithm. The authors prove that the linear relaxation of this reformulation is at least as strong as the compact relaxation, and they exhibit an instance on which it is strictly stronger; they also state, as Proposition 8, that the associated branch-and-price algorithm reaches an optimal solution even when the pricing problems are solved by non-trivial heuristics. Experiments on the resource-constrained shortest path problem compare the method with a dedicated MultiPulse algorithm and a compact ILP, and report optimal solutions with competitive run times.

Load-bearing premise

The claim that heuristic atomic algorithms still yield an optimal global solution depends on the cost estimate used to discard branches never being too optimistic, and the paper does not prove that when the atomic algorithms are heuristic or stopped early.

Editorial extensions

If this is right

Any collection of atomic algorithms that can return a minimum-cost elementary path and verify feasibility can in principle be combined into an exact solver, removing the need to write a dedicated algorithm for the combined problem.
The ACG relaxation is never weaker than the compact ILP relaxation and can be strictly stronger, so the branch-and-price search starts from a tighter bound.
In the telecom use case, an Augmented PCE can add new routing requirements by plugging in existing path-computation engines, including third-party black boxes, without modifying them.
On the tested resource-constrained shortest path instances, ACG finds optimal solutions where the comparison methods succeed, and its computation time approaches a dedicated algorithm's time on harder instances.
For union-free problems, branching only on the original variables is sufficient, since an integer $x$ forces integer $y$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

One consequence the authors leave implicit is that the scheme is not tied to paths: any structural family with additive costs and atomic solvers that can optimize and verify feasibility could be merged the same way, for instance spanning trees, matchings, or tours.
The optimality proof with heuristic atomic algorithms assumes the Lagrangian bound $l$ is trustworthy for pruning, so a worthwhile stress test would feed deliberately weak atomic algorithms on small instances with known optima to see whether $l$ ever invalidly prunes an optimal branch.
The unfeasible-instance results suggest the consensus model could also serve as an incompatibility detector, telling an operator which atomic constraint conflicts before a full solve is attempted.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The core idea here is genuinely worth attention: a consensus-based Dantzig-Wolfe reformulation that duplicates variables per additional constraint, then uses existing atomic algorithms as pricing solvers. That's a real extension of decomposition thinking, and the practical framing around Path Computation Elements makes it concrete. The branching scheme—building paths arc by arc and using atomic algorithms as feasibility and optimality oracles—is clever, and the experimental study on RCSP is substantial, with public instances and a reasonable new MultiPulse baseline. The relaxation improvement claimed in Prop 3 is real for the class they consider; the example there checks out (compact relaxation 3, ACG relaxation 4).

The soft spots are mostly in the theory, and they are not cosmetic. The abstract and Prop 2/8 claim that ACG converges to an optimal global solution even when atomic algorithms are heuristic. The proofs do not establish the one thing you need for a branch-and-prune scheme: that the lower bound used to discard branches is valid. Algorithm 1 prunes any node with B.l >= B*.c, and Algorithm 2 raises B.l to the l returned by ACG-Solve even when pricing is time-limited or heuristic. The text even admits that under a timeout "we cannot infer lower bounds"—yet the algorithm and theorems rely on exactly that inference. Without a proof that l is a true lower bound (e.g. via dual-feasible prices or solved-to-optimality subproblems), the central optimality guarantee for heuristic pricing is unsupported. That is a load-bearing gap, not a minor caveat.

There is also a concrete error in Prop 4's example: the columns identified as {su,vt} and {sv,ut} are not s-t paths at all, so that part of the DW-M-RL comparison is broken. The claim that ACG strictly strengthens the classical Dantzig-Wolfe relaxation may still be true, but this example doesn't show it.

On the practical side, the method is competitive on the tested RCSP instances, and the experiments are honestly reported—ACG-H's difficulty is shown, not hidden. Hyperparameters are tuned on the test set, which is a mild concern, and no solver code is shipped, though instances are available.

Who is this for? Someone working on decomposition methods or network path computation will want to see the framing and the experimental setup. The paper is not ready as is, because the main theoretical selling point is unproven. But the modeling idea and the empirical study deserve a serious referee and a chance for major revision.

I'd take the review if asked, and I'd push the authors to either prove the lower-bound validity under weak pricing or explicitly drop the "any kind of atomic algorithms" claim to what is actually shown.

Referee Report

5 major / 5 minor

Summary. The paper introduces Atomic Column Generation (ACG), a Dantzig-Wolfe style decomposition that merges several 'atomic algorithms', each solving the structural problem with a subset of the additional constraints, through a master problem that forces consensus on a common solution. For the resource-constrained shortest path use case, the pricing problem is solved by calling atomic algorithms on filtered graphs with dual arc costs, and a branch-and-prune scheme is proposed to reach integer optimality. The paper also gives a generic reformulation (Generic-ACG), claims that its continuous relaxation dominates the compact formulation and the classical Dantzig-Wolfe relaxation, proves structural properties of the reformulation, and reports experiments on RCSP instances where ACG is competitive with a dedicated MultiPulse algorithm and outperforms a compact ILP solved by CPLEX.

Significance. If the theorems were correct, ACG would be a significant contribution: it would allow composing black-box solvers for heterogeneous constraints into an exact method without re-implementing a joint algorithm, and the reported RCSP experiments support the practical viability of the idea. The paper is well written and the experimental setup (instance generation, comparison to a Pulse-based benchmark, and unfeasible instances) is careful. However, the central optimality guarantee for heuristic pricing is not proven, and several propositions in Section 4.2 need qualification or correction. The contribution is therefore promising but requires substantive revision before the claims can be accepted.

major comments (5)

[§3.3 (Algorithms 1 and 2), Propositions 2 and 8] The proof of optimality with heuristic or time-limited atomic pricing is incomplete in a load-bearing way. Algorithm 1 (line 16) discards every branch with B'.l >= B*.c, so correctness requires B'.l to be a valid lower bound for all feasible completions of that branch. The only bounds shown to be valid are the shortest-path completion bound (Algorithm 2, line 1) and the update in lines 9-14 when an atomic algorithm returns an optimality certificate. The update in lines 20-21 sets B.l = max(B.l, l) with l returned by ACG-Solve(Tacg), where the text in Section 3.3 claims a Lagrangian bound is available even if column generation is stopped early. No proof is given that this l is a valid lower bound when pricing problems are solved heuristically or stopped by a time limit; in that situation the restricted-master dual can be infeasible for undiscovered columns and l can exceed the true optimum of the branch. Proposition 2's proof only argues that the branching enumerates all cases and never addresses the validity of the pruning condition, and Proposition 8 has the same gap. Consequently the abstract's claim that ACG converges to an optimal global solution with any kind of atomic algorithms is not supported as stated.
[§4.2, Proposition 3] Proposition 3 claims that Generic-ACG-M-RL is always at least as strong as Compact-RL, but the proof uses the step 'x* is a convex combination of all solutions in F_j. Therefore, x* satisfies all Constraints (8)'. This inference is valid only if each additional constraint f_j is such that every convex combination of feasible points remains feasible, which holds for linear constraints but not for the arbitrary black-box or non-linear functions allowed in Section 4.1. The proposition and the corresponding claim in the introduction should be restricted to convex or linear additional constraints, or accompanied by an explicit assumption.
[§4.2, Proposition 4] The proof of Proposition 4 contains an erroneous example. The text says 'two generated columns have values y_{su,vt} = y_{sv,ut} = 0.5', but the sets {su,vt} and {sv,ut} are not elementary s-t paths in the graph G=({s,u,v,t},{su,sv,ut,vt}); they are pairs of arcs that do not form a path. The intended columns are presumably y_{su,ut} and y_{sv,vt}. As written, the proof does not demonstrate the claimed comparison with DW-M-RL, although the conclusion appears correct once the column names are fixed.
[§4.2, Proposition 5] The proof of Proposition 5 is not convincing: from the fact that x is feasible and contains two different atomic solutions, it does not follow that the union of those two solutions itself belongs to F, which is what the union-free definition requires. For the path application the conclusion is correct, but the general statement as proved is too strong. A correct proof would need an additional argument showing that the presence of two distinct atomic solutions inside a feasible x violates the union-free property for the specific problem class.
[§4.2, Proposition 7] The proof of Proposition 7 also uses the problematic union reasoning: the claim that equalities (16) imply Fx is the union of F_y1 and F_y2 is not generally justified, since x_e = sum_{F: e in F} y_F implies Fx is the union of the supports of all positive y-variables, not necessarily of just two named columns. The statement may be true for union-free problems with integer x, but the proof as written does not establish it, and this proposition is load-bearing for the decision to branch only on x variables.

minor comments (5)

[§3.1, Proposition 1] The proof of Proposition 1 concludes that the x-variables always induce an elementary path, but the argument uses optimality (positive arc costs) to exclude cycles; the statement should be phrased as 'there exists an optimal solution in which x induces an elementary path', since feasible solutions may contain disconnected cycles.
[§3.3, Algorithm 2] The text acknowledges that when an atomic algorithm is stopped by a timeout, 'we cannot get any certificates on optimality and feasibility, which means that we cannot infer lower bounds or (un)-feasibility'. This is in tension with the later statement that a lower bound can still be extracted from ACG-Solve; the conditions under which the Lagrangian bound l is certified should be made explicit.
[§4.2, Proposition 6] In the definition of F', the text writes 'E' < F', which should read 'E' ∉ F' (the set of element subsets that are not feasible solutions).
[§5, Figures 4 and 5] The figures are referenced with qualitative descriptions such as 'path size greater than 25' and 'path size equals to 5', but the axes and the meaning of the path-size parameter are not fully defined in the captions; adding explicit axis labels and a definition of the plotted quantities would improve readability.
[Throughout] There are several typographical issues: 'T able 1' (page 18), 'developped' (conclusion), and 'pp. 11-p.' in reference [4].

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the ACG model is a Dantzig-Wolfe reformulation built from first principles, and its claims, however proof-gappy, do not reduce to fitted inputs or self-citations.

full rationale

The derivation is not circular. ACG-M is constructed from first principles as a Dantzig-Wolfe decomposition over a consensus-based reformulation of a compact integer program; the master/pricing relationship is the standard column-generation mechanism. Proposition 3's claim that Generic-ACG-M-RL is at least as strong as Compact-RL is a mathematical statement proved by mapping a relaxation solution to a convex combination of subproblem solutions, plus an explicit example showing strict improvement; it is not an input fitted to the desired conclusion. The optimality claims in Propositions 2 and 8 are argued from branching completeness and feasibility certification, and although the validity of the Lagrangian bound l under heuristic pricing is a genuine proof gap, that gap is a correctness issue rather than a logical reduction of the conclusion to the premise. No predicted quantity is defined in terms of a fitted parameter: the time-limit settings in Table 1 are tuned on the benchmark instances, but they are not used to prove optimality, and no reported result is the fitted value itself by construction. The only overlapping-author citations, [6] and [27], are illustrative references for a QoE constraint and an existing Constrained Shortest Path Tour algorithm; the central claims of the paper do not rest on them. Thus there is no circular step under the stated definition, and the paper is self-contained in its derivation chain.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The framework itself is new but leans on standard decomposition theory and on three load-bearing assumptions: atomic algorithms can price with arbitrary costs and verify feasibility, the additional constraints are convex enough for the relaxation proof, and the lower bound used for pruning remains valid under heuristic pricing. The latter two are not stated or proven.

free parameters (3)

Gamma = 0.2
Threshold on remaining arc ratio for invoking ACG-Solve; chosen by hand, affects runtime and lower-bound updates; not derived from theory.
Tacg = 500 ms
Time limit for ACG-Solve per branch; tuned in Table 1 on the 70 benchmark instances.
Tatomic = 60 ms
Time limit for each atomic algorithm call; tuned in Table 1 on the same instances.

assumptions (4)

domain assumption Atomic algorithms always return an elementary path of minimum arc cost for arbitrary nonnegative arc costs, and can verify feasibility of any given path.
Used in Sec 3.1 and Sec 3.2 to call an atomic algorithm as pricing solver with dual values as costs; also in Algorithm 2 for feasibility checks. If an atomic algorithm cannot do this, pricing may miss negative reduced cost columns.
ad hoc to paper Additional constraints f_j are such that every convex combination of feasible solutions in F_j satisfies f_j, which holds for linear constraints.
Prop 3 proof: x* is a convex combination of solutions in F_j and is asserted to satisfy f_j. For black-box or non-linear constraints this fails; the paper does not state convexity. Required for the claimed relaxation dominance.
ad hoc to paper The Lagrangian bound extracted from the restricted master in ACG-Solve is a valid lower bound for all branches even when pricing problems are solved heuristically or stopped after a time limit.
Algorithm 2 lines 19-23 updates B.l with l from ACG-Solve; Algorithm 1 line 16 prunes when B.l >= B*.c. Valid pruning requires l to be a true lower bound. The paper does not prove this for heuristic or time-limited pricing; Proposition 2 relies on it implicitly.
standard math Linear programming duality, Dantzig-Wolfe decomposition, and branch-and-bound are assumed as background.
Used throughout Sec 3 and 4 to derive pricing problems and branching rules.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Atomic Column Generation For Consensus Between Algorithms: Application to Path Computation." pith.science (2026). https://pith.science/paper/YRAV3ERS

@misc{pith2026250113463,
  author       = {Pith},
  title        = {Pith review of: Atomic Column Generation For Consensus Between Algorithms: Application to Path Computation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YRAV3ERS}},
  note         = {Machine review of arXiv:2501.13463}
}

read the original abstract

In real-life applications, most optimization problems are variants of well-known combinatorial optimization problems, including additional constraints to fit with a particular use case. Usually, efficient algorithms to handle a restricted subset of these additional constraints already exist, or can be easily derived, but combining them together is difficult. The goal of our paper is to provide a framework that allows merging several so-called atomic algorithms to solve an optimization problem including all associated additional constraints together. The core proposal, referred to as Atomic Column Generation (ACG) and derived from Dantzig-Wolfe decomposition, allows converging to an optimal global solution with any kind of atomic algorithms. We show that this decomposition improves the continuous relaxation and describe the associated Branch-and-Price algorithm. We consider a specific use case in telecommunication networks where several Path Computation Elements (PCE) are combined as atomic algorithms to route traffic. We demonstrate the efficiency of ACG on the resource-constrained shortest path problem associated with each PCE and show that it remains competitive with benchmark algorithms.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

41 extracted references · 40 canonical work pages

[1]

Ahuja, T.L

R.K. Ahuja, T.L. Magnanti, J.B. Orlin, and M. Reddy, Applications of network optimization , Handbooks Oper. Res. Manage. Sci. 7 (1995), 1–83

work page 1995
[2]

Aneja and K.P

Y.P . Aneja and K.P . Nair, The constrained shortest path problem, Naval Res. Logist. Q. 25 (1978), 549–555

work page 1978
[3]

Beasley and N

J.E. Beasley and N. Christoﬁdes, An algorithm for the resource constrained shortest path problem , Networks 19 (1989), 379–394

work page 1989
[4]

Bockmayr and N

A. Bockmayr and N. Pisaruk, Detecting infeasibility and generating cuts for MIP using CP , 5th International Work- shop on Integration of AI and OR T echniques in Constraint Programming for Combinatorial Optimization Problems-CPAIOR’03, 2003, pp. 11–p

work page 2003
[5]

Bui and C.M

T.N. Bui and C.M. Zrncic, An ant-based algorithm for ﬁnding degree-constrained minimum spanning tree, Proceedings of the 8th annual conference on Genetic and evolutionary computation, 2006, pp. 11–18

work page 2006
[6]

Calvigioni, R

G. Calvigioni, R. Aparicio-Pardo, L. Sassatelli, J. Leguay, P . Medagliani, and S. Paris, Quality of Experience-based routing of video traﬃc for overlay and isp networks , Proc. IEEE INFOCOM, 2018

work page 2018
[7]

Dantzig, R

G. Dantzig, R. Fulkerson, and S. Johnson, Solution of a large scale traveling salesman problem , J. Oper. Res. Soc. America 2 (1954), 393–410

work page 1954
[8]

Desaulniers, J

G. Desaulniers, J. Desrosiers, and M.M. Solomon, Column generation Vol. 5, Springer Science & Business Media, 2006

work page 2006

Show all 41 references

[9]

Ferone, P

D. Ferone, P . Festa, F . Guerriero, and D. Laganà, The constrained shortest path tour problem , Comput. Oper. Res. 74 (2016), 64–77

2016
[10]

Goldberg, J.D

A.V. Goldberg, J.D. Oldham, S. Plotkin, and C. Stein, An implementation of a combinatorial approximation algorithm for minimum-cost multicommodity ﬂow , Integer Programming and Combinatorial Optimization, Springer Berlin Heidelberg, Berlin, Heidelberg, 1998, pp. 338–352

1998
[11]

Gower and G.J

J.C. Gower and G.J. Ross, Minimum spanning trees and single linkage cluster analysis , J. Royal Stat. Soc.: Ser. C (Applied Statistics) 18 (1969), 54–64

1969
[12]

Griset, P

R. Griset, P . Bendotti, B. Detienne, M. Porcheron, H. Şen, and F . Vanderbeck,Combining dantzig-wolfe and benders decompositions to solve a large-scale nuclear outage planning problem , Eur. J. Oper. Res. 298 (2022), 1067–1083

2022
[13]

Hartert, S

R. Hartert, S. Vissicchio, P . Schaus, O. Bonaventure, C. Filsﬁls, T. T elkamp, and P . Francois, A declarative and ex- pressive approach to control forwarding paths in carrier-grade networks, ACM SIGCOMM computer communication review 45 (2015), 15–28

2015
[14]

He and X

B. He and X. Yuan, On the O(1/n) convergence rate of the Douglas–Rachford alternating direction method , SIAM J. Numer. Anal. 50 (2012), 700–709

2012
[15]

Iana registry for pcep

IANA, 2008. Iana registry for pcep. https://www.iana.org/assignments/pcep/pcep.xhtml

2008
[16]

Ibm ilog cplex 12.6

IBM, 2013. Ibm ilog cplex 12.6. https://www.ibm.com/products/ilog-cplex-optimization-studio . 27

2013
[17]

Jadin, F

M. Jadin, F . Aubry, P . Schaus, and O. Bonaventure,CG4SR: Near optimal traﬃc engineering for segment routing with column generation, Proc. IEEE INFOCOM, 2019

2019
[18]

Jeong, A review of decentralized optimization focused on information ﬂows of decomposition algorithms, Comput

I.J. Jeong, A review of decentralized optimization focused on information ﬂows of decomposition algorithms, Comput. Oper. Res. (2023), 106190

2023
[19]

Juttner, B

A. Juttner, B. Szviatovski, I. Mécs, and Z. Rajkó, Lagrange relaxation based method for the QoS routing problem , Proc. IEEE INFOCOM 2001, Vol. 2, 2001, pp. 859–868

2001
[20]

Knight, X

S. Knight, X. Nguyen, H., N. Falkner, R. Bowden, and M. Roughan, The internet topology zoo , IEEE J. Selected Areas Commun. 29 (2011)

2011
[21]

Korkmaz, M

T. Korkmaz, M. Krunz, and S. T ragoudas, An eﬃcient algorithm for ﬁnding a path subject to two additive constraints, Comput. Commun. 25 (2002), 225–238

2002
[22]

Kritikos and G

M. Kritikos and G. Ioannou, A greedy heuristic for the capacitated minimum spanning tree problem, J. Oper. Res. Soc. 68 (2017), 1223–1235

2017
[23]

Y. Liu, Y. Pan, M. Y ang, W. Wang, C. Fang, and R. Jiang, The multi-path routing problem in the software deﬁned network, 2015 11th International Conference on Natural Computation (ICNC), 2015, pp. 250–254

2015
[24]

Lozano and A.L

L. Lozano and A.L. Medaglia, On an exact method for the constrained shortest path problem , Comput. Oper. Res. 40 (2013), 378–384

2013
[25]

Lübbecke, Column generation, Wiley encyclopedia operations research management science

M.E. Lübbecke, Column generation, Wiley encyclopedia operations research management science. Wiley, New Y ork (2010), 1–14

2010
[26]

Luby and P

M. Luby and P . Ragde, A bidirectional shortest-path algorithm with good average-case behavior , Algorithmica 4 (1989), 551–567

1989
[27]

Martin, Y

S. Martin, Y. Magnouche, C. Juvigny, and J. Leguay, Constrained shortest path tour problem: branch-and-price algorithm, Comput. Oper. Res. 144 (2022), 105819

2022
[28]

Mendiola, J

A. Mendiola, J. Astorga, E. Jacob, and M. Higuero, A survey on the contributions of software-deﬁned networking to traﬃc engineering, IEEE Commun. Surveys T utorials 19 (2016), 918–953

2016
[29]

Morrison, S.H

D.R. Morrison, S.H. Jacobson, J.J. Sauppe, and E.C. Sewell, Branch-and-bound algorithms: A survey of recent ad- vances in searching, branching, and pruning , Discr. Optim. 19 (2016), 79–102

2016
[30]

Orlowski, R

S. Orlowski, R. Wessäly, M. Pióro, and A. T omaszewski, Sndlib 1.0—survivable network design library, Networks 55 (2010), 276–286

2010
[31]

Paolucci, F

F . Paolucci, F . Cugini, A. Giorgetti, N. Sambo, and P . Castoldi, A survey on the path computation element (PCE) architecture, IEEE Commun. Surveys T utorials 15 (2013), 1819–1841

2013
[32]

Pugliese and F

L.D.P . Pugliese and F . Guerriero,A survey of resource constrained shortest path problems: Exact solution approaches, Networks 62 (2013), 183–200. 28

2013
[33]

N. Shi, S. Zhou, F . Wang, Y. T ao, and L. Liu, The multi-criteria constrained shortest path problem , T ransp. Res. Part E: Logist. T ransp. Review101 (2017), 13–29

2017
[34]

Vanderbeck and M.W

F . Vanderbeck and M.W. Savelsbergh, A generic view of dantzig–wolfe decomposition in mixed integer programming, Oper. Res. Lett. 34 (2006), 296–306

2006
[35]

Vasseur, A

J. Vasseur, A. Farrel, and G. Ash, 2006. A Path Computation Element (PCE)-Based Architecture

2006
[36]

Vassilaras, L

S. Vassilaras, L. Gkatzikis, N. Liakopoulos, I.N. Stiakogiannakis, M. Qi, L. Shi, L. Liu, M. Debbah, and G.S. Paschos, The algorithmic aspects of network slicing , IEEE Commun. Magazine 55 (2017), 112–119

2017
[37]

Y. Xiao, K. Thulasiraman, and G. Xue, GEN-LARAC: A generalized approach to the constrained shortest path problem under multiple additive constraints, Proc. ISAAC, 2005, pp. 92–105

2005
[38]

Z. Xu, G. T aylor, H. Li, M.A. Figueiredo, X. Yuan, and T. Goldstein, Adaptive consensus ADMM for distributed optimization, International Conference on Machine Learning, 2017, pp. 3841–3850

2017
[39]

Y ang, X

Y. Y ang, X. Guan, Q.S. Jia, L. Yu, B. Xu, and C.J. Spanos, A survey of ADMM variants for distributed optimization: Problems, algorithms and features, arXiv preprint arXiv:2208.03700 (2022)

2022 arXiv
[40]

Y. Y ao, X. Zhu, H. Dong, S. Wu, H. Wu, L.C. T ong, and X. Zhou, ADMM-based problem decomposition scheme for vehicle routing problem with time windows , T ransp. Res. Part B: Methodological 129 (2019), 156–174

2019
[41]

B. Zhou, I. Howenstine, S. Limprapaipong, and L. Cheng, A survey on network calculus tools for network infrastruc- ture in real-time systems, IEEE Access 8 (2020), 223588–223605

2020

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.

[1] [1]

Ahuja, T.L

R.K. Ahuja, T.L. Magnanti, J.B. Orlin, and M. Reddy, Applications of network optimization , Handbooks Oper. Res. Manage. Sci. 7 (1995), 1–83

work page 1995

[2] [2]

Aneja and K.P

Y.P . Aneja and K.P . Nair, The constrained shortest path problem, Naval Res. Logist. Q. 25 (1978), 549–555

work page 1978

[3] [3]

Beasley and N

J.E. Beasley and N. Christoﬁdes, An algorithm for the resource constrained shortest path problem , Networks 19 (1989), 379–394

work page 1989

[4] [4]

Bockmayr and N

A. Bockmayr and N. Pisaruk, Detecting infeasibility and generating cuts for MIP using CP , 5th International Work- shop on Integration of AI and OR T echniques in Constraint Programming for Combinatorial Optimization Problems-CPAIOR’03, 2003, pp. 11–p

work page 2003

[5] [5]

Bui and C.M

T.N. Bui and C.M. Zrncic, An ant-based algorithm for ﬁnding degree-constrained minimum spanning tree, Proceedings of the 8th annual conference on Genetic and evolutionary computation, 2006, pp. 11–18

work page 2006

[6] [6]

Calvigioni, R

G. Calvigioni, R. Aparicio-Pardo, L. Sassatelli, J. Leguay, P . Medagliani, and S. Paris, Quality of Experience-based routing of video traﬃc for overlay and isp networks , Proc. IEEE INFOCOM, 2018

work page 2018

[7] [7]

Dantzig, R

G. Dantzig, R. Fulkerson, and S. Johnson, Solution of a large scale traveling salesman problem , J. Oper. Res. Soc. America 2 (1954), 393–410

work page 1954

[8] [8]

Desaulniers, J

G. Desaulniers, J. Desrosiers, and M.M. Solomon, Column generation Vol. 5, Springer Science & Business Media, 2006

work page 2006