Моделирование комбинаторной оптимизации? проблема

Мне не удалось сопоставить эту проблему с какой-то канонической, и я хотел бы, чтобы некоторые руководства построили/использовали алгоритм и решили его. Описание выглядит следующим образом:

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

InitialOrder = { C1, J1, T1 } with C1, J1, T1 being integer non-negative numbers.

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

InitialPrice = C1 * Pc + J1 * Pj + T1 * Pt with Pc, Pj, Pt being rational positive numbers

В кафетерии также есть «меню завтраков», состоящее из комбинаций стандартных блюд.

full breakfast = coffee + juice + toast
normal breakfast = coffee + toast
bread breakfast = 2 toast

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

Pf < Pc + Pj + Pt
Pn < Pc + Pt
Pb < 2 * Pt
with Pf, Pn, Pb being rational positive numbers

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

FinalOrder = { C2, J2, T2, F, N, B } with C2, J2, T2, F, N, B integer non-negative numbers

и у нас будет FinalPrice ‹= InitialPrice как

FinalPrice = C2 * Pc + J2 * Pj + T2 * Pt + F * Pf + N * Pn + B * Pb with Pc, Pj, Pt, Pf, Pn, Pb as rational positive numbers

Все цены (Pc, Pj, Pt, Pf, Pn и Pb) известны заранее.

Пожалуйста, знаете ли вы, какой подход я должен использовать для построения алгоритма минимизации FinalPrice для данного InitialOrder? Не стесняйтесь спрашивать любые дополнительные детали, которые вам нужны.

Заранее спасибо.


algorithm puzzle combinatorics theory
person fglez    schedule 10.08.2010    source источник

Ответы (3)


arrow_upward
1
arrow_downward

Это похоже на проблему линейного целочисленного программирования.

У вас есть шесть переменных и линейное уравнение (для окончательной цены), которое вам нужно минимизировать, учитывая линейные ограничения (должны соответствовать начальному порядку). Ограничение состоит в том, что переменные неотрицательны и принимают целые значения.

Например, в вашем примере это будет (я предполагаю, что ваша реальная проблема сложнее, чем ваш пример :-))

Минимизировать

C2 * Pc + J2 * Pj + T2 * Pt + F * Pf + N * Pn + B * Pb

(Умножьте Pc и т. д. на подходящее целое число, чтобы сделать их целыми, если это необходимо)

С учетом ограничений, которые

   C2 + F + N = C1
   T2 + F + N + 2B = T1
   J2 + F = J1

В общем случае целочисленное программирование является NP-сложным, но, учитывая небольшой размер проблемы и ограничения, стандартные методы решения, вероятно, могут быстро решить ее за вас.

Надеюсь, это поможет.

person Community    schedule 10.08.2010
comment
Извините, если я ошибаюсь, но я думаю, что шесть последних переменных не являются независимыми (меню составляются из элементов). Можно ли смоделировать это ограничение в LIP? - person fglez; 10.08.2010
comment
@antispam: Да, это те ограничения, о которых я говорил. Я отредактирую ответ, чтобы сделать его более понятным. - person ; 10.08.2010
comment
Я постараюсь следовать этому направлению и обновить вопрос с моими выводами. Спасибо! - person fglez; 10.08.2010
comment
После нескольких успешных тестов я буду использовать симплекс для решения линейной релаксации, а затем переходить и связывать, чтобы найти целочисленное решение, поскольку переменных не так уж много. - person fglez; 11.08.2010
comment
@anti: Рад, что твои тесты прошли успешно. Надеюсь, вы используете один из множества уже написанных решателей :-) - person ; 11.08.2010

arrow_upward
0
arrow_downward

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

Однако, как говорит Морон, для любой крупной проблемы вам понадобится ILP.

person Rafe    schedule 11.08.2010
comment
В конце я буду использовать B&B после симплекса для поиска целочисленных решений. Спасибо за ваш ответ. - person fglez; 11.08.2010
comment
Вам, вероятно, следует попробовать B&B на ванильном поиске в глубину и посмотреть, достаточно ли быстро он находит результаты. Переход от решения LP к целочисленному решению — это что-то вроде черного искусства и обширная область исследований. Если вы ищете высококачественный бесплатный решатель ILP, взгляните на SCIP (scip.zib.de ). - person Rafe; 12.08.2010

arrow_upward
0
arrow_downward

Поскольку ваша проблема тесно связана с упаковкой контейнеров (или, по крайней мере, с ее векторной версией), некоторые из связанных с ней эвристик также могут пригодиться. В частности, жадной эвристики, когда вы сначала жадно упаковываете полные завтраки (или 2 * обычных + тосты в зависимости от относительной стоимости), а затем продолжаете в том же духе, может быть достаточно.

person Suresh    schedule 11.08.2010
comment
В зависимости от цен у него может не быть оптимальной подструктуры, поэтому существует вероятность неоптимального решения. В любом случае спасибо за предложение. - person fglez; 11.08.2010