Optimization Online


Visible points, the separation problem, and applications to MINLP

Felipe Serrano(serrano***at***zib.de)

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 \emph{separates} the infeasible point, is valid for the feasible region. We show that the reverse polar of the \emph{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.

Keywords: Separation problem, Visible points, Mixed-integer nonlinear programming, Reverse polar, Global optimization

Category 1: Global Optimization

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 3: Integer Programming (Cutting Plane Approaches )

Citation: ZIB-Report 19-38, Zuse Institute Berlin, Takustr. 7, 14195 Berlin, July 2019

Download: [PDF]

Entry Submitted: 07/18/2019
Entry Accepted: 07/18/2019
Entry Last Modified: 07/18/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society