Pith. sign in

REVIEW 2 major objections 22 references

Relaxation strength for multilinear optimization: McCormick strikes back

T0 review · 2 major / 0 minor · reviewed 2026-05-24 · grok-4.3

Challenge this review Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The extended flower relaxation equals the strength of intersections from general McCormick linearizations in multilinear optimization.

desk verdict Extends Khajavirad to a broader class of linearizations with a simpler proof and shows the intersection with the extended flower relaxation is invariant to the choice of linearization. read the letter →

arxiv 2311.08570 v3 submitted 2023-11-14 math.OC cs.DMmath.CO

Emily Schutte , Matthias Walter This is my paper · ORCID
classification math.OCcs.DMmath.CO
keywords multilinearoptimizationMcCormickrelaxationextendedflowerlinearrelaxationsstrengthouterapproximation
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 shows that the extended flower relaxation dominates the relaxation obtained from any McCormick linearization, including those beyond the recursive cases covered in prior work, and supplies a simpler proof of the dominance. It further demonstrates that intersecting any such McCormick relaxation with the extended flower relaxation produces no gain in strength. A reader would care because multilinear terms appear in many hard optimization models, and identifying the strongest linear relaxation directly affects how tightly one can bound solutions without solving the full nonlinear problem.

What carries the argument

The extended flower relaxation, a linear outer approximation for multilinear terms that dominates McCormick envelopes through intersection arguments.

What would settle it

An explicit multilinear function and a non-McCormick linearization whose relaxation cuts off a point feasible for the extended flower relaxation.

Watch

Extended reading notes

Core claim

The extended flower relaxation is at least as strong as the relaxation of any McCormick linearization that satisfies the required structural properties, and the intersection of the relaxations of such linearizations and the extended flower relaxation are equally strong.

Load-bearing premise

The linearizations must obey the structural properties of McCormick envelopes so that dominance and intersection arguments apply.

Editorial extensions

If this is right

  • Any McCormick-based linear relaxation, recursive or not, can be replaced by the extended flower relaxation without loss of strength.
  • Intersecting multiple McCormick relaxations with the extended flower adds nothing beyond the flower alone.
  • The dominance result extends from recursive to general McCormick linearizations via the same intersection mechanism.
  • A simpler proof makes the result easier to apply or generalize to other factorization structures.

Reading between the lines

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

  • Implementations could drop explicit McCormick linearizations and retain only the flower constraints for equivalent bounds.
  • The result suggests examining whether other common envelope constructions are also dominated by the flower relaxation.
  • Tighter bounds from this equivalence could improve branch-and-bound performance on polynomial programs without changing the relaxation family.
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, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 0 minor

Summary. The manuscript extends Khajavirad (Operations Research Letters 2023) by proving that the extended flower relaxation dominates the relaxation obtained from any linearization in a broader class than recursive McCormick envelopes, supplies a simpler proof of this dominance, and shows that the intersection of any such linearization relaxation with the extended flower relaxation is independent of the particular linearization chosen within the class.

Significance. If the claims hold, the result strengthens the theoretical toolkit for constructing tight relaxations of multilinear optimization problems and indicates that the extended flower relaxation can be used as a canonical strengthening step. The simpler proof is a clear improvement over the cited prior work.

major comments (2)
  1. [Abstract, §1] Abstract and §1: the extension from recursive McCormick linearizations to a 'more general' class is invoked without an explicit characterization of the class or a supporting lemma verifying that every member satisfies the envelope or recursive dominance identities required for the R ⊇ F and R ∩ F = F arguments. This premise is load-bearing for both the dominance claim and the intersection-equality claim.
  2. The central intersection result (that R ∩ F is equally strong for any admissible R) is stated in the abstract but the manuscript supplies no concrete example or small-instance verification that would allow direct checking of the independence from the choice of linearization.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive report. The comments highlight opportunities to strengthen the exposition of the class of linearizations and to provide verification for the intersection claim. We address each point below and will revise accordingly.

read point-by-point responses

  1. Referee: [Abstract, §1] Abstract and §1: the extension from recursive McCormick linearizations to a 'more general' class is invoked without an explicit characterization of the class or a supporting lemma verifying that every member satisfies the envelope or recursive dominance identities required for the R ⊇ F and R ∩ F = F arguments. This premise is load-bearing for both the dominance claim and the intersection-equality claim.

    Authors: We agree that an explicit characterization improves clarity. Section 2 defines the class as all linearizations whose relaxations R satisfy the recursive dominance property with respect to the multilinear term (i.e., R contains the McCormick envelope on every pair and the resulting inequalities are valid). To make this load-bearing premise fully rigorous, we will insert a formal definition (Definition 2.1) together with a short supporting lemma (Lemma 2.2) that verifies every member of the class obeys the envelope and recursive dominance identities used in the proofs of R ⊇ F and R ∩ F = F. revision: yes

  2. Referee: The central intersection result (that R ∩ F is equally strong for any admissible R) is stated in the abstract but the manuscript supplies no concrete example or small-instance verification that would allow direct checking of the independence from the choice of linearization.

    Authors: The independence is proved in Theorem 3.2 by showing that any feasible point in R ∩ F automatically satisfies all extended-flower inequalities regardless of the particular linearization chosen for R. While the argument is general, we concur that a small numerical check would be helpful. We will add a brief computational example (a single trilinear term in three variables) at the end of Section 3 that explicitly computes two distinct admissible relaxations R1 and R2, forms R1 ∩ F and R2 ∩ F, and verifies that both coincide with F. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity; extension and intersection claims rest on independent proofs citing external work

full rationale

The paper cites Khajavirad (external, 2023) for the recursive McCormick case and supplies its own simpler proof plus intersection result for more general linearizations. No self-citations are load-bearing, no equations reduce the dominance or equality statements to fitted inputs or self-definitions, and no ansatz or uniqueness is imported from the authors' prior work. The derivation chain is self-contained once the structural properties of the linearizations are granted; the reader's noted assumption about the class is a completeness issue, not a circular reduction.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

The paper is a pure proof contribution that relies on standard convex-analysis facts about McCormick envelopes and polyhedral relaxations; no numerical fitting or new postulated objects appear.

assumptions (2)
  • standard math McCormick envelopes and their recursive extensions are valid linear relaxations of bilinear and multilinear terms
    Invoked when the paper compares relaxations; this is background from the optimization literature.
  • domain assumption The extended flower relaxation is a well-defined polyhedron for the multilinear problems considered
    Used throughout the dominance and intersection arguments.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Relaxation strength for multilinear optimization: McCormick strikes back." pith.science (2026). https://pith.science/paper/2311.08570

@misc{pith2026231108570,
  author       = {Pith},
  title        = {Pith review of: Relaxation strength for multilinear optimization: McCormick strikes back},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2311.08570}},
  note         = {Machine review of arXiv:2311.08570}
}
read the original abstract

We consider linear relaxations for multilinear optimization problems. In a recent paper, Khajavirad proved that the extended flower relaxation is at least as strong as the relaxation of any recursive McCormick linearization (Operations Research Letters 51 (2023) 146-152). In this paper we extend the result to more general linearizations, and present a simpler proof. Moreover, we complement Khajavirad's result by showing that the intersection of the relaxations of such linearizations and the extended flower relaxation are equally strong.

Figures

Figures reproduced from arXiv: 2311.08570 by the authors.

Figure 1
Figure 1. Three linearizations for the minimization problem in Figure [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. An instance in which several extended flower inequalities ar [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Recursive linearizations showing that being a [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Hyperedges for a flower inequality with four neighbors and [PITH_FULL_IMAGE:figures/full_fig_p008_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

  1. [1]

    Letchford

    Samuel Burer and Adam N. Letchford. Non-convex mixed-integ er nonlinear programming: A survey. Surveys in Operations Research and Management Science , 17:97–106, 2012. doi:10.1016/j.sorms.2012.08.001

    work page doi:10.1016/j.sorms.2012.08.001 2012

  2. [2]

    George B. Dantzig. Maximization of a linear function of variables su bject to linear inequalities. In Tjalling C. Koopmans, editor, Activity Analysis of Production and Allocation, Cowles Commission Mono- graph No. 13, pages 339–347. John Wiley & Sons, Inc., 1951

    work page 1951

  3. [3]

    Chv´ atal rank in binary polyn omial optimization

    Alberto Del Pia and Silvia Di Gregorio. Chv´ atal rank in binary polyn omial optimization. INFORMS Journal on Optimization , 2021. doi:10.1287/ijoo.2019.0049

    work page doi:10.1287/ijoo.2019.0049 2021

  4. [4]

    A Polyhedral Study of Binary Polynomial Programs

    Alberto Del Pia and Aida Khajavirad. A Polyhedral Study of Binary Polynomial Programs. Mathematics of Operations Research, 42(2):389–410, 2017. doi:10.1287/moor.2016.0804

    work page doi:10.1287/moor.2016.0804 2017

  5. [5]

    The multilinear polytope for ac yclic hypergraphs

    Alberto Del Pia and Aida Khajavirad. The multilinear polytope for ac yclic hypergraphs. SIAM Journal on Optimization , 28(2):1049–1076, 2018. doi:10.1137/16M1095998. 9

    work page doi:10.1137/16m1095998 2018

  6. [6]

    The running intersection rela xation of the multilinear polytope

    Alberto Del Pia and Aida Khajavirad. The running intersection rela xation of the multilinear polytope. Mathematics of Operations Research , 2021. doi:10.1287/moor.2021.1121

    work page doi:10.1287/moor.2021.1121 2021

  7. [7]

    Sahinidis

    Alberto Del Pia, Aida Khajavirad, and Nikolaos V. Sahinidis. On the im pact of running intersection inequalities for globally solving polynomial optimization problems. Mathematical Programming Compu- tation, 12(2):165–191, 2020. doi:10.1007/s12532-019-00169-z

    work page doi:10.1007/s12532-019-00169-z 2020

  8. [8]

    Simple odd β -cycle inequalities for binary polynomial optimiza- tion

    Alberto Del Pia and Matthias Walter. Simple odd β -cycle inequalities for binary polynomial optimiza- tion. In Karen Aardal and Laura Sanit` a, editors, Integer Programming and Combinatorial Optimization , pages 181–194. Springer International Publishing, 2022. doi:10.1007/978-3-031-06901-7_14

    work page doi:10.1007/978-3-031-06901-7_14 2022

Show all 22 references
  1. [9]

    Simple odd β -cycle inequalities for binary polynomial optimiza- tion

    Alberto Del Pia and Matthias Walter. Simple odd β -cycle inequalities for binary polynomial optimiza- tion. Mathematical Programming, Jul 2023. doi:10.1007/s10107-023-01992-y

    2023 doi

  2. [10]

    Lloyd L. Dines. Systems of linear inequalities. Annals of Mathematics , pages 191–199, 1919

    1919

  3. [11]

    Applications de l’algebre de boole en recherche o p´ erationelle

    Robert Fortet. Applications de l’algebre de boole en recherche o p´ erationelle. Revue Fran¸ caise de Recherche Op´ erationelle, 4(14):17–26, 1960

    1960

  4. [12]

    L’algebre de boole et ses applications en recher che operationnelle

    Robert Fortet. L’algebre de boole et ses applications en recher che operationnelle. Trabajos de Estadistica, 4:17–26, 1960. doi:10.1007/BF03006558

    1960 doi

  5. [13]

    Analyse des travaux de i’academ ie royale des sciences pendant i’annee

    Jean Baptiste Joseph Fourier. Analyse des travaux de i’academ ie royale des sciences pendant i’annee

  6. [14]

    Partie mathematique, Histoire de l’Academie Royale des Sci ences de l’Institut de France, 7:xlvii–lv, 1827

  7. [15]

    Further reduction of zero-o ne polynomial programming problems to zero-one linear programming problems

    Fred Glover and Eugene Woolsey. Further reduction of zero-o ne polynomial programming problems to zero-one linear programming problems. Operations Research , 21(1):156–161, 1973. doi:10.1287/opre.21.1.156

    1973 doi

  8. [16]

    Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program

    Fred Glover and Eugene Woolsey. Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program. Operations Research, 22(1):180–182, 1974. doi:10.1287/opre.22.1.180

    1974 doi

  9. [17]

    A polynomial algorithm in linear programming

    Leonid Khachiyan. A polynomial algorithm in linear programming. Doklady Akademii Nauk , 244:1093– 1096, 1979

    1979

  10. [18]

    On the strength of recursive mccormick relax ations for binary polynomial optimization

    Aida Khajavirad. On the strength of recursive mccormick relax ations for binary polynomial optimization. Operations Research Letters, 51(2):146–152, 2023. doi:10.1016/j.orl.2023.01.009

    2023 doi

  11. [19]

    Some re sults on the strength of relaxations of multilinear functions

    James Luedtke, Mahdi Namazifar, and Jeff Linderoth. Some re sults on the strength of relaxations of multilinear functions. Mathematical Programming , 136(2):325–351, 2012. doi:10.1007/s10107-012-0606-z

    2012 doi

  12. [20]

    McCormick

    Garth P. McCormick. Computability of global solutions to factor able nonconvex programs: Part i — convex underestimating problems. Mathematical Programming , 10(1):147–175, 1976. doi:10.1007/BF01580665

    1976 doi

  13. [21]

    Theodore S. Motzkin. Beitr¨ age zur Theorie der linearen Ungleichungen. PhD thesis, Universit¨ at Basel, 1936

    1936

  14. [22]

    Sahinidis

    Mohit Tawarmalani and Nikolaos V. Sahinidis. Convex extensions a nd envelopes of lower semi-continuous functions. Mathematical Programming, 93:247–263, 2002. doi:10.1007/s10107-002-0308-z . 10

    2002 doi

Pith tools

Reviewed May 24, 2026 · model on record in the stance chip above.