Method of Hill Tunneling via Weighted Simplex Centroid for Continuous Piecewise Linear Programming

This paper works on a heuristic algorithm with determinacy for the global optimization of Continuous PieceWise Linear (CPWL) programming. The widely applied CPWL programming can be equivalently transformed into D.C. programming and concave optimization over a polyhedron. Considering that the super-level sets of concave piecewise linear functions are polyhedra, we propose the Hill Tunneling via Weighted Simplex Centroid (HTWSC) algorithm, which can escape a local optimum to reach the other side of its contour surface by cutting across the super-level set. The searching path for hill tunneling is established via the weighted centroid of a constructed simplex. In the numerical experiments, different weighting methods are studied first, and the best is chosen for the proposed HTWSC algorithm. Then, the HTWSC algorithm is compared with the hill detouring method and the software CPLEX for the equivalent mixed integer programming, with results indicating its superior performance in terms of numerical efficiency and the global search capability.