В принципе, для таких задач оптимизации у вас есть выбор между точными методами решения, такими как линейное программирование и программирование ограничений, и приближенными методами, такими как эвристика или любой вариант локального поиска (который включает методы, такие как генетические алгоритмы или имитационный отжиг).
Для размера проблемы, которую вы упомянули, я бы определенно использовал точный метод, поскольку только они гарантируют, что вы найдете глобальный оптимум. Используя приблизительные методы, вы можете быть уверены, что нашли глобальный оптимум только в том случае, если показатель стоимости имеет нулевое значение (например, нет нарушений ограничений).
Версия 1: целочисленное программирование
Вашу проблему можно рассматривать как вариант упаковки для мусора. Для такого типа проблем, на мой взгляд, наилучшим выбором является смешанное целочисленное программирование (вариант линейного программирования). Вам понадобится MIP-решатель, так как вы не хотите программировать его самостоятельно. Вероятно, лучший бесплатный можно найти в библиотеке COIN-OR: CLP / CBC. Это нормально для небольших проблем с MIP, но может столкнуться с проблемами с большими. Для задач с чистым LP это неплохо, но для вашей конкретной задачи вам нужны интегральные переменные решения, а значит, MIP. Для решения проблем MIP промышленного масштаба вам нужен коммерческий решатель. Выберите CPLEX, Xpress или Gurobi. Они все отлично.
Проблема может быть смоделирована следующим образом:
для каждой комбинации участника и семинара вы вводите двоичную переменную решения. Переменная будет равна единице, если посетитель посещает семинар. В вашем примере таких переменных будет 1800.
для каждого участника сумма переменных решения будет равна количеству посещенных семинаров. В вашем примере это три.
для каждого участника, сумма перекрывающихся семинаров не более 1.
стоимость единицы товара взимается, если посетитель должен посетить резервный выбор
переменные решения для курсов, которые посетитель не выбрал, устанавливаются в ноль
Целью является минимизация общих затрат.
Вот быстро написанный пример кода в ECLiPSe (вариант Пролога):
:- lib(eplex).
:- lib(random).
:- lib(listut).
:- local struct(attendee(choices, reserve, workshops)).
generate_attendees(NA, NW, NC, NR, Atts) :-
seed(1), % always generate the same set
( for(I, 1, NW), foreach(I, WD) do true ),
(
for(_I, 1, NA),
foreach(Att, Atts),
param(NC, NR, WD)
do
Att = attendee{},
generate_choices(Att, NC, NR, WD)
).
generate_choices(Att, NC, NR, WD) :-
(
for(_I, 1, NC),
fromto(WD, DI, DO, RD),
foreach(C, Choices)
do
select_course(DI, C, DO)
),
(
for(_I, 1, NR),
fromto(RD, DI, DO, _),
foreach(R, Reserve)
do
select_course(DI, R, DO)
),
Att = attendee{choices:Choices, reserve:Reserve}.
select_course(L, E, RL) :-
length(L, LL),
random(R),
N is R mod LL,
nth0(N, L, E, RL).
solve_with_mip(Atts, NA, NW, NC, Excl) :-
decision_vars(NA, NW, Decs),
workshop_visits(Decs, NA, NW, NC),
workshop_choices(Atts, Decs, NA, NW, Cost),
workshop_exclusions(Decs, NA, Excl),
% set up solver and solve
eplex:eplex_solver_setup(min(Cost), Cost, [], []),
eplex:eplex_solve(Result),
printf("Found solution with cost: %w%n", [Result]),
% retrieve solution
eplex:eplex_get(vars, Vars),
eplex:eplex_get(typed_solution, Vals),
Vars = Vals,
retrieve_solution(Atts, Decs, NA, NW).
% make array of decision variables
decision_vars(NA, NW, Decs):-
dim(Decs, [NA,NW]),
(
multifor(Idx, 1, [NA,NW]),
foreach(D, Ds),
param(Decs)
do
subscript(Decs, Idx, D),
eplex:(D $>= 0),
eplex:(D $=< 1)
),
eplex:integers(Ds).
% each attendee visits NC workshops
workshop_visits(Decs, NA, NW, NC) :-
(
for(AIdx, 1, NA),
param(Decs, NW, NC)
do
(
for(WIdx, 1, NW),
fromto(0, R, D+R, Sum),
param(AIdx, Decs)
do
subscript(Decs, [AIdx, WIdx], D)
),
eplex:(Sum $= NC)
).
% each attendee must not visit a workshop not in
% her list of choices or reserve choices
% choosing a reserve workshop induces a unit cost
workshop_choices(Atts, Decs, NA, NW, Cost):-
(
for(AIdx, 1, NA),
foreach(Att, Atts),
fromto(0, CI, CO, Cost),
param(Decs, NW)
do
Att = attendee{choices:Cs, reserve:Rs},
(
for(WIdx, 1, NW),
fromto(CI, ACI, ACO, CO),
param(Decs, AIdx, Cs, Rs)
do
(
memberchk(WIdx, Cs)
->
% choices do not induce cost
ACO = ACI
;
memberchk(WIdx, Rs)
->
% reserves induce unit cost
% (if decision variable is 1)
subscript(Decs, [AIdx, WIdx], D),
ACO = ACI + D
;
% other workshops must not be chosen
subscript(Decs, [AIdx, WIdx], D),
eplex:(D $= 0),
ACO = ACI
)
)
).
% some workshops overlap, so exclude each other
workshop_exclusions(Decs, NA, Excl) :-
(
foreach(W1-W2, Excl),
param(Decs, NA)
do
(
for(AIdx, 1, NA),
param(Decs, W1, W2)
do
subscript(Decs, [AIdx, W1], D1),
subscript(Decs, [AIdx, W2], D2),
eplex:(D1+D2 $=< 1)
)
).
% retrieve workshopnumbers for attendees
retrieve_solution(Atts, Decs, NA, NW) :-
(
for(AIdx, 1, NA),
foreach(Att, Atts),
param(Decs, NW)
do
(
for(WIdx, 1, NW),
fromto([], WI, WO, Ws),
param(Decs, AIdx)
do
subscript(Decs, [AIdx, WIdx], D),
( D == 1 -> WO = [WIdx|WI] ; WO = WI )
),
Att = attendee{workshops:Ws}
).
test(Atts) :-
NA = 300,
NW = 6,
NC = 3,
NR = 2,
% list of exclusions
Excl = [1-2, 1-3, 3-4, 5-6],
generate_attendees(NA, NW, NC, NR, Atts),
cputime(T1),
solve_with_mip(Atts, NA, NW, NC, Excl),
cputime(T2),
D1 is T2-T1,
printf("Found solution with MIP in %w seconds.%n", [D1]).
Я генерировал посетителей и их выбор случайным образом. Список исключений жестко закодирован. Вот вывод, сгенерированный для прогона:
?- test(Atts).
Found solution with cost: 219.0
Found solution with MIP in 0.119999999999997 seconds.
Atts = [attendee([2, 3, 4], [5, 6], [6, 3, 2]), attendee(...), ...]
Yes (0.12s cpu)
Т.е. в решении 219 раз посетитель был помещен в резервный выбор. Обратите внимание, что это происходит исключительно из-за ограничений на перекрытие, так как в модели нет ограничений по емкости для размеров мастерской. Отобранные семинары для первого посетителя - 2, 3 и 6. Первый выбор [2,3,4] был невозможен, поскольку семинары 3 и 4 частично совпадают. (Я отредактировал остальных участников из ответа)
Для этого теста я использовал бесплатный решатель CLP / CBC из библиотеки COIN-OR, который включен в дистрибутив ECLiPSe. COIN-OR также предлагает библиотеки API для C ++ и Python.
Версия 2: Программирование логики ограничений
Вот вторая версия, на этот раз с использованием Constraint Logic Programming. Ограниченное программирование - это еще один точный метод решения. Здесь я использую другую модель:
для каждого участника составьте список из трех переменных. Эти переменные обозначают назначенные семинары и, следовательно, имеют номера семинаров в качестве домена. Все три переменные должны иметь разные значения.
чтобы нарушить симметрию, я обязуюсь, чтобы переменные увеличивались в своем порядке.
нежелательные мастерские удалены с доменов.
привязка переменных к выбору резерва приводит к удельным затратам
выбор мастерской для одной из переменных удаляет все перекрывающиеся мастерские из области других переменных.
Ключом к успешному программированию ограничений является выбор умной стратегии маркировки, в которой переменные связаны со значениями.Поскольку в этом примере нет ограничений по пропускной способности семинаров, можно просто выбрать предпочтительные семинары, пока домены не содержат только резервные семинары (из-за ограничений исключения).Однако упорядочение значений здесь имеет решающее значение: нужно начинать с семинаров с наименьшим перекрытием.
Если это будет сделано, тогда оптимизация не потребуется: первое решение будет оптимальным (из-за отсутствияограничения емкости).В противном случае можно найти решение, близкое к оптимальному, но затем придется пересечь огромное дерево поиска, чтобы найти лучшее решение.
Вот код, снова в ECLiPSe:
:- lib(ic).
:- lib(random).
:- lib(lists).
:- lib(listut).
:- local struct(attendee(choices, reserve, workshops)).
solve_with_clp(Atts, NA, NW, NC, Excl) :-
decision_vars_clp(NA, NW, NC, Decs),
workshop_choices_clp(Atts, Decs, NA, NW, NC, CostSum),
workshop_exclusions_clp(Decs, NA, NW, Excl, BestOrder),
% solve
Cost #= eval(CostSum),
% order for labeling worskhops
% start with workshop with fewest exclusions
% should be computed!
label(Decs, Atts, BestOrder),
printf("Found solution with cost: %w%n", [Cost]),
% retrieve solution
retrieve_solution_clp(Atts, Decs, NA).
% search solution
label(Decs, Atts, BestOrder) :-
(
foreacharg(A, Decs),
foreach(Att, Atts),
param(BestOrder)
do
Att = attendee{choices:Cs, reserve:Rs},
label_att(A, Cs, Rs, BestOrder)
).
label_att(A, Cs, Rs, BestOrder) :-
(
foreacharg(C, A),
param(Cs, Rs, BestOrder)
do
(
member(V, BestOrder),
memberchk(V, Cs)
;
member(V, BestOrder),
memberchk(V, Rs)
),
C #= V
).
% make array of decision variables
% for each attendee, one variable for every visited course is created
decision_vars_clp(NA, NW, NC, Decs):-
dim(Decs, [NA,NC]),
(
multifor(Idx, 1, [NA,NC]),
foreach(D, Ds),
param(Decs)
do
subscript(Decs, Idx, D)
),
Ds #:: 1..NW,
% for each attendee, each variable must have a different value
(
for(AIdx, 1, NA),
param(Decs, NC)
do
(
for(CIdx, 1, NC),
foreach(C, Cs),
param(Decs, AIdx)
do
subscript(Decs, [AIdx,CIdx], C)
),
alldifferent(Cs),
% break symmetry by requiring ascending order
Cs = [H|T],
(
foreach(C, T),
fromto(H, L, C, _)
do
C #> L
)
).
% each attendee must not visit a workshop not in
% her list of choices or reserve choices
% choosing a reserve workshop induces a unit cost
workshop_choices_clp(Atts, Decs, NA, NW, NC, Cost):-
(
for(AIdx, 1, NA),
foreach(Att, Atts),
fromto(0, CI, CO, Cost),
param(Decs, NW, NC)
do
Att = attendee{choices:Cs, reserve:Rs},
% make list of costs
functor(RCost, c, NW),
(
for(I, 1, NW),
param(Rs, RCost)
do
( memberchk(I, Rs) -> arg(I, RCost, 1) ; arg(I, RCost, 0) )
),
RCost =.. [_|RCL],
% remove unwanted workshops
(
for(CIdx, 1, NC),
param(Decs, AIdx, Cs, Rs, NW)
do
subscript(Decs, [AIdx, CIdx], C),
(
for(I, 1, NW),
param(Cs, Rs, C)
do
(
( memberchk(I, Cs) ; memberchk(I, Rs) )
->
true
;
C #\= I
)
)
),
% add costs for workshops
(
for(CIdx, 1, NC),
fromto(CI, ACI, ACO, CO),
param(Decs, AIdx, RCL)
do
subscript(Decs, [AIdx, CIdx], C),
element(C, RCL, CCost),
ACO = ACI+CCost
)
).
% some workshops overlap, so exclude each other
% assumption: W1 < W2
% also compute best order to label workshops:
% start with lowest number of overlaps
workshop_exclusions_clp(Decs, NA, NW, Excl, BestOrder) :-
(
foreach(W1-W2, Excl),
param(Decs, NA)
do
(
for(AIdx, 1, NA),
param(Decs, W1, W2)
do
subscript(Decs, [AIdx], ACs),
ACs =.. [_|ACList],
(
fromto(ACList, [H|T], T, [_]),
param(W1, W2)
do
(
foreach(N, T),
param(H, W1, W2)
do
( H #= W1 => N #\= W2 ),
( N #= W2 => H #\= W1 )
)
)
)
),
% compute best order for labeling workshops
(
for(W, 1, NW),
foreach(C-W, CWs),
param(Excl)
do
(
foreach(W1-W2, Excl),
fromto(0, I, O, C),
param(W)
do
( memberchk(W, [W1,W2]) -> O is I+1 ; O = I )
)
),
sort(CWs, SCWs),
( foreach(_-W, SCWs), foreach(W, BestOrder) do true ).
% retrieve workshop numbers for attendees
retrieve_solution_clp(Atts, Decs, NA) :-
(
for(AIdx, 1, NA),
foreach(Att, Atts),
param(Decs)
do
subscript(Decs, [AIdx], AD),
AD =.. [_|Ws],
Att = attendee{workshops:Ws}
).
test(Atts1) :-
NA = 300,
NW = 6,
NC = 3,
NR = 2,
% list of exclusions
Excl = [1-2, 1-3, 3-4, 5-6],
generate_attendees(NA, NW, NC, NR, Atts1),
cputime(T1),
solve_with_clp(Atts1, NA, NW, NC, Excl),
cputime(T2),
D is T2-T1,
printf("Found solution with CLP in %w seconds.%n", [D]).
Обратите внимание, что предикаты генерации проблемы такие же, как в решении MIP.Вот вывод для одного прогона:
?- test(A).
Found solution with cost: 219
Found solution with CLP in 0.330000000000002 seconds.
A = [attendee([2, 3, 4], [5, 6], [2, 4, 5]), ...]
Yes (0.34s cpu, solution 1, maybe more)
Как видите, это несколько медленнее, чем решение MIP.Кроме того, реальное решение немного отличается, хотя и имеет одинаковую стоимость.
Какую версию выбрать?Это зависит от того, какие дополнительные ограничения вы ожидаете добавить.Если это ограничения емкости, используйте MIP.Если есть более сложные ограничения, такие как ограничения планирования, тогда CLP будет лучше.С такой системой, как ECLiPSe, вы также можете создавать гибридные алгоритмы.