  


Generating feasible points for mixedinteger convex optimization problems by inner parallel cuts
Christoph Neumann (christoph.neumannkit.edu) Abstract: In this article we introduce an inner parallel cutting plane method (IPCP) to compute good feasible points along with valid cutting planes for mixedinteger convex optimization problems. The method iteratively generates polyhedral outer approximations of an enlarged inner parallel set (EIPS) of the continuously relaxed feasible set. This EIPS possesses the crucial property that any rounding of any of its elements is feasible for the original problem. The outer approximations are refined in each iteration by using modified Kelley cutting planes, which are defined via rounded optimal points of linear optimization problems (LPs). We show that the method either computes a feasible point or certifies that the EIPS is empty. Moreover, we demonstrate how inner parallel cuts can be reversed so that they are valid for the original problem, and we provide bounds on the objective value of the generated feasible points. As there exist consistent problems which possess an empty EIPS, the IPCP is not guaranteed to find a feasible point for the latter. Yet, the crucial advantage of the method lies in the difficulty of each iteration: While other approaches need to solve a mixedinteger linear optimization problem, the IPCP only needs to solve an LP. Indeed, our computational study indicates that the IPCP is able to quickly compute feasible points and reversed inner parallel cutting planes for many practical applications. It further demonstrates that the computed points are generally of good quality and that the reversed inner parallel cuts can help to speed up outer approximation based methods. Keywords: Mixedinteger programming, feasibility problem, cutting plane method, inner parallel set Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming ) Category 2: Integer Programming (Cutting Plane Approaches ) Citation: Optimization Online, Preprint ID 2018116947, 2020 Download: [PDF] Entry Submitted: 11/27/2018 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  