{"id":"11a3b3a5-0fe8-4cc6-8850-2823835bd32b","arxiv_id":"2501.15345","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A pseudo basic step, solved by Lagrangian decomposition, gives provable lower bounds on the improvement from a basic step in convex disjunctive programming, and on K-means instances it closes far more of the optimality gap than commercial solvers.","lead":"The paper introduces a way to estimate, in advance and with a guarantee, how much tighter a convex optimization model gets when you combine two logical 'or' choices (disjunctions) into one. This matters because tighter models give better lower bounds and faster proofs of optimality for hard mixed-integer problems like K-means clustering.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 5's optimal-multiplier claim for K-means is false: μ=0 satisfies Σ_i μ_ik=0 but is not a maximizer; a two-point, one-cluster example gives dual value 0 at μ=0 versus 1/2 at the true optimum.","rationale":"The reader's weakest assumption identified Proposition 5, and our analysis confirms and strengthens that concern: the claimed optimal multipliers λ*=1, μ*=0 are not only unsupported by the proof, they are demonstrably suboptimal. The proof's unboundedness argument fails because the centroid copies c'_ki0 are bounded by (27f), and boundedness of the c_k terms in (31a) requires only column sums Σ_i μ_ik=0, not termwise vanishing μ. The two-point counterexample shows a strictly better dual feasible point with nonzero μ. This matters because Section 4.2 presents the analytical optimality of these multipliers as a way to avoid solving the hull relaxation; that claim is false. However, the paper's principal theoretical contribution—the pseudo basic step and the hierarchy in Corollary 2—does not depend on Proposition 5. The partition relaxation lower bound is valid for any multipliers satisfying the summing condition, and the numerical K-means lower bounds would remain valid even with suboptimal multipliers, though they would no longer be certified as the best possible Lagrangian bound. Consequently, the appropriate disposition remains CONDITIONAL: the authors should correct Proposition 5 (or replace 'optimal' with 'valid'), fix the prose/constraint mismatch around (27f), and clarify that the K-means experiments use a valid, rather than optimal, multiplier set. No change to the reader's verdict is needed.","tokens_in":1043,"tokens_out":930,"duration_ms":237690,"concrete_test":"Independently evaluate the Lagrangian dual (30) for the two-point, one-cluster instance p1=0, p2=1 in R^1. With λ=(1,1), the dual function at μ=(t,−t) is t − t^2/2, so its maximum over t is 1/2 at t=1, while μ=(0,0) gives 0. Since the primal hull relaxation (27) also has value 1/2, μ=0 is suboptimal, directly refuting Proposition 5. This is an analytic one-line computation and requires no solver.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central hierarchy (Propositions 2–4, Corollaries 1–2) is sound: Corollary 2 follows from weak duality and Proposition 4, and the partition-relaxation lower bound holds for any multipliers summing to the objective coefficients. The load-bearing weakness is Proposition 5. In the K-means Lagrangian (31a), the coefficient of each c_k is −Σ_i μ_{ik}; boundedness only forces Σ_i μ_{ik}=0, not μ_{ik}=0. The proof tries to force unboundedness by sending c'_kÎ0ĵ to ±∞ when y_Îk=0, but constraint (27f) bounds c'_ki0j by ±M (and the experimental version by [0,1]^D), so the minimization remains bounded. Moreover, μ=0 is not a maximizer. For N=2 points p1=0, p2=1 and K=1, the hull relaxation (27) has value 1/2. With λ=(1,1), μ=(0,0), LRN=0; with μ=(t,−t), LRN=t−t^2/2, maximized at t=1 with value 1/2. Thus Proposition 5's asserted analytical optimum is false. The text around (27f) also reverses the actual constraint: (27f) as printed forces c'_ki0=0 when y_ik=1, while the prose says the opposite. This does not destroy the main theoretical result, because the partition-relaxation lower bound remains valid for any valid multipliers; it invalidates only the 'optimal multipliers' claim used to motivate the K-means experiments.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a \"pseudo basic step\" for convex disjunctive programming: an operation that, given Lagrange multipliers from a hull reformulation, computes lower bounds on the improvement that an actual basic step would produce. The main theoretical contributions are a hierarchy (Propositions 2–4, Corollaries 1–2) showing that a partition relaxation lies between the hull relaxation and the Lagrangian dual, and that a pseudo basic step can never improve more than an actual basic step. The paper also presents computational experiments on random conic quadratic disjunctive programs and on K-means clustering, reporting large improvements in lower bounds relative to commercial MIQCP solvers. The central hierarchy is sound, but the analytical optimal-multiplier claim for K-means (Proposition 5) is not.","tokens_in":20319,"tokens_out":20738,"duration_ms":182766,"significance":"If the central hierarchy is correct, the paper offers a useful, simple tool: for any feasible multipliers, a partition relaxation gives a computable lower bound on the gain from a basic step, and the bound is guaranteed not to exceed the gain of an actual basic step. This is a clean, parameter-free result with clear practical potential, and the numerical demonstrations on conic quadratic programs and K-means instances show meaningful improvements over commercial solvers. The K-means claim of analytically optimal multipliers is, however, false as stated; this affects the exposition and justification of the K-means experiments but not the validity of the hierarchy itself, provided the K-means bounds are reframed as coming from feasible (not necessarily optimal) multipliers.","major_comments":[{"comment":"Proposition 5 is false as stated. The proof argues that if μ*_ki ≠ 0, the minimization in (31) is unbounded because c'_ki0j can tend to ±M with y_ik = 0. But constraint (27f) explicitly bounds c'_ki0j in [−M, M] (and the experimental model restricts it to [0,1]^D), so the objective remains finite for any fixed μ. The unboundedness argument does not force μ_ik = 0. A concrete counterexample is N=2, K=1, p1=0, p2=1. The hull relaxation (27) has optimal value 1/2. At λ=(1,1), μ=(0,0), each point can choose its own copy c'_i1 = p_i and d'_i = 0 because (27c) is dualized, giving LRN = 0. Taking μ=(−t,t) gives LRN = t − t^2/2, which is maximized at t=1 with value 1/2. Thus μ=0 is not an optimal multiplier, contradicting the proposition. The analysis of the coefficients in (31a) only forces λ_i=1 and Σ_i μ_ik = 0, not μ_ik = 0.","section":"Section 4.2.2, Proposition 5"},{"comment":"The prose following (27f) is reversed. As printed, (27f) forces c'_ki0j = 0 when y_ik = 1 and allows c'_ki0j ∈ [−M, M] when y_ik = 0. The text states the opposite: it says c'_ki0 = 0 when y_ik = 0 and c'_ki0 ∈ [−M, M]^D otherwise. This reversal is directly connected to the erroneous unboundedness argument in Proposition 5 and must be corrected.","section":"Section 4.2.2, constraint (27f) and surrounding text"},{"comment":"Because Proposition 5 is false, the statement in Section 4.2 that multipliers for K-means \"can be determined analytically\" as optimal multipliers is unsupported. The numerical lower bounds may still be valid if the subproblems are solved with feasible multipliers (e.g., λ_i=1 and μ_ik=0, which satisfy the necessary sum conditions), because Corollary 2 gives a valid lower bound for any feasible multipliers. The paper should explicitly reframe the K-means contribution as using feasible multipliers rather than optimal ones, and should clarify exactly which constraints are kept in the subproblems of the partition relaxation. In particular, it should be stated whether the subproblems retain the dualized constraint (27c); if they do not, the reported bounds need to be re-justified.","section":"Section 4.2.2, Proposition 5 and Section 4.2, K-means experiments"}],"minor_comments":[{"comment":"There are several typos and small inconsistencies, e.g., 'reek havoc' should be 'wreak havoc', 'Basics steps' in the conclusions should be 'Basic steps', and the abstract and text alternate between 'Lagrangian' and 'Lagrangean' spellings.","section":"Throughout"},{"comment":"The columns 'time (s)' and 'parallel (s)' are not fully explained; the caption should state that 'time (s)' includes the time to solve the hull relaxation and obtain the multipliers, and how the parallel times are measured.","section":"Table 3"},{"comment":"The 'NA' entry in the HR-LB column for instance 10 is not explained; the caption or text should say why no hull-relaxation bound was available for that instance.","section":"Table 4"},{"comment":"The notation for the Lagrangian subproblem is dense; it would help readers if the feasible set and the exact role of the binary variables y_ik in the subproblem were stated explicitly, especially since the subproblems are solved with CPLEX as MIQCPs.","section":"Section 4.2.2, Eq. (30)-(31)"}],"recommendation":"major_revision","confidential_remarks":"The main theoretical hierarchy (Propositions 2–4 and Corollaries 1–2) is correct and is the paper's core contribution. Proposition 5 is a load-bearing error in the K-means section, but it appears fixable by weakening the claim to feasible multipliers and re-deriving the validity of the computational bounds; the numerical results are not inherently discredited. The paper fits the journal's scope and the central idea is worth publishing after the K-means optimality claim is corrected."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is worth reading for Corollary 2's inequality chain. The pseudo basic step — solving min over an intersection of a subset of disjunctions with summed multipliers — gives a computable, guaranteed lower bound on the improvement from an actual basic step, and the chain z* >= z_Hrel_Q >= z_LD_Q >= L_P(...) >= LR_K(lambda) is correct and clean. Propositions 2 through 4 are elementary (minimum over an intersection is at least the sum of minima), but they assemble into a hierarchy that I don't think appears elsewhere. The K-means experiments show large lower-bound gains over three commercial solvers, and the deterministic partition heuristic is a reasonable idea.\n\nThe soft spots are real but localized. Proposition 5 is the load-bearing problem. In the K-means Lagrangian, the coefficient of each c_k is -sum_i mu_ik; boundedness only forces the sum to be zero, not each mu_ik = 0. The proof tries to argue unboundedness by sending c'_ki0 to +/-infinity when y_ik=0, but the formulation bounds that variable, and the printed constraint (27f) actually forces c'_ki0=0 when y_ik=1, the opposite of the prose. A two-point, one-cluster check gives LRN=0 at mu=0 and 1/2 at mu=(1,-1), so the claimed 'analytical optimum' is false. That said, the main numerical method does not collapse: the partition relaxation bound is valid for any multipliers summing to c, and the experiments don't require mu=0 to be optimal. The paper should fix Proposition 5 to claim only that mu=0 is a feasible multiplier choice, or derive the actual optimal multipliers. The constraint typo needs correcting. Minor issues: no code or data, old solver versions, and |Ns|=20 is tuned; these make the computational claims harder to verify but do not undermine the central hierarchy.\n\nBottom line: the core theoretical contribution is sound and citable, with one flawed proposition that should be revised. Send it to peer review; a good referee will catch the same issue quickly, and the fix is local.","headline":"The pseudo-basic-step hierarchy is a sound and genuinely useful framing, but the paper's analytic multiplier claim for K-means is wrong and needs revision before publication.","tokens_in":20828,"tokens_out":1807,"would_cite":true,"duration_ms":16653,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C11","90C25","90C26"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that a pseudo basic step, a cheap partition-relaxation operation, provides a guaranteed lower bound on how much an actual basic step can tighten a convex disjunctive program's hull relaxation, and that it can never…","keywords":["pseudo basic step","disjunctive programming","Lagrangian decomposition","hull relaxation","partition relaxation","convex MINLP","K-means clustering","conic quadratic optimization"],"falsifier":"Compute the exact optimal dual multipliers of the continuous relaxation of the K-means hull reformulation (27) with variables restricted to $[0,1]^D$; if any $\\lambda_i \\neq 1$ or any $\\mu_{ki} \\neq 0$ appears, Proposition 5's analytic-multiplier claim is false. Alternatively, exhibit a convex disjunctive program in which a pseudo basic step using optimal multipliers produces a strictly larger bound improvement than the corresponding actual basic step, which would contradict Corollary 2.","tokens_in":19699,"feed_emoji":"🧮","tokens_out":5315,"duration_ms":49854,"temperature":0.7,"pith_summary":"This paper addresses the open question of what guaranteed bounds can be placed on the improvement from a basic step, the operation that intersects two disjunctions to tighten a disjunctive relaxation. It introduces a pseudo basic step, which intersects a group of disjunctions while keeping their discrete structure, and proves that this cheaper operation produces a computable lower bound on the improvement that an actual basic step would deliver. The main inequality chain shows that a pseudo basic step can never tighten the relaxation more than the corresponding actual basic step, even though in the extreme partition it recovers the true optimum. On conic quadratic disjunctive programs and K-means clustering instances, the resulting partition relaxation closes a substantial fraction of the optimality gap while commercial mixed-integer nonlinear programming solvers make little progress.","feed_headline":"Pseudo basic steps give provable relaxation-gain bounds","feed_subtitle":"Cheap pseudo basic steps certify most of a basic step's relaxation gain at a fraction of the cost.","key_machinery":"The central object is the partition relaxation $L_{\\mathcal{P}}(\\mu_1,\\dots,\\mu_P) = \\sum_{p=1}^P \\min\\{\\mu_p^\\top v : v \\in \\cap_{k \\in J_p} F_k\\}$, where the subproblem for a single group $J$ is exactly a pseudo basic step. The argument rides on Lagrangian decomposition of the hull reformulation, whose multipliers must satisfy $\\sum_{k \\in K} \\lambda_k = c$, together with weak duality between the hull relaxation and the Lagrangian dual. Intersecting disjunctions inside a subproblem only shrinks that subproblem's feasible set, which yields the monotone chain and the guaranteed lower bound on a basic step's improvement.","core_discovery":"The central claim is that, for any set of Lagrange multipliers summing to the objective vector $c$ and any partition $\\mathcal{P}$ of the disjunction set, the optimal value $L_{\\mathcal{P}}$ of the induced partition relaxation satisfies $z^* \\ge z_{Hrel_Q} \\ge z_{LD_Q} \\ge L_{\\mathcal{P}} \\ge L R_K(\\lambda)$, placing pseudo basic steps precisely inside Balas's hierarchy of relaxations. As a corollary, the bound improvement from a basic step between two disjunctions is at least the gap between the partition relaxation value and the Lagrangian relaxation value, and a pseudo basic step is guaranteed not to outperform an actual basic step. The paper also shows that, for K-means clustering, optimal multipliers for the hull reformulation take the simple form $\\lambda_i^* = 1$ and $\\mu_{ki}^* = 0$, allowing the partition relaxation to be formed analytically without solving the hull relaxation.","pith_inferences":["The same inequality chain suggests a strong-branching-style rule: choose the pair or group of disjunctions whose pseudo basic step yields the largest bound gain, and use that group for an actual basic step or as a branching guide.","Iterating pseudo basic steps while re-deriving multipliers from each successive partition relaxation could climb the hierarchy of relaxations without ever constructing a full disjunctive normal form.","A natural stress test is to compute exact dual multipliers for the bounded K-means hull reformulation with variables restricted to $[0,1]^D$; if any differ from $\\lambda_i^* = 1, \\mu_{ki}^* = 0$, the analytic-multiplier claim needs amendment even though the partition bound itself remains valid.","The success on multi-term convex disjunctions points toward cut-generating mechanisms for multi-term convex disjunctions, paralleling lift-and-project cuts from multi-term linear disjunctions."],"forward_implications":["For any partition of the disjunctions, the partition relaxation yields a valid lower bound that can be computed by solving small convex disjunctive subproblems rather than the full hull reformulation.","Solving the hull relaxation first supplies optimal multipliers, and the resulting pseudo basic step bound is guaranteed to be no larger than the improvement of the corresponding actual basic step.","The deterministic point-to-subproblem assignment for K-means clustering produces lower bounds that commercial MIQCP solvers fail to reach within fifteen minutes on the tested instances.","Because pseudo basic steps retain discrete features and decompose into independent subproblems, they offer a parallelizable way to tighten formulations without enlarging the hull reformulation.","The chain in Corollary 2 gives a principled way to screen candidate basic steps by evaluating only the cheap pseudo step before committing to an expensive actual step."],"supporting_citations":[{"why":"Defines basic steps and the hierarchy of relaxations that the pseudo basic step bounds sit inside.","marker":"[3]"},{"why":"Establishes the hull reformulation of a union of convex sets via perspective functions, the object whose multipliers are used.","marker":"[11]"},{"why":"Introduces Lagrangian relaxation of the hull reformulation for linear disjunctive programs, the starting point extended here to the convex case.","marker":"[23]"},{"why":"Provides the hierarchy of relaxations for nonlinear convex disjunctive programs and the subproblem equivalence used in Proposition 3.","marker":"[18]"},{"why":"Supplies the nonlinear programming duality results underpinning Proposition 3 and the existence of optimal multipliers.","marker":"[9]"},{"why":"Gives the Big-M formulation used to solve the subproblems arising in pseudo basic steps.","marker":"[13]"},{"why":"Provides the explicit extended hull reformulation for linear disjunctive programs and the basic-step operation in its original form.","marker":"[2]"}],"fun_headline_variants":["Pseudo basic steps prove relaxation-gain bounds at low cost","Pseudo basic steps certify most relaxation gain for less","Lagrangian decomposition yields cheap basic-step bound proofs","Pseudo steps give provable relaxation-gain bounds cheaply","Cheap pseudo basic steps certify relaxation gains"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The lower-bound guarantees in Proposition 3 and Corollary 1 require optimal Lagrange multipliers for the hull relaxation to exist, which typically needs a constraint qualification; separately, the analytic K-means multipliers in Proposition 5 assume the dual subproblem allows centroid copies to grow unboundedly, which the computational model's finite variable bounds do not permit.","fun_headline_variants_meta":{"raw":{"variants":["Pseudo basic steps prove relaxation-gain bounds at low cost","Pseudo basic steps certify most relaxation gain for less","Lagrangian decomposition yields cheap basic-step bound proofs","Pseudo steps give provable relaxation-gain bounds cheaply","Cheap pseudo basic steps certify relaxation gains"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000742,"raw_usage":{"total_tokens":3286,"prompt_tokens":895,"completion_tokens":2391,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":511,"completion_tokens_details":{"reasoning_tokens":2314}},"tokens_in":511,"tokens_out":2391,"duration_ms":16805,"temperature":1.0,"reasoning_tokens":2314,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T14:24:46.346040+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the exact optimal dual multipliers of the continuous relaxation of the K-means hull reformulation (27) with variables restricted to $[0,1]^D$; if any $\\lambda_i \\neq 1$ or any $\\mu_{ki} \\neq 0$ appears, Proposition 5's analytic-multiplier claim is false. Alternatively, exhibit a convex disjunctive program in which a pseudo basic step using optimal multipliers produces a strictly larger bound improvement than the corresponding actual basic step, which would contradict Corollary 2.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines basic steps and the hierarchy of relaxations that the pseudo basic step bounds sit inside."},{"cited_title":"Ceria and J","cited_arxiv_id":null,"evidence_quote":"Establishes the hull reformulation of a union of convex sets via perspective functions, the object whose multipliers are used."},{"cited_title":"Trespalacios and I","cited_arxiv_id":null,"evidence_quote":"Introduces Lagrangian relaxation of the hull reformulation for linear disjunctive programs, the starting point extended here to the convex case."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the hierarchy of relaxations for nonlinear convex disjunctive programs and the subproblem equivalence used in Proposition 3."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the nonlinear programming duality results underpinning Proposition 3 and the existence of optimal multipliers."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the Big-M formulation used to solve the subproblems arising in pseudo basic steps."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the explicit extended hull reformulation for linear disjunctive programs and the basic-step operation in its original form."}],"review_version":1}