StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>In principle, for optimization problems like this you have the choice between exact solving methods like Linear Programming and Constraint Programming, and approximate methods like heuristics or any flavour of Local Search (which includes methods like Genetic Algorithms or Simulated Annealing).</p> <p>For the problem size that you mentioned, I would definitely use an exact method, since only these guarantee that you find the global optimum. With approximate methods, you can only be sure that you found the global optimum if the cost measure has a value of zero (e.g., no constraint violations).</p> <p><strong>Version 1: Integer Programming</strong></p> <p>Your problem can be seen as a variant of Bin Packing. For this type of problem, Mixed Integer Programming (a variant of Linear Programming) is the best choice in my opinion. You will need a MIP solver, since you don't want to program one yourself. The probably best free one can be found in the COIN-OR library: CLP/CBC. It's okay-ish for small MIP problems, but may run into troubles with larger ones. For pure LP problems, it's quite good, but for your particular problem, you need integral decision variables, hence MIP. For industrial-sized MIP problems, you need a commercial solver. Take your pick of CPLEX, Xpress, or Gurobi. They are all excellent.</p> <p>The problem can be modelled thus:</p> <ul> <li><p>for each combination of attendee and workshop, you introduce a binary decision variable. The variable will be one if the attendee visits the workshop. In your example, there will be 1800 such variables.</p></li> <li><p>for each attendee, the sum of the decision variables will be the number of visited workshops. In your example, this is three.</p></li> <li><p>for each attendee, the sum of overlapping workshops is at most 1.</p></li> <li><p>a unit cost is induced if an attendee must visit a reserve choice</p></li> <li><p>decision variables for courses that an attendee has not selected are set to zero</p></li> </ul> <p>The objective is then to minimize the overall cost.</p> <p>Here's a quickly written example code in ECLiPSe (a variant of Prolog):</p> <pre><code>:- 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]). </code></pre> <p>I have generated attendees and their choices randomly. The exclusion list is hard-coded. Here is the output generated for a run:</p> <pre><code>?- 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) </code></pre> <p>I.e., in the solution, 219 times an attendee was placed in a reserve choice. Note that this is purely due to the overlap exclusion constraints, since there are no capacity constraints on the workshop sizes in the model. The selected workshops for the first attendee are 2, 3, and 6. The first choice of [2,3,4] was infeasible, since workshops 3 and 4 overlap. (I have edited out the remaining attendees from the answer)</p> <p>For this test, I have used the free CLP/CBC solver from the COIN-OR library, which is included in the ECLiPSe distribution. COIN-OR also offers API libraries for C++ and Python.</p> <p><strong>Version 2: Constraint Logic Programming</strong></p> <p>Here is a second version, this time using Constraint Logic Programming. Constraint Programming is another exact solution method. Here, I use a different model:</p> <ul> <li><p>for each attendee, construct a list of three variables. These variables denote the assigned workshops, and hence have the workshop numbers as domain. All three variables must have different values.</p></li> <li><p>in order to break symmetries, I enforce that the variables must be increasing in their order.</p></li> <li><p>the unwanted workshops are removed from the domains.</p></li> <li><p>binding the variables to reserve choices induces unit costs</p></li> <li><p>choosing a workshop for one of the variables removes any overlapping workshop from the domain of the other variables.</p></li> </ul> <p>The key for successful Constraint Programming is selecting a clever labeling strategy, where the variables are bound to values. Since in this example, there are no capacity constraints on the workshops, one can simply choose preferred workshops until the domains contain only reserve workshops (due to the exclusion constraints). However, the value ordering is crucial here: one must start with the workshops with the fewest overlap.</p> <p>If this is done, then no optimization will be necessary: the first solution will be optimal (thanks to the lack of capacity constraints). Otherwise, one will find a solution that is close to optimal, but then will have to traverse a huge search tree to find a better solution.</p> <p>Here's the code, again in ECLiPSe:</p> <pre><code>:- 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]). </code></pre> <p>Note that the problem generation predicates are the same as in the MIP solution. Here's the output for one run:</p> <pre><code>?- 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) </code></pre> <p>As you can see, it's somewhat slower than the MIP solution. Also, the actual solution is slightly different, although it has the same cost.</p> <p>Which version should you choose? It depends on what further constraints you expect to add. If it's capacity constraints, use MIP. If there it's more complicated constraints like scheduling constraints, then CLP will be better. With a system like ECLiPSe you could also construct hybrid algorithms.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload