Re: [Help-glpk] Column generation for 0-1 assignment problems

[xypron]

Hello Pietro,

try to change your main problem such that if there are too few operators on
a shift
this causes a penalty and not an infeasibility. The penalty will direct the
subproblems
to create shift patterns that allow to fill the gap.

Best regards

Xypron


Pietro Scionti wrote:
> 
> <introduction>
> This is a reply to a to thread I started in the Bug mailing list, but
> since the discussion shifted from the bug itself to an open question
> concerning Column Generation, I am posting this new message to the Help
> list as a new thread, attaching all the previous replies in the end.
> </introduction>
> 
> 
> Thank you for your suggestion. I did not reply till now because I got down
> to understanding and studying this approach, which was completely new to
> me.
> I found it really hard to adapt the concept of column generation to my
> model, because it is basically a constrainst feasibility problem and
> optimisation is not a priority, and so "initial set of promising
> variables" and "generating a new variable from the dual problem" seem
> kinda fuzzy concepts in here to me (but it's probably my fault).
> Anyway, I tried generating at first a small number of evenly distributed
> variables per operator: (r is operator, g is day, t is shift, R is a
> constant)
> 
>   (r mod 19 in {1, 2, 3} and g mod 10 in {1, 2} and t != R)
>   or (r mod 19 in {3, 4, 5} and g mod 10 in {2, 3} and t != R)
>   or (r mod 19 in {5, 6, 7} and g mod 10 in {3, 4} and t != R)
>   or ...
> 
> I managed to get the model running with up to (prior to preprocessing) 100
> 000~ rows, 45 000~ columns, 12 000 000~ non-zeros (playing with the above
> sets defining the r & g variables) which decreased to 80 000~, 30 000~ and
> 8 000 000~ respectively after pre-processing, but each time I ran it I got
> "no feasible solution". I infer the constraint which caused the
> infeasibility from the KKT part of the output, and every time it's the
> same constraint, a fundamental one (covering the work shifts needs).
> I think this is a plausible set of initial variables, because it covers
> all the operators (which are divided in groups of 19 for a specific
> reason) uniformly; also, inside each group a single operator is
> indistinguishable from the other, so there is no point in permutating
> those sets.
> Guessing this assumpion is wrong, I tried to generate for each operator a
> pseudo-random sequence of days
> 
>   set RandomDays{Righe} := setof{i in 1..100} round(Uniform(1,365));
> 
> combined with the --seed ? option, but with no gain. I am starting to
> think the model itself in infeasible, but I can't be sure.
> 
> So basically, I couldn't even get to step one of the column generation
> algorithm (find a set of initial variables and solve the related LP
> relaxation)!
> Am I missing something? Is there a tested, "canon" way of approaching
> column generation with 0-1 assignment models? I couldn't find any on the
> internet.
> 
> Thank you anyway,
> Pietro Scionti
> 
> 

-- 
View this message in context: 
http://old.nabble.com/Column-generation-for-0-1-assignment-problems-tp27245277p27291625.html
Sent from the Gnu - GLPK - Help mailing list archive at Nabble.com.