Advanced Search
MyIDEAS: Login to save this article or follow this journal

Computing Block-Angular Karmarkar Projections with Applications to Stochastic Programming

Contents:

Author Info

  • John R. Birge

    (Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, Michigan 48109)

  • Liqun Qi

    (Department of Industrial Engineering, University of Wisconsin, Madison, Wisconsin 53706)

Abstract

We present a variant of Karmarkar's algorithm for block-angular structured linear programs, such as stochastic linear programs. By computing the projection efficiently, we give a worst-case bound on the order of the running time that can be an order of magnitude better than that of Karmarkar's standard algorithm. Further implications for approximations and very large-scale problems are given.

Download Info

If you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
File URL: http://dx.doi.org/10.1287/mnsc.34.12.1472
Download Restriction: no

Bibliographic Info

Article provided by INFORMS in its journal Management Science.

Volume (Year): 34 (1988)
Issue (Month): 12 (December)
Pages: 1472-1479

as in new window
Handle: RePEc:inm:ormnsc:v:34:y:1988:i:12:p:1472-1479

Contact details of provider:
Postal: 7240 Parkway Drive, Suite 300, Hanover, MD 21076 USA
Phone: +1-443-757-3500
Fax: 443-757-3515
Email:
Web page: http://www.informs.org/
More information through EDIRC

Related research

Keywords: linear programming; stochastic programming; Karmarkar method;

References

No references listed on IDEAS
You can help add them by filling out this form.

Citations

Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
as in new window

Cited by:
  1. Berkelaar, A.B. & Dert, C.L. & Oldenkamp, K.P.B. & Zhang, S., 1999. "A primal-dual decomposition based interior point approach to two-stage stochastic linear programming," Econometric Institute Research Papers EI 9918-/A, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
  2. Berkelaar, Arjan & Dert, Cees & Oldenkamp, Bart, 1999. "A primal-dual decompsition-based interior point approach to two-stage stochastic linear programming," Serie Research Memoranda 0026, VU University Amsterdam, Faculty of Economics, Business Administration and Econometrics.
  3. Meszaros, Csaba, 1997. "The augmented system variant of IPMs in two-stage stochastic linear programming computation," European Journal of Operational Research, Elsevier, vol. 101(2), pages 317-327, September.
  4. Gondzio, Jacek, 2012. "Interior point methods 25 years later," European Journal of Operational Research, Elsevier, vol. 218(3), pages 587-601.
  5. Gondzio, J. & Sarkissian, R. & Vial, J.-P., 1997. "Using an interior point method for the master problem in a decomposition approach," European Journal of Operational Research, Elsevier, vol. 101(3), pages 577-587, September.
  6. J. Gondzio, 1994. "Preconditioned Conjugate Gradients in an Interior Point Method for Two-stage Stochastic Programming," Working Papers wp94130, International Institute for Applied Systems Analysis.
  7. Kouwenberg, Roy, 2001. "Scenario generation and stochastic programming models for asset liability management," European Journal of Operational Research, Elsevier, vol. 134(2), pages 279-292, October.
  8. Bocanegra, Silvana & Castro, Jordi & Oliveira, Aurelio R.L., 2013. "Improving an interior-point approach for large block-angular problems by hybrid preconditioners," European Journal of Operational Research, Elsevier, vol. 231(2), pages 263-273.
  9. A. Ruszczynski, 1993. "Interior Point Methods in Stochastic Programming," Working Papers wp93008, International Institute for Applied Systems Analysis.
  10. Vladimirou, Hercules, 1998. "Computational assessment of distributed decomposition methods for stochastic linear programs," European Journal of Operational Research, Elsevier, vol. 108(3), pages 653-670, August.
  11. Diana Barro & Elio Canestrelli, 2005. "Time and nodal decomposition with implicit non-anticipativity constraints in dynamic portfolio optimization," GE, Growth, Math methods 0510011, EconWPA.
  12. Mulvey, John M. & Rosenbaum, Daniel P. & Shetty, Bala, 1997. "Strategic financial risk management and operations research," European Journal of Operational Research, Elsevier, vol. 97(1), pages 1-16, February.
  13. Zhang, S., 2002. "An interior-point and decomposition approach to multiple stage stochastic programming," Econometric Institute Research Papers EI 2002-35, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.
  14. Jacek Gondzio & Andreas Grothey, 2009. "Exploiting structure in parallel implementation of interior point methods for optimization," Computational Management Science, Springer, vol. 6(2), pages 135-160, May.
  15. Cosmin Petra & Mihai Anitescu, 2012. "A preconditioning technique for Schur complement systems arising in stochastic optimization," Computational Optimization and Applications, Springer, vol. 52(2), pages 315-344, June.

Lists

This item is not listed on Wikipedia, on a reading list or among the top items on IDEAS.

Statistics

Access and download statistics

Corrections

When requesting a correction, please mention this item's handle: RePEc:inm:ormnsc:v:34:y:1988:i:12:p:1472-1479. See general information about how to correct material in RePEc.

For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Mirko Janc).

If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

If references are entirely missing, you can add them using this form.

If the full references list an item that is present in RePEc, but the system did not link to it, you can help with this form.

If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your profile, as there may be some citations waiting for confirmation.

Please note that corrections may take a couple of weeks to filter through the various RePEc services.