-

 

 

 




Optimization Online





 

Generating feasible points for mixed-integer convex optimization problems by inner parallel cuts

Christoph Neumann (christoph.neumann***at***kit.edu)
Oliver Stein (stein***at***kit.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 mixed-integer 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 mixed-integer 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: Mixed-integer 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 2018-11-6947, 2020

Download: [PDF]

Entry Submitted: 11/27/2018
Entry Accepted: 11/27/2018
Entry Last Modified: 02/28/2020

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
Mathematical Optimization Society