我正在寻找一种算法来解决以下问题:
假设我正在组织一门类(class)，有300名参与者和6个讲习类，分为3个时间段。
每个参与者都必须在网站上注册，然后选择他想参加的3个研讨会，以及2个储备金选择。
讲习类在时间范围内随机划分，大多数情况下，同一讲习类在多个时间范围内发生。参加者在什么时间跟随讲习类无关紧要。
该算法需要在不同的时间范围内产生理想的与会者分布，以便他们都尽可能地到达那里最喜欢的研讨会。
我可以使用哪种技术来产生这种价差？我可以使用ActionScript或PHP吗？有没有人有很好的榜样？
非常感谢你的帮助!
最佳答案
原则上，对于此类优化问题，您可以在精确求解方法(如线性规划和约束规划)与近似方法(如启发式方法或任何本地搜索形式)(包括诸如遗传算法或模拟退火方法)之间进行选择。
对于您提到的问题大小，我肯定会使用精确的方法，因为只有这些保证您可以找到全局最优值。使用近似方法时，只有在成本测度值为零(例如，没有违反约束条件)的情况下，才能确保找到全局最优值。
版本1:整数编程
您的问题可以看作是Bin Packing的一种变体。对于这种类型的问题，我认为混合整数编程(线性编程的一种形式)是最佳选择。您将不需要MIP求解器，因为您不想自己编程。可能最好的免费软件可以在COIN-OR库中找到:CLP/CBC。对于较小的MIP问题来说可以，但是对于较大的MIP可能会遇到麻烦。对于纯LP问题，这很好，但是对于您的特定问题，您需要积分决策变量，因此需要MIP。对于工业规模的MIP问题，您需要一个商业解决方案。选择CPLEX，Xpress或Gurobi。他们都很棒。
可以对问题进行建模:
对于与会者和研讨会的每种组合
尚未选择参加者的类(class)的
然后，目标是使总成本最小化。
这是ECLiPSe(Prolog的一个变体)中快速编写的示例代码:
:- 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重叠。 (我已经从答案中删除了其余的与会者)
对于此测试，我使用了来自ECINPSe发行版中包含的COIN-OR库的免费CLP/CBC求解器。 COIN-OR还提供C++和Python的API库。
版本2:约束逻辑编程
这是第二个版本，这次使用约束逻辑编程。约束编程是另一种精确的解决方法。在这里，我使用不同的模型:
对于每个与会者
成功进行约束编程的关键是选择一种巧妙的标记策略，将变量绑定(bind)到值上。由于在此示例中，讲习类没有容量限制，因此可以简单地选择首选的讲习类，直到域中仅包含备用讲习类(由于排除限制)。但是，这里的值(value)排序至关重要:必须从重叠最少的研讨会开始。
如果这样做，则无需进行优化:第一个解决方案将是最佳的(由于缺乏容量限制)。否则，将找到接近最佳的解决方案，但随后必须遍历庞大的搜索树以找到更好的解决方案。
这也是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这样的系统，您还可以构建混合算法。