×

Toward unification of exact and heuristic optimization methods. (English) Zbl 1309.90087

Summary: This paper argues that many exact and heuristic methods have common structure that permits some degree of unification. It interprets solution algorithms as primal-dual methods in which the primal component searches over problem restrictions, and the dual component obtains bounds on the optimal value. In particular, the concept of an inference dual provides the basis for constraint-directed search, which is a feature of many exact and heuristic methods. The motivations for unification are (a) to encourage the exchange of algorithmic techniques between exact and heuristic methods and (b) to design solution methods that transition gracefully from exact to heuristic modes as problem instances scale up.

MSC:

90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming

Software:

Chaff
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Achterberg, Conflict analysis in mixed integer programming, Discrete Optimization 4 pp 4– (2007) · Zbl 1169.90414
[2] Ahuja, A survey of very large scale neighborhood search techniques, Discrete Applied Mathematics 123 pp 75– (2002) · Zbl 1014.68052
[3] Barricelli, Numerical testing of evolution theories. Part II: preliminary tests of performance, symbiogenesis and terrestrial life, Acta Biotheoretica 16 pp 99– (1963)
[4] Beame , P. Kautz , H. Sabharwal , A. 2003 Understanding the power of clause learning International Joint Conference on Artificial Intelligence (IJCAI 2003), Acapulco, Mexico
[5] Benchimol, Proceedings of the International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2010) pp 40– (2010) · Zbl 1285.68149
[6] Benders, Partitioning procedures for solving mixed-variables programming problems, Numerische Mathematik 4 pp 238– (1962) · Zbl 0109.38302
[7] Benichou, Experiments in mixed-integer linear programming, Mathematical Programming 1 pp 76– (1971) · Zbl 0233.90016
[8] Bixby , R.E. Cook , W. Cox , A. Lee , E.K. 1995 Parallel mixed integer programming
[9] Bliek, National Conference on Artificial Intelligence (AAAI 1998) pp 319– (1998)
[10] Blum, Hybrid Optimization: The Ten Years of CPAIOR pp 305– (2011) · Zbl 1205.90298
[11] Davis, A machine program for theorem proving, Communications of the ACM 5 pp 394– (1962) · Zbl 0217.54002
[12] Davis, A computing procedure for quantification theory, Journal of the ACM 7 pp 201– (1960) · Zbl 0212.34203
[13] Dhyani, Proceedings of the International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2010) pp 97– (2010) · Zbl 05724355
[14] Dorigo , M. 1992 Optimization, learning and natural algorithms Politecnico di Milano
[15] Dorigo, Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation 1 pp 53– (1997) · Zbl 05451865
[16] El Hachemi, Proceedings of the International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2009) pp 319– (2009) · Zbl 05561115
[17] Feo, A greedy randomized adaptive search procedure for maximum independent set, Operations Research 42 pp 860– (1994) · Zbl 0815.90121
[18] Feo, Greedy randomized adaptive search procedures, Journal of Global Optimization 6 pp 109– (1995) · Zbl 0822.90110
[19] Gaschnig , J. 1978 Experimental studies of backtrack vs. Waltz-type vs. new algorithms for satisficing-assignment problems Proceedings, 2nd National Conference of the Canadian Society for Computational Studies of Intelligence, Toronto, Canada 19 21
[20] Gautier, Experiments in mixed-integer linear programming using pseudo-costs, Mathematical Programming 12 pp 26– (1977) · Zbl 0362.90070
[21] Ginsberg, Dynamic backtracking, Journal of Artificial Intelligence Research 1 pp 25– (1993)
[22] Ginsberg , M.L. McAllester , D.A. 1994 GSAT and dynamic backtracking Lecture Notes in Computer Science Springer New York 216 225
[23] Glover, Tabu search: part I, ORSA Journal on Computing 1 pp 190– (1989) · Zbl 0753.90054
[24] Golden, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization pp 207– (1985)
[25] Gomes, Handbook of Knowledge Representation pp 89– (2008)
[26] Hansen , P. 1986 The steepest ascent mildest descent heuristic for combinatorial programming
[27] Holland, Adaptation in Natural and Artificial Systems (1975)
[28] Hooker, Logic-Based Methods for Optimization: Combining Optimization and Constraint Satisfaction (2000) · Zbl 0974.90001
[29] Hooker , J.N. 2005 Unifying local and exhaustive search Villaseñor , L. Martinez , A.I. Avances en la Ciencia de la Computación (ENC 2005) Puebla, Mexico 237 243
[30] Hooker , J.N. 2006 Duality in optimization and constraint satisfaction Beck , J.C. Smith , B.M. Lecture Notes in Computer Science Springer New York 3 15 · Zbl 1177.68188
[31] Hooker, Integrated Methods for Optimization (2007a) · Zbl 1122.90002
[32] Hooker, Planning and scheduling by logic-based Benders decomposition, Operations Research 55 pp 588– (2007b) · Zbl 1167.90512
[33] Hooker, Integrated Methods for Optimization (2012) · Zbl 1263.90002
[34] Hooker, Logic-based Benders decomposition, Mathematical Programming 96 pp 33– (2003) · Zbl 1023.90082
[35] Hooker, Principles and Practice of Constraint Programming: The Newport Papers pp 267– (1995)
[36] Kennedy , J. Eberhart , R. 1995 Particle swarm optimization Proceedings of IEEE International Conference on Neural Networks, Perth, Australia 1942 1948
[37] Khichane, Proceedings of the International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2010) pp 232– (2010) · Zbl 1285.68158
[38] Kirkpatrick, Optimization by simulated annealing, Science 220 pp 671– (1983) · Zbl 1225.90162
[39] Lin, An effective heuristic algorithm for the traveling salesman problem, Operations Research 21 pp 498– (1973) · Zbl 0256.90038
[40] McAllester, Partial order backtracking (1993)
[41] Moskewicz , M.W. Madigan , C.F. Zhao , Y. Zhang , L. Malik , S. 2001 Chaff: engineering an efficient SAT solver Proceedings of the 38th Design Automation Conference (DAC 2001), Las Vegas, NV 530 535
[42] Pham, Proceedings of the International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2010) pp 267– (2010) · Zbl 1285.68160
[43] Pisinger, Handbook of Metaheuristics pp 399– (2010)
[44] Prestwich , S. 2004 Exploiting relaxation in local search · Zbl 1145.90059
[45] Rechenberg, Evolutionsstrategie (1973)
[46] Sandholm , T. Shields , R. 2006 Nogood learning for mixed integer programming
[47] Shaw, Hybrid Optimization: The Ten Years of CPAIOR pp 271– (2011) · Zbl 1206.90182
[48] Shi , Y. Eberhart , R. 1998 A modified particle swarm optimizer Proceedings of IEEE International Conference on Neural Networks, Anchorage, AK 69 73
[49] Stallman, Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis, Journal of Artificial Intelligence 9 pp 135– (1977) · Zbl 0372.94024
[50] Yunes, An integrated solver for optimization problems, Operations Research 58 pp 342– (2010) · Zbl 1226.90047
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.