Piecewise-linear programming: The compact (CPLP) algorithm.(English)Zbl 0617.90070
A compact algorithm is presented for solving the convex piecewise-linear programming problem, formulated by means of a separable convex piecewise- linear objective function (to be minimized) and a set of linear constraints. This algorithm consists of a finite sequence of cycles, derived from the simplex method, characteristic of linear programming, and the line search, characteristic of nonlinear programming. Both the required storage and amount of calculation are reduced with respect to the usual approach, based on a linear-programming formulation with an expanded tableau. The tableau dimensions are \(m\times (n+1)\), where m is the number of constraints and n the number of the (original) structural variables, and they do not increase with the number of breakpoints of the piecewise-linear terms constituting the objective function.
MSC:
| 90C25 | Convex programming |
| 90C05 | Linear programming |
| 65K05 | Numerical mathematical programming methods |
Keywords:
degeneracy;compact algorithm;convex piecewise-linear programming;linear constraints;simplex method;line searchCite
Full Text:DOI
References:
| [1] | N.N. Abdelmalek, ”An efficient method for the discrete linearL 1 approximation problem,”Mathematics of Computation 29 (1975) 844–850. ·Zbl 0307.65052 |
| [2] | J. Barrodale and F.D.K. Roberts, ”An improved algorithm for discretel 1 linear approximation,”SIAM Journal on Numerical Analysis 10 (1973) 839–848. ·Zbl 0266.65016 ·doi:10.1137/0710069 |
| [3] | R.H. Bartels, A.R. Conn and J.W. Sinclair, ”Minimization techniques for piecewise differentiable functions: thel 1 solution to an overdetermined linear system”,SIAM Journal on Numerical Analysis 15 (1978) 224–241. ·Zbl 0376.65018 ·doi:10.1137/0715015 |
| [4] | A. Bobbio and A. Premoli, ”A nonlinear integer algorithm for optimal reliability allocation,”Proceedings of the 1980 IEEE International Conference on Circuits and Computers (Port Chester, NY, October 1–3, 1980) pp. 1142–1145. |
| [5] | A. Charnes and W.W. Cooper,Management Models and Industrial Applications of Linear Programming, (John Wiley & Sons, New York, 1961). ·Zbl 0107.37004 |
| [6] | A.R. Conn. ”Linear programming via a nondifferentiable penalty function,”SIAM Journal on Numerical Analysis 13 (1976) 145–154. ·Zbl 0333.90029 ·doi:10.1137/0713016 |
| [7] | G.B. DantzigLinear Programming and Extensions (Princeton University Press, Princeton, NJ, 1963). |
| [8] | M. Davies, ”Linear approximation usign the criterion of least total deviations”,Journal of the Royal Statistical Society (Series B) 29 (1967) 101–109. |
| [9] | R. Fourer, ”Notes on semi-linear programming,” Draft report, Department of Industrial Engineering and Management Science, Northwestern University (Evanston, IL, 1981). ·Zbl 0538.90051 |
| [10] | R. Fourer, ”Piecewise-linear programming,” Draft report, Department of Industrial Engineering and Management Science, Northwestern University (Evanston, IL, 1983). ·Zbl 0506.90054 |
| [11] | R. Fourer, ”A simplex algorithm for piecewise-linear programming, I: Derivation and proof,”Mathematical Programming 33 (1985) 204–233. ·Zbl 0579.90084 ·doi:10.1007/BF01582246 |
| [12] | R. Fourer, ”A simplex algorithm for piecewise-linear programming, II: Finiteness, feasibility, and degeneracy,” Technical Report 85-03, Department of Industrial Engineering and Management Sciences, Northwestern University, (Evanston, IL, 1985). ·Zbl 0579.90084 |
| [13] | E.G. Goldstein, ”A certain class of nonlinear extremum problems,”Doklady Akademii nauk SSSR 133; translated inSoviet Mathematics, 1 (1960) 863–866. ·Zbl 0171.18103 |
| [14] | J.K. Ho, ”Relationships among linear formulation of separatble convex piecewise linear programs,”Mathematical Programming Studies 24 (1985) 121–140. ·Zbl 0581.90070 |
| [15] | B.A. Murtagh,Advanced Linear Programming (McGraw-Hill, New York, 1981). ·Zbl 0525.90062 |
| [16] | A. Orden and V. Nalbandian, ”A bidirectional simplex algorithm,”Journal of the Association for Computing Machinery 15 (1968) 221–235. |
| [17] | R.T. Rockafellar, ”Monotropic programming: descent algorithms and duality,” in O.L. Mangasarian, R.R. Meyer and S.M. Robinson eds.,Nonlinear Programming 4 (Academic Press, New York, 1981) pp. 327–366. ·Zbl 0537.49016 |
| [18] | R.T. Rockafellar,Network Flows and Monotropic Optimization (Wiley-Interscience, New York, 1984). ·Zbl 0596.90055 |
| [19] | H.M. Salkin,Integer Programming (Addison-Wesley, Reading, MA, 1975). |
| [20] | R.D. Snyder, ”Programming with piecewise linear objective functions,” Working Paper 9/81, Department of Econometrics and Operations Research, Monash University (Clayton, Victoria, Australia, 1981). |
| [21] | R.D. Snyder, ”Linear programming with special ordered sets,”Journal of the Operational Research Society 35 (1984) 69–74. ·Zbl 0526.90071 |
| [22] | K. Spyropoulos, E. Kiountouzis, and A. Young, ”Discrete approximation in theL I norm,”The Computer Journal 16 (1973) 180–186. ·Zbl 0257.65015 ·doi:10.1093/comjnl/16.2.180 |
| [23] | H.M. Wagner,Principles of Operations Research (Prentice-Hall, Englewood Cliffs, NJ, 1969). ·Zbl 0193.18402 |
| [24] | P. Wolfe, ”The composite simplex algorithm,”SIAM Review 7 (1965) 42–54. ·Zbl 0133.42703 ·doi:10.1137/1007004 |
| [25] | S. Zionts,Linear and Integer Programming (Prentice-Hall, Englewood Cliffs, NJ, 1974). |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
