Alternative branching rules for some nonconvex problems

作者：Locatelli M^*

来源：Optimization Methods and Software, 2015, 30(2): 365-378.

DOI：10.1080/10556788.2014.885521

• branch-and-bound
• branching rules
• envelopes
• sum of affine products
• sum of affine ratios

Following Linderoth (A simplicial branch-and-bound algorithm for solving quadratically constrained quadratic programs, Math. Program. 103 (2005), pp. 251-282), in this paper we show how a preliminary theoretical analysis about the quality of convex and concave envelopes over different regions may suggest branching rules alternative to the traditional ones based on boxes. For two nonconvex problems (minimization of the sum of products of affine functions and maximization of the sum of ratios of affine functions, in both cases over polytopes), we show how the indications of the theoretical analysis lead to computational results which confirm the superiority of the alternative branching rules with respect to those based on boxes.

• 出版日期2015