Extreme Strong Branching for QCQPs

Santanu S. Dey, Dahye Han, Yang Wang · 2025

Read Extreme Strong Branching for QCQPs by Santanu S. Dey, Dahye Han, Yang Wang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-20650.txt.

Introduction

Santanu S Dey, Dahye Han, and Yang Wang extend a strong branching method from whole number problems to problems with squared terms and squared limits. Branching means testing a choice, solving relaxed versions of the task, and keeping the split that improves the goal value most.

For a binary choice the split point is fixed, but for a smooth value someone must also pick where to split, and past methods fixed that point in advance. The new rule tests several split points per value and picks the value and point together, gaining tighter bounds as a side benefit. On some squared problems, tests show the rule beats leading paid solvers, a notable result for hard design and planning tasks.

Catalog record

CREATORSantanu S. Dey, Dahye Han, Yang Wang
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE31 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-20650

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Extreme Strong Branching for QCQPs Santanu S. Dey, Dahye Han, Yang Wang Abstract For mixed-integer programs (MIPs), strong branching is a highly effective variable selection method to reduce the number of nodes in the branch-and-bound algorithm. Extending it to nonlinear problems is conceptually simple but practically limited. Branching on a binary variable fixes the variable to 0 or 1, whereas branching on a continuous variable requires an additional decision to choose a branching point. Previous extensions of strong branching predefine this point and then solve 2 ​ n 2n relaxations where n n is the number of candidate variables to branch. We propose extreme strong branching , which evaluates multiple branching points per variable and jointly selects both the branching variable and point based on the objective value improvement. This approach resembles the success of strong branching for MIPs while additionally exploiting bound tightening as a byproduct. For certain types of quadratically constrained quadratic programs (QCQPs), computational experiments show that the extreme strong branching rule outperforms existing commercial solvers. 1 Introduction The strong branching technique has been recognized as one of the most effective variable selection rules in the branch-and-bound algorithm for solving mixed-integer programs (MIPs) since its introduction [ 2 ] ; see also [ 1 , 7 ] . The method evaluates every fractional variable as a candidate variable to branch by fixing the candidate variable to either 0 or 1, solving relaxations at two child nodes, and evaluating the corresponding improvements in the objective function. The final branching variable is selected based on a composite score that combines the improvements from both branched child nodes, often measured by the product of the two gains in the child nodes. Our work investigates whether the success of strong branching can be extended beyond binary variables. Although the extension to continuous variables is conceptually straightforward, its practical applicability remains limited and challenging. Unlike the case of branching on binary variables in MIP, branching on a continuous variable, known as spatial branching [ 20 ] , requires an additional decision on the branching point. Recent advances in spatial branch-and-bound have introduced algorithmic strategies to address the fundamental challenges of variable and branching point selections. Violation transfer rule was proposed in [ 21 ] , which systematically addresses constraint violations through strategic variable selection. The author of [ 16 ] developed a geometric approach that partitions the feasible region into triangles and rectangles, enabling finer spatial decomposition and convexification. Authors of [ 6 ] designed a specialized branching strategy for quadratically constrained quadratic programs (QCQPs) involving complex variables, addressing the unique difficulties in complex optimization domains. For bilinear problems, a branching rule that balances the violations across two child nodes was suggested in [ 10 ] , while specifically for bilinear bipartite programs (BBPs), authors of [ 9 ] designed a branching rule that leverages second-order cone programming (SOCP) relaxations to guide variable selection decisions. More recently, a branching rule tailored for nonconvex separable piecewise linear functions was proposed in [ 13 ] . In addition, several works have adapted the strong branching technique from MIP to spatial branch-and-bound. One such variant is introduced in [ 4 ] , in which a branching point is defined as a convex combination of the relaxed solution and the midpoint of a variable’s bound, followed by solving 2n relaxations where n is the number of candidate variables to evaluate the improvement associated with the preselected branching point for each variable. In [ 14 ] , the authors proposed a learning-based approach to estimate both the branching point and branching variable expected to yield the largest improvement. Our proposed approach performs an exhaustive search for a branching point for each variable using binary search while leveraging the bound-tightening technique during this process. This approach has two main benefits: 1. Bound tightening is performed as part of the branching process. Although this resembles the spirit of the feasibility-based bound tightening or optimality-based bound tightening implemented in modern global solvers [ 4 , 23 ] , one key distinction is that the bound reduction here arises directly from evaluating candidate branching points and thus is a byproduct of the branching process rather than a separate preprocessing or postprocessing step. 2. Since the extreme strong branching rule considers improvement in the objective function value, it resembles closely the objective-driven rationale that makes strong branching effective in MIP. The binary search restricts the number of evaluated points, providing an efficient trade-off between the computational search effort and improvement evaluation. 2 Extreme strong branching algorithm We consider a general nonlinear programming (NLP) of the form \min\{c^{\top}x\ |\ x\in P\} . For simplicity of presentation, we have considered a linear objective here, but the method holds for nonconvex objective functions as well. Within a branch-and-bound tree, a subproblem at node k is given by: \displaystyle\min \displaystyle c^{\top}x (1) \displaystyle s.t. \displaystyle x\in P_{k} where P_{k} denotes the feasible region defined by the branching decisions taken along the path to node k . To obtain a dual bound of the problem, we consider R_{k} , a convex relaxation of P_{k} . For a branching decision on variable x_{i} at threshold \alpha , we denote by: R_{k}(x_{i}\leq\alpha)\ \ \text{and}\ \ R_{k}(x_{i}\geq\alpha), the convex relaxation of P_{k}\cap\{x_{i}\leq\alpha\} and P_{k}\cap\{x_{i}\geq\alpha\} , respectively. Our proposed branching algorithm is provided in Algorithm 1 with two subroutines. The main algorithm is based on binary search. During the search, we may obtain a bound reduction. Finally, to choose the best branching variable and branching point combination, we compute branching scores. Each element is detailed in the following sections. 2.1 Binary search To identify the optimal branching threshold \alpha for variable x_{i} , we employ a binary search over the interval defined by the current variable bounds [\overline{lb}_{i},\overline{ub}_{i}] for a fixed number of iterations. First, let us focus on the left child node problem corresponding to solving a relaxed subproblem of the form: \displaystyle obj_{L}(\alpha)=\min\{c^{\top}x\ |\ x\in R_{k}(x_{i}\leq\alpha)\}. Since the feasible region R_{k}(x_{i}\leq\alpha) expands as \alpha increases, obj_{L}(\alpha) is a monotonically non-increasing function of \alpha . The first iteration begins with \alpha=(\overline{lb}_{i}+\overline{ub}_{i})/2 . If the subproblem at this \alpha is feasible and the optimal objective function value obj_{L}(\alpha) does not exceed the tree’s best incumbent objective value (i.e., the tree’s upper bound), then obj_{L}(\alpha) is recorded and \alpha is a candidate for branching. The search continues to the left for a smaller \alpha . On the other hand, if the subproblem is infeasible or obj_{L}(\alpha) is greater than the tree’s upper bound, the search direction is reversed to the right for a larger \alpha . We note that in this case, the lower bound of x_{i} can be updated as further discussed in Section 2.2 . This binary search is done until the binary search iteration limit. The same binary search procedure is then applied symmetrically to the right child node corresponding to solving a relaxed subproblem of the form obj_{R}(\alpha)=\min\{c^{\top}x\ |\ x\in R_{k}(x_{i}\leq\alpha)\} . We note that obj_{R}(\alpha) is now a monotonically non-decreasing function in \alpha . After completing the binary search on both the left and right sides, we have a set of candidate branching points corresponding to different \alpha values evaluated in both left and right directions. If

Read the complete text