×

zbMATH — the first resource for mathematics

Future paths for integer programming and links to artificial intelligence. (English) Zbl 0615.90083
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
PDF BibTeX XML Cite
Full Text: DOI
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)
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.