×

A simplex based algorithm to solve separated continuous linear programs. (English) Zbl 1165.90011

The author develops a simplex based algorithm to solve separated continuous linear programs (SCLP) of the form
\[ \max \int_0^T \left(\left(\gamma' + (T-t) c'\right) u(t) + d'x(t)\right) dt \]
\[ \text{s.t. } \int_0^t Gu(s)ds + F x(t) \leq \alpha + at \]
\[ Hu(t) \leq b \]
\[ x(t), u(t) \geq 0 \quad t \in [0,T]. \]
A symmetric dual SCLP* is formulated and weak duality and complementary slackness are shown. By construction, as a result of the algorithm, strong duality is proved under feasibility and boundedness assumptions. Under the same assumptions the existence of solutions to SCLP and SCLP* for all \(0<T<\infty\) is shown. Under a nondegeneracy assumption the solution is proved to be unique.
The algorithm is based on the characterization of optimal solutions of SCLP and SCLP* as (finite) sequences of bases which correspond to extreme points of the feasible region. The validity region of a base sequence is shown to be a convex polyhedral cone. This allows the definition of neighboring base sequences (those whose validity regions have boundaries with an intersection containing more than the origin) which describe the iterations of the algorithm.
The algorithm solves SCLP/SCLP* by a sequence of SCLP steps analogous to the parametric self dual simplex method for LP. The author first gives a simplified version of the algorithm with some assumption that he later removes in the general and extended versions.

MSC:

90C05 Linear programming
49N05 Linear optimal control problems
65K05 Numerical mathematical programming methods

Software:

LPbook
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anderson, E.J.: A Continuous Model for Job-Shop Scheduling. Ph. D. Thesis. University of Cambridge, Cambridge (1978)
[2] Anderson, E.J.: A new continuous model for job-shop scheduling. Int. J. Syst. Sci. 12, 1469–1475 (1981) · Zbl 0468.90033 · doi:10.1080/00207728108963831
[3] Anderson, E.J., Nash, P.: Linear Programming in Infinite Dimensional Spaces. Wiley-Interscience, Chichester (1987) · Zbl 0632.90038
[4] Anderson, E.J., Philpott, A.B.: A continuous time network simplex algorithm. Networks 19, 395–425 (1989) · Zbl 0672.90048 · doi:10.1002/net.3230190403
[5] Anderson, E.J., Philpott, A.B.: Erratum, a continuous time network simplex algorithm. Networks 19, 823–827 (1989) · Zbl 0672.90048 · doi:10.1002/net.3230190403
[6] Anderson, E.J., Pullan, M.C.: Purification for separated continuous linear programs. Math. Methods Oper. Res. 43, 9–33 (1996) · Zbl 0842.90078 · doi:10.1007/BF01303432
[7] Anstreicher, K.M.: Generation of feasible descent directions in continuous time linear programming. Technical Report, SOL 83–18, Department of Operations Research, Stanford University, Stanford (1983)
[8] Barvinok, A.: A Course in Convexity American Mathematical Society, Providence (2002)
[9] Bellman, R.: Bottleneck problems and dynamic programming. Proc. Natl. Acad. Sci. 39, 947–951 (1953) · Zbl 0053.27903 · doi:10.1073/pnas.39.9.947
[10] Bellman, R.: Dynamic Programming. Princeton University Press, Princeton (1957) · Zbl 0077.13605
[11] Dantzig, G.B.: Linear Programming and Extensions. Princeton University Press, Princeton (1963) · Zbl 0108.33103
[12] Dorfman, R., Samuelson, P.A., Solow, R.M.: Linear Programming and Economic Analysis. MacGraw Hill, New York (Dover edn, 1987) (1958) · Zbl 0123.37102
[13] Fleischer, L., Sethuraman, J.: Efficient algorithms for separated continuous linear programs: the multicommodity flow problem with holding costs and extensions. Math. Oper. Res. 30, 916–938 (2005) · Zbl 1278.90061 · doi:10.1287/moor.1050.0166
[14] Fleischer, L., Skutella, M.: Quickest flows over time. SIAM J. Comput. 36, 1600–1630 (2007) · Zbl 1146.90014 · doi:10.1137/S0097539703427215
[15] Fukuda, K., Terlaky, T.: Criss cross methods, a fresh view on pivot algorithms. Math. Program. 79, 369–395 (1997) · Zbl 0887.90113
[16] Grinold, R.C.: Symmetric duality for continuous linear programs. SIAM J. Appl. Math. 18, 32–51 (1970) · Zbl 0213.45003 · doi:10.1137/0118011
[17] Hajek, B., Ogier, R.G.: Optimal dynamic routing in communications networks with continuous traffic. Networks 14, 457–487 (1984) · Zbl 0546.90097 · doi:10.1002/net.3230140308
[18] Ito, C., Kelley, T., Sachs, E.W.: Inexact primal dual interior point iteration for linear program in function spaces. Comput. Optim. Appl. 4, 189–202 (1995) · Zbl 0827.49019 · doi:10.1007/BF01300870
[19] Koopmans, T.C. (ed.) in Cooperation with Alchien, A., Dantzig, G.B., Georgescu-Roegen, N., Samuelson, P.A., Tucker, A.W. Activity Analysis of Production and Allocation. Wiley/Chapman and Hall, New York/London (1951)
[20] Leontief, W.W.: The Structure of the American Economy, 1919–1929 Harvard University Press, Cambridge (new, enlarged edition, Oxford University Press, New York, 1951) (1941)
[21] Luo, X., Bertsimas, D.: A new algorithm for state constrained separated continuous linear programs. SIAM J. Control Optim. 37, 177–210 (1998) · Zbl 0921.49023 · doi:10.1137/S0363012995292664
[22] Nazarathy, Y., Weiss, G.: Near optimal control of queueing networks over a finite time horizon Annals of Operations Research (to appear) (2007)
[23] Perold, A.F.: Fundamentals of a continuous time simplex method. Technical Report, SOL 78-26, Department of Operations Research, Stanford University, Stanford (1978) · Zbl 0389.90077
[24] Perold, A.F.: Extreme points and basic feasible solutions in continuous time linear programming. SIAM J. Control Optim. 19, 52–63 (1981) · Zbl 0488.49019 · doi:10.1137/0319005
[25] Philpott, A.B., Craddock, M.: An adaptive discretization algorithm for a class of continuous network programs. Networks 26, 1–11 (1995) · Zbl 0840.90064 · doi:10.1002/net.3230260102
[26] Pullan, M.C.: An algorithm for a class of continuous linear programs. SIAM J. Control Optim. 31, 1558–1577 (1993) · Zbl 0833.90124 · doi:10.1137/0331073
[27] Pullan, M.C.: Forms of optimal solutions for separated continuous linear programs. SIAM J. Control Optim. 33, 1952–1977 (1995) · Zbl 0861.49027 · doi:10.1137/S0363012993247858
[28] Pullan, M.C.: A duality theory for separated continuous linear programs. SIAM J. Control Optim. 34, 931–965 (1996) · Zbl 0847.49028 · doi:10.1137/S0363012993257507
[29] Pullan, M.C.: Existence and duality theory for separated continuous linear programs. Math. Model. Syst. 3, 219–245 (1997) · Zbl 0886.90100
[30] Pullan, M.C.: Convergence of a general class of algorithms for separated continuous linear programs. SIAM J. Optim. 10, 722–731 (2000) · Zbl 0963.90040 · doi:10.1137/S1052623494278827
[31] Pullan, M.C.: An extended algorithm for separated continuous linear programs. Math. Program. 93, 415–451 (2002) · Zbl 1023.90040 · doi:10.1007/s10107-002-0307-0
[32] Shapiro, A.: On duality theory of conic linear problems. In: Goberna, M.A., Lopez , M.A.(eds) Semi-Infinite Programming, Chap. 7., pp. 135–165. Kluwer, Netherlands (2001) · Zbl 1055.90088
[33] Vanderbei, R.J: Linear Programming, Foundations and Extensions. Kluwer, Boston, 2nd edn. 2001 (1997)
[34] Weiss, G.: On optimal draining of fluid re-entrant lines. In: Kelly, F.P., Williams, R.(eds) Stochastic Networks, IMA Volumes in Mathematics and its Applications, pp. 93–105. Springer, New York (1995) · Zbl 0823.60084
[35] Weiss, G.: Scheduling and control of manufacturing systems–a fluid approach Proceedings of the 37 Allerton Conference, pp. 577–586, 21–24 September, 1999, Monticello (1999)
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.