zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
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.

90C10Integer programming
Full Text: DOI
[1] Garfinkel, R. S.; Nemhauser, G. L.: Integer programming. (1972) · Zbl 0259.90022
[2] Lawler, E. L.: Combinatorial optimization: networks and matroids. (1976) · Zbl 0413.90040
[3] Papadimitriou, C. H.; Steiglitz, K.: Combinatorial optimization: algorithm and complexity. (1982) · Zbl 0503.90060
[4] Rockafellar, R. T.: Convex analysis. (1970) · Zbl 0193.18401
[5] Salkin, H. M.: Integer programming. (1975) · Zbl 0319.90038
[6] Sherali, H. D.; Shetty, C. M.: Optimization with disjunctive constraints. Lecture notes in economics and mathematical systems 81 (1980) · Zbl 0437.90052
[7] Zionts, S.: Linear and integer programming. (1974)
[8] Balas, E.: Disjunctive programming. Discrete optimation, 3-52 (1979) · 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)
[16] Bazaraa, M. S.; Shetty, C. M.: Foundations of optimization. (1976) · Zbl 0334.90049
[17] Geoffrion, A. M.: Lagrangean relaxation for integer programming. Mathematical programming, study 2 (1974) · 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) · Zbl 0224.90038
[21] Fisher, M. L.; Jaikumar, R.; Iii, J. T. Lester: A computerized vehicle routing application. Report no. 81-10-03 (1981)
[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)
[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. Nonlinear programming 2, 279-312 (1975) · Zbl 0349.90117
[27] Jeroslow, R. G.: Cutting-plane theory: disjunctive methods. Ann. discr. Math. 1, 293-330 (1977) · Zbl 0358.90035
[28] Jeroslow, R. G.: Representability in mixed integer programming, I: Characterization results. (1984) · Zbl 0618.90069
[29] Jeroslow, R. G.; Lowe, J. K.: Modelling with integer variables. (1985) · 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)
[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. NBS pub. 569, 517-524 (1979)
[34] Greenberg, H. J.; Maybee, J. S.: Computer-assisted analysis and model simplification. (1981) · 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.; Jr, X. Gelatt; 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)
[41] Crowston, W.; Glover, F.; Thompson, G.; Trwick, J.: Probabilistic and parametric learning methods for the job shop scheduling problem. (1964)
[42] Glover, F.: A strategy for traveling salesman problems. (1964) · Zbl 0207.50502
[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. The traveling salesman problem (1985) · 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.; Kan, A. H. G. Rinnooy: The traveling salesman problem. (1985) · Zbl 0563.90075
[47] Thompson, G. L.: Approaches to solving large and symmetric traveling salesman problems. (1985)
[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)
[54] Marsten, R. E.: 2nd edition user’s manual for ZOOM/XMP. User’s manual for ZOOM/XMP (1984)
[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 (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)
[58] Barr, A.; Feigenbaum, E. A.: 2nd edition the handbook of artificial intelligence. The handbook of artificial intelligence (1981)
[59] Nilsson, N. J.: Principles of artificial intelligence. (1980) · Zbl 0422.68039
[60] Pearl, J.: Heuristics: intelligent search strategies for computer problem solving. (1984)
[61] Rich, E.: Artificial intelligence. (1983)
[62] Winston, P. H.: Artificial intelligence. (1984) · Zbl 0598.68056
[63] Dantzig, G. B.: Linear programming and extensions. (1963) · Zbl 0108.33103
[64] Courtois, P. J.: Decomposability, queueing and computer applications. (1977) · Zbl 0368.68004
[65] Simon, H. A.: The science of the artificial. (1969)
[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. Progress in combinatorial optimization, 39-67 (1984) · Zbl 0542.90097
[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)
[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. Computer assisted analysis and model simplification (1981) · Zbl 0471.90044
[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) · Zbl 0578.90088
[74] Ali, I.; Kennington, J.; Shetty, B.: The equal flow problem. Technical report 85-OR-1 (1985) · Zbl 0653.90015
[75] Chen, C. H.; Engquist, M.: A primal simplex approach to pure processing networks. Research report CCS 496 (1985) · 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. Working paper (1982)
[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) · 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) · 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 (1974)
[85] Glover, F.; Klingman, D.: Layering strategies of creating exploitable structure in linear and integer programs. Cbda 199 (1984) · Zbl 0667.90070
[86] Guignard-Spielberg, M.: Lagrangean decomposition: an improvement over lagragean and surrogate duals. Technical report no. 62 (1984)
[87] Glover, F.; Mcmillan, C.; Novick, B.: Interactive decision software and computer graphics for architectural and space planning. CAAI report no. 85-3 (1985)
[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) · 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) · Zbl 0384.90079
[96] Christofides, N.; Eilon, S.: Algorithm for large scale tsp’s. Opns res. Q. 23, 511 (1972) · Zbl 0248.90039