  


Visible points, the separation problem, and applications to MINLP
Felipe Serrano(serranozib.de) Abstract: In this paper we introduce a technique to produce tighter cutting planes for mixedinteger nonlinear 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 nonconvex constraint intersected with a convex set we provide a characterization of the visible points. Furthermore, when the nonconvex constraint is quadratic the characterization is particularly simple. We also provide an extended formulation for a relaxation of the visible points when the nonconvex constraint is a general polynomial. Finally, we give some conditions under which for a given set there is an inclusionwise smallest set, in some predefined family of sets, whose reverse polars coincide. Keywords: Separation problem, Visible points, Mixedinteger 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: ZIBReport 1938, Zuse Institute Berlin, Takustr. 7, 14195 Berlin, July 2019 Download: [PDF] Entry Submitted: 07/18/2019 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  