[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] Stop criterion

From: Michael Hennebry
Subject: Re: [Help-glpk] Stop criterion
Date: Fri, 13 Apr 2012 16:58:45 -0500 (CDT)
User-agent: Alpine 1.00 (DEB 882 2007-12-20)

On Fri, 13 Apr 2012, glpk xypron wrote:

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.

# 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;

Just declare o to be integer.

Note that o will have very few likely values.
The probable optimum is 2(K/2)(K/2-1)G/(K(K-1)),
where all divisions truncate,
K is the number of kids and G is the number of games.
I think that the linear relaxation will truncate to that,
but I'm not sure.

Note also, that you still have horrible symmetries.
Kids are fungible.
Games are fungible.
Teams are fungible.

I'd constrain o and minimize the deviation
from some solution selected at random.

If it helps,
any valid assignment for the first game is as good as any other.

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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]