Дискретна оптимізація

Дискретна оптимізація — розділ оптимізації в прикладній математиці та інформатиці. На відміну від неперервної оптимізації, деякі або всі змінні, що використовуються в задачі дискретної оптимізації, діскретні(інші мови), тобто, можуть набувати значень лише з дискретного набору, наприклад, цілих^[1].

Галузі

Три основні гілки дискретної оптимізації:^[2]

комбінаторна оптимізація, що розглядає задачі на графах, матроїдах та інших дискретних структурах;
цілочисельне програмування;
програмування в обмеженнях.

Однак усі ці гілки тісно переплетені, оскільки багато задач комбінаторної оптимізації можна змоделювати як цілочисельні програми (наприклад, задачу про найкоротший шлях) або програми в обмеженнях, будь-яку програму в обмеженнях можна сформулювати як цілочисельну програму і навпаки, а програми в обмеженнях та цілочисельні часто допускають комбінаторну інтерпретацію.

Див. також

Примітки

↑ Lee, Jon (2004), A First Course in Combinatorial Optimization, Cambridge Texts in Applied Mathematics, т. 36, Cambridge University Press, с. 1, ISBN 9780521010122.
↑ Hammer, P. L.; Johnson, E. L.; Korte, B. H. (2000), Conclusive remarks, Discrete Optimization II, Annals of Discrete Mathematics, т. 5, Elsevier, с. 427—453.

[1] Lee, Jon (2004), A First Course in Combinatorial Optimization, Cambridge Texts in Applied Mathematics, т. 36, Cambridge University Press, с. 1, ISBN 9780521010122.

[2] Hammer, P. L.; Johnson, E. L.; Korte, B. H. (2000), Conclusive remarks, Discrete Optimization II, Annals of Discrete Mathematics, т. 5, Elsevier, с. 427—453.

[1]

[2]