1070 Многопоточный солвер для задачи о ранце со многими ограничениями

Посыпкин Михаил Анатольевич

руководитель проекта

Старт

15.03.2022

Представление

29.04.2022

Постерная сессия

06.06.2022

Защита

03.11.2022

Паспорт проекта

Аннотация

Задача о ранце – одна из классических задач теории оптимизации с приложениями в логистике, экономике, криптографии. В рамках данного проекта рассматривается её вариант с несколькими ограничениями. В силу того, что задача относится к классу NP-полных, вопрос построения более эффективных по времени и памяти алгоритмов для её решения является актуальным. В ходе проекта необходимо проанализировать существующие решения данной задачи, а также методы верхних релаксационных оценок задач дискретной...

Отрасль

Информатика

Цель

Создание алгоритма решения многомерной задачи о булевом ранце с несколькими ограничениями и исследование эффективности применения различных оценок в методе ветвей и границ.

Ожидаемые результаты

Алгоритм для нахождения верхней границы, основанный на релаксации задачи.
Алгоритм для нахождения точного решения задачи, улучшенный внедрением априорной оценки решения сверху.
Результаты вычислительных экспериментов и обобщающие выводы об эффективности разработанных алгоритмов.