Abstract

In this paper we propose a simple and cheap method for extracting inner polytopes, i.e., entirely feasible convex regions in which all points satisfy the constraints. The method performs an inner linearization of a set of nonlinear constraints by using a Taylor form. Unlike a previous proposal, the expansion point of the Taylor form is not limited to the bounds of the domains; it can be given by any point inside the studied region producing, in general, a tighter approximation. The approach was used as an upper bounding method in a state-of-the-art global branch & bound optimizer. In the studied instances, the new method finds in average much more inner regions (in 20% of the processed nodes) than the original approach (in 5% of the nodes).