pith. sign in

arxiv: 2311.08570 · v3 · submitted 2023-11-14 · 🧮 math.OC · cs.DM· math.CO

Relaxation strength for multilinear optimization: McCormick strikes back

Emily Schutte , Matthias Walter This is my paper

Pith reviewed 2026-05-24 05:12 UTC · model grok-4.3

classification 🧮 math.OC cs.DMmath.CO
keywords multilinear optimizationMcCormick relaxationextended flower relaxationlinear relaxationsrelaxation strengthouter approximation
0
0 comments X

The pith

The extended flower relaxation equals the strength of intersections from general McCormick linearizations in multilinear optimization.

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

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.

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.

What carries the argument

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

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.

Where Pith is reading between the lines

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

Load-bearing premise

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

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.

Figures

Figures reproduced from arXiv: 2311.08570 by Emily Schutte, Matthias Walter.

Figure 1
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. 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. Figure 3: Recursive linearizations showing that being a [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Hyperedges for a flower inequality with four neighbors and [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

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

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.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 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.

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

pith-pipeline@v0.9.0 · 5608 in / 1262 out tokens · 23107 ms · 2026-05-24T05:12:28.688912+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

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

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

    work page doi:10.1007/s10107-023-01992-y 2023

  10. [10]

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

    work page 1919

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

    work page 1960

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

    work page doi:10.1007/bf03006558 1960

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

    work page

  14. [14]

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

    work page

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

    work page doi:10.1287/opre.21.1.156 1973

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

    work page doi:10.1287/opre.22.1.180 1974

  17. [17]

    A polynomial algorithm in linear programming

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

    work page 1979

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

    work page doi:10.1016/j.orl.2023.01.009 2023

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

    work page doi:10.1007/s10107-012-0606-z 2012

  20. [20]

    Mathematical Programming 10(1), 147–175 (1976)

    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

    work page doi:10.1007/bf01580665 1976

  21. [21]

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

    work page 1936

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

    work page doi:10.1007/s10107-002-0308-z 2002