AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (5 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

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

Zhiming Xu, Yu Bai, Kuangyu Liu, Shuning Wang( )
National Laboratory for Information Science and Technology, Department of Automation, Tsinghua University, Beijing 100084, China.
Faculty of Air Force Engineering University, Xi’an 710051, China.
Show Author Information

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.

Keywords

global optimizationpiecewise linearconcave minimizationcutting plane methodhill tunneling

References

[1]
Breiman L., Hinging hyperplanes for regression, classification and function approximation, IEEE Transactions on Information Theory, vol. 39, no. 3, pp. 999-1013, 1993.
Crossref Google Scholar
[2]
Dantzig G., Johnson S., White W., and Science M., A linear programming approach to the chemical equilibrium problem, Management Science, vol. 5, no. 1, pp. 38-43, 1958.
Crossref Google Scholar
[3]
Zionts S., Linear and Integer Programming. Prentice Hall, 1974.
[4]
Dantzig G. B., Linear Programming and Extensions. Princeton University Press, 1963.
[5]
Charnes A. and Cooper W. W., Management models and industrial applications of linear programming, Management Science, vol. 4, no. 1, pp. 38-91, 1957.
Crossref Google Scholar
[6]
Charnes A. and Lemke C. E., Minimization of nonlinear separable convex functionals, Naval Research Logistics Quarterly, vol. 1, no. 4, pp. 301-312, 1954.
Crossref Google Scholar
[7]
Wagner H. M., Principles of operations research, Operational Research Quarterly, vol. 21, no. 4, 1970.
Crossref Google Scholar
[8]
Dantzig G. B., Recent advances in linear programming, Management Science, vol. 2, no. 2, pp. 131-144, 1956.
Crossref Google Scholar
[9]
Ho J. K., Relationships among Linear Formulations of Separable Convex Piecewise Linear Programs. Springer, pp. 126–140, 1985.
Crossref
[10]
Fourer R., A simplex algorithm for piecewise-linear programming I: Derivation and proof, Mathematical Programming, vol. 33, no. 2, pp. 204-233, 1985.
Crossref Google Scholar
[11]
Fourer R., A simplex algorithm for piecewise-linear programming II: Finiteness, feasibility and degeneracy, Mathematical Programming, vol. 41, nos. 1–3, pp. 281-315, 1988.
Crossref Google Scholar
[12]
Fourer R., A simplex algorithm for piecewise-linear programming III: Computational analysis and applications, Mathematical Programming, vol. 53, nos. 1–3, pp. 213-235, 1992.
Crossref Google Scholar
[13]
Keha A. B., de Farias I. R., and Nemhauser G. L., A branch-and-cut algorithm without binary variables for nonconvex piecewise linear optimization, Operations Research, vol. 54, no. 5, pp. 847-858, 2006.
Crossref Google Scholar
[14]
Gendron B., Croxton K. L., and Magnanti T. L., A comparison of mixed-integer programming models for nonconvex piecewise linear cost minimization problems, Management Science, vol. 49, no. 9, pp. 1268-1273, 2003.
Crossref Google Scholar
[15]
Vielma J. P., Ahmed S., and Nemhauser G., Mixed-integer models for nonseparable piecewise linear optimization: Unifying framework and extensions, Operations Research, vol. 58, no. 2, pp. 303-315, 2010.
Crossref Google Scholar
[16]
Keha A. B., Ismael J. A. G. L., and De Farias R., Models for representing piecewise linear cost functions, Operations Research Letters, vol. 32, no. 1, pp. 44-48, 2004.
Crossref Google Scholar
[17]
Xi X., Xu J., Mu X., and Wang S., Continuous piecewise linear programming via concave optimization and genetic algorithm, in Proc. Decision and Control (CDC), 2012 IEEE 51st Annual Conference on, Osaka, Japan, 2012, pp. 2509-2514.
Crossref
[18]
Huang X., Xu J., Mu X., and Wang S., The hill detouring method for minimizing hinging hyperplanes functions, Computers & Operations Research, vol. 39, no. 7, pp. 1763-1770, 2012.
Crossref Google Scholar
[19]
Huang X., Xu J., and Wang S., Exact penalty and optimality condition for nonseparable continuous piecewise linear programming, Journal of Optimization Theory and Applications, vol. 155, no. 1, pp. 145-164, 2012.
Crossref Google Scholar
[20]
Wang S. and Sun X., Generalization of hinging hyperplanes, IEEE Transactions on Information Theory, vol. 51, no. 12, pp. 4425-4431, 2005.
Crossref Google Scholar
[21]
Horst R. and Tuy H., Global Optimization: Deterministic Approaches. Springer Science & Business Media, 1996.
Crossref
[22]
Bagirov A. M., Jin L., Karmitsa N., Al Nuaimat A., and Sultanova N., Subgradient method for nonconvex nonsmooth optimization, Journal of Optimization Theory and Applications, vol. 157, no. 2, pp. 416-435, 2013.
Crossref Google Scholar
[23]
Dolan E. D. and More J. J., Benchmarking optimization software with performance profiles, Mathematical Programming, Series B, vol. 91, no. 2, pp. 201-213, 2002.
Crossref Google Scholar
Tsinghua Science and Technology
Volume 24 Issue 3,
June 2019
Pages 301-316
DOI: 10.26599/TST.2018.9010089
Cite this article:
Xu Z, Bai Y, Liu K, et al. Method of Hill Tunneling via Weighted Simplex Centroid for Continuous Piecewise Linear Programming. Tsinghua Science and Technology, 2019, 24(3): 301-316. https://doi.org/10.26599/TST.2018.9010089

590

Views

16

Downloads

1

Crossref

N/A

Web of Science

0

Scopus

0

CSCD

Altmetrics
Received: 22 November 2017
Accepted: 22 February 2018
Published: 24 January 2019
© The author(s) 2019
Return