Применение constraint технологии при решении задач комбинаторной оптимизации в условиях фазовых переходов
Диссертация
Предложен подход к идентификации топологических особенностей исходных данных, приводящих к появлению фазового перехода в процедурах решения constraint систем, использующих метод ветвей и границ. На основании предложенного подхода разработаны алгоритмы идентификации топологических особенностей, приводящих к появлению фазового перехода в процедурах решения constraint систем, использующих метод… Читать ещё >
Содержание
- Список иллюстраций
- Список таблиц
- Список сокращений
- Глава 1. Обзор проблематики и постановка задачи
- Язык программирования Пролог
- Механизм доказательства в Прологе
- Задача удовлетворения ограничениям (Constraint Satisfaction Problem)
- Представление ограничений
- Алгоритмы разрешения ограничений
- Алгоритмы распространения ограничений
- Метод ветвей и границ
- Открытие середины 90х годов: фазовые переходы в комбинаторных задачах
- Постановка задачи исследования
- Преобразование задачи коммивояжера в BCSP
- Преобразование задачи коммивояжера в CSP
- Приближенные методы решения задачи коммивояжера
- Выводы по главе 1
- Глава 2. Анализ поведения метода ветвей и границ при появлении фазового перехода и разработка методов решения в условиях фазового перехода
- Раздел 2. 1 Особенности метода ветвей и границ при решении задач с топологическими особенностями класса I
- Топологические особенности
- Особенности решения
- Методы кластеризации
- Анализ топологии
- Гипотеза о природе фазового перехода от топологии
- Оценка вероятности появления топологических особенностей
- Выводы по разделу
- Раздел
- 2. 2. Особенности метода ветвей и границ при решении задач с топологическими особенностями класса II
- Топологические особенности класса II
- Экспериментальные результаты
- Анализ топологии
- Анализ работы метода ветвей и границ на задачах топологическими особенностями класса II
- Возможные модификации
- Геометрическая интерпретация
- Анализ сложности и точности решения приближенным алгоритмом
- Выводы по разделу
- Раздел
- 2. 3. Метод ветвей и границ при решении комбинаторных задачах с топологическими особенностями
- Задача коммивояжера
- Квадратическая задача о назначении
- Задача о 0/1 рюкзаке
- Фазовые переходы
- Влияние топологических особенностей на время решения методом ветвей и границ
- Выводы по разделу
- Раздел
- 2. 4. Методы декомпозиции
Список литературы
- Вальковский В.Б., Беляев С. А. «Использование фазовых переходов при решении комбинаторных задач» //Программные продукты и системы, #4, 2000, стр. 37 -38
- Беляев С.А. «Аспекты создания программного комплекса для решения оптимизационных экономических задач» //Современные аспекты экономики, #8, 2001, стр. 6−9
- Беляев С.А. «Заказчику программного обеспечения следует знать » //Компьютер Price, #46 (366), 2001, стр. 359 361
- Беляев С.А. «Планирование как точная наука, или constraint технологии на практике» //Терабайт, #12 (20), 2001, стр. 63−64
- Вальковский В.Б., Беляев С. А. «Интеллектуальный возврат в условиях фазового перехода при решении комбинаторных задач» //Программные продукты и системы, (в печати)
- Беляев С.А. «Технология составления расписаний и форма обучения» //Тезисы доклада на VIII международной конференции «Современные технологии обучения», Санкт-Петербург, 2002, том 2, стр. 131 133
- Hassan Ait-Kaci, Warren’s Abstract Machine, Simon Fraser University, Canada, reprinted from MIT Press Version, 1999
- Стерлинг JI., Шапиро Э. Искусство программирования на языке ПРОЛОГ. М.: Мир, 1990
- Братко И. Программирование на языке ПРОЛОГ для искусственного интеллекта. М.:Мир, 1990
- CP-AI-OR'99, Workshop on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems Ferrara, Italy, 25 — 26 February, 1999
- A. Borning, M. Maher, A. Mortindale, M. Wilson, Constraint Hierarchies and Logic Programming, TR 88−11−10, CSD, University of Washington, 1988, 1- 26pp
- D. Frost. Algorithms and Heuristics for Constraint Satisfaction Problems. PhD thesis, Information and Computer Science, University of California, Irvine, CA, 1997.
- J. Jaffar and J. Lassez. Constraint logic programming: A survey. Journal of Logic Programming, 19(20):503−581, 1994.
- A. K. Mackworth. Constraint satisfaction. In S. C. Shapiro, editor, Encyclopedia of Artificial Intelligence, 2nd Edition, pages 285−293. John Wiley & Sons, 1992.
- Podleski A. Constraint Programming: Basics and Trends, Springer-Verlag, 1995
- Tsang E. Foundation of Constraint Satisfaction, Academic Press, 1993
- Клиенты и партнеры COSYTEC, http://www.cosytec.com/casesstudies/English/index.htm
- В. A. Nadel. Some applications of the constraint satisfaction problem. In AAAI-90: Workshop on Constraint Directed Reasoning Working Notes, Boston, Mass., 1990.
- J. L. Lauriere. A language and a program for stating and solving combinatorial problems. Artificial Intelligence, 10(1), 1978.
- Гэри M., Джонсон Д. Вычислительные машины и труднорешаемые задачи. -М.:Мир, 1982
- Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. М.:Мир, 1985
- В. A. Nadel. Constraint Satisfaction Algorithms. Computational Intelligence, 5:188 224, 1989.
- V. Kumar. Algorithms for constraint satisfaction problems: A survey. AI magazine, 13(1):32—44, 1992.
- R. Bartak, Guide to Constraint Programming, 1998, http://kti.ms.mff.cuni.cz/~bartak/constraints/extendcsp.html
- B. Selman, H. A. Kautz, and B. Cohen. Noise Strategies for Improving Local Search. In Proceedings of the Twelfth National Conference on Artificial Intelligence, pages 337—343, Seattle, Washington, 1994.
- R. Debruyne and C. Bessfere. Some practicable filtering techniques for the constraint satisfaction problem. In Proc. of the 15th IJCAI, pages 412−417. 1997.
- E. C. Freuder and M. J. Quinn. The use of linear spanning trees to represent constraint satisfaction problems. Technical Report 87−41, University of New Hampshire, Durham, 1987.
- F. Bacchus and P. van Run. Dynamic variable ordering in CSPs. In Principles and Practice of Constraint Programming (CP-95), Cassis, France, 1995. Available as Lecture Notes on CS, vol 976, pp 258−277, 1995.
- Ian Gent, Ewan Maclntyre, Patrick Prosser, Barbara Smith and Toby Walsh. Random Constraint Satisfaction: Flaws and Structure. Constraints, 6 (4), 345−372,2001
- Ian Gent, Kostas Stergiou and Toby Walsh. Decomposable Constraints. Artificial Intelligence, 123 (1−2), 133−156, 2000
- A. K. Mackworth and E. C. Freuder. The complexity of some polynomial network consistency algorithms for constraint satisfaction problems. Artificial Intelligence, 25:65−74, 1985.
- G. Kondrak and P. van Beek. A theoretical evaluation of selected algorithms. Artificial Intelligence, 89:365−387, 1997.
- J. C. Sogno. Analysis of standard and new algorithms for the integer and linear constraint satisfaction problem. Technical report, INRIA, 1992.
- Roberto Bayardo and Daniel Mirankar. A complexity analysis of space-bounded learning algorithms for the constraint satisfaction problem. In Proceedings of the Thirteenth National Conference on Artificial Intelligence, pages 298—304, 1996.
- Zhe Lui, Algorithms for Constraint Satisfaction Problem, thesis presented to University Waterloo, Ontario, Canada, 1998, 1−13 lpp
- R.Detcher, D. Frost, Backtracking Algorithms for constraint satisfaction problems a tutorial survey, DICS, University of California, Irvine, 1999, l-47pp
- E. C. Freuder. A sufficient condition for backtrack-free search. Journal of the ACM, 29(1):24~32, 1982.
- E. C. Freuder. A sufficient condition for backtrack-free search. Journal of the ACM, 29(1):24—32, 1982.
- Steven Minton, Mark Johnston, Andrew Philips, and Philip Laird. Minimizing conflicts: a heuristic repair method for constraint satisfaction problem and scheduling problems. Artificial Intelligence, 58:161−205, 1992.
- D. Frost and R. Dechter. Look-ahead value ordering for constraint satisfaction problems. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-95), pages 572−578, 1995.
- D. Frost and R. Dechter. Looking at full look-ahead. In Proceedings of the Second International Conference on Constraint Programming (CP-96), 1996.
- Christian Bessiere. Arc-consistency and arc-consistency again. Artificial Intelligence, 65(1):179—190, 1994.47. «Constraint Satisfaction Problem», UGAI Lectures, http://yoda.cis.temple.edu:8080/UGAIWWW/lectures/constraints.html
- P. Van Hentenryck, Y. Deville, and C.-M. Teng. A generic arc consistency algorithm and its specializations. Artificial Intelligence, 57:291—321, 1992.
- D. A. McAllester. Truth maintenance. In AAAI-90: Proceedings of the Eighth National Conference on Artificial Intelligence, pages 1109—1116, 1990.
- Christian Bessiere, Eugene C. Freuder, and Jean-Charles Regin. Using Inference to Reduce Arc Consistency Computation. In Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence, pages 592−598, Montreal, Canada, 1995.
- Geographically Distributed Environments: Combinatorial Optimization Library, http://www.lsi.upc.es/~mallba/public/mallba-LL.html
- E.L. Lawler and D.E. Wood, «Branch-and-bound methods: a survey», Operations Research 14, 1966, pp 699−719
- Herbert Wilf. Algorithms and complexity. University of Pensilvania. Internet edition, 1994
- P. Gent and T. Walsh. Easy problems are sometimes hard. Artificial Intelligence, 70:335−345, 1994.
- Gent, T. Walsh «The TSP Phase Transition», RR/1995/178, Department of Computer Science, University of Strathclyde
- Axo А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.-М.Мир, 1979
- Кристофидес Н. Теория графов. Алгоритмический подход. М.:Мир, 1978
- Papadimitriou С.Н. Computational Complexity, Addison-Wesley, 1994
- I.Gent, T. Walsh, Phase Transition from Real Computational Problems, DCS, University of Strathclyde, 1995, SERC grant GR/H 23 610, 1995 l-9pp
- D. Mitchell, B. Selman, and H. Levesque. Hard and easy distributions of SAT problems. In Proc. of 10th National Conference on AI. AAAI Press/MIT Press, July 1992.
- Zhang W., Korf R.E., A study of complexity transitions on the asymmetric travelling salesman problem, Artificial Intelligence, 1996, Vol. 81, p. 223−239
- H.Rudova, L. Matyska, Constraint based Timetabling with students schedule, BRNO 60 200, Masaryk University, Czheh Republic, 1−15pp
- I.Gent, T. Walsh, The Number Partition Phase Transition, RR-95−185, DCS, University of Strathclyde, 1995, 1−19pp
- D. Corne, H-L. Fang, and C. Mellish. Solving the modular exam scheduling problem with genetic algorithms. In Industrial and Engineering Applications of AI and Expert Systems: Proc. of the 6th Int. Conference, 1992.
- B. Nudel. Consistent-labeling problems and their algorithms: Expected-complexities and theory-based heuristics. Artificial Intelligence, 21:135—178, 1983.
- D. Corne, H-L. Fang, and C. Mellish. Solving the modular exam scheduling problem with genetic algorithms. In Industrial and Engineering Applications of AI and Expert Systems: Proc. of the 6th Int. Conference, 1992.
- P. Prosser. Binary constraint satisfaction problems: Some are harder than others. In Proc. of ECAI-94, pages 95−99, 1994.
- P. Gent and T. Walsh. The hardest random SAT problems. In B. Nebel and L. Dreschler-Fischer, editors, KI-94: Advances in AI. 18th German Annual Conference on AI, pages 355—366. Springer- Yerlag, 1994.
- P. Gent and T. Walsh. The SAT phase transition. In Proc. of ECAI-94, pages 105 109,1994
- L. Saitta, Jean-Daniel Zucker, «Abstraction and Phase Transitions», Universita del Piemonte Orientate, Submission to SARA'2000
- G. Reinelt. TSPLIB a traveling salesman problem library. ORSA Journal on Computing, 3:376−384, 1991.
- M. Grotschel and 0. Holland, «Solution of large-scale symmetric travelling salesman problems», Mathematical Programming 51, 1991, pp 141−202
- B. Golden, L. Bodin, T. Doyle, W. Stewart «Approximate Traveling Salesman Algorithms»
- A. M. Frieze, G. Galbiati, F. Maffioli «On the Worst-Case Performance of Some Algorithms for the Asymmetric Travelling Salesman Problem»
- E. Lower, J. Lenstra, A. Rinooy Kan, D. Shmoys «The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization», pp. 676
- V. G. Deineko and G. J. Woeginger, A Study of Exponential Neighborhoods for the Traveling Salesman Problem and for the Quadratic Assignment Problem. Preprint, 1997, Graz TU, Austria.
- P. Cheeseman, B. Kanefsky, and W. Taylor. Where the really hard problems are. In Proceedings of the Twelfth International Joint Conference on Artificial Intelligence (IJCAI-91), pages 331−337, 1991.
- T. Lai and A. Sprague, «Performance of parallel branch-and-bound algorithms», IEEE Trans. Computers, vol. 34, pp. 962−964, 1985.
- K.G.Ramakrishnan, M.G.C.Resende, P.M.Pardalos, Branch and bound algorithm for the Quadratic Assignment Problem using Low-Bound based on Linear Programming, April 1995
- T.Koopmans, M. Berkmann, Assignment problems and the location of econimic activities, Econometria, 25 (1957), pp. 53−76
- E. Lawler. The quadratic assignment problem. Management Science, 9:586—599, 1963
- S.W. Hadley, F. Rendl, and H. Wolkowicz. A new lower bound via projection for the quadratic assignment problem. Mathematics of Operations Research, 17:727−739, 1992.
- E. C. Yela, The Quadratic Assignment Problem: Theory and Algorithms, Kluwer Academic Publishers, Dordrecht, 1998.
- M. S. Bazaraa and O. Kirca. A branch-and-bound-based heuristic for solving the quadratic assignment problem. Naval Research Logistics Quarterly, 30:287 304, 1983.
- P. Hahn, W. Hightower, T. Johnson, M. Guignard-Spielberg, C. Roucairol. 1999. Tree elaboration strategies in branch-and-bound algorithms for assigning the quadratic assignment problem, 6th SIAM Conference on Optimization.
- T. Stutzle. ACO Algorithms for the Quadratic Assignment Problem. In D. Corne, M. Dorigo, and F. Glover, editors, New Ideas in Optimization. McGraw-Hill, 1999.
- E. Balas. The asymmetric assignment problem and some new facets of the travelling salesman polytope on a directed graph. SIAM Journal on Discrete Mathematics, 3:425- 451, 1989.
- V. Chvatal, «Hard knapsack problems», Operations Research, vol. 28, pp. 1402−1411, 1980.
- S. Martello, D. Pisinger, P. Toth, «New trends in exact algorithms for the 0−1 knapsack problem», European Journal of Operational Research, 123, 325−332 (2000), http://www.diku.dk/research/published/1997/97−10.ps.gz
- Sadeh, N. and Fox, M. S. (1996) Variable and Value Ordering Heuristics for the Job Shop Scheduling page (46) A state-of-the-art review of job-shop scheduling techniques 03/10/98 Constraint Satisfaction Problem" Artificial Intelligence, 86(1), 141.
- M. L. Ginsberg. Dynamic backtracking. Journal of Artificial Intelligence Research, 1:25−46, 1993.
- J. R. Bitner and E. M. Reingold. Backtrack programming techniques. Communications of the ACM, 18(11):651—656, 1975.
- M. Stallmanand G. J. Sussman. Forward reasoning and dependency-directed backtracking in a system for computer-aided circuit analysis. Artificial Intelligence, 9:135−196, 1977.
- N. J. Nillson. Principles of Artificial Intelligence. Tioga, Palo Alto, CA, 1980.
- M. C. Cooper. An optimal k-consistency algorithm. Artificial Intelligence, 41(1):89−95, 1990.
- J.Borrett, E. Tsang, N. Walsh, Adaptive Constraint Satisfaction: The Quickest First Principle, DCS, University of Essex, UK, TR-CSM-256, 1955, l-24pp
- J. Pearl. Heuristics: Intelligent Search Strategies. Addison-Wesley, 1984.
- M. Bruynooghe. Solving combinatorial search problems by intelligent backtracking. Information Processing Letters, 12:36—39, 1981.
- A. B. Backer, Intelligent backtracking on the Hardest Constraint Problems, CIRL DCIS, University of Oregon, 1995, l-26pp
- A. B. Baker. Intelligent Backtracking on constraint satisfaction problems: experimental and theoretical results. PhD thesis, Graduate School of the University of Oregon, Eugene, OR, 1995.
- A. B. Baker. The hazards of fancy backtracking. In Proceedings of National Conference of Artificial Intelligence (AAAI-94), 1994.
- A. M. Frieze, G. Galbiati, F. Maffioli «On the Worst-Case Performance of Some Algorithms for the Asymmetric Travelling Salesman Problem»
- R. Dechter and I. Meiri. Experimental evaluation of preprocessing algorithms for constraint satisfaction problems. Artificial Intelligence, 68:211—241, 1994.
- P. Prosser. Hybrid algorithms for constraint satisfaction problems. Computational Intelligence, 9(3):268~299, 1993.
- R. Bayardo and D. Miranker. A complexity analysis of spacebounded learning algorithms for the constraint satisfaction problem. In AAAI-96: Proceedings of the Thirteenth National Conference on Artificial Intelligence, pages 298—304, Portland, OR, 1996.
- R. Bayardo, Jr. and D. P. Miranker. On the space-time trade-off in solving constraint satisfaction problems. In Fourteenth International Joint Conference on Artificial Intelligence (IJCAI-95), pages 558- 562, 1995.
- SICStus Prolog User’s Manual, Swedish Institute of Computer Science, 2001
- Mayoh В., Penjam J., Tyugu E. (Ets) Constraint Programming NATO Advanced Study Institute, Tallin, Institute of Cybernetics, Estonian Academy of Science, TR CS 57/1993
- R.J. Wallace, «Enhancements of branch and bound methods for the maximal constraint satisfaction problem», Proc. of AAAI-96, pp 188−196, Portland, Oregon, USA, 1996.
- Norman Sadeh and Mark S. Fox. Variable and value ordering heuristics for activity-based job-shop scheduling. In Proceedings of the Fourth International Conference on Expert Systems in Production and Management, pages 134−144, 1990.
- N. Sadeh, K. Sycara, and Y. Xiong. Backtracking techniques for the job shop scheduling constraint satisfaction problem. Artificial Intelligence, 76:455−480, 1995.
- D. Applegate and W. Cook. A computational study of the job-shop scheduling problem. ORSA Journal on Computing, 3:149−156, 1991.
- J.Han, M. Kamber «Data Mining: Concept and Techniques», ACADEMIC PRESS (www.academicpress.com), 2001, pages: 335 393
- Б.В. Гнеденко, Курс теории вероятностей, Москва, «Наука», 1965
- Н. Джонсон, Ф. Лион Статистика и планирование эксперимента в технике и науке. Методы обработки данных. Пер. с англ./ Под ред. Э. К. Лецкого. М.:Мир, 1980, стр. 155- 158, 297−302