(253g) A Novel Branching Scheme for Problems with Reverse Convex Quadratic Constraints and Its Application to Packing Problems

A quadratic constraint f(x) ≥ 0 is called reverse convex if f(x) is convex [1]. Reverse convex quadratic constraints are abundant in mathematical models for many industrial applications such as cutting and packing problems (CPP) [2] and wireless sensor network localization [3] among others. Though there have been impressive improvements in the general purpose global solvers for the past decades, solving problems with reverse convex quadratic constraints to ε-optimality is still a very challenging task. In this work, we propose a novel branching scheme in order to tackle this type of constraint and we compare our approach with global solvers via computational studies on cutting and packing instances.

Unlike a traditional, general purpose global solver, which must generically relax a nonconvex constraint and tighten that relaxation via branching on the domains of the native variables [4], our novel approach recognizes the physical meaning of the reverse convex quadratic constraint and proposes a direct branching on nonconvex constraints themselves. The inspiration emanates from two observations. First, branching on nonconvex constraints is enforcing their feasibility in a more direct way and therefore should be more effective in cutting off infeasible space. Second, in the context of specific applications such as CPP, due to a large number of these constraints and their close relationship, feasibility-based tightening techniques can be exploited in a more sophisticated fashion if the constraints feasible domain is explicitly split.

The CPP aims to find a packing of shapes that minimizes the amount of material needed to carve them out of a stock. This minimization of waste can be of utmost economic importance in certain large industrial sectors, wherein a minuscule reduction in the amount of stock material used would result in significant monetary savings across the whole industry. In this work, we focus on two types of CPP: circle packing problems (CP) [5] and irregular shape packing problems (ISP, also known as nesting problems) [2]. For CP and ISP, relevant studies in the CPP community have mostly focused on the development of heuristics to obtain large-scale packings. While heuristic methods are practically valuable for the generation of good solutions [6], they lack any guarantees of optimality and cannot rigorously quantify the quality of packings produced. The challenge of solving CP and ISP to global optimality results from the fact that enforcing no overlap between two shapes leads to certain nonconvexities that are still numerically very challenging for even the state-of-the-art global optimization solvers.

In this work, we focus on tackling reverse convex quadratic constraints and propose a novel branching scheme. In order to evaluate our approach’s effectiveness and compare its performance with deterministic global solvers, we conduct comprehensive computational studies on a suite of circle packing instances and irregular shape packing instances [7]. Preliminary results indicate that our new branching method is competitive to global solvers including BARON [8], COUENNE [9] and GloMIQO [10], LINDOGlobal [11] and SCIP [12].

References:

[1] Hillestad, R.J. and Jacobsen, S.E., 1980. Reverse convex programming. Applied Mathematics and Optimization, 6(1), pp.63-78.

[2] Wäscher, G., Haußner, H. and Schumann, H., 2007. An improved typology of cutting and packing problems. European journal of operational research, 183(3), pp.1109-1130.

[3] Biswas, P. and Ye, Y., 2004, April. Semidefinite programming for ad hoc wireless sensor network localization. In Proceedings of the 3rd international symposium on Information processing in sensor networks (pp. 46-54). ACM.

[4] Floudas, C.A. and Gounaris, C.E., 2009. A review of recent advances in global optimization. Journal of Global Optimization, 45(1), pp.3-38.

[5] Castillo, I., Kampas, F.J. and Pintér, J.D., 2008. Solving circle packing problems by global optimization: numerical results and industrial applications. European Journal of Operational Research, 191(3), pp.786-802.

[6] Hopper, E. and Turton, B.C., 2001. A review of the application of meta-heuristic algorithms to 2D strip packing problems. Artificial Intelligence Review, 16(4), pp.257-300.

[7] Wang, A., Hanselman, C.L. and Gounaris, C.E., 2018. A customized branch-and-bound approach for irregular shape nesting. Journal of Global Optimization, pp.1-21.

[8] Tawarmalani, M. and Sahinidis, N.V., 2005. A polyhedral branch-and-cut approach to global optimization. Mathematical Programming, 103(2), pp.225-249.

[9] Belotti, P., Lee, J., Liberti, L., Margot, F. and Wächter, A., 2009. Branching and bounds tighteningtechniques for non-convex MINLP. Optimization Methods & Software, 24(4-5), pp.597-634.

[10] Misener, R. and Floudas, C.A., 2013. GloMIQO: Global mixed-integer quadratic optimizer. Journal of Global Optimization, 57(1), pp.3-50.

[11] Lindo Systems Inc.: LINDOGlobal 11.0 (2017).

[12] Achterberg, T., 2009. SCIP: solving constraint integer programs. Mathematical Programming Computation, 1(1), pp.1-41.