i'm trying solve scheduling problem sports team. decision variables declared as:
dvar int plays[games][0..1] in teams; where games range 0..19 , teams range 0..9 in specific case. forms 20 2 matrix represents teams playing each game.
[ [3, 7], [2, 4], [9, 1] ] is example of 3 game matrix shows team 3 plays team 7 in first game, , team 2 vs team 4, concludes team 9 vs team 1.
in constraints, i'm trying express each team should play close same number of games. attempt @ expressing constraint follows:
subject { gamebalance: standarddeviation(all(t in teams) count(all(g in games, s in 0..1) plays[g][s], t)) < 1; } i believe formulation sound - however, feel i'm running sort of undefined behaviour, constraint not being satisfied though cplex says returns "optimal" solution of [18, 18, 0, 0, 0, 0, 0, 0, 0] 9 team case.
calculating hand, obtain standard deviation of 7.59, not less one. verify this, put following in result data section of model:
int playcounts[teams] = all(t in teams) count(all(g in games, s in 0..1) plays[g][s], t); float std = standarddeviation(all(t in teams) count(all(g in games, s in 0..1) plays[g][s], t)); execute { writeln("counts: " + playcounts); writeln("std: " + std); } which gives following output:
// solution objective 0 counts: [18 18 0 0 0 0 0 0 0] std: 7.48331477 which further confirms constraint wrote not correct. further debug situation, used following constraint instead:
standarddeviation(foo) < 1; where foo declared integer array of [1, 100, 10000, 1000000, 100000000] - not have standard deviation less 1. expected, model shown infeasible, shows standard deviation works expected, problem must in way build array of counts. tried following constraint:
standarddeviation(all(t in teams) count(all(g in games, s in 0..1) plays[g][s], t)) + 2.999999999 < 3; my theory if standard deviation being processed non-zero, should render model infeasible. surprise, model passed same trivial [18, 18, 0, ...] solution above. changing 2.999... 3, model infeasible. thus, conclude standard deviation calculate evaluating 0 in constraint, yet being calculated correctly in result data section after search has concluded.
at point confident problem stems way calculate array of counts ( all(t in teams) count(all(g in games, s in 0..1) plays[g][s], t) ), part not understand why works in result data not in constraints (as shown playcounts print-out above).
furthermore, following constraint works fine:
// total number of games played must 36 sum(t in teams) count(all(g in games, s in 0..1) plays[g][s], t) == 36; which leads me believe problem lies all(t in teams)... portion of constraint. test theory, used following constraint:
// number of games first team plays must 18 (all(t in teams) count(all(g in games, s in 0..1) plays[g][s], t))[0] == 18; in theory, should redundant constraint, since trivial solution being returned begins [18, 18, 0, ...]. surprise, created infeasible model. == 0 instead of == 18, model still infeasible. thus, wanted figure out number evaluating to. end, added following decision variable:
dvar int a; and changed objective function to:
maximize a; with following constraint:
(all(t in teams) count(all(g in games, s in 0..1) plays[g][s], t))[0] == a; which resulted in model had optimal solution. solution had a set -9007199254740991. same result happens if attempt minimize model.
if attempt constrain a non-negative, cplex crashes ### unexpected error.
ultimately, questions are:
- am violating rule of opl , using statements in way shouldn't be?
- if yes above, there legal, valid way express constraint looking for?
- if no above, why opl fail calculate standard deviation in constraint?
Comments
Post a Comment