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

[Pietro Scionti]

<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

>Message: 3
>Date: Tue, 5 Jan 2010 09:37:59 -0800 (PST)
>From: xypron <address@hidden>
>Subject: Re: [Bug-glpk] Memory allocation problem
>To: address@hidden
>Message-ID: <address@hidden>
>Content-Type: text/plain; charset=us-ascii
>
>
Hello Pietro,
>
>thank you for your post. The essential line in the output is:
>xmalloc: no memory available
>
>The memory size needed for your model depends does not directly depend on
>the number of
>columns and rows but on the number of non zeroes. For each non zero a
>structure GLPAIJ as
>defined in src/glpapi.h is needed.
>
>On a 32 bit system the size of the structure is 8 + 6 * 4 = 32 bytes, on a
>64 bit system
>8 + 6 * 8 = 56 bytes.
>
>The memory limits per process for Windows are described at
>http://msdn.microsoft.com/en-us/library/aa366778%28VS.85%29.aspx

>My expectation for 342 370 binaries is that you will not be able reach an
>integer solution
>with a brute force approach.
>
>One way to address such a big problem is to use column generation.
>
>Guy Desaulniers ed., "Column Generation", 2005
>is a valuable book on this theme.
>
>Best regards
>
>Xypron
>
>------------------------------
>
>Message: 2
>Date: Tue, 5 Jan 2010 21:33:01 +0300
>From: Andrew Makhorin <address@hidden>
>Subject: Re: [Bug-glpk] Memory allocation problem
>To: Pietro Scionti <address@hidden>
>Cc: "address@hidden" <address@hidden>
>Message-ID: <address@hidden>
>Content-Type: text/plain; charset=us-ascii
>
>Thank you for your report.
>
>It is not a bug. The mathprog translator used all available memory,
>and on a next call to malloc it failed (returned NULL).
>
>Please note that the current glpk mathprog implementation is not
>efficient, so the translator cannot process huge models at least on
>32-bit platforms.
>
>To estimate the amount of memory needed to translate and run mathprog
>models please see:
>http://lists.gnu.org/archive/html/help-glpk/2008-07/msg00044.html
>
>>------------------------------
>>Message: 1
>>Date: Mon, 4 Jan 2010 10:35:41 +0100
>>From: Pietro Scionti <address@hidden>
>>Subject: [Bug-glpk] Memory allocation problem
>>To: "address@hidden" <address@hidden>
>>Message-ID:
>>        <address@hidden>
>>Content-Type: text/plain; charset="us-ascii"
>>
>> Hi everyone,
>> I have been using GLPK for almost a year now to solve integer optimization
>> problems quite satisfactorily, but I'm now encountering a serious problem.
>> The model I'm trying to solve has 342 370 columns (variables are
>> 3-dimensional, in the form of 134 operators x 7 work shifts x 365 days),
>> all of them binary, and I fear an even bigger number of rows which I'm not
>> able to count. When I try to run GLPK (through command line) I get the
>> following log:
>>
>> GLPSOL: GLPK LP/MIP Solver 4.41
>> Parameter(s) specified in the command line:
>>  -m agente.txt -d dati_agente.txt -o out_agente_mipgap100000.txt --mipgap
>> 100000 --log log_mipgap100000.txt
>> Reading model section from agente.txt...
>> agente.txt:90: warning: final NL missing before end of file
>> 90 lines were read
>> Reading data section from dati_agente.txt...
>> dati_agente.txt:24: warning: final NL missing before end of file
>> 24 lines were read
>> Generating Turninelgiorno...
>> Generating RiposiFissiPrimi6Blocchi...
>> Generating RiposiFissiUltimoBlocco...
>> Generating FabbisogniTurniNotturniPerGiorno...
>> Generating NoNotturnoPrimaDiRiposo...
>> Generating StessiNotturniTraOperatori...
>> Generating StessiNotturniSingoliTraOperatori...
>> Generating StessiNotturniSingoliOgniOperatore...
>> Generating DistanzaMinimaTraNottiPerAgenti...
>> Generating assegnazioni...
>> Model has been successfully generated
>> xmalloc: no memory available
>> Error detected in file ..\src\glplib07.c at line 72
>>
>> And a pop-up tells me that "The exception unknown software exception
>> (0x40000015) occurred in the application at location 0x10034999.". I'm not
>> able to debug this myself.
>>
>> Note that this has been transcribed by me reading the prompt since that
>> error prevents the creation of the log itself.
>> I managed to make it work setting the days count to 49; 6 months gave me
>> the same treatment.
>> I got this both on a Pentium 4 2.40 GHz with 2 GB of RAM and on a Core2
>> Duo E8400 3 GHz with 4 GB of RAM, running XP Professional SP 3.
>>
>> Thanks
>> Pietro
>>
>> PS: I think this is the right newsletter, but if you'd rather have me post
>> it on 'help' just tell me


Archimede S.r.l.
Sede Legale:
Via Manzoni, 82
Ponte S. Giovanni

Sede Operativa e Amministrativa:
Via Settevalli, 133/v
06128 Perugia

P.IVA: 01992020543

Tel.  075 515 22 11
Fax. 075 515 22 99
www.archinet.it

**********************************************************************************************************************************************************************************************************************
La presente comunicazione, con le informazioni in essa contenute e ogni 
documento o file allegato, e' rivolta unicamente alla/e persona/e cui e' 
indirizzata ed alle altre da questa autorizzata/e a riceverla. Se non siete i 
destinatari/autorizzati siete avvisati che qualsiasi azione, copia, 
comunicazione, divulgazione o simili basate sul contenuto di tali informazioni 
e' vietata e potrebbe essere contro la legge (art. 616 C.P., D.Lgs n. 196/2003 
Codice in materia di protezione dei dati personali). Se avete ricevuto questa 
comunicazione per errore, vi preghiamo di darne immediata notizia al mittente e 
di distruggere il messaggio originale e ogni file allegato senza farne copia 
alcuna o riprodurne in alcun modo il contenuto.

This e-mail and its attachments are intended for the addressee(s) only and are 
confidential and/or may contain legally privileged information. If you have 
received this message by mistake or are not one of the addressees above, you 
may take no action based on it, and you may not copy or show it to anyone; 
please reply to this e-mail and point out the error which has occurred.
**********************************************************************************************************************************************************************************************************************