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

Zhiming Xu; Yu Bai; Kuangyu Liu; Shuning Wang

doi:10.26599/TST.2018.9010089

Tsinghua Science and Technology 2019, 24(3): 301-316 https://doi.org/10.26599/TST.2018.9010089

Open Access | Issue | Published: 24 January 2019

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

Show Author's Information Hide Author's Information 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.

Keywords:

global optimization, piecewise linear, concave minimization, cutting plane method, hill tunneling

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

Download citation

EndNote(RIS)

BibTeX

431

Views

Downloads

Citations

Crossref

N/A

WoS

Scopus

CSCD

Abstract Full text About this article

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.

Full text

Abstract

Full text

Outline

About this article

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

Show Author's information Hide Author's Information 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.

Abstract

Keywords: global optimization, piecewise linear, concave minimization, cutting plane method, hill tunneling

References(23)

[1]

Breiman L., Hinging hyperplanes for regression, classification and function approximation, IEEE Transactions on Information Theory, vol. 39, no. 3, pp. 999-1013, 1993.

DOI 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.

DOI 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.

DOI 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.

DOI Google Scholar

[7]

Wagner H. M., Principles of operations research, Operational Research Quarterly, vol. 21, no. 4, 1970.

DOI Google Scholar

[8]

Dantzig G. B., Recent advances in linear programming, Management Science, vol. 2, no. 2, pp. 131-144, 1956.

DOI Google Scholar

[9]

Ho J. K., Relationships among Linear Formulations of Separable Convex Piecewise Linear Programs. Springer, pp. 126–140, 1985.

DOI

[10]

Fourer R., A simplex algorithm for piecewise-linear programming I: Derivation and proof, Mathematical Programming, vol. 33, no. 2, pp. 204-233, 1985.

DOI 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.

DOI 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.

DOI 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.

DOI 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.

DOI 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.

DOI 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.

DOI 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.

DOI

[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.

DOI 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.

DOI 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.

DOI Google Scholar

[21]

Horst R. and Tuy H., Global Optimization: Deterministic Approaches. Springer Science & Business Media, 1996.

DOI

[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.

DOI 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.

DOI Google Scholar

About this article

Publication history

Acknowledgements

Rights and permissions

Publication history

Received: 22 November 2017

Accepted: 22 February 2018

Published: 24 January 2019

Issue date: June 2019

Copyright

Acknowledgements

This project was jointly supported by the National Key Basic Research and Development (973) Program of China (No. 2012CB720505) and the National Natural Science Foundation of China (Nos. 61473165 and 61134012).