算法-多个车间和时间段之间的理想分布
算法-多个车间和时间段之间的理想分布
提问于 2012-01-18 00:40:49
我正在寻找一种算法，以解决以下问题：
假设我正在组织一个有300名参与者和6个研讨会的课程，分成3个时间段。
每个与会者必须在网站上注册，并选择他想参加的3个研讨会，以及2个保留选择。
研讨会是在时间范围内随机划分的，大多数相同的研讨会在多个时间范围内发生。与会者在什么时间段内参加研讨会并不重要。
该算法需要在不同的时间范围内生成理想的与会者分布，以便他们都尽可能地获得最喜欢的研讨会……
我可以使用哪种技术来生成此价差？我能用ActionScript或PHP来做吗？有没有人有很好的例子？
非常感谢你的帮助！
回答 4
Stack Overflow用户
回答已采纳
发布于 2012-11-21 18:54:35
我们的最终解决方案在这里：
Stack Overflow用户
发布于 2012-01-18 16:45:29
原则上，对于这样的优化问题，您可以在精确求解方法(如线性规划和约束编程)和近似方法(如启发式方法)或任何风格的局部搜索(包括遗传算法或模拟退火方法)之间进行选择。
对于你提到的问题大小，我肯定会使用精确的方法，因为只有这些方法才能保证你找到全局最优。使用近似方法，只有当成本度量的值为零(例如，没有违反约束)时，您才能确保找到全局最优。
版本1:整数编程
您的问题可以看作是Bin包装的一种变体。对于这类问题，我认为混合整数编程(线性规划的一种变体)是最好的选择。您将需要一个MIP解算器，因为您不想自己编写一个。可能最好的免费版本可以在COIN-OR库中找到: CLP/CBC。对于小的MIP问题，这是可以的，但对于较大的问题，可能会遇到麻烦。对于纯LP问题，这是相当好的，但对于您的特定问题，您需要积分决策变量，因此MIP。对于工业规模的MIP问题，您需要一个商业解决方案。选择CPLEX、Xpress或Gurobi。他们都很优秀。
这个问题可以这样建模：
- 对于与会者和研讨会的每个组合，您都会引入一个二元决策变量。如果与会者访问研讨会，该变量将为1。在您的示例中，将有1800个这样的变量。
- 对于每个与会者，决策变量的总和将是访问过的研讨会的数量。在您的示例中，此值为3。对于每个与会者，重叠研讨会的总和最多为1。如果与会者必须访问保留课程，则会产生单位成本。对于尚未选择的课程，choice
- decision
- 设置为
然后，目标是将总成本降至最低。
下面是一个用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重叠。(我已经从答案中删除了剩余的与会者)
对于这个测试，我使用了来自COIN-OR库的免费的CLP/CBC求解器，该库包含在ECLiPSe发行版中。COIN-OR还为C++和Python提供了API库。
版本2:约束逻辑编程
这是第二个版本，这次使用约束逻辑编程。约束编程是另一种精确求解方法。这里，我使用了一个不同的模型：
- 为每个与会者构建一个包含三个变量的列表。这些变量表示分配的车间，因此具有车间编号作为域。这三个变量必须具有不同的值。为了打破对称性，我强制要求这些变量必须按顺序递增。从domains.
- binding中删除不需要的工作坊
- variables to
- choices unit costs
- choosing a workshop从其他变量的域中删除任何重叠的工作坊。
成功的约束编程的关键是选择一个巧妙的标记策略，其中变量绑定到值。由于在此示例中，研讨会没有容量限制，因此可以简单地选择首选研讨会，直到域仅包含保留研讨会(由于排除限制)。然而，价值排序在这里是至关重要的:必须从重叠最少的研讨会开始。
如果这样做了，那么将不需要优化:第一个解决方案将是最优的(由于缺乏容量限制)。否则，人们将找到一个接近最优的解决方案，但随后将不得不遍历巨大的搜索树来找到更好的解决方案。
下面是代码，同样是用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这样的系统，您还可以构建混合算法。
Stack Overflow用户
发布于 2012-01-18 01:08:01
要查看的一些基本说明：
Genetic Algorithms是解决这一问题的典型方法。而他们不能保证最好的日程安排。他们可以确保一个足够好的。
需要注意的事情。一旦所有的预订完成，你就会想要运行它。你不能在飞行中做到这一点，给每个新来的人一个时间表，因为他们预订了座位。事实上，没有任何方法可以做到这一点，并达到问题的最佳解决方案。
Genetic Programming也是通用调度器的常用方法。然而，这可能有些夸张，因为您不需要通用的解决方案，只需要一个特定于您的会议格式的解决方案。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/8898334
复制相关文章
相似问题
腾讯云开发者
