An Approximation Algorithm for Solving Generalized Separated Continuous Conic Programming

Abstract:

In this paper, we study the algorithm for solving a kind of new problem called generalized separated continuous conic programming (GSCCP), which has great modeling power. Based on the relationships between GSCCP and its discretization, GSCCP and its dual, we proposed an approximation algorithm which can produce a feasible solution for GSCCP with prescribed precision. We also present a numerical example to illustrate the efficiency of this algorithm. To our knowledge, this is the first algorithm for solving GSCCP so far.

• Periodical: Advanced Materials Research (Volumes 452-453)
• Pages: 1127-1132
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.452-453.1127
• Online since: January 2012
• Authors: Xiao Qing Wang
• Keywords: Approximation Algorithm, Continuous Conic Programming, Strong Duality

References

[1] E.J. Anderson: A Continuous Model for Job-Shop Scheduling. PhD. Thesis, University of Cambridge, Cambridge, U.K.,(1978).

[2] E.J. Anderson, P. Nash, and A. F. Perold: Some properties of a class of continuous linear programs, SIAM J. Control Optim., vol.21, (1983), pp.258-265.

DOI: 10.1137/0321046

[3] E.J. Anderson, A.B. Philpott: A continuous-time network simplex algorithm, Networks, vol.19, (1989), pp.395-425.

DOI: 10.1002/net.3230190403

[4] L. Fleischer and J. Sethuraman: Efficient algorithms for separated continuous linear programs: the multi-commodity flow problem with holding costs and extensions, Math. Oper. Res., vol. 30,(2005), pp.916-938.

DOI: 10.1287/moor.1050.0166

[5] X. Luo and D. Bertsimas: A new algorithm for state-constrained separated continuous linear programs, SIAM J. Control Optim., vol.37, (1998), pp.177-210.

DOI: 10.1137/s0363012995292664

[6] M.C. Pullan: An algorithm for a class of continuous linear programs, SIAM J. Control Optim., vol. 31, (1993), pp.1558-1577.

DOI: 10.1137/0331073

[7] M.C. Pullan: Forms of optimal solutions for separated continuous linear programs, SIAM J. Control Optim., vol.33, (1995), pp.1952-1977.

DOI: 10.1137/s0363012993247858

[8] M.C. Pullan: A duality theory for separated continuous linear programs, SIAM J. Control Optim., vol.34, (1996), pp.931-965.

DOI: 10.1137/s0363012993257507

[9] M.C. Pullan: Linear optimal control problems with piecewise analytic solutions, J. Math. Anal. Appl., vol.197, (1996),pp.207-226.

DOI: 10.1006/jmaa.1996.0016

[10] M.C. Pullan: A study of general dynamic network programs with arc time-delays, SIAM J. Optim., vol.7, (1997), pp.889-912.

DOI: 10.1137/s1052623495288180

[11] M.C. Pullan: Convergence of a general class of algorithms for separated continuous linear programs, SIAM J. Optim., vol.10, (2000), pp.722-731.

DOI: 10.1137/s1052623494278827

[12] M.C. Pullan: An extended algorithm for separated continuous linear programs, Math. Program., vol.93, (2002), pp.415-451.

DOI: 10.1007/s10107-002-0307-0

[13] X. Wang: The Duality Theory for Generalized Separated Continuous Conic Programming, submitted.

[14] G. Weiss: A simplex based algorithm to solve separated continuous linear programs, Math. Program., vol.115, (2008), pp.151-198.

DOI: 10.1007/s10107-008-0217-x