Future paths for integer programming and links to artificial intelligence. (English) Zbl 0615.90083

Glover, Fred

Comput. Oper. Res. 13, 533-549 (1986).

Integer programming has benefited from many innovations in models and methods. Some of the promising directions for elaborating these innovations in the future may be viewed from a framework that links the perspectives of artificial intelligence and operations research. To demonstrate this, four key areas are examined: (1) controlled randomization, (2) learning strategies, (3) induced decomposition and (4) tabu search. Each of these is shown to have characteristics that appear usefully relevant to developments on the horizon.

MSC:

90C10

Integer programming

Keywords:

artificial intelligence; controlled randomization; learning strategies; induced decomposition; tabu search

References:

[1]	Garfinkel, R.S.; Nemhauser, G.L., Integer programming, (1972), Wiley New York · Zbl 0271.90028
[2]	Lawler, E.L., Combinatorial optimization: networks and matroids, (1976), Holt, Rinehart & Winston New York · Zbl 0358.68059
[3]	Papadimitriou, C.H.; Steiglitz, K., Combinatorial optimization: algorithm and complexity, (1982), Prentice-Hall Englewood Cliffs, N.J · Zbl 0503.90060
[4]	Rockafellar, R.T., Convex analysis, (1970), Princeton University Press · Zbl 0229.90020
[5]	Salkin, H.M., Integer programming, (1975), Addison-Wesley Reading, Mass · Zbl 0319.90038
[6]	Sherali, H.D.; Shetty, C.M., Optimization with disjunctive constraints, () · Zbl 0437.90052
[7]	Zionts, S., Linear and integer programming, (1974), Prentice-Hall Englewood Cliffs, N.J
[8]	Balas, E., Disjunctive programming, (), 3-52 · Zbl 0409.90061
[9]	Bradley, G.H.; Hammer, P.L.; Wolsey, L.A., Coefficient reduction for inequalities in 0-1 variables, Math. progr., 7, 263-282, (1974) · Zbl 0292.90038
[10]	Crowder, H.; Johnson, E.; Padberg, M., Solving large scale 0-1 linear programming problems, Opns res., 31, 803-934, (1983)
[11]	Guignard, M.; Spielberg, K., Propagation, penalty improvement and use of logical inequalities, Math. opns res., 25, 157-171, (1977) · Zbl 0413.90046
[12]	Padberg, M.W., Covering, packing and knapsack problems, Ann. discr. math., 4, 265-287, (1982) · Zbl 0407.90056
[13]	van Roy, T.J.; Wolsey, L.A., A software system for mixed integer programming by reformulating automatically using cuts. talk at session TA7, ()
[14]	Wolsey, L.A., Facets and strong valid inequalities for integer programs, Opns res., 24, 367-372, (1976) · Zbl 0339.90036
[15]	Balas, E., Disjunctive programming and a hierarch of relaxations for discrete optimization problems, ()
[16]	Bazaraa, M.S.; Shetty, C.M., Foundations of optimization, (1976), Springer Berlin · Zbl 0334.90049
[17]	Geoffrion, A.M., Lagrangean relaxation for integer programming, () · Zbl 0395.90056
[18]	Held, M.; Wolfe, P.; Crowder, H.D., Validation of subgradient optimization, Math. progr., 6, 62-88, (1974) · Zbl 0284.90057
[19]	Karwan, M.H.; Rardin, R.L., Some relationships between Lagrangian and surrogate duality in integer programming, Math. progr., 18, 320-334, (1979) · Zbl 0421.90056
[20]	Lasdon, L., Optimization theory for large systems, (1970), Macmillan New York · Zbl 0224.90038
[21]	Fisher, M.L.; Jaikumar, R.; Lester, J.T., A computerized vehicle routing application, ()
[22]	Gavish, B.; Pirkul, H., Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality, Math. progr., 31, 78-105, (1985) · Zbl 0571.90065
[23]	Geoffrion, A.M.; Graves, G.W., Multicommidity distribution system design by benders decomposition, Mgmt sci., 20, 822-844, (1974) · Zbl 0304.90122
[24]	Glover, F.; Klingman, D.; Philips, N.; Ross, G.T., Integrating modeling, algorithm design and computational implementation to solve a large scale nonlinear mixed integer problem, (), To be published in Ann. Opns Res.
[25]	Mulvey, J.M.; Crowder, H.P., Cluster analysis: an application of Lagrangian relaxation, Mgmt sci., 25, 329, (1979) · Zbl 0415.90085
[26]	Balas, E., Disjunctive programming: cutting-planes from logical conditions, (), 279-312
[27]	Jeroslow, R.G., Cutting-plane theory: disjunctive methods, Ann. discr. math., I, 293-330, (1977) · Zbl 0358.90035
[28]	Jeroslow, R.G., Representability in mixed integer programming, I: characterization results, (1984), Georgia Tech Atlanta, Ga · Zbl 0545.90079
[29]	Jeroslow, R.G.; Lowe, J.K., Modelling with integer variables, (1985), College of Management, Georgia Institute of Technology, To be published in Math. Progr. Stud. · Zbl 0565.90047
[30]	Meyer, R.R., Integer and mixed-integer programming models: general properties, J. opt. theory appl., 16, 191-206, (1975) · Zbl 0283.90032
[31]	Glover, F.; Hultz, J.; Klingman, D., Improved computer-based planning techniques, Interfaces, 9, 12-20, (1979), part II
[32]	Glover, F.; Martinson, F., A netform system for resource planning in the U.S. bureau of land management, J. opl res. soc., 35, 605-616, (1984)
[33]	Greenberg, H.J., A new approach to analyze information contained in a model, (), 517-524, Washington, D.C.
[34]	Greenberg, H.J.; Maybee, J.S., Computer-assisted analysis and model simplification, (1981), Academic Press New York · Zbl 0495.93001
[35]	Glover, F.; McMillan, C., The general employee scheduling problem: an integration of MS and AI, Comput. opns res., 13, 563-573, (1986)
[36]	Johnson, D.S., Optimization by simulated annealing: a tutorial. AT&T Bell laboratories, ()
[37]	Kirkpatrick, S.; Gelatt, X.; Vecchi, M.P., Optimization by simulated annealing, Science, 220, 671-680, (1983) · Zbl 1225.90162
[38]	Metropolis, N.; Rosenbluth, A.; Rosenbluth, M.; Teller, A.; Teller, E., Equation of state calculations by fast computing machines, J. chem. phys., 21, 1087, (1953)
[39]	Golden, B.L.; Skiscim, C.C., Using simulated annealing to solve routing and location problems, University of maryland, college of business and management, working paper series MS/S 84-001, (1984)
[40]	Romeo, F.; Sangiovanni-Vincentelli, A., Probabilistic Hill climbing algorithms: properties and applications, (1985), Department of EECS. University of California Berkley, Calif
[41]	Crowston, W.; Glover, F.; Thompson, G.; Trwick, J., Probabilistic and parametric learning methods for the job shop scheduling problem, (1964), GSIA, Carnegie Institute of Technology
[42]	Glover, F., A strategy for traveling salesman problems, (1964), GSIA, Carnegie Institute of Technology
[43]	Lin, S., Computer solutions to the traveling salesman problem, Bell syst. tech. J., 44, 2245-2269, (1965) · Zbl 0136.14705
[44]	Golden, B.L.; Stewart, W.R., The empirical analysis of TSP heuristics, () · Zbl 0591.90090
[45]	Krolak, P.; Felts, W.; Marble, G., A man-machine approach toward solving the traveling salesman problem, Commun. ACM, 14, 327-344, (1971) · Zbl 0217.27302
[46]	()
[47]	Thompson, G.L., Approaches to solving large and symmetric traveling salesman problems, (1985), Carnegie-Mellon University
[48]	Glover, F., Heuristics for integer programming using surrogate constraints, Decis. sci., 8, 156-166, (1977)
[49]	Trauth, C.A.; Woolsey, R.E., Practical aspects of integer linear programming, Sandia corporation monograph, SC-R-66-925, (1966)
[50]	Bazaraa, M.S.; Elshafei, A.N., On the use of fictitious bounds in tree search algorithms, Mgmt sci., 23, 904-908, (1977) · Zbl 0361.90031
[51]	Glover, F., Parametric branch and bound, Omega, 6, 145-152, (1978)
[52]	Glover, F.; Tangedahl, L., Dynamic strategies for branch and bound, Omega, 4, 571-576, (1976)
[53]	Kostreva, M.M., Adaptive estimates improve binary programming, () · Zbl 0651.90087
[54]	Marsten, R.E., ()
[55]	Marsten, R.E.; Morin, T.L.; Nagarai, K.S., Using a posteriori bounds to improve the performance of branch-and-bound algorithms, ()
[56]	Mitra, G., Investigation of some branch-and-bound strategies for the solution of mixed-integer programs, Math. progr., 4, 155-170, (1973) · Zbl 0258.90034
[57]	Anderson, J.R., The architecture of cognition, (1983), Harvard University Press Cambridge, Mass
[58]	Barr, A.; Feigenbaum, E.A., (), William Kaufmann, Inc., Los Altos, Calif.
[59]	Nilsson, N.J., Principles of artificial intelligence, (1980), SRI International, Tioga Publishing Company Palo Alto, Calif · Zbl 0422.68039
[60]	Pearl, J., Heuristics: intelligent search strategies for computer problem solving, (1984), Addison-Wesley Reading, Mass
[61]	Rich, E., Artificial intelligence, (1983), The University of Texas at Austin, McGraw-Hill New York
[62]	Winston, P.H., Artificial intelligence, (1984), Artificial Intelligence Laboratory, MIT, Addison-Wesley Reading, Mass · Zbl 0598.68056
[63]	Dantzig, G.B., Linear programming and extensions, (1963), Princeton University Press Princeton, N.J · Zbl 0108.33103
[64]	Courtois, P.J., Decomposability, queueing and computer applications, (1977), Academic Press New York · Zbl 0368.68004
[65]	Simon, H.A., The science of the artificial, (1969), MIT Press Cambridge, Mass
[66]	Simon, H.A.; Ando, A., Aggregation of variables in dynamic systems, Econometrica, 29, 111-138, (1961) · Zbl 0121.15103
[67]	Bixby, R.E., Recent algorithms for two versions of graph realization and remarks on applications to linear programming, (), 39-67
[68]	Bixby, R.E.; Cunningham, W.H., Converting linear programs to network problems, Math. opns res., 5, 321-327, (1980) · Zbl 0442.90095
[69]	Bixby, R.E.; Wagner, D., An almost linear-time algorithm for graph realization, () · Zbl 0654.05023
[70]	Brown, G.G.; McBride, R.D.; Wood, R.K., Extracting embedded generalized networks from linear programming problems, Math. progr., 32, 11-31, (1985) · Zbl 0574.90060
[71]	Schrage, L., On hidden structures in linear programs, ()
[72]	Truemper, K., How to detect hidden networks and totally-unimodular subsections of linear programs, ()
[73]	Ali, A.; Allen, E.; Barr, R.; Kennington, J., Reoptimization procedures for bounded variable primal simplex network algorithms, () · Zbl 0578.90088
[74]	Ali, I.; Kennington, J.; Shetty, B., The equal flow problem, () · Zbl 0653.90015
[75]	Chen, C.H.; Engquist, M., A primal simplex approach to pure processing networks, () · Zbl 0609.90042
[76]	M. Engquist and C. H. Hen, Computational comparison of two solution procedures for allocation/processing networks. To be published in Math. Progr. Study.
[77]	McBride, R., Solving generalized processing network problems, ()
[78]	McBride, R., Solving embedded generalized network problems, Eur. J. opns res., 21, 82-92, (1985) · Zbl 0565.90038
[79]	Rockafellar, R.T., Network flows and monotropic optimization, () · Zbl 0596.90055
[80]	Glover, F., A multiphase-dual algorithm for the zero-one integer programming problem, Opns res., 13, 879-919, (1965) · Zbl 0163.41301
[81]	Hammer, P.L.; Johnson, E.L.; Korte, B.H.; Nemhauser, G.L., Studies in integer programming, (1977), North-Holland Amsterdam · Zbl 0349.00025
[82]	Hammer, P.L.; Johnson, E.L.; Peled, V.N., Facets of regular 0-1 polytopes, Math. progr., 8, 179-206, (1975) · Zbl 0314.90064
[83]	Glover, F.; Mulvey, J., Equivalence of the 0-1 integer programming problem to discrete generalized and pure networks, Opns res., 28, 829-835, (1980) · Zbl 0443.90064
[84]	Srinivasan, V.; Thompson, G.L., Stopped simplex algorithm for the set partitioning problem with transportation-like subproblems, ()
[85]	Glover, F.; Klingman, D., Layering strategies of creating exploitable structure in linear and integer programs, () · Zbl 0667.90070
[86]	Guignard-Spielberg, M., Lagrangean decomposition: an improvement over Lagragean and surrogate duals, ()
[87]	Glover, F.; McMillan, C.; Novick, B., Interactive decision software and computer graphics for architectural and space planning, (), To be published in Ann. Opns Res.
[88]	Senju, S.; Toyoda, Y., An approach to linear programming with 0-1 variables, Mgmt sci., 15, B196-B207, (1968)
[89]	Kochenberger, G.A.; McCarl, B.A.; Wyman, F.P., A heuristic for general integer programming, Decis. sci., 5, 36, (1974)
[90]	Arthanari, T.S.; Dodge, Y., Mathematical programming in statistics, (1981), Wiley New York · Zbl 0549.62002
[91]	Bajgier, S.M.; Hill, A.V., An experimental comparison of statistical and linear programming approaches to the discriminant problem, Decis. sci., 13, 604-618, (1982)
[92]	N. Freed and F. Glover, Evaluating alternative linear programming approaches to the discriminant problem. MSRS 85-5, University of Colorado. To be published in Decis. Sci. · Zbl 0521.62055
[93]	Liittschwager, J.M.; Wang, C., Integer programming solution of a classification problem, Mgmt sci., 24, 1515, (1978) · Zbl 0491.90056
[94]	Rao, M.R., Cluster analysis and mathematical programming, J. am. statist. ass., 66, 622, (1971) · Zbl 0238.90042
[95]	Williams, H.P., Model building in mathematical programming, (1978), Wiley New York · Zbl 0384.90079
[96]	Christofides, N.; Eilon, S., Algorithm for large scale TSP’s, Opns res. Q., 23, 511, (1972)