×

zbMATH — the first resource for mathematics

GENGUB: A generator for linear programs with generalized upper bound constraints. (English) Zbl 0771.90063
Summary: We report on the development and implementation of a random generator for linear programming (LP) problems. The generator extends previous efforts by considering problems that exhibit a form of special structure often found in real-world applications, namely the presence of generalized upper bound (GUB) constraints. The algorithm allows the user considerable flexibility in the form of the final problems created, and the ability to specify certain problem anomalies at the optimal solution. The generator is of use to those involved in several areas of LP research, including the computational performance of general LP algorithms and the development of methods for detecting special structure such as GUBs within an arbitrary LP.
MSC:
90C05 Linear programming
Software:
MPGENR; NETGEN
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] ()
[2] Rardin, R.L.; Lin, B.W., Test problems for computational experiments—issues and techniques, (), 8-15
[3] Charnes, A.; Raike, W.M.; Stutz, J.D.; Walters, A.S., On generation of test problems for linear programming codes, Commun. ACM, 17, 583-586, (1974) · Zbl 0293.65045
[4] Michaels, W.M.; O’Neill, R.P., ()
[5] Michaels, W.M.; O’Neill, R.P., A mathematical program generator MPGENR, ACM trans. mathl softw., 6, 31-44, (1980) · Zbl 0432.90063
[6] Arthur, J.L.; Frendewey, J.O.; Sumichrast, R.T., GENLP: a FORTRAN routine for generating linear programs with known optimal solutions, ()
[7] Lin, B.W.; Rardin, R.L., Development of a parametric generating procedure for integer programming test problems, J. ACM, 24, 465-472, (1977) · Zbl 0359.90057
[8] Rardin, R.L.; Lin, B.W., Controlled experimental design for statistical comparison of integer programming algorithms, Mgmt sci., 12, 1258-1271, (1980)
[9] Rardin, R.L.; Lin, B.W., The RIP random integer programming test problem generator, (1980), School of Industrial and Systems Engineering, Georgie Institute of Technology Atlanta, Ga
[10] Chang, M.G.; Shepardson, F., An integer programming test problem generator, (), 146-160
[11] Rosen, J.B.; Suzuki, S., Construction of nonlinear programming test problems, Commun. ACM, 8, 113, (1965)
[12] Lidor, G., Construction of nonlinear programming test problems with known solution characteristics, (), 35-43
[13] Klingman, D.; Napier, A.; Stutz, J., NETGEN: a program for generating large-scale capacitated assignment, transportation, and minimum cost flow network problems, Mgmt sci., 20, 814-821, (1974) · Zbl 0303.90042
[14] Burruss, J.; Elam, J.; Klingman, D., (), Research report
[15] Burruss, J.; Elam, J.; Klingman, D., ()
[16] Elam, J.; Klingman, D., NETGEN-II: a system for generating structured network-based mathematical programming problems, (), 16-23
[17] Pilcher, M.; Rardin, R., Generation and validation of traveling salesman problems with known optimal solutions, ()
[18] Arthur, J.L.; Frendewey, J.O., Generating traveling salesman problems with known optimal tours, J. opl res. soc., 39, 153-159, (1988) · Zbl 0643.90060
[19] Waren, A.D.; Hung, M.S.; Lasdon, L.S., The status of nonlinear programming software: an update, Ops res., 35, 489-503, (1987)
[20] Dantzig, G.B., Linear programming and extensions, (1963), Princeton University Press Princeton, N.J · Zbl 0108.33103
[21] Schrage, L.E., A more portable FORTRAN random number generator, ACM trans. mathl softw., 5, 132-138, (1979) · Zbl 0403.68041
[22] Arthur, J.L.; Frendewey, J.O., Notes on using the random problem generators GENGUB and GENNET. working paper, ()
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.