Visible points, the separation problem, and applications to MINLP

Felipe Serrano

arxiv: 1907.07909 · v1 · pith:KMWAW3NSnew · submitted 2019-07-18 · 🧮 math.OC

Visible points, the separation problem, and applications to MINLP

Felipe Serrano This is my paper

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

classification 🧮 math.OC

keywords visible pointsreverse polarcutting planesMINLPseparation problemnonconvex constraintsmixed-integer nonlinear programmingvalid inequalities

0 comments

The pith

The reverse polar of the visible points of the feasible region from the infeasible point coincides with the reverse polar of the feasible region.

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

The paper develops a technique for tighter cutting planes in mixed-integer nonlinear programs by restricting the feasible region to points visible from a given infeasible point. Validity is preserved because the reverse polar of this visible set equals the reverse polar of the original feasible region, so any separating cut valid for the visible set is valid for the full set. The equivalence is shown directly from the separation problem and reverse polar. When the feasible region consists of a single nonconvex constraint intersected with a convex set, the visible points admit an explicit characterization, which simplifies further for quadratic constraints and admits an extended formulation relaxation for general polynomial constraints. The work also states conditions under which a given set has an inclusion-wise smallest set in a family whose reverse polars coincide.

Core claim

We show that the reverse polar of the visible points of the feasible region from the infeasible point coincides with the reverse polar of the feasible region. In the special case where the feasible region is described by a single non-convex constraint intersected with a convex set we provide a characterization of the visible points. Furthermore, when the non-convex constraint is quadratic the characterization is particularly simple. We also provide an extended formulation for a relaxation of the visible points when the non-convex constraint is a general polynomial. Finally, we give some conditions under which for a given set there is an inclusion-wise smallest set, in some predefined family,

What carries the argument

The set of visible points of the feasible region from the infeasible point, whose reverse polar is shown to coincide with that of the full feasible region.

If this is right

Any cut separating the infeasible point from the visible points remains valid for the original feasible region.
Tighter cuts can be generated by working with the visible points rather than the full region.
For a single nonconvex quadratic constraint intersected with a convex set the visible points admit a simple explicit characterization.
An extended formulation is available for a relaxation of the visible points when the nonconvex constraint is a general polynomial.
Under stated conditions a given set possesses an inclusion-wise smallest set in a family whose reverse polars coincide.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The visible-point construction could be embedded inside existing branch-and-cut solvers for MINLP to tighten cut generation at each node.
The single-constraint characterization might extend to multiple nonconvex constraints if visibility can be computed componentwise.
The smallest-set result may supply a systematic way to select minimal outer approximations in other reverse-polar-based separation routines.

Load-bearing premise

Restricting the feasible region to visible points from the infeasible point preserves all valid cuts for the original region when the reverse polars coincide.

What would settle it

A hyperplane that separates the infeasible point from the visible points but intersects the original feasible region.

Figures

Figures reproduced from arXiv: 1907.07909 by Felipe Serrano.

**Figure 1.** Figure 1: The feasible region g(x) ≤ 0 and ¯x = (0, 0) together with the box V . It is possible to show that R ⊆ V , where V = [− 1 2 , 17 10 ] × [− 6 25 , 3 2 ]. Hence, by Corollary 21, (V ∩ S) x¯ = S x¯ . This means that we can solve the separation problem over {x ∈ V : g(x) ≤ 0} instead of S. Therefore, if we were to compute an underestimator of g, it could be computed over V ( B. Methods for obtaining tighter bo… view at source ↗

**Figure 2.** Figure 2: The region S. In the middle picture VS are the points described by the thick red line. In the right picture the red points form the smallest set V such that V 0 = S 0 . Example 2. Consider the constrained set S = {(x1, x2) ∈ R 2 + : (x1−x2) 2 ≥ 1} depicted in [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

**Figure 3.** Figure 3: The left plot shows the feasible region S and ¯x. The set {x ∈ B : g(x) = 0} appears in the middle plot. Finally, the visible points, VS(¯x), are plotted on the right. 4.1.2 Polynomial constraints For a general polynomial g, the condition g(x + λ(¯x − x)) > 0 for every λ ∈ (0, 1] (2) of (1) asks for the univariate polynomial px(λ) = g(x + λ(¯x − x)) to be positive on (0, 1]. We can then use the theory of n… view at source ↗

**Figure 4.** Figure 4: The point z = (−1, 0) is not visible from ¯x, because g(z + λ(¯x − z)) = g(−1 + 2λ, −2λ) = ((2λ − 1)2 + 4λ 2 − 1)(2λ − 1) = 4λ(2λ − 1)2 is zero at λ = 1 2 . On the other hand, z ∈ RS(¯x) since 4λ(2λ − 1)2 ≥ 0 for every λ ∈ [0, 1]. In this example VS(¯x) is closed, so we conclude that cl VS(¯x) 6= RS(¯x). 5 Conclusions and outlook Using the concept of visible points, we introduced a technique that allows to… view at source ↗

**Figure 4.** Figure 4: Feasible region g(x) ≤ 0 of Example 6 that shows that cl VS(¯x) 6= RS(¯x) when the degree of g is greater than 2. esting for MINLP, since the tightness of the domain directly affects the quality of underestimators, from which cuts are obtained. Some questions that could be interesting to look at in the future are the following. Is there a tighter domain other than VS that can be efficiently exploited? Is … view at source ↗

read the original abstract

In this paper we introduce a technique to produce tighter cutting planes for mixed-integer non-linear programs. Usually, a cutting plane is generated to cut off a specific infeasible point. The underlying idea is to use the infeasible point to restrict the feasible region in order to obtain a tighter domain. To ensure validity, we require that every valid cut separating the infeasible point from the restricted feasible region is still valid for the original feasible region. We translate this requirement in terms of the separation problem and the reverse polar. In particular, if the reverse polar of the restricted feasible region is the same as the reverse polar of the feasible region, then any cut valid for the restricted feasible region that separates the infeasible point, is valid for the feasible region. We show that the reverse polar of the visible points of the feasible region from the infeasible point coincides with the reverse polar of the feasible region. In the special where the feasible region is described by a single non-convex constraint intersected with a convex set we provide a characterization of the visible points. Furthermore, when the non-convex constraint is quadratic the characterization is particularly simple. We also provide an extended formulation for a relaxation of the visible points when the non-convex constraint is a general polynomial. Finally, we give some conditions under which for a given set there is an inclusion-wise smallest set, in some predefined family of sets, whose reverse polars coincide.

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.

Desk Editor's Note private letter to a colleague

The core result is that visible points from the infeasible point have the same reverse polar as the full feasible region, so cuts valid for the visible subset remain valid for the original.

read the letter

The main point is that restricting to visible points from the cut-off point keeps the reverse polar unchanged, which directly gives a way to generate tighter cuts that are still valid. The paper sets this up by linking the separation requirement to reverse-polar equality, then proves the visible-points set satisfies it in general. For the case of one non-convex constraint plus a convex set they supply an explicit characterization, which simplifies further when the constraint is quadratic. They also give an extended formulation for a relaxation when the constraint is a general polynomial, plus some conditions for minimal sets whose reverse polars match. This is a clean geometric move that is not just a rephrasing of existing separation methods. The argument is presented as a direct proof with no fitted parameters or circular steps, and the quadratic case looks especially usable. A minor limitation is that the work stays at the level of characterization and formulation; it does not include computational tests or solver integration details, so the practical payoff for branch-and-cut remains to be checked. The math itself appears solid and the claim is precise enough to verify. This is for people working on cutting-plane methods inside MINLP solvers. A reader who cares about geometric valid inequalities or separation oracles would get something concrete from it. The paper shows clear engagement with the separation and polar literature and states its results without overclaiming. It deserves a serious referee to examine the derivations and the polynomial extension.

Referee Report

0 major / 3 minor

Summary. The paper claims that in the context of generating cutting planes for MINLPs, the reverse polar of the visible points of a feasible region (from a given infeasible point) coincides with the reverse polar of the full feasible region. This equivalence ensures that any cut valid for the visible-points restriction and separating the infeasible point remains valid for the original region. The paper proves the general coincidence result, gives an explicit characterization of visible points when the region is a single non-convex constraint intersected with a convex set (with a simpler form when the constraint is quadratic), supplies an extended formulation for a relaxation when the constraint is a general polynomial, and states conditions under which a given set has an inclusion-wise smallest set in a predefined family with coinciding reverse polars.

Significance. If the central coincidence result holds, the technique offers a principled way to tighten cutting planes for non-convex MINLPs without sacrificing validity, which could improve branch-and-cut performance. The paper earns credit for supplying a direct mathematical translation via the separation problem and reverse polar (no fitted parameters), an explicit characterization in the quadratic case, and an extended formulation for the polynomial case; these are concrete, usable contributions.

minor comments (3)

Abstract, line 3: 'In the special where' is grammatically incomplete and should read 'In the special case where'.
[§5] §5 (extended formulation): the relaxation of visible points for general polynomials is stated but the precise lifting variables and constraints are not compared to existing outer-approximation schemes; a short remark on computational cost would help readers assess practicality.
[§2] Notation: the reverse polar is used throughout without an explicit reminder of its definition after the introduction; adding a one-line recall in §2 would improve readability for readers outside convex analysis.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the careful reading, positive assessment of significance, and recommendation for minor revision. The provided summary accurately reflects the paper's contributions regarding the coincidence of reverse polars for visible points and the feasible region, along with the characterizations and formulations supplied.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper's central claim is a direct mathematical proof that the reverse polar of the visible-points subset (from an infeasible point) equals the reverse polar of the full feasible region. This equivalence is derived from the definitions of the separation problem and reverse polar, with explicit characterizations supplied for special cases (single non-convex constraint intersected with convex set, quadratic case, polynomial case). No parameters are fitted to data and then renamed as predictions; no self-citations are invoked as load-bearing uniqueness theorems; no ansatz is smuggled via prior work; and no known empirical pattern is merely renamed. The derivation is self-contained as a theorem proof and does not reduce to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claim rests on standard properties of reverse polars and the separation problem from convex analysis, with the new defined concept of visible points introduced to restrict the domain without altering the polar.

axioms (1)

standard math Standard properties of reverse polars and separation in convex geometry hold for the feasible region
Invoked to translate the validity requirement for cuts into equivalence of reverse polars.

invented entities (1)

visible points no independent evidence
purpose: To define a restricted subset of the feasible region from which separating cuts remain valid for the original set
Newly defined set whose reverse polar is shown to coincide with the full feasible region's reverse polar.

pith-pipeline@v0.9.0 · 5776 in / 1374 out tokens · 46588 ms · 2026-05-24T19:51:06.317657+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We show that the reverse polar of the visible points of the feasible region from the infeasible point coincides with the reverse polar of the feasible region.
IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 25. ... VS(¯x) = {x∈C : g(x)=0, ⟨∇g(¯x),x⟩ + bT¯x + 2c ≥ 0}

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages · 1 internal anchor

[1]

Discrete Applied Mathematics 89(1-3), 3–44 (1998)

Balas, E.: Disjunctive programming: Properties of the convex hull of fea- sible points. Discrete Applied Mathematics 89(1-3), 3–44 (1998). DOI 10.1016/s0166-218x(98)00136-x

work page doi:10.1016/s0166-218x(98)00136-x 1998
[2]

European Journal of Operational Re- search 252(3), 701–727 (2016)

Boukouvala, F., Misener, R., Floudas, C.A.: Global optimization ad- vances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO. European Journal of Operational Re- search 252(3), 701–727 (2016). DOI 10.1016/j.ejor.2015.12.018

work page doi:10.1016/j.ejor.2015.12.018 2016
[3]

Springer International Publishing (2014)

Conforti, M., Cornu´ ejols, G., Zambelli, G.: Integer Programming. Springer International Publishing (2014). DOI 10.1007/978-3-319-11008-0

work page doi:10.1007/978-3-319-11008-0 2014
[4]

Mathematical Programming (2018)

Conforti, M., Wolsey, L.A.: “Facet” separation with one linear program. Mathematical Programming (2018). DOI 10.1007/s10107-018-1299-8

work page doi:10.1007/s10107-018-1299-8 2018
[5]

In: Computational and Analytical Mathematics, pp

Deutsch, F., Hundal, H., Zikatanov, L.: Visible points in convex sets and best approximation. In: Computational and Analytical Mathematics, pp. 349–364. Springer New York (2013). DOI 10.1007/978-1-4614-7621-4 15 18

work page doi:10.1007/978-1-4614-7621-4 2013
[6]

Journal of Optimization Theory and Applications 175(3), 764–794 (2017)

Fasano, G., Pesenti, R.: Conjugate direction methods and polarity for quadratic hypersurfaces. Journal of Optimization Theory and Applications 175(3), 764–794 (2017). DOI 10.1007/s10957-017-1180-6

work page doi:10.1007/s10957-017-1180-6 2017
[7]

Springer Berlin Heidelberg (1993)

Gr¨ otschel, M., Lov´ asz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer Berlin Heidelberg (1993). DOI 10.1007/978-3-642-78240-4

work page doi:10.1007/978-3-642-78240-4 1993
[8]

Journal of Global Optimization 3(1), 25–47 (1993)

Hamed, A.S.E.D., McCormick, G.P.: Calculation of bounds on variables satisfying nonlinear inequality constraints. Journal of Global Optimization 3(1), 25–47 (1993). DOI 10.1007/bf01100238

work page doi:10.1007/bf01100238 1993
[9]

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

McCormick, G.P.: Computability of global solutions to factorable noncon- vex programs: Part I — convex underestimating problems. Mathematical Programming 10(1), 147–175 (1976). DOI 10.1007/bf01580665

work page doi:10.1007/bf01580665 1976
[10]

Transactions of the American Mathematical Society 352(10), 4677–4693 (2000)

Powers, V., Reznick, B.: Polynomials that are positive on an interval. Transactions of the American Mathematical Society 352(10), 4677–4693 (2000). DOI 10.1090/s0002-9947-00-02595-2

work page doi:10.1090/s0002-9947-00-02595-2 2000
[11]

Constraints 22(3), 338–376 (2017)

Puranik, Y., Sahinidis, N.V.: Domain reduction techniques for global NLP and MINLP optimization. Constraints 22(3), 338–376 (2017). DOI 10. 1007/s10601-016-9267-5

work page 2017
[12]

Princeton university press (1970)

Rockafellar, R.T.: Convex analysis. Princeton university press (1970)

work page 1970
[13]

Ruys, P.: Public goods and decentralization: the duality approach in the theory of value. Ph.D. thesis, Tilburg University (1974)

work page 1974
[14]

Mathematical Programming 22(1), 71–81 (1982)

Tind, J., Wolsey, L.A.: On the use of penumbras in blocking and an- tiblocking theory. Mathematical Programming 22(1), 71–81 (1982). DOI 10.1007/bf01581026

work page doi:10.1007/bf01581026 1982
[15]

Integer Set Reduction for Stochastic Mixed-Integer Programming

Venkatachalam, S., Ntaimo, L.: Integer Set Reduction for Stochastic Mixed-Integer Programming. arXiv e-prints arXiv:1605.05194 (2016)

work page internal anchor Pith review Pith/arXiv arXiv 2016
[16]

Vigerske, S.: Decomposition in multistage stochastic programming and a constraint integer programming approach to mixed-integer nonlinear pro- gramming. Ph.D. thesis, Humboldt-Universit¨ at zu Berlin, Mathematisch- Naturwissenschaftliche Fakult¨ at II (2013)

work page 2013
[17]

Journal of Convex Analysis 15(2), 325–343 (2008) 19

Zaﬀaroni, A.: Convex coradiant sets with a continuous concave cogauge. Journal of Convex Analysis 15(2), 325–343 (2008) 19

work page 2008

[1] [1]

Discrete Applied Mathematics 89(1-3), 3–44 (1998)

Balas, E.: Disjunctive programming: Properties of the convex hull of fea- sible points. Discrete Applied Mathematics 89(1-3), 3–44 (1998). DOI 10.1016/s0166-218x(98)00136-x

work page doi:10.1016/s0166-218x(98)00136-x 1998

[2] [2]

European Journal of Operational Re- search 252(3), 701–727 (2016)

Boukouvala, F., Misener, R., Floudas, C.A.: Global optimization ad- vances in mixed-integer nonlinear programming, MINLP, and constrained derivative-free optimization, CDFO. European Journal of Operational Re- search 252(3), 701–727 (2016). DOI 10.1016/j.ejor.2015.12.018

work page doi:10.1016/j.ejor.2015.12.018 2016

[3] [3]

Springer International Publishing (2014)

Conforti, M., Cornu´ ejols, G., Zambelli, G.: Integer Programming. Springer International Publishing (2014). DOI 10.1007/978-3-319-11008-0

work page doi:10.1007/978-3-319-11008-0 2014

[4] [4]

Mathematical Programming (2018)

Conforti, M., Wolsey, L.A.: “Facet” separation with one linear program. Mathematical Programming (2018). DOI 10.1007/s10107-018-1299-8

work page doi:10.1007/s10107-018-1299-8 2018

[5] [5]

In: Computational and Analytical Mathematics, pp

Deutsch, F., Hundal, H., Zikatanov, L.: Visible points in convex sets and best approximation. In: Computational and Analytical Mathematics, pp. 349–364. Springer New York (2013). DOI 10.1007/978-1-4614-7621-4 15 18

work page doi:10.1007/978-1-4614-7621-4 2013

[6] [6]

Journal of Optimization Theory and Applications 175(3), 764–794 (2017)

Fasano, G., Pesenti, R.: Conjugate direction methods and polarity for quadratic hypersurfaces. Journal of Optimization Theory and Applications 175(3), 764–794 (2017). DOI 10.1007/s10957-017-1180-6

work page doi:10.1007/s10957-017-1180-6 2017

[7] [7]

Springer Berlin Heidelberg (1993)

Gr¨ otschel, M., Lov´ asz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer Berlin Heidelberg (1993). DOI 10.1007/978-3-642-78240-4

work page doi:10.1007/978-3-642-78240-4 1993

[8] [8]

Journal of Global Optimization 3(1), 25–47 (1993)

Hamed, A.S.E.D., McCormick, G.P.: Calculation of bounds on variables satisfying nonlinear inequality constraints. Journal of Global Optimization 3(1), 25–47 (1993). DOI 10.1007/bf01100238

work page doi:10.1007/bf01100238 1993

[9] [9]

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

McCormick, G.P.: Computability of global solutions to factorable noncon- vex programs: Part I — convex underestimating problems. Mathematical Programming 10(1), 147–175 (1976). DOI 10.1007/bf01580665

work page doi:10.1007/bf01580665 1976

[10] [10]

Transactions of the American Mathematical Society 352(10), 4677–4693 (2000)

Powers, V., Reznick, B.: Polynomials that are positive on an interval. Transactions of the American Mathematical Society 352(10), 4677–4693 (2000). DOI 10.1090/s0002-9947-00-02595-2

work page doi:10.1090/s0002-9947-00-02595-2 2000

[11] [11]

Constraints 22(3), 338–376 (2017)

Puranik, Y., Sahinidis, N.V.: Domain reduction techniques for global NLP and MINLP optimization. Constraints 22(3), 338–376 (2017). DOI 10. 1007/s10601-016-9267-5

work page 2017

[12] [12]

Princeton university press (1970)

Rockafellar, R.T.: Convex analysis. Princeton university press (1970)

work page 1970

[13] [13]

Ruys, P.: Public goods and decentralization: the duality approach in the theory of value. Ph.D. thesis, Tilburg University (1974)

work page 1974

[14] [14]

Mathematical Programming 22(1), 71–81 (1982)

Tind, J., Wolsey, L.A.: On the use of penumbras in blocking and an- tiblocking theory. Mathematical Programming 22(1), 71–81 (1982). DOI 10.1007/bf01581026

work page doi:10.1007/bf01581026 1982

[15] [15]

Integer Set Reduction for Stochastic Mixed-Integer Programming

Venkatachalam, S., Ntaimo, L.: Integer Set Reduction for Stochastic Mixed-Integer Programming. arXiv e-prints arXiv:1605.05194 (2016)

work page internal anchor Pith review Pith/arXiv arXiv 2016

[16] [16]

Vigerske, S.: Decomposition in multistage stochastic programming and a constraint integer programming approach to mixed-integer nonlinear pro- gramming. Ph.D. thesis, Humboldt-Universit¨ at zu Berlin, Mathematisch- Naturwissenschaftliche Fakult¨ at II (2013)

work page 2013

[17] [17]

Journal of Convex Analysis 15(2), 325–343 (2008) 19

Zaﬀaroni, A.: Convex coradiant sets with a continuous concave cogauge. Journal of Convex Analysis 15(2), 325–343 (2008) 19

work page 2008