Решение задачи о рюкзаке оптимизации доходов на практике

Напомним, что, как упоминалось в предыдущем посте, Onera может превратить задачу оптимизации доходов без ухудшения качества обслуживания клиентов в следующую задачу о рюкзаке. В частности, мы имеем следующую постановку задачи:

В приведенной выше формулировке розничный продавец продает набор товаров I. Каждый элемент i в I имеет значение v (i), которое является ожидаемым доходом ( или маржа), которую розничный продавец делает, если продает этот товар, и в соответствии с этим существует w (i), которое является ожидаемым количеством недовольных покупателей (размер товара в задаче о рюкзаке). Задача требует от нас максимизировать общий ожидаемый доход, обеспечивая при этом, чтобы общее недовольство клиентов оставалось ниже порогового значения W.

Задача о рюкзаке, как указано выше, выражается в виде целочисленной линейной программы. В частности, обратите внимание, что переменные x могут принимать только значение 0 или 1. Если мы гипотетически предположим, что мы можем включить предмет в рюкзак частично (бессмысленно в реальном мире, когда наполнение рюкзака из жестких предметов), то мы получаем так называемую релаксацию линейного программирования целочисленной программы. В релаксации линейного программирования мы просто преобразуем переменные x из двоичных в {0, 1} в действительные числа в [0, 1]. Расслабление линейного программирования - это проблема, которая находится в P, в то время как указанная выше целочисленная линейная программа - это проблема, которая является NP -полной как упоминалось раньше. Это должно иметь интуитивный смысл, поскольку, если я смогу разместить предмет по частям, тогда я смогу заполнить рюкзак полностью, и это значительно упростит задачу.

Обратите внимание, что есть ограничения I, I, которые гарантируют, что все переменные являются двоичными (или 2 ограничения I в ослаблении, обеспечивающие, что x находится в [0, 1]) и единственном ограничении, которое требует, чтобы сумма размеров выбранных элементов не превышала W. Мы будем называть это единственное ограничение ограничением рюкзака, а оставшиеся 2 ограничения I - бинарными граничными ограничениями. В этой задаче каждое ограничение 2I + 1 является I -мерной гиперплоскостью, каждая из которых обеспечивает выполнимость с одной стороны. Эти ограничения вместе, используя их пересечения, определяют I -мерный многогранник, внутри которого находятся все возможные решения задачи о рюкзаке. Точки вне многогранника - это те, которые нарушают хотя бы одно из вышеуказанного набора ограничений.

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

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

Теперь мы исследуем эти крайние точки многогранника рюкзака (опять же линейная релаксация), чтобы найти красивую структуру, которая помогает нам решать их чрезвычайно быстро. Обратите внимание, что крайняя точка в этом I -мерном многограннике определяется точно как пересечение I -линейно независимых I -мерных гиперплоскостей. Рассмотрим любую такую ​​крайнюю точку в многограннике задачи о ранце. Чтобы получить I -линейно независимые гиперплоскости, нам потребуется либо I из граничных ограничений, каждое из которых соответствует уникальной переменной, либо I- 1 линейно независимое граничное ограничение, каждое из которых соответствует уникальной переменной, и 1 ранцевое ограничение. В первом случае крайняя точка будет просто определяться плоскостями, каждая из которых требует, чтобы переменная была двоичной (в {0, 1}), но не между ними. В последнем случае у нас есть переменная I- 1, равная 0 или 1, и, возможно, одна переменная, соответствующая единственной переменной, которая не была частью граничных ограничений I, но Часть ограничения ранца имеет дробное значение в (0, 1).

Это означает, что когда мы решаем релаксацию линейной программы для целочисленной программы с использованием Simplex, это даст нам решение, в котором все переменные являются двоичными, за исключением не более 1 переменной.

На практике это имеет огромное значение. Давайте рассмотрим пример, где, как и в случае с системами Onera, каждая переменная соответствует товару, который может иметь при себе розничный продавец. Розничные торговцы обычно продают и продают миллионы товаров, поэтому эта программа содержит миллионы переменных. В одном быстром решении релаксации линейной программы мы получаем решение, в котором все переменные, кроме одной, являются целыми. Другими словами, у нас действительно есть оптимальное решение, если вы игнорируете только этот единственный продукт во всем каталоге продуктов, которые продает продавец. Действительно, эффект от этого настолько мал, что на практике требуется всего несколько дополнительных релаксаций ветвей и границ, чтобы найти истинную оптимальность, но даже в противном случае решение сразу становится невероятно близким к оптимальному, решая проблему в P. Скорее всего, если у вас есть миллион продуктов, вы можете утверждать, что ваше решение будет мгновенно примерно на 99,99% точным после решения этой релаксации. 0,01% определенно не будет проблемой для ваших моделей на практике.

На вынос. Что все это значит? Вот несколько простых и удобных наблюдений:

  1. Если проблему, которую вы решаете, можно смоделировать как задачу о ранце, не беспокойтесь сразу, что она NP -полная. На самом деле, мы можем радоваться тому, что это рюкзак.
  2. Вышеупомянутое утверждение, конечно, можно обобщить и за пределами рюкзака. В частности, при построении модели целочисленного линейного программирования посмотрите, можно ли ее определить с помощью всего лишь нескольких неграничных ограничений. Количество этих ограничений является верхней границей количества дробных переменных в релаксации линейного программирования. Чем их будет меньше, тем быстрее и ближе к оптимальному решению можно будет получить.

Боковое примечание: хотя на практике вы всегда можете очень быстро собрать рюкзак, он все еще очень NP -завершенный, и «быстро на практике» не переносится на другие NP -полные задачи, такие как k-клика или минимальное дерево Штейнера, которые не только NP -полные, но и также сложно решить на практике. Эти вещи также не влияют на классы сложности, и поэтому такие вещи, как шифрование с открытым ключом, остаются неизменными.