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

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.

Citation

SIAM Journal on Optimization, Vol. 31 (2021), 2396-2428.