“The act of being wise is the act of knowing what to overlook.”
William James (ca. 1890)
Abstract
If a linear program (LP) possesses a large generalized network (GN) submatrix, this structure can be exploited to decrease solution time. The problems of finding maximum sets of GN constraints and finding maximum embedded GN submatrices are shown to be NP-complete, indicating that reliable, efficient solution of these problems is difficult. Therefore, efficient heuristic algorithms are developed for identifying such structure and are tested on a selection of twenty-three real-world problems. The best of four algorithms for identifying GN constraint sets finds a set which is maximum in twelve cases and averages 99.1% of maximum. On average, the GN constraints identified comprise more than 62.3% of the total constraints in these problems. The algorithm for identifying embedded GN submatrices finds submatrices whose sizes, rows plus columns, average 96.8% of an LP upper bound. Over 91.3% of the total constraint matrix was identified as a GN submatrix in these problems, on average.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
J. Bartholdi, “A good submatrix is hard to find”,Operations Research Letters 1 (1982) 190–193.
R. Bixby and W. Cunningham, “Converting linear programs to network problems”,Mathematics of Operations Research 5 (1980) 321–357.
G. Bradley, G. Brown and G. Graves, “Implementation of large-scale primal transshipment algorithms”,Management Science 24 (1977) 1–34.
A. Brearley, G. Mitra and H. Williams, “Analysis of mathematical programming problems prior to applying the simplex algorithm”,Mathematical Programming 8 (1975) 54–83.
G. Brown and G. Graves, “Design and implementation of a large scale (mixed integer, non-linear) optimization system”, presented at ORSA/TIMS Conference, Las Vegas, NV, November 1975.
G. Brown and R. McBride, “Solving generalized networks”,Management Science 30 (1984) 1497–1523.
G. Brown and D. Thomen, “Automatic identification of generalized upper bounds in large-scale optimization models”,Management Science 26 (1980) 1166–1184.
G. Brown and W. Wright, “Automatic identification of embedded network rows in large-scale optimization models”,Mathematical Programming 29 (1984) 41–46.
G. Dobson, “Worst-case analysis of greedy heuristics for integer programming with nonnegative data”,Mathematics of Operations Research 7 (1982) 515–531.
M. Garey and D. Johnson,Computers and intractability: A guide to the theory of NP-completeness (W.H. Freeman, San Francisco, CA, 1978).
F. Glover, J. Hultz, D. Klingman and J. Stutz, “Generalized networks: A fundamental computerbased planning tool”,Management Science 24 (1978) 1209–1220.
F. Glover and D. Klingman, “The simplex son algorithm for LP/embedded network problems”,Mathematical Programming Study 15 (1981) 148–176.
G. Graves and R. McBride, “The factorization approach to large-scale linear programming”,Mathematical Programming 10 (1976) 91–110.
G. Graves and T. Van Roy, “Decomposition for large-scale linear and mixed integer programming”, Technical Report, University of California at Los Angeles (Los Angeles, CA, November 1979).
R. Karp, “Reducibility among combinatorial problems”, in: R. Miller and J. Thatcher, eds.,Complexity of computer computations (Plenum Press, New York and London, 1972) pp. 85–103.
S. Lin, “Computer solutions of the traveling salesman problem”,Bell System Technical Journal 44 (1965) 2245–2269.
S. Lin and B. Kernighan, “An effective heuristic for the traveling salesman problem”,Operations Research 21 (1973) 498–516.
R. McBride, “Solving generalized network problems with side constraints”, Working Paper, FBE Department, School of Business Administration, University of Southern California (Los Angeles, CA, September 1981).
R. McBride, “Solving embedded generalized network problems”, to appear,European Journal of Operations Research (1985). Also, Working Paper, FBE Department, School of Business Administration, University of Southern California (Los Angeles, CA, October 1982).
J. Musalem, “Converting linear models to network models”, Ph.D. Dissertation, University of California at Los Angeles (Los Angeles, CA, January 1980).
L. Schrage, “Some comments on hidden structure in linear programs”, in: H. Greenberg and J. Maybee, eds.,Computer-assisted analysis and model simplification (Academic Press, New York, 1981) pp. 389–395.
S. Senju and Y. Toyoda, “An approach to linear programming with 0–1 variables”,Management Science 15 (1968) B196-B207.
Y. Toyoda, “A simplified algorithm for obtaining approximate solutions to zero–one programming problems”,Management Science 21 (1975) 1417–1427.
M. Yannakakis, “Node-deletion problems on bipartite graphs”,SIAM Journal on Computing 10 (1981) 310–327.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Brown, G.G., McBride, R.D. & Wood, R.K. Extracting embedded generalized networks from linear programming problems. Mathematical Programming 32, 11–31 (1985). https://doi.org/10.1007/BF01585656
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01585656