[Cbc] Using hotstarting functionality with modifications

[Haroldo Santos]

Hi Ed,

It is important to observe that there's no proper "reoptimization"
routine for Integer Programs, at least not as efficient as
reoptimization in continuous linear programs. As Gabrielle noted,
entering an initial solution may not help too much, since this
solution will only provide a valid bound to prune the tree. Even if
you inform the optimal solution, the solver can take a long time to
prove its optimality, for example.

So, our tips are only useful to speed up a little bit the start of the search.

In summary, you approach can be very slow even if you use the proper
settings and you have a good solver.

Haroldo

On Thu, Jul 29, 2010 at 1:05 AM, Ed Bulog <ebul014 at aucklanduni.ac.nz> wrote:
> Thank you for your responses.
> Could anyone provide an example of how to correctly use solution information
> when adding/removing columns and then resolving? Does my general approach
> make sense or can hotstarting not be used for this purpose?
> Thanks again,
> Ed
>
> On 28 July 2010 11:18, Haroldo Santos <haroldo.santos at gmail.com> wrote:
>>
>> Thanks
>>
>> On Tue, Jul 27, 2010 at 7:06 PM, Gabrielle A. Grun <grun at cs.sfu.ca> wrote:
>> >  Hi Haroldo and Ed,
>> >
>> > In order the disable storing branching, I think that
>> > model.setNumberBeforeTrust(0); has to be in place too i.e.
>> > numberBeforeTrust_ has to be 0 as well.
>> >
>> > Take care.
>> >
>> > Gabrielle
>> >
>> >
>> > ----- Original Message -----
>> > From: Haroldo Santos
>> > To: Ed Bulog
>> > Cc: cbc at list.coin-or.org
>> > Sent: Monday, July 26, 2010 3:20 PM
>> > Subject: Re: [Cbc] Using hotstarting functionality with modifications
>> > Hi Ed,
>> >
>> > I think that at the start of the MIP search there are some very
>> > expensive routines which do not use any information of previous
>> > solutions.
>> >
>> > In particular, doing strong branching is very expensive.
>> >
>> > If you want to speed up the restart, perhaps one useful option would
>> > be to disable strong branching.
>> >
>> > setNumberStrong( 0 )
>> >
>> >
>> > On Mon, Jul 26, 2010 at 7:04 PM, Ed Bulog <ebul014 at aucklanduni.ac.nz>
>> > wrote:
>> >> Dear All,
>> >>
>> >> I have a large IP which I will be modifying constantly (by
>> >> adding/removing
>> >> coulmns) and resolving after each modification. I am trying to see if
>> >> there
>> >> is some way I could re-use the previous solution to make each solve
>> >> faster.
>> >> The obvious problem is that by adding and removing columns each time I
>> >> have
>> >> no way of guaranteeing that the previous solution will still be
>> >> feasible,
>> >> let alone optimal.
>> >>
>> >> I have experimented with the cbc example files (mostly hotstart.cpp,
>> >> modify.cpp and repeat.cpp). It would be ideal if I could solve the
>> >> problem,
>> >> modify it and then re-use the previous solution in a hotstart. My basic
>> >> approach is:
>> >> - call model.initialSolve()
>> >> - call model.branchandbound()
>> >> - save the bestSolution array
>> >> - remove some columns from the reference solver
>> >> - add some columns to the reference solver
>> >> - modify the bestSolution array accordingly (i.e. remove entries
>> >> corresponding to deleted columns and add zeros for new columns)
>> >> - call model.resetToReferenceSolver()
>> >> - call model.setHotstartSolution(
>> >> bestSolution)
>> >> - resolve using model.branchandbound()
>> >>
>> >> However, this approach does not seem to do anything particularly
>> >> useful.
>> >> branchandbound() does not appear to do anything differently from what
>> >> it
>> >> does when I do not use the hotstart solution.
>> >>
>> >> Does 'hotstarting' only work if the model remains unchanged (as in
>> >> hotstart.cpp)? Does anyone have any other suggestions? Your help is
>> >> greatly
>> >> appreciated.
>> >>
>> >> Thank you for your time,
>> >>
>> >> Ed
>> >>
>> >> _______________________________________________
>> >> Cbc mailing list
>> >> Cbc at list.coin-or.org
>> >> http://list.coin-or.org/mailman/listinfo/cbc
>> >>
>> >>
>> >
>> >
>> >
>> > --
>> > =============================================================
>> > Haroldo Gambini Santos
>> > Computing Department - Universidade Federal de Ouro Preto - UFOP
>> > email: haroldo [at ] iceb.ufop.br
>> > home/research page: http://www.iceb.ufop.br/decom/prof/haroldo/
>> >
>> > "Computer science is no more about computers than astronomy
>> > is about telescopes." Edsger Dijkstra
>> >
>> >
>> > _______________________________________________
>> > Cbc mailing list
>> > Cbc at list.coin-or.org
>> > http://list.coin-or.org/mailman/listinfo/cbc
>> >
>> >
>> > Gabrielle A. Grün, Ph.D. Student
>> > School of Computing Science
>> > Simon Fraser University
>> > 8888 University Drive
>> > Burnaby, BC
>> > V5A 1S6
>> > <http://www.cs.sfu.ca/~grun>
>> >
>> >
>>
>>
>>
>> --
>> =============================================================
>> Haroldo Gambini Santos
>> Computing Department - Universidade Federal de Ouro Preto - UFOP
>> email: haroldo [at ] iceb.ufop.br
>> home/research page: http://www.iceb.ufop.br/decom/prof/haroldo/
>>
>> "Computer science is no more about computers than astronomy
>> is about telescopes." Edsger Dijkstra
>
>



-- 
=============================================================
Haroldo Gambini Santos
Computing Department - Universidade Federal de Ouro Preto - UFOP
email: haroldo [at ] iceb.ufop.br
home/research page: http://www.iceb.ufop.br/decom/prof/haroldo/

"Computer science is no more about computers than astronomy
is about telescopes." Edsger Dijkstra