Hi guys Harald is looking for topics for Google Summer of Code, and I was wondering if you thought this & some other issues w/MILP might be worth looking at. For example, I have an email from Dima from March 13th of last year regarding constraint normalization, which I still haven't gotten round to thinking about. Maybe there are other issues we could identify, as well. Since linear programming is an important part of Sage, and also very accessible to undergraduates in both math and computer science (& maybe other disciplines as well: management? finance?) this could be appealing -- what do you guys think?
john perry On Monday, February 10, 2014 4:53:38 PM UTC-6, Dima Pasechnik wrote: > > On 2014-02-10, Erik Quaeghebeur <sa...@equaeghe.nospammail.net<javascript:>> > wrote: > > op 09-02-14 19:12, john_perry_usm schreef: > >> > >> Actually, I was thinking of doing it when I have time. This should be > quite > >> useful for what I need, but I wanted to investigate just how he's going > >> about it. > >> > >> And, as you point out, it isn't a problem to add a feature that works > with > >> only one solver; we simply add an optional argument (or more), right? > > > > For warm restart functionality, the GLPK simplex solver needs to be > > given a valid basis after it has been modified (by > > adding/removing/changing variables/constraints/bounds; changes to the > > objective does not require any attention to the basis). Furthermore, the > > new basis matrix needs to be factorized; this is easiest to do using the > > warm_up routine. > > Adding a constraint does not affect the feasibility of the dual basis. > (As I already mentioned in a previous message). > That's why typically one uses dual simplex method while doing > "contraint generation". > Similarly, while doing "column generation", i.e. adding variables on > the fly, it is cheap to do warm restart while using the primary > simplex, as the primal feasibility is not affected when you add a > variable. > > For all practical purposes, these are scenarios one would care about, > and so I don't see much value in having "general" warm restart. > (As it's not really "warm" any more :-) I'd argue that after losing > feasibility what happens in the algorithm isn't even referred to as warm > restart.) > > If the feasibility is lost, one should bort and start from scratch. > An efficient implementation would just carry on, assuming that > feasibility is not lost. > > > > > In the epyglpki code, the necessary logic is captured in the 'basis' > > method of the SimplexSolver class. > > > > The specification of the basis requires insight of the modeler; as far > > as I know, no automatic creation of a valid basis guarantees preserved > > feasibility, so manually adapting the basis settings are necessary. > see above. Once again, the appropriate choice of the algorithm does > guarantee preserved feasibility! > > > Therefore I do not think this is simply adding an extra parameter > > (variable statuses need to be read out and applied, factorization > > routine run). But given that the solver object is solver-specific in the > > Sage numerical module, I now think there is little risk of getting in > > the way of the other solvers if one wishes to implement this in the GLPK > > backend only. > > > > > > Erik > > > > -- You received this message because you are subscribed to the Google Groups "sage-support" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/groups/opt_out.
