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.


90C10 Integer programming
Full Text: DOI


[1] Garfinkel, R. S.; Nemhauser, G. L., Integer Programming (1972), Wiley: Wiley New York · Zbl 0271.90028
[2] Lawler, E. L., Combinatorial Optimization: Networks and Matroids (1976), Holt, Rinehart & Winston: Holt, Rinehart & Winston New York · Zbl 0358.68059
[3] Papadimitriou, C. H.; Steiglitz, K., Combinatorial Optimization: Algorithm and Complexity (1982), Prentice-Hall: 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: Addison-Wesley Reading, Mass · Zbl 0319.90038
[6] Sherali, H. D.; Shetty, C. M., Optimization with Disjunctive Constraints, (Lecture Notes in Economics and Mathematical Systems, Vol. 81 (1980), Springer: Springer Berlin) · Zbl 0437.90052
[7] Zionts, S., Linear and Integer Programming (1974), Prentice-Hall: Prentice-Hall Englewood Cliffs, N.J
[8] Balas, E., Disjunctive programming, (Hammer, P. L.; Johnson, E. L.; Korte, B. H., Discrete Optimation (1979), North-Holland: North-Holland Amsterdam), 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, (TIMS XXVI meeting in Copenhagen (1984))
[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, (Management Research Report No. MSRR-492 (1983), Carnegie-Mellon University)
[16] Bazaraa, M. S.; Shetty, C. M., Foundations of Optimization (1976), Springer: Springer Berlin · Zbl 0334.90049
[17] Geoffrion, A. M., Lagrangean relaxation for integer programming, (Mathematical Programming, Study 2 (1974), North-Holland: North-Holland Amsterdam) · 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: Macmillan New York · Zbl 0224.90038
[21] Fisher, M. L.; Jaikumar, R.; Lester, J. T., A computerized vehicle routing application, (Report No. 81-10-03 (1981), The Wharton School, University of Pennsylvania)
[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, (CBDA 104 (1984), The University of Texas: The University of Texas Austin, Tex), 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, (Mangasarian, O. L.; Meyer, R. R.; Robinson, S. M., Nonlinear Programming, Vol. 2 (1975), Academic Press: Academic Press New York), 279-312 · Zbl 0349.90117
[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: 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, (Glass, S. I., Validation and Assessment Issues of Energy Models. Validation and Assessment Issues of Energy Models, NBS Pub. 569 (1979)), 517-524, Washington, D.C.
[34] Greenberg, H. J.; Maybee, J. S., Computer-Assisted Analysis and Model Simplification (1981), Academic Press: 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, (Presented at the 12th International Symposium on Mathematical Programming (1985))
[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) · Zbl 1431.65006
[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: 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, (Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., The Traveling Salesman Problem (1985), North-Holland: North-Holland Amsterdam) · 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] (Lawler, E. L.; Lenstra, J. K.; Rinnooy Kan, A. H.G., The Traveling Salesman Problem (1985), North-Holland: North-Holland Amsterdam) · Zbl 0563.90075
[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, (Research Publication GMR-3217 (1980), Mathematics Department, General Motors Research Laboratories: Mathematics Department, General Motors Research Laboratories Waren, Mich) · Zbl 0651.90087
[54] Marsten, R. E., (User’s manual for ZOOM/XMP (1984), Department of Management Information Systems, University of Arizona)
[55] Marsten, R. E.; Morin, T. L.; Nagarai, K. S., Using a posteriori bounds to improve the performance of branch-and-bound algorithms, (Paper presented at the 12th International Symposium on Mathematical Programming. MIT. Paper presented at the 12th International Symposium on Mathematical Programming. MIT, Cambridge, Mass. (1985))
[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: Harvard University Press Cambridge, Mass
[58] Barr, A.; Feigenbaum, E. A., (The Handbook of Artificial Intelligence, Volume I (1981), Department of Computer Science, Stanford University, HeurisTech Press: Department of Computer Science, Stanford University, HeurisTech Press Stanford, Calif), William Kaufmann, Inc., Los Altos, Calif. · Zbl 0509.68087
[59] Nilsson, N. J., Principles of Artificial Intelligence (1980), SRI International, Tioga Publishing Company: 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: Addison-Wesley Reading, Mass
[61] Rich, E., Artificial Intelligence (1983), The University of Texas at Austin, McGraw-Hill: The University of Texas at Austin, McGraw-Hill New York
[62] Winston, P. H., Artificial Intelligence (1984), Artificial Intelligence Laboratory, MIT, Addison-Wesley: Artificial Intelligence Laboratory, MIT, Addison-Wesley Reading, Mass · Zbl 0598.68056
[63] Dantzig, G. B., Linear Programming and Extensions (1963), Princeton University Press: Princeton University Press Princeton, N.J · Zbl 0108.33103
[64] Courtois, P. J., Decomposability, Queueing and Computer Applications (1977), Academic Press: Academic Press New York · Zbl 0368.68004
[65] Simon, H. A., The Science of the Artificial (1969), MIT Press: 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, (Pulleyblank, W. R., Progress in Combinatorial Optimization (1984)), 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, (Technical Report 85-2 (1985), Department of Mathematical Sciences, Rice University) · 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, (Greenberg, X.; Maybee, X., Computer Assisted Analysis and Model Simplification (1981), Academic Press: Academic Press New York)
[72] Truemper, K., How to detect hidden networks and totally-unimodular subsections of linear programs, (TIMS/ORSA Joint National Meeting (1983))
[73] Ali, A.; Allen, E.; Barr, R.; Kennington, J., Reoptimization procedures for bounded variable primal simplex network algorithms, (Technical Report 83-PR-2 (1984), Southern Methodist University) · Zbl 0578.90088
[74] Ali, I.; Kennington, J.; Shetty, B., The equal flow problem, (Technical Report 85-OR-1 (1985), Southern Methodist University) · Zbl 0653.90015
[75] Chen, C. H.; Engquist, M., A primal simplex approach to pure processing networks, (Research Report CCS 496 (1985), Center for Cybernetic Studies, University of Texas) · Zbl 0609.90042
[77] McBride, R., Solving generalized processing network problems, (Working Paper (1982), School of Business, University of California: School of Business, University of California Los Angeles, Calif)
[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, ((1984), Wiley: Wiley New York) · 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: 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, (Presented at the ORSA/TIMS Conference. Presented at the ORSA/TIMS Conference, Boston, Mass. (1974))
[85] Glover, F.; Klingman, D., Layering strategies of creating exploitable structure in linear and integer programs, (CBDA 199 (1984), The University of Texas: The University of Texas Austin, Tex) · Zbl 0667.90070
[86] Guignard-Spielberg, M., Lagrangean decomposition: an improvement over Lagragean and surrogate duals, (Technical Report No. 62 (1984), Wharton School, University of Pennsylvania)
[87] Glover, F.; McMillan, C.; Novick, B., Interactive decision software and computer graphics for architectural and space planning, (CAAI Report No. 85-3 (1985), University of Colorado: University of Colorado Boulder, Colo), 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: 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)
[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: 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.