[Help-glpk] R: Re: Column Generation

[Pietro Scionti]

Andrew, Heinrich,
would it be correct then if I just solved the continuous relaxation of my 
problem via column generation, take the generated columns and then run the 
original MIP problem (no col generation, just try to solve it to optimality) 
with those variables only?
Would I have any hope, I dare not say guarantee, that I would get a good 
solution to my MIP problem?
Keep in mind that due to the complexity of the problem, I could be satisfied 
with a close to optimal solution; solvability and speed are the main 
requirements

Thanks again and sorry if what I said makes no sense :-)
Pietro

-----Messaggio originale-----
Da: Heinrich Schuchardt [mailto:address@hidden
Inviato: mercoledì 12 marzo 2014 18:47
A: Andrew Makhorin
Cc: Pietro Scionti; address@hidden
Oggetto: Aw: Re: [Help-glpk] Column Generation

Hello Pietro,

http://www.xypron.de/viewvc/svn/glpk/branches/glpk-4.38-dot/src/glpapi16.c?view=markup
shows how function glp_mpl_postsolve could be patched to provide the dual cost 
of the LP problem, which results from fixing all integers to their optimal 
value.
cf.
http://lists.gnu.org/archive/html/help-glpk/2010-05/msg00013.html

This value then could be accessed in the GMPL language (ie in glpsol).

http://code.google.com/p/cspsol/
might be of interest to you.

Best regards

Heinrich Schuchardt

http://www.xypron.de


> Gesendet: Mittwoch, 12. März 2014 um 17:38 Uhr
> Cc: "address@hidden" <address@hidden>
> Betreff: Re: [Help-glpk] Column Generation
>
>
> > I am trying to develop a column generation algorithm for a MIP
> > problem
>
> Please note that glpk mip solver does *not* support column generation.
> Only rows (lazy constraints and/or cutting planes) can be added to
> subproblems during the search.
>
> >  and I want to calculate the reduced costs of my variables.
> >
> > I do not have access to the API but I can only call the glpsol
> > executable and so I thought I would  use the .dual suffix after
> > “--read"ing the solution of the current subproblem.
> >
> > The problem is that the .dual function always returns 0, for every
> > structural variable.
> >
> > I thought that the problem was I have a MIP problem instead of a LP
> > problem. So I ran glpsol with the --nomip option but the result is
> > still 0!
> >
> > What am I doing wrong?
> >
>
> If your mathprog model has integer variables, it is considered as mip
> independently on --nomip option. The latter affects only output from
> the problem object (e.g. -o option) and doesn't affect which solution
> components (lp or mip) go into the model. And since for mip solution
> dual variables have no meaning, they all are set to zero.
>
>
>
>
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> https://lists.gnu.org/mailman/listinfo/help-glpk
>


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

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.
**********************************************************************************************************************************************************************************************************************