[SCIP] Restart after root node
Gerald Gamrath
gamrath at zib.de
Thu Sep 3 12:43:28 CEST 2015
Dear Emily,
I have an idea what might be the problem. Some presolvers remember which
presolving steps they did already on which constraints in order to not
do the same work again and again. Only after the constraint or the
variables in there were changed, this step will be done again. I fear
that setting a constraint to not being modifiable anymore is not counted
as a change in the constraint (because originally, this was not supposed
to be done during solving). Therefore, please disable presolving in the
first phase (where the constraints are modifiable anyway) by setting
"presolving/maxrounds" to 0. When doing the restart, reset this
parameter to -1. I hope this should give the same behaviour in the
second run as you expect.
After that, please:
1) disable lpinfo in the second run, such that the output is not spammed
with LP solver output?
2) send us the complete log of run 2 (which should be much smaller
without LP output). Currently, I can only use the statistics, but don't
see any information about how much presolving was done in which phase,
which you see roughly in the log.
3) best send the log files to Jakob and me directly to not spam the
mailing list.
Best,
Gerald
On 02.09.2015 22:25, Aao Du wrote:
> 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
> <mailto: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
>>> <mailto: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 <tel: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
>>> <tel:%2B49%20%280%2930%2084185-416>
>>> <tel:%2B49%20%280%2930%2084185-416>
>>> Fax : +49 (0)30 84185-269
>>> <tel:%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
>>> <tel:%2B49%20%280%2930%2084185-416>
>>> Fax : +49 (0)30 84185-269
>>> <tel:%2B49%20%280%2930%2084185-269>
>>> email: witzig at zib.de
>>>
>>>
>>>
>>>
>>> _______________________________________________ Scip mailing
>>> list Scip 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/20150903/aed88812/attachment.html>
More information about the Scip
mailing list