[sage-support] Re: MixedIntegerLinearProgram: warm restart possible?

[john_perry_usm]

> my posts about the dual simplex method and warm restart here are met 
> with deafening silnce...


Actually, I'm very interested in it, and that's one of the reasons I was 
suggesting this. Although I believe its possible to run dual simplex in 
GPLK with the current implementation (it's a solver option).

john perry

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

[sage-support] Re: MixedIntegerLinearProgram: warm restart possible?

[Dima Pasechnik]

On 2014-02-13, Nathann Cohen  wrote:
> Hell !!
>
>> 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.
>
> Hmmm... Well, I always thought that it would be nice to have a way to
> express constraints "formally". I mean : it would be nice to have
> "\sum_{i=0}^15 x_i <= 3" when you type p.show() rather than all individual
> constraints. That's fancy and useless stuff, but it would look
> so cool !
>
> I have no idea how to implement this, though :-)
>
>> 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.
>
> Hmmm Well, a way to check if a constraint is tight ? I am sure I have
> been asked this several times... O_o

infeasibility certifcates; I was lamenting about the lack of this
feature. 
>
>> 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?

my posts about the dual simplex method and warm restart here are met
with deafening silnce... Perhaps it's harder stuff than derived
categories :-)


>
> Well, I use it a lot but unfortunately it does what I want it to do ^^;
>
> A bit like graphs It's getting boring these days :-P
>
> Nathann
>

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

Re: [sage-support] Re: MixedIntegerLinearProgram: warm restart possible?

[Nathann Cohen]

Hell !!

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

Hmmm... Well, I always thought that it would be nice to have a way to
express constraints "formally". I mean : it would be nice to have
"\sum_{i=0}^15 x_i <= 3" when you type p.show() rather than all individual
constraints. That's fancy and useless stuff, but it would look
so cool !

I have no idea how to implement this, though :-)

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

Hmmm Well, a way to check if a constraint is tight ? I am sure I have
been asked this several times... O_o

> 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?

Well, I use it a lot but unfortunately it does what I want it to do ^^;

A bit like graphs It's getting boring these days :-P

Nathann

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

[sage-support] Re: MixedIntegerLinearProgram: warm restart possible?

[john_perry_usm]

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

[sage-support] Re: MixedIntegerLinearProgram: warm restart possible?

[Dima Pasechnik]

On 2014-02-10, Erik Quaeghebeur  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.

Re: [sage-support] Re: MixedIntegerLinearProgram: warm restart possible?

[Erik Quaeghebeur]

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.


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

Re: [sage-support] Re: MixedIntegerLinearProgram: warm restart possible?

[Nathann Cohen]

> 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?

Well, if it boils down to the addition of an optional argument
somewhere this would be a very easy way out :-)

Anyway, we have no reason to stop ourselves from adding any code which
is useful to us, only because it is not available for ALL solvers. Who
uses all of them at the same time anyway ?

It's just better to have something available for GLPK if it is
available for proprietary solvers... At least it appears somewhere in
the doc :-)

Nathann

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

Re: [sage-support] Re: MixedIntegerLinearProgram: warm restart possible?

[john_perry_usm]

On Sunday, February 9, 2014 7:15:02 AM UTC-6, Nathann Cohen wrote:
>
> > For my purpose of learning Cython, this approach was more useful and 
> certainly faster.
> >
> > As for this works usefulness for Sage: the numerical module is far more 
> than just a wrapper for GLPK (also, but not limited to, wrappers for CBC, 
> Gurobi, CPLEX, and a wrapper to unify them all). Such coverage makes code 
> modifications more difficult (much more factors to take into account). With 
> what I have done now, the maintainers of the numerical module can copy the 
> parts of the glpk.pxd file I created they deem useful, the same goes for 
> the glpk-constants.pxi file.
>
> Ahahahaah. Well, there are no numerical/ "maintainers", unfortunately.
> Only contributors, who add some stuff there when they need it for 
> themselves, and want to help by sharing it with others. I am afraid that if 
> you chose to write this code somewhere else, nobody else will do the job of 
> making it Sage code, for everybody else's loss.
>

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?

john perry

>

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

Re: [sage-support] Re: MixedIntegerLinearProgram: warm restart possible?

[Nathann Cohen]

> For my purpose of learning Cython, this approach was more useful and
certainly faster.
>
> As for this works usefulness for Sage: the numerical module is far more
than just a wrapper for GLPK (also, but not limited to, wrappers for CBC,
Gurobi, CPLEX, and a wrapper to unify them all). Such coverage makes code
modifications more difficult (much more factors to take into account). With
what I have done now, the maintainers of the numerical module can copy the
parts of the glpk.pxd file I created they deem useful, the same goes for
the glpk-constants.pxi file.

Ahahahaah. Well, there are no numerical/ "maintainers", unfortunately.
Only contributors, who add some stuff there when they need it for
themselves, and want to help by sharing it with others. I am afraid that if
you chose to write this code somewhere else, nobody else will do the job of
making it Sage code, for everybody else's loss.

There is no problem with changing the way the interface between Sage and LP
solvers is written when needed, though. The fact that only one solver
supports a feature must not mean that it never gets implemented in Sage.
Especially when this solver is GLPK, i.e. the default one. I don't like to
write cplex-specific code myself, but if there is a GLPK counterpart now
that is a different thing :-)

Nathann

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

Re: [sage-support] Re: MixedIntegerLinearProgram: warm restart possible?

[Erik Quaeghebeur]

[...], and wanted to learn Cython, I decided to try and write a
Cython/Python GLPK interface.


Would it be faster, and more useful for Sage development, to modify
Sage code ?


For my purpose of learning Cython, this approach was more useful and 
certainly faster.


As for this works usefulness for Sage: the numerical module is far more 
than just a wrapper for GLPK (also, but not limited to, wrappers for 
CBC, Gurobi, CPLEX, and a wrapper to unify them all). Such coverage 
makes code modifications more difficult (much more factors to take into 
account). With what I have done now, the maintainers of the numerical 
module can copy the parts of the glpk.pxd file I created they deem 
useful, the same goes for the glpk-constants.pxi file. The epyglpki.pyx 
module is most likely too far removed from the Sage numerical 
architecture to be directly useful.


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.

[sage-support] Re: MixedIntegerLinearProgram: warm restart possible?

[Dima Pasechnik]

On 2014-02-07, Erik Quaeghebeur  wrote:
>> []... I conduct iterative linear solving, and don't like the idea of
>> starting afresh every time I add a constraint; as I recall, one ought
>> to be able to warm start even at that point, simply moving from the
>> old, at worst currently infeasible solution to a feasible solution.
>> [...]
>
> FYI: because I needed the warm restart functionality, and wanted to 
> learn Cython, I decided to try and write a Cython/Python GLPK interface. 
Would it be faster, and more useful for Sage development, to modify Sage code ?


> Current preliminary version can be found at
>
>   https://github.com/equaeghe/epyglpki/
>
> Nothing but the most trivial operations have been tested at this point 
> and many aspects have not yet been wrapped. In case the Sage developers 
> find something interesting in the code, they are of course very welcome 
> to take parts. Suggestions and comments are welcome as issues on Github; 
> pull-requests also welcome. (No promises of acting on them, however.)
>
>
> Cheers,
>
> 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.

[sage-support] Re: MixedIntegerLinearProgram: warm restart possible?

[Dima Pasechnik]

On 2014-01-17, Erik Quaeghebeur  wrote:
>>> Does MixedIntegerLinearProgram allow for warm restarts, meaning that
>>> after solving a first time one changes the objective and resolve,
>>> starting from the feasible solution of the previous solver run?
>
> Based on the responses by Raniere and John (Thanks), and the implicit 
> pointers contained therein, I went to look in the glpk_backend source 
> code and the GLPK reference. My conclusion is now that, when using the 
> simplex method explicitly:
>
>   solver_parameter(backend.glp_simplex_or_intopt,
>backend.glp_simplex_only)
>
one also needs to specify that the dual simplex method is used
(the primal simplex method is not meant for warm restart with adding
constraints, although it should be able to warm-restart after adding
variables...)
The default is primal (according to glpk_backend.pyx)

  * - ``primal_v_dual``

   - - ``GLP_PRIMAL``  (default)
 - ``GLP_DUAL``
 - ``GLP_DUALP``

So you'd need to set this (not sure whether it's GLP_DUAL or
GLP_DUALP)

HTH,
Dmitrii

> Then (by GLPK default), presolving is turned off, and then a warm start 
> will be performed when the basis still present in the solver object is 
> still valid. So this should work when only changing the objective 
> function. Otherwise (for constraint add/remove or for bound change), the 
> "LP basis constructing routines"
>
>   glp_set_row_stat
>   glp_set_col_stat
>
> must be used to construct a valid basis before calling the solver again. 
> It is not clear to me whether glp_factorize and/or glp_warm_up needs to 
> be called. Currently, when removing constraints the sage module creates 
> a new basis using the basic crashing routine glp_std_basis (undocumented 
> why -- will need to test).
>
>
> 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.

[sage-support] Re: MixedIntegerLinearProgram: warm restart possible?

[Erik Quaeghebeur]

[]... I conduct iterative linear solving, and don't like the idea of
starting afresh every time I add a constraint; as I recall, one ought
to be able to warm start even at that point, simply moving from the
old, at worst currently infeasible solution to a feasible solution.
[...]


FYI: because I needed the warm restart functionality, and wanted to 
learn Cython, I decided to try and write a Cython/Python GLPK interface. 
Current preliminary version can be found at


https://github.com/equaeghe/epyglpki/

Nothing but the most trivial operations have been tested at this point 
and many aspects have not yet been wrapped. In case the Sage developers 
find something interesting in the code, they are of course very welcome 
to take parts. Suggestions and comments are welcome as issues on Github; 
pull-requests also welcome. (No promises of acting on them, however.)



Cheers,

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.

[sage-support] Re: MixedIntegerLinearProgram: warm restart possible?

[john_perry_usm]

> Then (by GLPK default), presolving is turned off, and then a warm start 
> will be performed when the basis still present in the solver object is 
> still valid. So this should work when only changing the objective 
> function. Otherwise (for constraint add/remove or for bound change), the 
> "LP basis constructing routines" 
>
> glp_set_row_stat 
> glp_set_col_stat 
>
> must be used to construct a valid basis before calling the solver again. 


Thanks. That makes sense.
 

> It is not clear to me whether glp_factorize and/or glp_warm_up needs to 
> be called.


I'll ask on their mailing list about that. I was wondering about that 
function yesterday, too. I conduct iterative linear solving, and don't like 
the idea of starting afresh every time I add a constraint; as I recall, one 
ought to be able to warm start even at that point, simply moving from the 
old, at worst currently infeasible solution to a feasible solution. (This 
is not my specialty, as is probably obvious by now.)
 

> Currently, when removing constraints the sage module creates 
> a new basis using the basic crashing routine glp_std_basis (undocumented 
> why -- will need to test). 
>

IIRC, we did that in case someone tried to extract solutions after 
deleting, without first solving.

john perry

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

[sage-support] Re: MixedIntegerLinearProgram: warm restart possible?

[Erik Quaeghebeur]

Does MixedIntegerLinearProgram allow for warm restarts, meaning that
after solving a first time one changes the objective and resolve,
starting from the feasible solution of the previous solver run?


Based on the responses by Raniere and John (Thanks), and the implicit 
pointers contained therein, I went to look in the glpk_backend source 
code and the GLPK reference. My conclusion is now that, when using the 
simplex method explicitly:


solver_parameter(backend.glp_simplex_or_intopt,
 backend.glp_simplex_only)

Then (by GLPK default), presolving is turned off, and then a warm start 
will be performed when the basis still present in the solver object is 
still valid. So this should work when only changing the objective 
function. Otherwise (for constraint add/remove or for bound change), the 
"LP basis constructing routines"


glp_set_row_stat
glp_set_col_stat

must be used to construct a valid basis before calling the solver again. 
It is not clear to me whether glp_factorize and/or glp_warm_up needs to 
be called. Currently, when removing constraints the sage module creates 
a new basis using the basic crashing routine glp_std_basis (undocumented 
why -- will need to test).



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.

[sage-support] Re: MixedIntegerLinearProgram: warm restart possible?

[john_perry_usm]

On Thursday, January 16, 2014 9:24:05 AM UTC-6, Erik Quaeghebeur wrote:

> Hi, 
>
>
> Does MixedIntegerLinearProgram allow for warm restarts, meaning that 
> after solving a first time one changes the objective and resolve, 
> starting from the feasible solution of the previous solver run? 
>

It's my understanding (from having worked on the code w/Nathann, & having 
looked at it just now) that if you merely add constraints & ask MILP to 
solve, then MILP just passes that all on to the solver. That is, Sage 
doesn't request a cold start.

If no in general, does the GLPK backend (or another specific backend) 

support it? Perhaps only when using a simplex solver?


GLPK has a presolver, which always constructs a valid solution "from 
scratch" but by default it's off (in GLPK and in Sage, too). Several 
comments in the GLPK manual suggest that it performs a warm start when 
minor changes are made. (e.g., "It is much better at fi rst to fi nd an 
optimal basis with the routine glp_simplex and only then to call glp_exact, 
in which case only a few simplex iterations need to be performed in exact 
arithmetic.") That said, this 
messageon 
the mailing list gives me pause.

I guess a surefire way would be to run a long loop of adding constraints & 
solving & see what happens.

I just ran a loop, and from what I can tell, it's cold-starting (though I'm 
not sure).

sage: lp = MixedIntegerLinearProgram(maximization = False)
sage: lp.add_constraint(lp[0] + lp[1] >= 1)
sage: lp.set_objective(lp[0] + lp[1])
sage: i = 2
sage: while i < 1000:
lp.add_constraint(i*lp[0] - lp[1] >= 0)
timeit('lp.solve()',repeat=1)
i += 1

The times on my machine rise from 33μs to 564μs by the time i=441. That 
looks to me like a cold start, but I'm not sure this is a good method of 
testing, since merely creating the same system w/441 constraints solves in 
53ns, which I didn't expect at all...

john perry

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