Method of hill tunneling via 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. CPWL is widely applied since it can be equivalently transformed into D.C. programming, and further, concave optimization over a polyhedron. Considering that the super-level sets of concave piecewise linear functions are polyhedra, we propose the hill tunneling via simplex centroid (HTSC) algorithm, which is able to escape a local optimum to the other side of its contour surface by cutting across the super-level set. The searching path for the hill tunneling is established by using the centroid of a constructed simplex. In the numerical experiments, the proposed HTSC algorithm is compared with CPLEX and the hill detouring (HD) method, which shows its superior performance on the numerical efficiency and the global search capability.