Введение
Глава 1. Задачи дискретной оптимизации и выполнимость логических формул 9
1.1 Постановки задач и их сложность 9
1.2 Связь с другими задачами и некоторые приложения . 11
1.3 L-структура задач целочисленного программирования . 15
1.4 Методы решения 21
Глава 2. Исследование задач с использованием L-разбиения 25
2.1 L-структура многогранников задач максимальной и минимальной выполнимости 25
2.2 Построение специальных семейств логических формул . 32
2.3 Анализ L-накрытий задач 36
Глава 3. Разработка и анализ алгоритмов для задач максимальной и минимальной выполнимости 45
3.1 Анализ некоторых алгоритмов целочисленного программирования на основе L-разбиения 45
3.2 Алгоритмы точного решения для задачи максимальной выполнимости 62
3.3 Алгоритмы локального поиска для задачи максимальной выполнимости 69
Глава 4. Результаты вычислительного эксперимента 72
4.1 Исследование и сравнение алгоритмов точного решения . 72
4.2 Исследование алгоритмов локального поиска 84
Заключение 90
Список литературы
