Nonconvex separable piecewise-linear functions (PLFs) are widespread in Operations Research due to their frequent appearance in applications and their use to approximate nonlinearitites. Commonly, nonconvex PLFs are approached from the perspective of discrete optimisation, using special ordered sets and mixed integer linear programs (MILPs). In contrast, we take the viewpoint of global continuous optimization and present a spatial branch-and-bound algorithm (sBB). It offers (i) slim and sparse linear programming relaxations, (ii) sharpness throughout the search tree and (iii) an increased flexibility in branching decisions. We present convergence results demonstrating finiteness of the sBB in case of continuous PLFs and convergence in the limit in case of general discontinuous PLFs. The sBB algorithm is implemented in Python and compared with logarithmic MILP formulations solved by Gurobi. Tests on knapsack and network flow problems indicate significant performance gains up to an order of magnitude for medium- to large-sized PLFs.
Article
View Spatial branch-and-bound for non-convex separable piecewise-linear optimization