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