Detecting Embedded Networks in LP Using GUB Structures and Independent Set Algorithms

1. R.K. Ahuja, T.L. Magnanti, and J.B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice-Hall, 1993.

2. B.M. Baker and P.J. Maye, “A heuristic for finding embedded network structure in mathematical programs,” European Journal of Operational Research, vol. 67, pp. 52-63, 1993.

   Google Scholar 

3. J.J. Bartholdi, “A good submatrix is hard to find,” Operations Research Letters, vol. 1, pp. 190-193, 1982.

   Google Scholar 

4. R.E. Bixby and R. Fourer, “Finding embedded network rows in linear programs I. Extraction heuristics,” Management Science, vol. 34, no. 3, pp. 342-376, 1988.

   Google Scholar 

5. A.L. Brearley, G. Mitra, and H.P. Williams, “Analysis of mathematical programming problems prior to applying the simplex algorithm,” Mathematical Programming, vol. 8, pp. 54-83, 1975.

   Google Scholar 

6. G.G. Brown and M.P. Olson, “Dynamic factorization in large-scale optimization,” Mathematical Programming, vol. 64, pp. 17-51, 1994.

   Google Scholar 

7. G.G. Brown and W.G. Wright, “Automatic identification of embedded network rows in large-scale optimization models,” Mathematical Programming, vol. 29, pp. 41-56, 1984.

   Google Scholar 

8. G.G. Brown and D.S. Thomen, “Automatic identification of generalized upper bounds in large-scale optimization models,” Management Science, vol. 26, no. 11, pp. 1166-1184, 1980.

   Google Scholar 

9. G.G. Brown and W.G. Wright, “Automatic identification of embedded structure in large-scale optimization models,” in Computer-Assisted Analysis and Model Simplification, H. Greenberg and J. Maybee (Eds.), Academic Press: New York, 1981, pp. 369-388.

   Google Scholar 

10. G.B. Dantzig and R.M. Van Slyke, “Generalized upper bounding techniques,” Journal of Computer and System Sciences, vol. 1, pp. 213-226, 1967.

    Google Scholar 

11. S. Duff, A.M. Erisman, and J.K. Reid, Direct Methods for Sparse Matrices, Oxford University Press: Oxford-London, 1986.

    Google Scholar 

12. D.M. Gay, “Electronic mail distribution of linear programming test problems,” Mathematical Programming Society, Coal, Newsletter, vol. 13, pp. 10-12, 1985.

    Google Scholar 

13. F. Glover and D. Klingman, “The simplex SON algorithm for LP/embedded network problems,” Mathematical Programming Study, vol. 15, pp. 148-176, 1971.

    Google Scholar 

14. H.J. Greenberg, “A functional description of analyze: A computer assisted analysis system for linear programming models,” ACM Trans. Math. Software, vol. 9, no. 1, 1983.

15. N. Gülpınar, G. Gutin, and G. Mitra, “Detecting embedded pure network structure using independent set algorithms,” Technical Report, TR/12/97, Brunel University, 1997.

16. N. Gülpınar, I. Maros, and G. Mitra, “Detecting pure embedded network structures in large-scale LP problems,” Technical Report, TR/20/96, Brunel University, 1996.

17. N. Gülpınar, G. Mitra, and I. Maros, “Creating advanced starting basis for large scale programs exploiting embedded network structures,” Technical Report, TR/04/98, Brunel University, 1998.

18. A. Hsu and R. Fourer, “Exploiting network structure for solving large scale linear programming models,” Working Paper, Jan. 1996.

19. S. Khanna, R. Motwani, M. Sudan, and U. Vazirani, “On syntactic versus computational views of approximately,” in Proceedings Symposium on Foundations of Computer Science, 1994.

20. H.M. Markowitz, “The elimination form of the inverse and its application to linear programming,” Management Science, vol. 3, pp. 255-267, 1957.

    Google Scholar 

21. E. Messina and G. Mitra, “Modelling and analysis of multi-stage stochastic programming problems: A software environment,” European Journal of Operational Research, vol. 101, no. 2, pp. 343-359, 1997.

    Google Scholar 

22. G. Mitra and M. Tamiz, “Alternative methods for representing the inverse of linear programming basis matrices,” in Recent Developments in Mathematical Programming, S. Kumar (Ed.), 1991, pp. 273-301.

23. V.T. Paschos, “A (δ/2)-approximation algorithm for the maximum independent set problem,” Information Processing Letters, vol. 44, pp. 11-13, 1992.

    Google Scholar 

Download references