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" <[email protected]> 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:[email protected]] > Inviato: mercoledì 12 marzo 2014 18:47 > A: Andrew Makhorin > Cc: Pietro Scionti; [email protected] > 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: "[email protected]" <[email protected]> > > 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 > > [email protected] > > 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 > [email protected] > https://lists.gnu.org/mailman/listinfo/help-glpk >
_______________________________________________ Help-glpk mailing list [email protected] https://lists.gnu.org/mailman/listinfo/help-glpk
