Вопрос, недавно опубликованный в sci.op-research, предложил мне долгожданную передышку от некоторой утомительной работы, о которой я предпочел бы не думать, и о которой вы бы не хотели слышать.Мы знаем, что жадная эвристика решает задачу непрерывного ранца максимизировать c'xs.ta′x≤bx≤ux∈ℜ + n (1) до оптимальности.(Доказательство с использованием теории двойственности довольно просто.) Предположим, что мы добавим то, что я назову ограничением подсчета, получая maximizec′xs.ta′x≤be′x = b˜x≤ux∈ℜ + n (2) где е = (1,…, 1).Может ли это быть решено с помощью чего-то другого, кроме симплекс-метода, такого как вариант жадной эвристики?
Ответ - да, хотя я совсем не уверен, что то, что я придумал, легчепрограмма или более эффективный, чем симплекс метод.Лично я хотел бы связать библиотеку с решателем линейного программирования и использовать симплекс, но было забавно найти альтернативу, даже если альтернатива не может быть улучшением по сравнению с симплексом.
Метод, который я представлю, основан наЧто касается двойственности, в частности, хорошо известный результат, что если выполнимое решение линейной программы и выполнимое решение ее дуала удовлетворяют условию дополнительной слабости, то оба являются оптимальными в своих соответствующих задачах.Обозначим двойственные переменные для ограничений по ранцу и счету λ и µ соответственно.Заметим, что λ≥0, но µ неограничен по знаку.По сути, тот же метод, изложенный ниже, будет работать с ограничением числа неравенств (e′x≤b˜), и на самом деле будет немного проще, поскольку мы априори знаем знак µ (неотрицательный).В постере исходного вопроса было указано ограничение на равенство, поэтому я буду этим пользоваться.Существуют также двойственные переменные (ρ≥0) для верхних оценок.Двойственная проблема: минимализмbλ + b˜μ + u′ρs.t.λa + μe + ρ≥cλ, ρ≥0. (3)
Это пост в блоге, а не диссертация, япредположим, что (2) выполнимо, что все параметры строго положительны, а оптимальное решение единственно и не вырождено.Уникальность и вырожденность не приведут к аннулированию алгоритма, но они могут усложнить представление.В оптимальном базовом выполнимом решении (2) будет одна или две базовые переменные - одна, если ограничение на рюкзак не является обязательной, две, если она является обязательной, - с любой другой переменной, не являющейся основной, в нижней или верхней границе.Предположим, что (λ, µ, ρ) является оптимальным решением двойственности (2).Приведенная стоимость любой переменной xi равна ri = ci − λai − µ.Если ограничение по ранцу не является обязательным, то λ = 0 и оптимальным решением является xi = uiri> 0b˜ − ∑rj> 0ujri = 00ri <0. (4) Если ограничение по ранцу является обязательным, будет два элемента (j,k) чьи переменные являются основными, с rj = rk = 0.(Предполагая отсутствие вырожденности, я исключил возможность того, что переменная слабины в ограничении ранца является базовой со значением 0).Положим xi = uiri> 00ri <0 (5) и пусть b ′ = b − ∑i∉ {j, k} aixi и b˜ ′ = b˜ − ∑i∉ {j, k} xi.Две основные переменные задаются как xj = b′ − akb˜′aj − akxk = b′ − ajb˜′ak − aj. (6) </p>
Алгоритм будет проходить в два этапа, сначала ищарешение с несвязанным ранцем (одна базовая переменная x) и затем поиск решения с привязкой ранца (две базовые переменные x).Заметьте, что в первый раз, когда мы найдем выполнимые первичные и двойственные решения, подчиняющиеся дополнительному расслаблению, оба должны быть оптимальными, поэтому мы закончилиТакже отметим, что для любого µ и любого λ≥0 мы можем завершить его, чтобы получить выполнимое решение (3), задав ρi = ci − λai − µ +.Таким образом, мы всегда будем иметь дело с выполнимым двойным решением, и алгоритм будет создавать первичные решения, которые удовлетворяют дополнительному ослаблению.Следовательно, критерий остановки сводится к тому, чтобы построенное первичное решение было выполнимым.
Для первой фазы мы сортируем переменные так, чтобы c1≥ ⋯ ≥cn.Поскольку λ = 0 и существует одна базовая переменная (xh), стоимость которой сниженаt ноль, очевидно, µ = ch. Это означает, что приведенная стоимость ri = ci − λai − μ = ci − ch для xi неотрицательна для ih. Если решение (3) выполнимо, то есть, если ∑ih. Таким образом, мы можем использовать поиск пополам, чтобы завершить этот этап. Если мы примем большое значение n, начальная сортировка может быть выполнена за время O (nlogn), а оставшаяся часть фазы требует O (logn) итераций, каждая из которых использует время O (n).
К сожалению, я не вижу способа применить поиск деления пополам ко второй фазе, в которой мы ищем решения, в которых ограничение по ранцу является обязательным и λ> 0. Мы снова будем искать значение μ, но на этот раз монотонно. Сначала примените жадную эвристику к задаче (1), сохраняя ограничение ранца, но игнорируя ограничение счета. Если решение происходит случайно, чтобы удовлетворить ограничение количества, мы закончили. Однако в большинстве случаев ограничение количества будет нарушено. Если счет превышает b˜, то можно сделать вывод, что оптимальное значение µ в (4) положительно; если отсчет не достигает b˜, оптимальное значение µ является отрицательным. Мы начинаем вторую фазу с μ = 0 и движемся в направлении оптимального значения.
Так как жадный эвристик сортирует элементы так, что c1 / a1≥ ⋯ ≥cn / an, и поскольку мы начинаем с μ = 0, наш текущий порядок сортировки имеет (c1 − μ) / a1≥ ⋯ ≥ (cn − μ ) / ан. Мы сохраним этот порядок (прибегая по мере необходимости) при поиске оптимального значения μ. Чтобы избежать путаницы (я надеюсь), позвольте мне предположить, что оптимальное значение μ положительно, так что мы будем увеличивать μ по мере продвижения. Мы ищем значения (λ, µ), где две из переменных x являются основными, что означает, что две имеют уменьшенную стоимость 0. Предположим, что это происходит для xi и xj; затем
п = 0 = rj⟹ci-λai-μ = 0 = Cj-λaj-μ (7) ⟹ci-μai = λ = Cj-μaj.
Легко показать (оставлено читателю в качестве упражнения), что если (c1 − μ) / a1≥ ⋯ ≥ (cn − μ) / an для текущего значения μ, то следующее более высокое (более низкое) значение μ который создает связь в (7), должен включать в себя последовательную пару последовательных элементов (j = i + 1). Более того, снова отказываясь от вырождения (в данном случае это означает, что более двух элементов с уменьшенной стоимостью 0), если мы слегка подтолкнем μ к значению, при котором элементы i и i + 1 снизили стоимость 0, единственное изменение порядка сортировки будет что пункты i и i + 1 меняются местами. Дальнейшее движение в этом направлении не приведет к тому, что i и i + 1 снова начнут связываться, но, конечно, любой из них может в конечном итоге связать своего нового соседа по дороге.
Второй этап, начиная с μ = 0, происходит следующим образом. Для каждой пары (i, i + 1) вычисляют значение μi μ, при котором (ci − μ) / ai = (ci + 1 − μ) / ai + 1; замените это значение на ∞, если оно меньше текущего значения μ (что указывает на то, что связь происходит в неправильном направлении). Обновите µ до miniμi, вычислите λ из (7) и вычислите x из (5) и (6). Если x является выполнимым (в основном, 0≤xi≤ui и 0≤xi + 1≤ui + 1), stop: x является оптимальным. В противном случае поменяйте местами i и i + 1 в порядке сортировки, установите μi = ∞ (переиндексированные элементы i и i + 1 больше не будут связываться) и пересчитайте μi-1 и μi + 1 (обмен не влияет на другие μj).
Если первая фаза не нашла оптимума (и если жадной эвристике в начале второй фазы не повезло), вторая фаза должна завершиться с оптимумом, прежде чем она исчерпает значения μ для проверки ( все μj = ∞). Вырождение может быть обработано либо с небольшими дополнительными усилиями при кодировании (например, проверка нескольких комбинаций i и j во второй фазе, когда происходят трехсторонние или более высокие связи), либо с помощью небольших возмущений, чтобы сломать вырождение.