Решение линейного программирования за один проход с упорядоченными переменными

9

У меня есть семейство задач линейного программирования: максимизировать учетом , . Элементы , и являются неотрицательными целыми числами, строго положительными. ( также должен быть целым, но я буду беспокоиться об этом позже.)cxAxbx0Abccx

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

Этот алгоритм работает, когда столбцы и элементы отсортированы от «дешевых» до «дорогих». «Дешевая» переменная - это столбец с обычно небольшими значениями, для которого соответствующий элемент большой: для этого элемента вы получаете много выходных данных с не очень большой нагрузкой на ограничение . Таким образом, алгоритм просто говорит «делай сначала простые вещи».AcAcxb

Мой вопрос: какое свойство и может заверить нас, что этот упрощенный алгоритм работает для всех ? Моя первоначальная гипотеза состояла в том, что ненулевые элементы должны увеличиваться в каждой строке, но это не правильно.AcbA

Вот несколько примеров, все с : c=(1,1,1)A1=(111123320) , A2=(001302032), A3=(111100101), A4=(101010011), Для всего этого последовательный алгоритм дает оптимальное решение для всех значенийb (путем численных экспериментов). A3 это единственный, для которого все перестановки столбцов также работают. A1 а также A3 особенно сбивают с толку, так как (1,1,3) выглядит дороже, чем (1,3,0) а также (1,1,1) дороже чем (1,0,0),

Я был бы чрезвычайно признателен за любые ссылки на литературу, за любые подобные проблемы, или любые предложения вообще. Должны быть и другие случаи, когда некоторые переменные могут быть определены как «более дешевые», чем другие, и их можно безопасно сделать в первую очередь. Со всей работой, проделанной за линейное программирование на протяжении многих лет, кажется, что-то похожее должно было произойти, но я не смог найти это.

Роберт Алмгрен
источник

Ответы:

4

Вероятно, наиболее известный случай, когда жадный алгоритм, как известно, решает LP, относится к частному случаю проблемы транспортировки. Хоффман («О простых линейных программах», в выпуклости , том 7 « Трудов симпозиумов по чистой математике» , стр. 317-327, 1963) доказал, что если матрица затрат для (максимизации) транспортной задачи удовлетворяет свойству Монжа (cij+cklcil+ckj когда 1i<kn, 1j<ln) тогда оптимальное решение может быть найдено жадным способом, подобным тому, который вы описываете.

У Хоффмана также есть обзорная статья (« О жадных алгоритмах, которые преуспевают ») от 1985 года, в которой он обсуждает известные случаи, когда жадный алгоритм дает оптимальное решение для LP. Помимо его собственной работы, процитированной выше (о которой он говорит, «большинство проблем линейного программирования, известных [к 1963 г.] как восприимчивые к жадному алгоритму, были частными случаями идеи Монжа»), он упоминает интерпретацию Эдмондса линейного программирования обобщение матроидов и обсуждение случая, когдаA неотрицательный, между прочим.

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

Майк Спиви
источник
2
Я хотел бы поблагодарить профессора Спиви за его предложение. Мне потребовалось некоторое время, чтобы преследовать ссылки, но я предоставлю более полное описание в качестве ответа.
Роберт Алмгрен
3

Благодаря предложению профессора Спиви я, наконец, нашел то, что я считаю современным: Ульрих Фейгл, Алан Дж. Хоффман и Уолтер Керн, «Характеристика неотрицательных матриц Бокса-Жадности», SIAM J. Disc. Математика 9 (1996), стр. 1-6. Матрица «жадная», если алгоритм, который я описал выше, дает оптимальное решение для всехb, Матрица является «коробчато-жадной», если жадный алгоритм дает оптимальное решение с дополнительным условиемxd для всех b и все d0, Ясно, что жадность в поле - более сильное условие, чем жадность.

Всегда предполагайте, что c1cn>0, Файгл, Хоффман и Керн доказывают этоA коробка жадная, если и только если она не имеет k×(k+1) (для любой k) подматрица формы (r1s1r2s2rksk) с каждым rj>0 а также i:si>0risi>1, При извлечении подматриц допускаются произвольные перестановки строк, но не столбцов, а также разрешается произвольная подстановка строк и столбцов. Таким образом, в частности, сk=1ненулевые элементы в каждом ряду A должно быть неубывающим.

К сожалению, оказывается, что в моей задаче матрицы не являются жадными, хотя я все еще считаю, что они жадные. Например, в моемA1выше условие нарушается, и эта матрица не является жадной, хотя она жадная. Насколько я знаю, результатов по выявлению жадных матриц нет.

Роберт Алмгрен
источник
Я рад, что мой ответ помог вам найти это!
Майк Спиви
3

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

анонимный
источник