{"id":"55ceae30-7d95-46f7-932e-f99b859d9bd1","arxiv_id":"2501.04563","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Branch-and-price for classical project scheduling is structurally disadvantaged: degeneracy slows column generation and the Dantzig-Wolfe bound is usually no stronger than the bound from a compact formulation.","lead":"This paper explains why branch-and-price algorithms, which work well for vehicle routing and bin packing, fail to be competitive for most resource-constrained project scheduling problems. It shows that the reformulated master problem is highly degenerate and that, for common decompositions, the linear relaxation is no stronger than a compact formulation that is far faster to solve.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 6.1's unproven polytope identity is the load-bearing bridge from Proposition 2 to the literature's aggregated-precedence pricing; without it the no-bound-advantage conclusion does not follow for those algorithms.","rationale":"The reader's weakest-assumption identification matches the most load-bearing point: the paper's central no-bound-advantage theorem for classical single-mode problems is proven for the disaggregated pricing problem, while the actual literature algorithms use aggregated precedence constraints. The Section 6.1 assertion is the only thing connecting Proposition 2 to those algorithms. It is plausible and likely true, since the disaggregated precedence polytope is integral and both constraint sets define the same integer schedules, but the paper does not demonstrate it. A failure of this identity would leave open the possibility that the master relaxation is strictly stronger than PDDT-LP for some instances, undermining the claim that branch-and-price offers no bound advantage. Other weaknesses, such as the incomplete proof of Proposition 6 and the unstabilized column-generation experiments, are secondary: the former only affects a supporting argument, and the latter is empirical rather than structural. Because the concern is a missing proof rather than a demonstrated falsehood, it supports the reader's CONDITIONAL verdict without changing it.","tokens_in":56,"tokens_out":25222,"duration_ms":447593,"concrete_test":"For small random single-mode instances (e.g., 5-8 activities, time horizon T up to 10), enumerate all integer schedules feasible under the aggregated precedence constraints (10), compute the convex hull of their incidence vectors, and compare it with the feasible region of the disaggregated LP relaxation (19)-(20) with x in [0,1] and assignment equalities (5). If every disaggregated-LP vertex is integral, or the two polyhedra coincide, the Section 6.1 identity is confirmed for those instances; if any fractional vertex of the disaggregated LP lies outside conv(integer aggregated schedules), the bridge fails and the no-bound-advantage conclusion must be qualified for the literature formulations.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that, for classical single-mode project scheduling, the Dantzig-Wolfe master relaxation is as weak as the PDDT relaxation depends on Proposition 2 and Theorem 2, which concern the disaggregated pricing problem min{(18):(19)-(21)}. However, the branch-and-price algorithms by Deckro et al. (1991), Drexl and Kimms (2001), and Volland et al. (2017) use the weaker aggregated PDT precedence constraints in pricing. The paper bridges this gap in Section 6.1 by asserting that 'the convex hull of the pricing problem with aggregated precedence constraints coincides with the feasible region of the linear relaxation of the stronger formulation with disaggregated precedence constraints.' No proof or citation is given for this identity. If the identity fails for some instance class, the LMP bound need not equal the PDDT-LP bound, and the conclusion that DW offers no bound advantage for these methods is unsupported. Since this is precisely the step that transfers a theorem about an idealized pricing problem to the actual algorithms under criticism, it is load-bearing for the paper's main negative claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Dantzig-Wolfe reformulations and branch-and-price for non-preemptive resource-constrained project scheduling. It proposes a general multi-mode multi-project model (MRCMPSP-GO) and a master/pricing framework that subsumes several decompositions from the literature. The main analytical claims are: the restricted master is prone to primal degeneracy (Proposition 1); single-mode resource-unconstrained pricing has the integrality property (Proposition 2), so by Theorem 2 the master relaxation is no stronger than the compact PDDT relaxation; multi-mode pricing is not integral (Proposition 3); resource-constrained pricing is not integral (Proposition 4); branching on start times preserves the bound equality (Proposition 5), while branching on resource demands can strengthen the bound (Proposition 6) but makes pricing NP-hard. Computational experiments on 480 PSPLIB j30 instances and 200 MMLIB instances quantify the runtime disadvantage of column generation. The paper concludes that branch-and-price is not competitive for classical single- and multi-mode RCPSP variants, with possible exceptions for dedicated-resource and preemptive settings.","tokens_in":23531,"tokens_out":12779,"duration_ms":124873,"significance":"The result, if established rigorously, is significant because it explains the poor performance of column generation for classical RCPSP and warns against routine Dantzig-Wolfe decomposition for this problem class. The paper's strengths are its systematic survey, the unifying MRCMPSP-GO model, the clean link between the integrality property of the pricing problem and the master bound (Theorem 2 with Proposition 2), and the direct PSPLIB/MMLIB comparisons. The single-mode equality z_LMP = z_PDDT-LP is a crisp, parameter-free theoretical statement, and the experiments confirm it. No free parameters are fitted anywhere in the analysis. However, two load-bearing arguments need repair: the unproved polytope identity in Section 6.1 and the logically inconsistent proof of Proposition 6 in Section 7.2. The multi-mode experiments also solve a different pricing problem than the one analyzed theoretically. The paper does not ship machine-checked proofs or code, and a reproducibility statement with instance selection and column-generation details would strengthen the experimental part.","major_comments":[{"comment":"Section 6.1 states, without proof or citation, that 'the convex hull of the pricing problem with aggregated precedence constraints coincides with the feasible region of the linear relaxation of the stronger formulation with disaggregated precedence constraints.' This identity is the bridge that transfers the no-bound-improvement result from the disaggregated pricing problem min{(18):(19)-(21)} to the actual algorithms of Deckro et al. (1991), Drexl and Kimms (2001), and Volland et al. (2017), which use aggregated precedence in pricing. Without a proof, the central conclusion in Section 8 that these branch-and-price approaches offer no bound advantage is not supported. The identity is in fact true and follows from Proposition 2 together with the observation that, for single-mode binary schedules, the integer feasible sets of the two precedence formulations coincide; the authors should include this argument or provide a precise citation.","section":"Section 6.1"},{"comment":"The proof of Proposition 6 is logically inconsistent. It says that NP-hardness of the pricing problem 'implies' that 'the feasible region of the linear relaxation of the compact formulation LP is a proper subset of the linear relaxed master problem LMP,' and then concludes 'This implies the existence of a point x* in LP and x* not in LMP.' These two statements are contradictory: if LP were a subset of LMP, a point in LP could not fail to be in LMP. The intended inclusion is that LMP is a proper subset of LP. Moreover, NP-hardness alone does not establish the required separation; one must exhibit a fractional vertex of the pricing polytope and an objective for which that fractional point is the unique LP optimum. Please rewrite the proof with a concrete instance or an explicit construction, and correct the inclusion direction.","section":"Section 7.2, Proposition 6"},{"comment":"The multi-mode LMP is computed using aggregated precedence constraints in the pricing problem as a speed-up, while Proposition 3 and the surrounding theoretical analysis concern the disaggregated pricing problem (19)-(21). The reported 0.42% average improvement over PDDT-LP is therefore not a direct measurement of the bound gain of the theoretically analyzed Dantzig-Wolfe formulation. The practical conclusion that column generation is uncompetitive may survive this issue, but the claim that the stronger relaxations 'translate only into marginal lower-bound improvements' should be either tested with the disaggregated pricing problem or explicitly qualified as applying to the aggregated-price LMP.","section":"Section 6.2, Table 8"}],"minor_comments":[{"comment":"The statement that the violated disaggregated precedence constraints 'are likely to be generated by commercial solvers automatically' is speculative and not directly supported by the experiments; please soften or verify.","section":"Section 6.1"},{"comment":"In constraint (B.3), the sum over all times other than t' is written with j as the summation index ('sum over j in T\\{t'}'); it should be sum over t in T\\{t'}.","section":"Appendix B"},{"comment":"The right-hand side of the up-branch contains an apparent typo, 'rkntr*knt'; it should likely be just 'r*knt'.","section":"Section 7.2, Eq. (25)"},{"comment":"The reference to Geoffrion (1974) lists the journal as 'Mathemtical Programming' instead of 'Mathematical Programming'.","section":"References"},{"comment":"The experimental section does not describe how the initial column set for the LMP was generated, how the column-generation runs were terminated, or how the 200 MMLIB instances were sampled (no seed or list is given); please add a reproducibility statement.","section":"Section 5, computational setup"}],"recommendation":"major_revision","confidential_remarks":"The paper's negative conclusion for classical single-mode RCPSP is likely correct, and the PSPLIB experiment confirms it. The two proof gaps described in the major comments should be fixed before publication: the Section 6.1 polytope identity is easy to prove explicitly, whereas Proposition 6 needs a real construction or a weakened statement. The survey and the unifying decomposition are valuable on their own and could carry the paper even if the strict-gap claim of Proposition 6 is downgraded."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a clearly written negative-result paper that has the right message — branch-and-price is usually a bad bet for the classical RCPSP — but the paper's load-bearing transfer step is asserted rather than proved, and one proposition is not proven as stated. Worth refereeing, but it needs work.\n\nWhat is genuinely new: the paper assembles known results (Geoffrion, Möhring et al.) into a coherent explanation of why DW reformulation fails for project scheduling, and it adds new observations: multi-mode pricing loses the integrality property (Prop. 3), branching on start times preserves the status quo (Prop. 5), and branching on resource demands breaks the pricing problem (Prop. 6, sketch). The single-mode bound equivalence (z_LMP = z_PDDT-LP) is correctly derived from Proposition 2 plus Theorem 2, and the PSPLIB experiments confirm it on 480 j30 instances. The survey of 11 column-generation papers is thorough and will be useful to the community.\n\nThe soft spots are in the proof of the paper's headline claim. Section 6.1 asserts that the convex hull of the aggregated-precedence pricing problem coincides with the LP relaxation of the disaggregated one. That identity is the bridge from Proposition 2 to the actual algorithms of Deckro et al., Drexl and Kimms, and Volland et al. — but no proof or citation is given. Table 5 in fact lists those papers as using the disaggregated pricing problem, contradicting the text. If the identity fails for some instance class, the conclusion 'no bound advantage for these methods' does not follow. The stress-test note is right. Second, Proposition 6's proof jumps from NP-hardness of the pricing problem to a strict gap between z_LP and z_LMP; that does not logically imply the claimed containment. The gap might be true, but it is not demonstrated. Proposition 1 (degeneracy) is also heuristic, not a theorem. Finally, the experiments lack code and seeds, so the runtimes are not independently repeatable.\n\nThat said, the paper is honest about its scope, explicitly excludes MSRCPSP and PRCPSP where branch-and-price can be stronger, and the recommendation to focus on alternative formulations is reasonable. Researchers in project scheduling and column generation will get the most value from this. It deserves a proper peer review; the referee should ask for the polytope identity to be proved or referenced, for Prop. 6's proof to be repaired, and for the table/text mismatch to be fixed.\n\nI would bring this paper to a reading group, and I would cite it once the proof gaps are closed.","headline":"A useful, honest negative-result paper on branch-and-price for project scheduling, but the key bound-transfer claim rests on an unproved polytope identity.","tokens_in":24096,"tokens_out":5325,"would_cite":true,"duration_ms":48912,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C10","90C27","90B35"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper establishes why branch-and-price is ineffective for most project scheduling problems: single-mode pricing problems have the integrality property, so the master LP is as weak as the compact PDDT LP, while column generation is far…","keywords":["branch-and-price","column generation","Dantzig-Wolfe decomposition","resource-constrained project scheduling","integrality property","lower bounds","degeneracy","RCPSP"],"falsifier":"Find a single-mode RCPSP instance where the linear relaxation of the master problem, solved exactly by column generation, has a strictly larger optimal value than the linear relaxation of the compact PDDT formulation; such an instance would contradict Propositions 2 and 5 and Theorem 2 as applied here. A complementary check is to test whether the aggregated-precedence pricing polytope ever has a fractional vertex that is not in the disaggregated PDDT polyhedron.","tokens_in":23121,"feed_emoji":"📉","tokens_out":5871,"duration_ms":50056,"temperature":0.7,"pith_summary":"Branch-and-price has been proposed for many resource-constrained project scheduling problems, but existing studies never show a clear win over solving the compact integer program directly. This paper explains why: for single-mode problems, the Dantzig-Wolfe pricing problem has the integrality property, so the master LP relaxation is exactly as strong as the compact PDDT relaxation, and solving it via column generation is far slower. For multi-mode problems the reformulation strengthens the bound only marginally, and the increase in runtime dominates. The paper also shows that branching on start times preserves the bound equality, while branching on resource demands can strengthen bounds but makes the pricing problem NP-hard. The conclusion is a recommendation against branch-and-price for classical RCPSP variants and a call for alternative decompositions with hard-but-efficiently-solvable pricing problems.","feed_headline":"Branch-and-price fails to beat compact solvers for project scheduling","feed_subtitle":"Single-mode reformulations match the compact LP bound but run far slower; multi-mode gains are marginal.","key_machinery":"The central object is the integrality property of the pricing problem: an integer program has this property when its linear relaxation has only integral vertices, so the convex hull of feasible integer solutions equals the LP polyhedron. Theorem 2 (attributed to Geoffrion's Lagrangian-relaxation analysis) then implies that the linear relaxation of the master problem achieves exactly the same bound as the compact formulation. The paper combines this with Proposition 1 on primal degeneracy of the restricted master problem, showing that many zero-valued basic variables mislead column generation and slow convergence. For the multi-mode case, the counterexample in Appendix A shows the integrality property fails, but the resulting bound gains are small. The branching analysis then shows start-time branching preserves the integrality property, while resource-demand branching adds one knapsack-style constraint that makes the pricing problem NP-hard.","core_discovery":"For classical single-mode project scheduling, the Dantzig-Wolfe decomposition yields a pricing problem that can be solved as a linear program (Proposition 2), yet the linear relaxation of the master problem is as weak as the relaxation of the compact PDDT formulation (Theorem 2 and Proposition 2). Adding standard branching on start times does not change this: branch-and-price and branch-and-bound on the compact formulation generate the same branching trees (Proposition 5). The master problem is highly degenerate, so column generation needs many iterations and long runtimes for no bound gain. For multi-mode pricing problems, the integrality property fails, but computational experiments on MMLIB instances show only marginal lower-bound improvements that are offset by runtimes averaging 26 times longer than the compact LP; the compact formulation with solver-generated cuts matches or beats the master bound in a fraction of the time. The paper concludes that branch-and-price is not competitive for most project scheduling problems, with the possible exceptions of preemptive variants and dedicated-resource variants, where NP-hard pricing problems can yield genuinely stronger relaxations.","pith_inferences":["The integrality-property argument likely extends to other scheduling or packing formulations whose pricing polytopes are known to be integral, meaning branch-and-price should not be expected to improve bounds in those settings either.","The degeneracy diagnosis suggests that dual stabilization could mitigate the runtime penalty of column generation for project scheduling, but since the underlying bound is the weak point in the single-mode case, stabilization alone would not make branch-and-price competitive.","The paper's negative result is scoped to the activity-subset decomposition; decompositions that change the pricing problem's structure, such as time-indexed or antichain-based formulations, are the direction most likely to escape the conclusion.","A testable extension would be to apply the same decomposition analysis to project scheduling variants with time-dependent resource capacities or calendars, where the pricing problems lose the integrality property and might behave like the multi-mode case."],"forward_implications":["Lower-bound computations for single-mode RCPSP that rely on Dantzig-Wolfe column generation do not deliver stronger bounds than solving the compact PDDT relaxation with a commercial solver.","A branch-and-price algorithm for single-mode problems that branches on start times will explore exactly the same branching tree as a standard branch-and-bound on the compact formulation, so it cannot be competitive unless its node solves are faster, which the runtime experiments rule out.","For multi-mode problems, the small bound improvement of the master LP can be recovered or even exceeded by adding cutting planes to the compact formulation, at a fraction of the runtime.","The only column-generation approaches that can promise stronger relaxations are those whose pricing problems are genuinely hard, such as preemptive antichain formulations or dedicated-resource decompositions; even there, the NP-hard pricing becomes the bottleneck.","Researchers should focus on alternative Dantzig-Wolfe decompositions whose pricing problems are hard but efficiently solvable by tailored algorithms."],"supporting_citations":[{"why":"Established the Lagrangian-relaxation equivalence that underlies Theorem 2: a relaxation is unchanged when the subproblem has the integrality property.","marker":"Geoffrion (1974)"},{"why":"Provides the branch-and-price framework, Theorem 1 on bound ordering, and the master/pricing notation the paper builds on.","marker":"Desrosiers et al. (2024)"},{"why":"Proves the integrality property of the single-mode project scheduling polytope, which the paper uses as Proposition 2.","marker":"Möhring et al. (2001)"},{"why":"Shows that the disaggregated PDDT formulation has a stronger linear relaxation than the aggregated PDT, providing the baseline for bound comparisons.","marker":"Artigues (2017)"},{"why":"Supplies the PSPLIB j30 instances used in the single-mode computational experiments.","marker":"Kolisch and Sprecher (1997)"},{"why":"Documents the branch-price-and-cut approach for dedicated resources, the evidence that NP-hard pricing problems can strengthen bounds but become the bottleneck.","marker":"Coughlan et al. (2015)"}],"fun_headline_variants":["Why branch-and-price stumbles on project scheduling","Branch-and-price loses to compact solvers on scheduling","Weak relaxation and degeneracy doom branch-and-price for scheduling","Project scheduling: decomposition gains too small, cost too high","Branch-and-price: not worth it for most project scheduling problems"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument that literature pricing problems with aggregated precedence constraints give no bound gain relies on the assumption that the convex hull of the aggregated pricing polytope equals the feasible region of the disaggregated PDDT relaxation; if this fails for some instance class, the master bound could differ.","fun_headline_variants_meta":{"raw":{"variants":["Why branch-and-price stumbles on project scheduling","Branch-and-price loses to compact solvers on scheduling","Weak relaxation and degeneracy doom branch-and-price for scheduling","Project scheduling: decomposition gains too small, cost too high","Branch-and-price: not worth it for most project scheduling problems"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00024,"raw_usage":{"total_tokens":1514,"prompt_tokens":934,"completion_tokens":580,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":550,"completion_tokens_details":{"reasoning_tokens":501}},"tokens_in":550,"tokens_out":580,"duration_ms":5743,"temperature":1.0,"reasoning_tokens":501,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T21:29:37.822472+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a single-mode RCPSP instance where the linear relaxation of the master problem, solved exactly by column generation, has a strictly larger optimal value than the linear relaxation of the compact PDDT formulation; such an instance would contradict Propositions 2 and 5 and Theorem 2 as applied here. A complementary check is to test whether the aggregated-precedence pricing polytope ever has a fractional vertex that is not in the disaggregated PDDT polyhedron.","supporting_citations":[{"cited_title":", year 1974","cited_arxiv_id":null,"evidence_quote":"Established the Lagrangian-relaxation equivalence that underlies Theorem 2: a relaxation is unchanged when the subproblem has the integrality property."},{"cited_title":", author L \\\"u bbecke, M","cited_arxiv_id":null,"evidence_quote":"Provides the branch-and-price framework, Theorem 1 on bound ordering, and the master/pricing notation the paper builds on."},{"cited_title":", year 2017","cited_arxiv_id":null,"evidence_quote":"Shows that the disaggregated PDDT formulation has a stronger linear relaxation than the aggregated PDT, providing the baseline for bound comparisons."},{"cited_title":", author Sprecher, A","cited_arxiv_id":null,"evidence_quote":"Supplies the PSPLIB j30 instances used in the single-mode computational experiments."},{"cited_title":", author L \\\"u bbecke, M.E","cited_arxiv_id":null,"evidence_quote":"Documents the branch-price-and-cut approach for dedicated resources, the evidence that NP-hard pricing problems can strengthen bounds but become the bottleneck."}],"review_version":1}