[Help-glpk] Stop criterion

[glpk xypron]

Hello Andrew,

for assigment problems where the objective can only be integer the lower bound 
of each node in the search tree can always be rounded to the next lower/higher 
integer (depending on optimization direction).

Probably automatic identification is difficult. It would be great if you could 
define an option on glpsol to enable such behaviour manually.

See example below.

Best regards

Xypron


# kids
set K := {1..6};
# games
set G := {1..6};
# team assignment
var t{K,G}, binary;
# same team
var s{K,K,G}, >=0, <=1;
# equality measure
var o;

maximize obj: o;

# >= o times on same team
s.t. c1{i in K, j in K : i < j} :
  o <= sum{g in G} s[i,j,g];
# >= o times on different team
s.t. c2{i in K, j in K : i < j} :
  o <= card(G) - sum{g in G} s[i,j,g];

# both on team 1
s.t. c3{i in K, j in K, g in G} :
  s[i,j,g] >= t[i,g] + t[j,g] - 1;
# both on team 0
s.t. c4{i in K, j in K, g in G} :
  s[i,j,g] >= 1 - t[i,g] - t[j,g];

# first on team 1, second on team 0
s.t. c5{i in K, j in K, g in G} :
  s[i,j,g] <= 1 + t[i,g] - t[j,g];
# first on team 0, second on team 1
s.t. c6{i in K, j in K, g in G} :
  s[i,j,g] <= 1 - t[i,g] + t[j,g];

# teams are of same size
s.t. c7{g in G} :
  sum{k in K} t[k,g] = floor(.5 * card(K));

solve;

display t;

end;



-------- Original-Nachricht --------
> Datum: Fri, 13 Apr 2012 10:37:52 -0500 (CDT)
> Betreff: Re: [Help-glpk] Fair soccer team split problem

> On Fri, 13 Apr 2012, Andreas F wrote:
> 
> > For a team of 17 kids I am assigned to split the group into 2 teams for
> each match.  Lets say there are 20 matches in a season.  The objective is
> to divide the group such that each kid spend equally many matches together
> with any other kid (i.e. no two kids play most games on same team, while two
> almost never play on same team).
> >
> > Using perl I have quickly created a script to randomly create teams. I
> would like it to be *fair*, but this approach isn't fair with only 20
> matches (i.e. solutions).
> 
> > Is it feasible to use glpk to model this?
> 
> Yes, but you won't like it.
> First of all, exact fairness is impossible.
> With 17 kids and 20 matches,
> some kid will be on the small team more often than the others.
> No pair occurs no more than one more often than any other probably works.
> The most straightforward model is an array of binaries:
> For match m, kid k is on team team[m][k].
> You will need auxillary variables same[m][k1][k2].
> same[m][k1][k2]==1 iff kid k1 is on the same team as kidk2 in match , else
> 0.
> same[m][k1][k2]==same[m][k2][k1].
> In principle, same would not have to be declared integer,
> but probably should be.
> 
> There are horrible symmetries.
> Matches and kids are both fungible.
> 
> To alleviate those symmetries, you might generate a random schedule
> and minimize some measure of the deviation from that schedule.
> You can tell the solver to stop at the first solution.
> 
> The constraints are left as an exercise for the reader.
> 
> -- 
> Michael   address@hidden
> "On Monday, I'm gonna have to tell my kindergarten class,
> whom I teach not to run with scissors,
> that my fiance ran me through with a broadsword."  --  Lily
> 

-- 
Follow me at http://twitter.com/#!/xypron

Empfehlen Sie GMX DSL Ihren Freunden und Bekannten und wir
belohnen Sie mit bis zu 50,- Euro! https://freundschaftswerbung.gmx.de