In the branch-and-bound algorithm, branching is the key step to deal with the nonconvexity of the problem. For Mixed Integer Linear Optimization (MILO) problems and, in general, Mixed Integer Nonlinear Optimization (MINLO) problems whose continuous relaxation is convex, branching on integer and binary variables suffices, because fixing all integer variables yields a convex relaxation. General, nonconvex MINLO problems, on the other hand, require spatial branching, i.e., branching on continuous variables.
While spatial branching could be seen as necessary for the general MINLO class only, we show that when the branching point is carefully chosen, spatial branching can be more effective than its integer counterpart for a special class of problems arising from Support Vector Machines with Ramp Loss (SVMRL), which can be modeled as mixed integer problems with linear constraints and a convex quadratic objective. We present a strong spatial branching approach for SVMRL coupled with a procedure to strengthen the continuous relaxation, then report on computational tests on known instances from the literature where our approach yields a significant improvement in solve time.
Article
View Spatial branching for a special class of convex MIQO problems