Какой алгоритм поиска наилучших двух вариантов сетевого подключения для 1200 сайтов?

Question

Я инженер данных, который пытается решить интересную аналитическую задачу.Я связался с небольшой книгой Excel с примерами данных.

Постановка проблемы:

У компании есть филиалы в 1200 местах.Они хотят подключения к сети для всех филиалов.Они требуют двух решений для подключения от двух отдельных поставщиков услуг, чтобы обеспечить непрерывность обслуживания.

Существует более 20 поставщиков услуг, каждый из которых предлагает до 30 предложений по подключению.Не все поставщики услуг присутствуют во всех местоположениях, а некоторые местоположения покрываются только некоторыми продуктами поставщика.Типы продуктов ранжируются от лучших к худшим.

Чем выше емкость, тем лучше, но общий бюджет является ограничением.

Поиск подходящих поставщиков и продуктов в каждом месте - утомительный процесс, особенно когдадругие ограничения включены.

Поиск предполагает, что LTR может использовать класс алгоритмов, но, пожалуйста, укажите мне какое-нибудь лучшее решение или подход.

Ссылка на рабочую книгу в Dropbox

Спасибо, Алан.

Answer 1

Эта проблема кажется естественной для целочисленного программирования.Вы можете описать переменные, ограничения и целевую функцию для библиотеки, такой как PuLP, и позволить библиотеке выполнить грязную работу по поиску оптимального решения.

Answer 2

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

MCFSimplex - это , вероятно, самая быстрая открытая реализация симплексной сети с открытым исходным кодом, так что это может быть то, что вы ищете.И у него есть оболочка Python .

Answer 3

Ваша проблема невелика, и вы можете ее перебить, если функция стоимости не слишком сложна.

У вас есть 1200 мест, в каждом по 20 провайдеров по 30 предложений в каждом.Вы хотите выбрать 2 предложения для каждого местоположения от независимых поставщиков: (20 * 30 + 19 * 30) + 1200 = 1,4 млн. Решений для анализа.

Вы можете запустить простой возврат, чтобы найти решение, которое минимизирует общее количествостоимость, и поскольку проблема не слишком велика, запуск займет всего несколько секунд.Основным псевдокодом может быть:

 bruteForce(partialAnswer, currentLocation, constraints, bestAnswer):
     for (each possible pairOfOfferings from different provicers at
               currentLocation):
         add pairOffering to partialAnswer
         if (pairOfOffering ok according to constraints):
             if (currentLocation is last location left):
                if (partialAnswer beats bestAnswer according to cost function):
                    update bestAnswer
             othwerwise:
                call bruteForce(
                         partialAnswer, nextLocation, constraints, bestAnswer)
         remove pairOffering from partialAnswer

Сокращение пространства поиска может значительно ускорить это, но если у вас на порядок больше мест или вам действительно не нужно время отклика менее секунды, этонаверное не стоит.