Article Title
Method of Hill Tunneling via Weighted Simplex Centroid for Continuous Piecewise Linear Programming
Keywords
global optimization, piecewise linear, concave minimization, cutting plane method, hill tunneling
Abstract
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.
Publisher
Tsinghua University Press
Recommended Citation
Zhiming Xu, Yu Bai, Kuangyu Liu et al. Method of Hill Tunneling via Weighted Simplex Centroid for Continuous Piecewise Linear Programming. Tsinghua Science and Technology 2019, 24(03): 301-316.
