[SCIP] Restart after root node
Aao Du
aaoduu at gmail.com
Wed Sep 2 22:25:53 CEST 2015
Dear Gerald,
I attached the log files. The second method's log file is after setting the
parameter "presolving/restartminred" to 0. Unfortunately, it did not make
a difference. I appreciate your time.
Regards,
Emily
On Wed, Sep 2, 2015 at 5:20 AM, Gerald Gamrath <gamrath at zib.de> wrote:
> Dear Emiliy,
>
> I made the change to the SCIPdeactivatepricer. Now based on the
> statistics, restarting is performed and there are 2 runs. However, compared
> to the method 1, it is still slower. What I see in the first method,s
> logfile, there are several round of presolving performed and several
> runs(which I think it means aeveral restarts happen?). It looks to me the
> second method does only the first round of presolving that is performed in
> method 1. Is there a reason to expect this? I could not figure if there is
> any parameter that I need to adjust in oreder to have several restarts?
>
> Indeed, the effect of the first restart is measured (in terms of fixed
> variables) and more restarts are only allowed if at least 10% of the
> variables were removed. It may be that this is not the case for the restart
> you trigger and thus, no second restart will be performed. You can change
> the parameter "presolving/restartminred" to adjust this behaviour, e.g.,
> just set it to 0.0 to see if another restart is then performed.
>
> If there is still a significant difference afterwards, please send us the
> log files again. If you do so, please include also the SCIP output during
> solving.
>
>
> Also, i am changing the modifiable flags and deactivating pricer in the
> redcost method. Doing it in the exitsol method did not perform restrating
> as it enters the exitsol method only when the whole problem is solved. I am
> not sure if this is what is supposed to happen.
>
>
> Did you change the lines in solve.c? Without this, the restart will not be
> triggered. If a restart is triggered, the exitsol method should be called,
> so that you can disable the pricer and mark the constraints unmodifiable.
>
>
> Best,
> Gerald
>
>
>
> Thanks in advance,
>
> Emily
> On Tue, Sep 1, 2015 at 1:35 PM, Gerald Gamrath <gamrath at zib.de> wrote:
>
>> Hi Emily,
>>
>> it looks like in the second log file, no restart is performed at all. As
>> far as I can see in your code snippet, you did not deactivate the pricer
>> using SCIPdeactivatePricer(), but just internally set a flag such that it
>> always just returns.
>>
>> However, with an active pricer, restarts are not allowed, so SCIP just
>> does not do a restart ("number of runs" is 1) and just continues solving.
>> This was changed compared to the old mails you are referencing. Therefore,
>> you do not do presolving again, and if you did not set the result pointer
>> to SCIP_SUCCESS before returning in the pricer while it is
>> pseudo-deactivated, SCIP might even not be able to use the node LP
>> relaxation values as lower bound (because your pricer returns
>> SCIP_DIDNOTRUN by default, meaning that there might still be improving
>> columns and the dual bound must not be used).
>>
>> The problem is that you are currently not allowed to deactivate a pricer
>> during solving. You could try to change this by changing line 5048 in
>> src/scip/scip.c from
>> SCIP_CALL( checkStage(scip, "SCIPdeactivatePricer", FALSE, TRUE,
>> FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE,
>> FALSE) );
>> to
>> SCIP_CALL( checkStage(scip, "SCIPdeactivatePricer", FALSE, TRUE,
>> FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, FALSE, TRUE, FALSE, TRUE, FALSE,
>> FALSE) );
>> (set the fifth-last parameter to TRUE). However, I'm not completely sure
>> if deactivating a pricer during solving may corrupt internal data
>> structures.
>>
>> If you run into any troubles after the change, please try the following:
>> In src/scip/solve.c lines 3605 and 3609, change
>> "set->nactivepricers == 0" to "(set->nactivepricers == 0 ||
>> stat->userrestart)".
>>
>> This will allow a user restart even if pricers are active. Then, you need
>> to follow the advice given in the old mail and implement the exitsol
>> callback to change the modifiable flags and deactivate your pricer.
>>
>> Best,
>> Gerald
>>
>>
>> On 01.09.2015 17:50, Aao Du wrote:
>>
>> Hi Jakob,
>>
>> I have attached the log files. For the instance solved by the first
>> method, the log file is for the second part of the solving process where
>> the final master problem is fed to SCIP. (So the time does not include the
>> root node time)
>> For the instance solved by the second method, the solving time does
>> include the root node time (which is around ~100 seconds).
>> Note that in larger instances. the difference become more significant.
>>
>> Just to check whether the way I am doing is correct. In the scip_redcost
>> method, I have the following code lines at the beginning:
>> if(SCIPgetDepth(scip) == 1)
>> Change the modifiable flag of the constraints, and
>> SCIPrestartSolve(scip)
>> isrestart = true; (isrestart is a pricer variable which is
>> initialized to false)
>> return SCIP_OKAY
>> if (isrestart)
>> return
>>
>>
>> In the previous emails, it was instructed to change the flag of
>> constraints at the scip_exitsol method, but that method is not entered
>> until the mixed integer master problem is solved optimally. So trying that
>> did not work either. (
>> http://listserv.zib.de/pipermail/scip/2011-September/000754.html)
>>
>> Emily
>>
>>
>> On Tue, Sep 1, 2015 at 3:41 AM, Jakob Witzig <witzig at zib.de> wrote:
>>
>>> Hi Emily,
>>>
>>> probably the presolving in the second case is finished earlier because
>>> [i] presolving after a restarts is reduced (but I'm not sure) [ii] the
>>> presolver itself remember that they could not find anything (because your
>>> constraints were modifiable) and they do not run.
>>>
>>> If you want, you can send me your two log-files and I will have a look
>>> at it.
>>>
>>> Best,
>>> Jakob
>>>
>>> On 08/31/15 15:57, Aao Du wrote:
>>>
>>>> Hi Jacob,
>>>>
>>>> I believe I did not explain my question well. Here are the two methods I
>>>> have tried:
>>>> 1) Solve the master problem at the root node. Change the variables type
>>>> and write it as an lp file.Then solve the MIP separately with SCIP.
>>>> 2) Define the variables as integer from the beginning. After the root
>>>> node, restart the scip and change the modifiable flag of constraints.
>>>>
>>>> Now these two methods solve in two significantly different solution
>>>> time. From the log files, I figured the number of variables in the final
>>>> master problem is decreased in the first method after presolving by
>>>> SCIP. However, in the second method, after the scip is restarted(which I
>>>> think does the presolving too), the number of variables stay the same.
>>>> I would appreciate if you can help me figure out the reason
>>>>
>>>> Thanks,
>>>> Emily
>>>>
>>>> On Mon, Aug 31, 2015 at 4:19 AM, Jakob Witzig <witzig at zib.de
>>>> <mailto:witzig at zib.de>> wrote:
>>>>
>>>> Hi Jens,
>>>>
>>>> what do you mean was 'differ in the results'? Only solving time and
>>>> nodes? The problem is, that the variable order can change if you
>>>> write the problem is an lp file. You can try to write your problem
>>>> as an mps or cip file.
>>>>
>>>> If you want, you can send me the log-files including the statistics
>>>> of the two solves (1: copy into a subscip, 2: write as an lp and
>>>> solve separately) and I will have a look on it.
>>>>
>>>> Best,
>>>> Jakob
>>>>
>>>>
>>>> On 08/31/15 08:33, Jens Leoff wrote:
>>>>
>>>> Hi,
>>>>
>>>> I also tried to write a heuristic to solve my Branch & Price
>>>> problem as
>>>> Price & Branch. I tried to copy the node problem to a subscip
>>>> where I
>>>> change the constraints to be non-modifiable. Apart from that the
>>>> scips
>>>> differ in what plugins are included (no pricer, but e.g.
>>>> separators).
>>>> However, I also wasn't able to produce the same results this way
>>>> as one
>>>> can obtain by writing the node problem as a MIP and solving this
>>>> separately with scip.
>>>>
>>>> I guess this kind of heuristic would be interesting for lots of
>>>> Branch &
>>>> Price applications.
>>>> So, I would like to know how to do this properly as well.
>>>>
>>>> Best,
>>>>
>>>> Jens
>>>>
>>>>
>>>> On 31.08.2015 08 <31.08.2015%2008> <tel:31.08.2015%2008>:06,
>>>> Jakob Witzig wrote:
>>>>
>>>> Hi Emily,
>>>>
>>>> you can use the method SCIPvarChgType to convert the
>>>> variables into
>>>> integers, but the method can only be called if the variables
>>>> are not
>>>> part of the problem, e.g., before you call
>>>> SCIPtransformProb. Do you
>>>> use sub-SCIPs to solve your subproblems? If yes, than you
>>>> can call the
>>>> method mentioned above before you start solving the
>>>> subproblem.
>>>>
>>>> I don't get the connection between your two ways. Why is
>>>> changing the
>>>> variables and changing the modifiability flag of the
>>>> constraint
>>>> equivalent?
>>>>
>>>> If you restart your problem SCIP tries to transform cuts
>>>> into globally
>>>> valid constraints and will fix all variables that have equal
>>>> global
>>>> upper and lower bounds, i.e., the variables can removed
>>>> from the
>>>> problem. Hence, if you could not tighten the bounds of your
>>>> variables
>>>> enough or you didn't found global valid cuts a restart
>>>> directly after
>>>> the root will give you the same problem as before.
>>>>
>>>> I think changing the flags of a constraint should be done
>>>> before you
>>>> start solving your subproblem.
>>>>
>>>> Best,
>>>> Jakob
>>>>
>>>>
>>>> On 08/31/15 04:38, Aao Du wrote:
>>>>
>>>> Dear all,
>>>>
>>>> I have a decomposed model, a master problem and
>>>> subproblems. I am trying
>>>> to perform pricing only at the root node, and then
>>>> change the variables
>>>> to integer and solve it again. I have tried two ways.
>>>> One is to print
>>>> the lp format of the problem after root node, with
>>>> variables as integer,
>>>> and give it to SCIP binaries. In this way, the second
>>>> part of the
>>>> solving process ( solving the final master problem with
>>>> binaries) is
>>>> performed fast.
>>>> The other way, is to define the variables as integer
>>>> from begining, and
>>>> stop pricing at the root node, and change the
>>>> constarints to
>>>> unmodifiable. In this way, after the lp of master
>>>> problem is solved, it
>>>> takes way more than the first method to solve it.
>>>> Following a previous
>>>> email, I tried to restart the master problem after root
>>>> node, but it did
>>>> not make any change in the time. I thought maybe i am
>>>> doing sth wrong.
>>>> What is the proper place in the pricerobj to change the
>>>> modifiable flag
>>>> of constraints? I think it should be somewhere before
>>>> redcost, or maybe
>>>> in it.
>>>>
>>>> Sorry for the long email.
>>>>
>>>> Thanks,
>>>> Emily
>>>>
>>>>
>>>> _______________________________________________
>>>> Scip mailing list
>>>> Scip at zib.de <mailto:Scip at zib.de>
>>>> http://listserv.zib.de/mailman/listinfo/scip
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>
>>>> --
>>>> Jakob Witzig
>>>>
>>>> Konrad-Zuse-Zentrum für
>>>> Informationstechnik Berlin (ZIB)
>>>>
>>>> Division Mathematical Optimization and Scientific Information
>>>> Research Group Mathematical Optimization Methods
>>>>
>>>> Takustrasse 7
>>>> 14195 Berlin
>>>>
>>>> Tel. : +49 (0)30 84185-416 <%2B49%20%280%2930%2084185-416>
>>>> <tel:%2B49%20%280%2930%2084185-416>
>>>> Fax : +49 (0)30 84185-269 <%2B49%20%280%2930%2084185-269>
>>>> <tel:%2B49%20%280%2930%2084185-269>
>>>> email: witzig at zib.de <mailto:witzig at zib.de>
>>>> _______________________________________________
>>>> Scip mailing list
>>>> Scip at zib.de <mailto:Scip at zib.de>
>>>> http://listserv.zib.de/mailman/listinfo/scip
>>>>
>>>>
>>>>
>>>
>>> --
>>> Jakob Witzig
>>>
>>> Konrad-Zuse-Zentrum für
>>> Informationstechnik Berlin (ZIB)
>>>
>>> Division Mathematical Optimization and Scientific Information
>>> Research Group Mathematical Optimization Methods
>>>
>>> Takustrasse 7
>>> 14195 Berlin
>>>
>>> Tel. : +49 (0)30 84185-416 <%2B49%20%280%2930%2084185-416>
>>> Fax : +49 (0)30 84185-269 <%2B49%20%280%2930%2084185-269>
>>> email: witzig at zib.de
>>>
>>
>>
>>
>> _______________________________________________
>> Scip mailing listScip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip
>>
>>
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listserv.zib.de/pipermail/scip/attachments/20150902/dfc6c933/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: logfile_method1
Type: application/octet-stream
Size: 23500 bytes
Desc: not available
URL: <http://listserv.zib.de/pipermail/scip/attachments/20150902/dfc6c933/attachment.obj>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: logfile_method2.2
Type: application/octet-stream
Size: 98047 bytes
Desc: not available
URL: <http://listserv.zib.de/pipermail/scip/attachments/20150902/dfc6c933/attachment-0001.obj>
More information about the Scip
mailing list