Re: [Help-glpk] R: Re: Column Generation

[Haroldo Santos]

Hi Pietro,

Your final solution may not be the optimal one, since column generation should be done at each node of the b&b tree. In some case you may not find a feasible integer solution.

One easy thing you can do to improve the quality of the integer solution is to include more columns: if you include additional columns at the root node (I.e. those with a small or zero reduced cost) you increase your chances that all relevant columns to the MIP problem are already included at the root node.

Cheers

Em 16/03/2014 15:35, "Pietro Scionti" <address@hidden> escreveu:

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

_______________________________________________
Help-glpk mailing list
address@hidden
https://lists.gnu.org/mailman/listinfo/help-glpk