Re: [Help-glpk] lp/mip preprocessor api
On Mon, 2018-05-07 at 11:08 -0300, Luiz Rafael dos Santos wrote:
> Dear Andrew,
>
>
> As I said to you before, I was trying to make the new preprocessor API
> of GLPK work on Julia (http://github.com/JuliaOpt/GLPK.jl). Indeed, it
> worked like a charm! Thanks for that
>
>
> However now, on the multiple test we run on GLPK.jl, the
> `ios_del_row()` routine is not working.
>
>
> I believe this is happening because now, on version 4.65, at
> glpios01.c, lines 1550-1553:
> ```#ifdef NEW_LOCAL /* 02/II-2018 */
> void ios_del_row(glp_tree *tree, IOSPOOL *pool, int i)
> { /* remove row (constraint) from the cut pool */
> xassert(0);
> }
> #elsedef```
> the routine is not defined anymore.
>
>
> Is this a feature that will become obsolete and will be removed?
>
>
> Is this a bug?
Neither. ios_del_row is just not reimplemented for NEW_LOCAL. However,
now IOSPOOL which is a synonym for glp_pool is also a synonym for
glp_prob (i.e. cut pool is implemented as an ordinary problem object).
So, if needed, you may replace it with the following routine:
void ios_del_row(glp_tree *tree, IOSPOOL *pool, int i)
{ /* remove row (constraint) from the cut pool */
int num[2];
num[1] = i;
glp_del_rows(pool, 1, num);
return;
}
See, for example, ios_clear_pool below in the same file.
Best regards,
Andrew Makhorin
>
>
> Best regards,
>
>
> Rafa
>
>
>
>
> --
> Luiz Rafael dos Santos
> Departamento de Matemática
> Centro de Blumenau
> Universidade Federal de Santa Catarina
> Blumenau/SC/Brasil
> Fone: +55 47 3232 5184 / +55 48 3721 3384
> Voip: +55 48 3363 2267
>
> > Em 19 de mar de 2018, à(s) 20:52, Luiz Rafael dos Santos
> > escreveu:
> >
> > That’s great.
> >
> >
> > Thank Andrew for your work with GLPK.
> >
> >
> > Cheers,
> >
> >
> > Rafa
> > --
> > Luiz Rafael dos Santos
> > Departamento de Matemática
> > Centro de Blumenau
> > Universidade Federal de Santa Catarina
> > Blumenau/SC/Brasil
> > Fone: +55 47 3232 5184 / +55 48 3721 3384
> > Voip: +55 48 3363 2267
> >
> > > Em 19 de mar de 2018, à(s) 14:52, Andrew Makhorin
> > > escreveu:
> > >
> > > Hi Luiz,
> > >
> > >
> > > > I’m Prof. Rafael Santos from University of Santa Catarina,
> > > > Brazil.
> > > > I would like to use your LP/MIP preprocessor API together with
> > > > Julia
> > > > GLPK, for a paper I’m writing on a new method for LP that makes
> > > > use of
> > > > a Augmented Lagrangian method.
> > >
> > > Thank you for your interest in glpk.
> > >
> > > > Do you have any timetable to release such API?
> > >
> > > This feature is already implemented in glpk 4.65; please see
> > > http://lists.gnu.org/archive/html/help-glpk/2018-02/msg9.html
> > >
> > >
> > > Best regards,
> > >
> > > Andrew Makhorin
> > >
> > >
> > >
> >
> >
>
>
___
Help-glpk mailing list
Help-glpk@gnu.org
https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] lp/mip preprocessor api
Please see attached a description of an initial version of the LP/MIP preprocessing routines. Any comments/suggestions are appreciated. Thank you, Andrew Makhorin npp.txt.gz Description: GNU Zip compressed data ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] lp/mip preprocessor api
Hi Chris, > > There is no need (and technically it'd be difficult) to load Q > back into > the PP wksp. It would be sufficient to provide some specific > preprocessor routines that allows, for example, fixing a > column or add a > row to the current instance residing in the workspace. > > > If I understand correctly, currently glp_npp_build_prob() frees almost > all problem data from the workspace, keeping only the references > needed for glp_npp_load_sol() and glp_npp_recover_sol(). This is a > reasonable design since in most cases there is no need to keep the > additional data in the workspace. However this means that after > calling glp_npp_build_prob() no further preprocessing can be done > using the same workspace, and that glp_npp_build_prob() can only be > called once. Currently, yes, npp_build_prob removes that data from the workspace. However on api level there will be a flag not to do that. I think to implement an initial version of api and then to see what needs to be added or improved. Best, Andrew Makhorin ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] lp/mip preprocessor api
Hi Andrew, > There is no need (and technically it'd be difficult) to load Q back into > the PP wksp. It would be sufficient to provide some specific > preprocessor routines that allows, for example, fixing a column or add a > row to the current instance residing in the workspace. > If I understand correctly, currently glp_npp_build_prob() frees almost all problem data from the workspace, keeping only the references needed for glp_npp_load_sol() and glp_npp_recover_sol(). This is a reasonable design since in most cases there is no need to keep the additional data in the workspace. However this means that after calling glp_npp_build_prob() no further preprocessing can be done using the same workspace, and that glp_npp_build_prob() can only be called once. The patch I sent earlier associates the references left in the workspace with the rows/columns of the problem when glp_npp_load_prob() is called a second time, so that the solution to the original problem can still be recovered. For an unmodified problem the workspace would be in the same state it was right before calling glp_npp_build_prob(). Of course there are limitations to what kind of modifications can be done to the preprocessed problem (e.g. no column/row deletions). However, glp_npp_load_sol() and glp_npp_recover_sol() have exactly the same restrictions, so I don't see it as a show stopper. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] lp/mip preprocessor api
> This is true, however after step L4 in your suggested API: > Q = glp_npp_build_prob(npp, ...); > any subsequent modifications to Q are not reflected in the PP > workspace. My suggestion is to allow calling glp_npp_load_prob() with > this modified Q (with changed bounds or added rows) to update the > workspace before further preprocessing passes. There is no need (and technically it'd be difficult) to load Q back into the PP wksp. It would be sufficient to provide some specific preprocessor routines that allows, for example, fixing a column or add a row to the current instance residing in the workspace. ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] lp/mip preprocessor api
Hi Andrew, > Sorry, I don't catch your idea. The resulting (preprocessed) problem > always resides in the PP workspace, so one can preprocess it in several > passes, if necessary. > This is true, however after step L4 in your suggested API: Q = glp_npp_build_prob(npp, ...); any subsequent modifications to Q are not reflected in the PP workspace. My suggestion is to allow calling glp_npp_load_prob() with this modified Q (with changed bounds or added rows) to update the workspace before further preprocessing passes. In a way this takes your suggestion to Heinrich, to "...first preprocess your instance with glpk pp and then preprocess the resulting instance with your own preprocessor" one step further, in that it allows to rerun the glpk preprocessor again using the same workspace. I have used this procedure myself in: a) a loop that fixes columns of the proproecessed problem using probing until no further changes are possible; and b) for additional preprocessing after adding symmetry breaking inequalities to the preprocessed problem. Best Regards, Chris Matrakidis ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] lp/mip preprocessor api
Hi Chris, > Here is my suggestion, together with a patch to implement it: > > > I think it is useful to be able to perform step L2 more than once, > i.e. to be able to call glp_npp_load_prob() after modifying the > problem returned from glp_npp_build_prob() in order to update the PP > workspace and continue preprocessing. > > > The attached patch modifies glp_npp_load_prob() to allow this. > Sorry, I don't catch your idea. The resulting (preprocessed) problem always resides in the PP workspace, so one can preprocess it in several passes, if necessary. Andrew Makhorin ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] lp/mip preprocessor api
> >> the API should allow the user to add his own simplifications. > >> > >> This may require access to the npp internal structure. > > > > It would be problematic. I only plan to include a set of preprocessing > > operations sufficient in most cases (at least for LP). On the other > > hand, if the user needs to perform his own preprocessing, why not to do > > that independently on the glpk preprocessor? > > You have already implemented a lot of useful presolving and scaling > routines. > > If I wanted to build on it and simply add another one I would not like > to reimplement your work. You may first preprocess your instance with glpk pp and then preprocess the resulting instance with your own preprocessor. > > > > >> > >> It would be great if the variable mapping could be applied forward and > >> reverse in the MIP callback hook. > > > > Could you provide an example of what you mean? > > In the MIP callback currently we can only access the scaled and > presolved model. > > If we could apply the backwards transformation we would be able to > understand the solution in our original variables. This feature is already implemented (and even available in glpsol), i.e. it will be possible to recover the solution to the original mip within the callback. > > If we could apply the forward transformation we would be able to create > a constraint in our own variables and than add the transformed > constraint to the scaled and presolved model. > Currently the preprocessor is unable to do this. May be to implement such a feature later. Andrew Makhorin ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] lp/mip preprocessor api
On 12/02/2017 05:54 PM, Andrew Makhorin wrote: > Hi Heinrich, > >> >> the API should allow the user to add his own simplifications. >> >> This may require access to the npp internal structure. > > It would be problematic. I only plan to include a set of preprocessing > operations sufficient in most cases (at least for LP). On the other > hand, if the user needs to perform his own preprocessing, why not to do > that independently on the glpk preprocessor? You have already implemented a lot of useful presolving and scaling routines. If I wanted to build on it and simply add another one I would not like to reimplement your work. > >> >> It would be great if the variable mapping could be applied forward and >> reverse in the MIP callback hook. > > Could you provide an example of what you mean? In the MIP callback currently we can only access the scaled and presolved model. If we could apply the backwards transformation we would be able to understand the solution in our original variables. If we could apply the forward transformation we would be able to create a constraint in our own variables and than add the transformed constraint to the scaled and presolved model. Best regards Heinrich ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
Re: [Help-glpk] lp/mip preprocessor api
Hi Heinrich, > > the API should allow the user to add his own simplifications. > > This may require access to the npp internal structure. It would be problematic. I only plan to include a set of preprocessing operations sufficient in most cases (at least for LP). On the other hand, if the user needs to perform his own preprocessing, why not to do that independently on the glpk preprocessor? > > It would be great if the variable mapping could be applied forward and > reverse in the MIP callback hook. Could you provide an example of what you mean? Best regards, Andrew Makhorin ___ Help-glpk mailing list Help-glpk@gnu.org https://lists.gnu.org/mailman/listinfo/help-glpk
