Pseudo basic steps: Bound improvement guarantees from Lagrangian decomposition in convex disjunctive programming

Dimitri J. Papageorgiou; Francisco Trespalacios

REVIEW 3 major objections 4 minor 24 references

Pseudo basic steps: Bound improvement guarantees from Lagrangian decomposition in convex disjunctive programming

T0 review · 3 major / 4 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 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…

desk verdict 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. read the letter →

arxiv 2501.15345 v1 pith:QT4ROUJO submitted 2025-01-25 math.OC

Dimitri J. Papageorgiou , Francisco Trespalacios This is my paper · ORCID

classification math.OC MSC 90C1190C2590C26

keywords pseudobasicstepdisjunctiveprogrammingLagrangiandecompositionhullrelaxationpartitionconvexMINLPK-meansclusteringconicquadraticoptimization

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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

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 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.

The 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.

Bottom 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.

Referee Report

3 major / 4 minor

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.

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 (3)

[Section 4.2.2, Proposition 5] 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 4.2.2, constraint (27f) and surrounding text] 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 4.2.2, Proposition 5 and Section 4.2, K-means experiments] 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.

minor comments (4)

[Throughout] 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.
[Table 3] 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.
[Table 4] 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 4.2.2, Eq. (30)-(31)] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the bound hierarchy is proved from weak duality and set inclusion, with no parameter fitted to the target bounds; Proposition 5 is a correctness risk, not a circular step.

full rationale

The central derivation chain is self-contained. Proposition 2 follows from unboundedness of x unless the multipliers sum to c, and Proposition 4 uses only the set inclusion ∩_{j∈J} F_j ⊆ F_k to show that the partition relaxation dominates the sum of per-disjunction Lagrangian subproblems. Corollary 2 assembles these facts with weak duality (Proposition 3) and with the feasibility of grouped multipliers for the Lagrangian dual of the basic-stepped problem; no inequality in this chain is calibrated to the improvement being bounded. The pseudo-basic-step bound L_P(...) - LR_K(λ*) is a computed relaxation, not a prediction fitted to actual basic-step outcomes. The self-citations to Trespalacios and Grossmann (2014, 2016) are contextual and not load-bearing, since the required inequalities are proved directly in this paper. The K-means lower bounds are also not circular: even without optimality of λ_i=1, μ_ki=0, Proposition 4 guarantees a valid partition-relaxation bound for any multipliers summing to the objective coefficients, and the subproblems are solved directly on the original formulations. The genuine weakness is Proposition 5 in Section 4.2.2, which asserts λ_i*=1 and μ_ki*=0 are optimal for the K-means Lagrangian dual; its proof relies on c'_{ki0} growing unboundedly when y_ik=0, which conflicts with the finite bound M and with either reading of constraint (27f), and a two-point, one-cluster example gives dual value 0 at μ=0 versus 1/2 at the true optimum. That is a mathematical error in an auxiliary optimality claim, not a circularity, because the paper's hierarchical bound statements do not depend on Proposition 5 for their validity.

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

The central inequality chain is self-contained given convexity, compactness, and existence of multipliers. The paper introduces no physical entities; the pseudo basic step is a mathematical construct. The main unstated burden is the correctness of the K-means multiplier claim, which rests on the questionable unboundedness argument in Proposition 5.

free parameters (3)

Subproblem size |Ns| = 20 points
Chosen after minimal experimentation in Section 4.2.3; directly affects TresPapas performance and reported gap closing.
Number of random partition trials = 10
TresPapas R calls Algorithm 2 ten times (Table 5); an arbitrary choice with no sensitivity analysis.
Time limit per subproblem = max{60, TOTAL_TIME_LIMIT/|Ns|} seconds
A computational heuristic influencing how many subproblems are solved to optimality.

assumptions (4)

domain assumption All disjuncts C_ki are compact convex sets and the objective is linear.
Assumed after equation (2); needed for finite hull relaxations and for multiplier arguments.
domain assumption Optimal Lagrange multipliers to the hull relaxation (4) exist, e.g., under a Slater-type constraint qualification.
Invoked in Propositions 3 and 5 and Corollary 1; the paper notes this is not guaranteed in general.
standard math Minimizing a linear function over a union of compact convex sets is equivalent to minimizing over the convex closure (Ruiz and Grossmann [18, Section 2.5]).
Used in the proof of Proposition 3 to relate the Lagrangian subproblems to the hull relaxation.
ad hoc to paper For K-means, the printed hull constraint (27f) is assumed to allow c'_ki0 to be free when y_ik=0, as needed for the unboundedness argument in Proposition 5.
The printed inequality -M(1-y) <= c'_ki0 <= M(1-y) forces c'_ki0=0 when y_ik=1, the opposite of what the text claims; the proof therefore relies on a formulation different from the one written.

invented entities (1)

Pseudo basic step
purpose: Approximate an actual basic step by solving one subproblem of a partition relaxation (14), in order to obtain guaranteed bound improvements without forming an explicit DNF expansion.
Introduced in Section 3.1 as a mathematical construct. It is defined by the paper and has no external falsifiable handle.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Pseudo basic steps: Bound improvement guarantees from Lagrangian decomposition in convex disjunctive programming." pith.science (2026). https://pith.science/paper/QT4ROUJO

@misc{pith2026250115345,
  author       = {Pith},
  title        = {Pith review of: Pseudo basic steps: Bound improvement guarantees from Lagrangian decomposition in convex disjunctive programming},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QT4ROUJO}},
  note         = {Machine review of arXiv:2501.15345}
}

read the original abstract

An elementary, but fundamental, operation in disjunctive programming is a basic step, which is the intersection of two disjunctions to form a new disjunction. Basic steps bring a disjunctive set in regular form closer to its disjunctive normal form and, in turn, produce relaxations that are at least as tight. An open question is: What are guaranteed bounds on the improvement from a basic step? In this paper, using properties of a convex disjunctive program's hull reformulation and multipliers from Lagrangian decomposition, we introduce an operation called a pseudo basic step and use it to provide provable bounds on this improvement along with techniques to exploit this information when solving a disjunctive program as a convex MINLP. Numerical examples illustrate the practical benefits of these bounds. In particular, on a set of K-means clustering instances, we make significant bound improvements relative to state-of-the-art commercial mixed-integer programming solvers.

Figures

Figures reproduced from arXiv: 2501.15345 by the authors.

**Figure 1.** Illustration of basic steps. A basic step is an elementary, but fundamental, operation in disjunctive programming, tantamount in importance to a branching rule or cutting plane in mixed-integer programming. In words, a basic step applied to a disjunctive set F = T k∈K S i∈Dk Ski is the operation of taking two disjunctions p and q in K and bringing their intersection into disjunctive normal form. In set notation, a b… view at source ↗

**Figure 2.** Illustration of example (17). a) Shows the feasible region and optimal solution. b) Shows the [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗

**Figure 3.** Illustration of the hull relaxation after basic steps for (17) intersecting a) disjunctions 1 and 2; b) [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: Comparison of average optimality gap closed for various solvers and methods on [PITH_FULL_IMAGE:figures/full_fig_p021_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 23 canonical work pages

[1]

Achterberg, T

T. Achterberg, T. Koch, and A. Martin. Branching rules revisited. Operations Research Letters, 33(1):42–54, 2005

work page 2005
[2]

E. Balas. Disjunctive programming. Annals of Discrete Mathematics, 5:3–51, 1979

work page 1979
[3]

E. Balas. Disjunctive programming and a hierarchy of relaxations for discrete optimization problems. SIAM Journal on Algebraic Discrete Methods, 6(3):466–486, 1985

work page 1985
[4]

E. Balas. Disjunctive programming: Properties of the convex hull of feasible points. Discrete Applied Mathe- matics, 89(1):3–44, 1998

work page 1998
[5]

E. Balas. Disjunctive Programming, pages 283–340. Springer Berlin Heidelberg, Berlin, Heidelberg, 2010

work page 2010
[6]

Balas, S

E. Balas, S. Ceria, and G. Cornu´ ejols. A lift-and-project cutting plane algorithm for mixed 0–1 programs. Mathematical programming, 58(1-3):295–324, 1993

work page 1993
[7]

Belotti, P

P. Belotti, P. Bonami, M. Fischetti, A. Lodi, M. Monaci, A. Nogales-G´ omez, and D. Salvagnin. On handling indicator constraints in mixed integer programming. Computational Optimization and Applications, pages 1–22, 2016

work page 2016
[8]

Ben-Tal and A

A. Ben-Tal and A. Nemirovski. Lectures on modern convex optimization: analysis, algorithms, and engineering applications. SIAM, 2001

work page 2001

Show all 24 references

[9]

D. P. Bertsekas. Nonlinear programming. Athena Scientific, 2nd edition, 1999

1999
[10]

Bonami, A

P. Bonami, A. Lodi, A. Tramontani, and S. Wiese. On mathematical programming with indicator constraints. Mathematical Programming, 151(1):191–223, 2015

2015
[11]

Ceria and J

S. Ceria and J. Soares. Convex programming for disjunctive convex optimization. Mathematical Programming, 86(3):595–614, 1999

1999
[12]

Fischetti, A

M. Fischetti, A. Lodi, and D. Salvagnin. Just MIP it! In Matheuristics, pages 39–70. Springer, 2009

2009
[13]

I. E. Grossmann and F. Trespalacios. Systematic modeling of discrete-continuous optimization models through generalized disjunctive programming. AIChE Journal, 59(9):3276–3295, 2013

2013
[14]

Guignard

M. Guignard. Lagrangean relaxation. Top, 11(2):151–200, 2003

2003
[15]

G. L. Nemhauser and L. A. Wolsey. Integer and combinatorial optimization. John Wiley & Sons, 1988

1988
[16]

Perregaard and E

M. Perregaard and E. Balas. Generating Cuts from Multiple-Term Disjunctions, pages 348–360. Springer Berlin Heidelberg, Berlin, Heidelberg, 2001

2001
[17]

Raman and I

R. Raman and I. E. Grossmann. Modelling and computational techniques for logic based integer programming. Computers & Chemical Engineering, 18(7):563–578, 1994

1994
[18]

J. P. Ruiz and I. E. Grossmann. A hierarchy of relaxations for nonlinear convex generalized disjunctive pro- gramming. European Journal of Operational Research, 218(1):38–47, 2012

2012
[19]

N. Sawaya. Reformulations, relaxations and cutting planes for generalized disjunctive programming. PhD thesis, 2006. 23

2006
[20]

Sawaya and I

N. Sawaya and I. Grossmann. A hierarchy of relaxations for linear generalized disjunctive programming.European Journal of Operational Research, 216(1):70–82, 2012

2012
[21]

R. A. Stubbs and S. Mehrotra. A branch-and-cut method for 0-1 mixed convex programming. Mathematical programming, 86(3):515–532, 1999

1999
[22]

Trespalacios and I

F. Trespalacios and I. E. Grossmann. Algorithmic approach for improved mixed-integer reformulations of convex generalized disjunctive programs. INFORMS Journal on Computing, 27(1):59–74, 2014

2014
[23]

Trespalacios and I

F. Trespalacios and I. E. Grossmann. Lagrangean relaxation of the hull-reformulation of linear generalized disjunctive programs and its use in disjunctive branch and bound. European Journal of Operational Research, 253(2):314 – 327, 2016

2016
[24]

J. P. Vielma and G. L. Nemhauser. Modeling disjunctive constraints with a logarithmic number of binary variables and constraints. Mathematical Programming, 128(1-2):49–72, 2011. 24

2011

Pith tools

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

[1] [1]

Achterberg, T

T. Achterberg, T. Koch, and A. Martin. Branching rules revisited. Operations Research Letters, 33(1):42–54, 2005

work page 2005

[2] [2]

E. Balas. Disjunctive programming. Annals of Discrete Mathematics, 5:3–51, 1979

work page 1979

[3] [3]

E. Balas. Disjunctive programming and a hierarchy of relaxations for discrete optimization problems. SIAM Journal on Algebraic Discrete Methods, 6(3):466–486, 1985

work page 1985

[4] [4]

E. Balas. Disjunctive programming: Properties of the convex hull of feasible points. Discrete Applied Mathe- matics, 89(1):3–44, 1998

work page 1998

[5] [5]

E. Balas. Disjunctive Programming, pages 283–340. Springer Berlin Heidelberg, Berlin, Heidelberg, 2010

work page 2010

[6] [6]

Balas, S

E. Balas, S. Ceria, and G. Cornu´ ejols. A lift-and-project cutting plane algorithm for mixed 0–1 programs. Mathematical programming, 58(1-3):295–324, 1993

work page 1993

[7] [7]

Belotti, P

P. Belotti, P. Bonami, M. Fischetti, A. Lodi, M. Monaci, A. Nogales-G´ omez, and D. Salvagnin. On handling indicator constraints in mixed integer programming. Computational Optimization and Applications, pages 1–22, 2016

work page 2016

[8] [8]

Ben-Tal and A

A. Ben-Tal and A. Nemirovski. Lectures on modern convex optimization: analysis, algorithms, and engineering applications. SIAM, 2001

work page 2001