Article ID: | iaor201111479 |
Volume: | 39 |
Issue: | 7 |
Start Page Number: | 1763 |
End Page Number: | 1770 |
Publication Date: | Jul 2012 |
Journal: | Computers and Operations Research |
Authors: | Wang Shuning, Huang Xiaolin, Xu Jun, Mu Xiaomu |
Keywords: | programming: nonlinear, heuristics, graphs |
This paper studies the problem of minimizing hinging hyperplanes (HH) which is a widely applied nonlinear model. To deal with HH minimization, we transform it into a d.c. (difference of convex functions) programming and a concave minimization on a polyhedron, then some mature techniques are applicable. More importantly, HH is a continuous piecewise linear function and for concave HH, the super‐level sets are polyhedra. Inspired by this property, we establish a method which searches on the counter map in order to escape a local optimum. Intuitively, this method bypasses the super‐level set and is hence called hill detouring method, following the name of hill climbing. In numerical experiments, the proposed algorithm is compared with CPLEX and a heuristic algorithm showing its effectiveness.