假设我正在组织一个有300名与会者和6个研讨会的课程,分为3个时间框架.
每位与会者都必须在网站上注册,并选择他想参加的3个研讨会,以及2个预备选择.
研讨会在时间范围内随机分配,大多数研讨会在多个时间框架内进行.与会者在研讨会之后的时间框架无关紧要.
该算法需要在不同的时间范围内产生理想的参与者传播,以便他们尽可能地获得最喜欢的研讨会……
我可以使用哪种技术来产生这种传播？我可以使用ActionScript或PHP来完成吗？有没有人有一个很好的例子？
非常感谢你的帮助！
对于你提到的问题大小,我肯定会使用一个精确的方法,因为只有这些才能保证你找到全局最优.使用近似方法,如果成本度量值为零(例如,没有约束违规),则只能确保找到全局最优值.
版本1：整数编程
您的问题可以看作是Bin Packing的变种.对于这类问题,混合整数规划(线性规划的一种变体)是我认为的最佳选择.你需要一个MIP求解器,因为你不想自己编程.可能最好的免费版本可以在COIN-OR库中找到：CLP / CBC.这对于小型MIP问题是可以接受的,但是对于较大的MIP问题可能会遇到麻烦.对于纯LP问题,它非常好,但对于您的特定问题,您需要积分决策变量,因此需要MIP.对于工业级MIP问题,您需要一个商业解算器.选择CPLEX,Xpress或Gurobi.他们都非常出色.
这个问题可以这样建模：
>对于与会者和研讨会的每个组合,您将引入二元决策变量.如果与会者访问研讨会,该变量将为1.在您的示例中,将有1800个此类变量.
>对于每位与会者,决策变量的总和将是访问过的研讨会的数量.在您的示例中,这是三个.
>对于每位与会者,重叠研讨会的总和最多为1.
>如果参加者必须参加预订选择,则会产生单位成本
>参加者未选择的课程的决策变量设置为零
然后,目标是最小化总成本.
这是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,NA),foreach(Att,Atts),param(NC,WD)
do
Att = attendee{},generate_choices(Att,WD)
).
generate_choices(Att,WD) :-
(
for(_I,NC),fromto(WD,DI,DO,RD),foreach(C,Choices)
do
select_course(DI,C,DO)
),NR),fromto(RD,_),foreach(R,Reserve)
do
select_course(DI,R,Att = attendee{choices:Choices,reserve:Reserve}.
select_course(L,E,RL) :-
length(L,LL),random(R),N is R mod LL,nth0(N,L,RL).
solve_with_mip(Atts,NA,Excl) :-
decision_vars(NA,Decs),workshop_visits(Decs,workshop_choices(Atts,Decs,Cost),workshop_exclusions(Decs,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,NW).
% make array of decision variables
decision_vars(NA,Decs):-
dim(Decs,[NA,NW]),(
multifor(Idx,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,NC) :-
(
for(AIdx,param(Decs,NC)
do
(
for(WIdx,fromto(0,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,Cost):-
(
for(AIdx,CI,CO,NW)
do
Att = attendee{choices:Cs,reserve:Rs},(
for(WIdx,fromto(CI,ACI,ACO,CO),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,ACO = ACI + D
;
% other workshops must not be chosen
subscript(Decs,eplex:(D $= 0),ACO = ACI
)
)
).
% some workshops overlap,so exclude each other
workshop_exclusions(Decs,Excl) :-
(
foreach(W1-W2,NA)
do
(
for(AIdx,W1,W2)
do
subscript(Decs,W1],D1),subscript(Decs,W2],D2),eplex:(D1+D2 $=< 1)
)
).
% retrieve workshopnumbers for attendees
retrieve_solution(Atts,NW) :-
(
for(AIdx,NW)
do
(
for(WIdx,fromto([],WI,WO,Ws),AIdx)
do
subscript(Decs,( 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,cputime(T1),solve_with_mip(Atts,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,2]),attendee(...),...] Yes (0.12s cpu)
即,在解决方案中,有219名与会者被安排在预备选择中.请注意,这纯粹是由于重叠排除约束,因为模型中的车间规模没有容量限制.为第一位与会者选定的研讨会是2,3和6. [2,4]的第一选择是不可行的,因为研讨会3和4重叠. (我已经从答案中删除了其余的与会者)
对于此测试,我使用了COIN-OR库中的免费CLP / CBC解算器,该解算器包含在ECLiPSe发行版中. COIN-OR还为C和Python提供API库.
版本2：约束逻辑编程
这是第二个版本,这次使用Constraint Logic Programming.约束编程是另一种精确的解决方法.在这里,我使用不同的模型：
>为每位与会者,构建一个包含三个变量的列表.这些变量表示指定的研讨会,因此将研讨会编号作为域.所有三个变量必须具有不同的值.
>为了打破对称性,我强制要求变量必须按顺序增加.
>从域中删除不需要的研讨会.
>将变量绑定到保留选择会导致单位成本
>为其中一个变量选择一个研讨会,从其他变量的领域中删除任何重叠的研讨会.
成功的约束编程的关键是选择一个聪明的标记策略,其中变量绑定到值.由于在此示例中,研讨会没有容量限制,因此可以简单地选择首选研讨会,直到域仅包含预留研讨会(由于排除约束).但是,价值排序在这里至关重要：必须从最少重叠的研讨会开始.
如果这样做,那么就不需要进行优化：第一个解决方案将是最优的(由于缺乏容量限制).否则,人们会找到一个接近最优的解决方案,但是必须遍历一个巨大的搜索树才能找到更好的解决方案.
这是代码,再次在ECLiPSe中：
:- lib(ic).
:- lib(random).
:- lib(lists).
:- lib(listut).
:- local struct(attendee(choices,workshops)).
solve_with_clp(Atts,Excl) :-
decision_vars_clp(NA,workshop_choices_clp(Atts,CostSum),workshop_exclusions_clp(Decs,Excl,BestOrder),% solve
Cost #= eval(CostSum),% order for labeling worskhops
% start with workshop with fewest exclusions
% should be computed!
label(Decs,Atts,[Cost]),% retrieve solution
retrieve_solution_clp(Atts,NA).
% search solution
label(Decs,BestOrder) :-
(
foreacharg(A,param(BestOrder)
do
Att = attendee{choices:Cs,label_att(A,Rs,BestOrder)
).
label_att(A,BestOrder) :-
(
foreacharg(C,A),param(Cs,BestOrder)
do
(
member(V,memberchk(V,Cs)
;
member(V,Rs)
),C #= V
).
% make array of decision variables
% for each attendee,one variable for every visited course is created
decision_vars_clp(NA,NC]),D)
),Ds #:: 1..NW,% for each attendee,each variable must have a different value
(
for(AIdx,NC)
do
(
for(CIdx,Cs),CIdx],C)
),alldifferent(Cs),% break symmetry by requiring ascending order
Cs = [H|T],(
foreach(C,T),fromto(H,_)
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,NC)
do
Att = attendee{choices:Cs,% make list of costs
functor(RCost,c,(
for(I,param(Rs,RCost)
do
( memberchk(I,Rs) -> arg(I,RCost,1) ; arg(I,0) )
),RCost =.. [_|RCL],% remove unwanted workshops
(
for(CIdx,NW)
do
subscript(Decs,C),(
for(I,C)
do
(
( memberchk(I,Cs) ; memberchk(I,Rs) )
->
true
;
C #\= I
)
)
),% add costs for workshops
(
for(CIdx,RCL)
do
subscript(Decs,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,BestOrder) :-
(
foreach(W1-W2,[AIdx],ACs),ACs =.. [_|ACList],(
fromto(ACList,[H|T],T,[_]),param(W1,W2)
do
(
foreach(N,param(H,W2)
do
( H #= W1 => N #\= W2 ),( N #= W2 => H #\= W1 )
)
)
)
),% compute best order for labeling workshops
(
for(W,foreach(C-W,CWs),param(Excl)
do
(
foreach(W1-W2,I,O,param(W)
do
( memberchk(W,[W1,W2]) -> O is I+1 ; O = I )
)
),sort(CWs,SCWs),( foreach(_-W,foreach(W,BestOrder) do true ).
% retrieve workshop numbers for attendees
retrieve_solution_clp(Atts,NA) :-
(
for(AIdx,AD),AD =.. [_|Ws],Att = attendee{workshops:Ws}
).
test(Atts1) :-
NA = 300,Atts1),solve_with_clp(Atts1,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,[2,4,5]),...] Yes (0.34s cpu,solution 1,maybe more)
如您所见,它比MIP解决方案慢一些.而且,实际的解决方案略有不同,尽管它具有相同的成本.
你应该选择哪个版本？这取决于您希望添加的进一步约束.如果是容量限制,请使用MIP.如果有更复杂的约束,比如调度约束,那么CLP会更好.使用像ECLiPSe这样的系统,您还可以构建混合算法.
