[SCIP] Questions on detecting unbounded
Gerald Gamrath
gamrath at zib.de
Tue Feb 21 08:33:44 CET 2017
Hi Yankai,
if you could imagine implementing a plugin for SCIP which does this for
you, please have a look at the event handler example of SCIP
(examples/Eventhdlr). There is an example event handler implemented
there already, which is called every time a new best solution is found
(src/event_bestsol.{c,h}).
This event handler just prints the solution value, but you could instead
check that the solution value is below your limit (e.g., -1e+10) and
just call SCIPinterruptSolve() to stop the solving process.
Best,
Gerald
Am 20.02.2017 um 20:24 schrieb Ambros Gleixner:
> Hi Yankai.
>
> Maybe the following does it for you, although this cannot be realized
> with one settings file:
>
> 1. set limits solution 1
> 2. call solve: either SCIP proves infeasibility or stops after the first
> found solution
> 3. if not infeasible:
> - set limits objective -1e10
> - set limits solution -1
> - continue solving
>
> You could implement a small program that does this automatically using
> the C API of SCIP.
>
> Best,
> Ambros
>
>
>
> Am 20.02.2017 um 20:01 schrieb Yankai Cao:
>> Hi, All,
>>
>> I tried 2 methods suggested by Jakob and Gregor,
>>
>> The first method is to set
>> numerics/infinity = 1e+10
>> This method not only changes unbounded definition, but also changes
>> infinity definition for other parameters in the solver. The result is
>> not preferred.
>> node | left |LP iter|LP it/n| mem | dualbound | primalbound |
>> gap
>> t 1 | 0 | 0 | - | 206k| -- |-1.000000e+05 |
>> Inf
>> 1 | 0 | 1 | - | 209k| -- |-1.000000e+05 |
>> Inf
>> (node 1) LP relaxation is unbounded (LP 1)
>> 1 | 2 | 4 | - | 210k| -- |-1.000000e+05 |
>> Inf
>> WARNING: could not enforce feasibility by separating or branching;
>> declaring solution with viol 1e+17 as feasible
>> 100 | 99 | 4 | 0.0 | 255k| -- |-1.000000e+05 |
>> Inf
>> WARNING: could not enforce feasibility by separating or branching;
>> declaring solution with viol 1e+17 as feasible
>> 200 | 171 | 5 | 0.0 | 281k| -- |-1.000000e+05 |
>> Inf
>> 300 | 271 | 6 | 0.0 | 308k| -- |-1.000000e+05 |
>> Inf
>> …
>> WARNING: could not enforce feasibility by separating or branching;
>> declaring solution with viol 1e+17 as feasible
>> 33400 | 31475 | 207 | 0.0 |8816k| -- |-1.000000e+05 |
>> Inf
>> 33500 | 31575 | 207 | 0.0 |8841k| -- |-1.000000e+05 |
>> Inf
>>
>>
>> The second method is to set
>>
>> set limits objective -1e+10
>> set limits solutions 1
>>
>> This method works well for the unbounded problem I show before. However,
>> if the problem is not unbounded (I am not sure if the problem is bounded
>> or not), then ideal SCIP should tell me that the problem is infeasible.
>> Then I need to solve the problem again with the default setting. This
>> method has 2 drawbacks for bounded problems: a. I need to solve the
>> problem twice, b. when I solve the problem with limits objective
>> -1e+10 limits solutions 1, SCIP might takes long to prove the problem is
>> infeasible. The following is the output for a bounded problem:
>>
>> node | left |LP iter|LP it/n| mem | dualbound | primalbound |
>> gap
>> 1 | 0 | 0 | - | 209k| -- |-1.000000e+10*|
>> Inf
>> (node 1) LP relaxation is unbounded (LP 0)
>> 1 | 2 | 2 | - | 210k| -- |-1.000000e+10*|
>> Inf
>> 100 | 99 | 2 | 0.0 | 244k| -- |-1.000000e+10*|
>> Inf
>> 200 | 197 | 2 | 0.0 | 276k| -- |-1.000000e+10*|
>> Inf
>> 300 | 295 | 2 | 0.0 | 302k| -- |-1.000000e+10*|
>> Inf
>> ...
>> 624400 |619385 | 2 | 0.0 | 159M| -- |-1.000000e+10*|
>> Inf
>> 624500 |619483 | 2 | 0.0 | 159M| -- |-1.000000e+10*|
>> Inf
>> 624600 |619583 | 2 | 0.0 | 159M| -- |-1.000000e+10*|
>> Inf
>> 624700 |619681 | 2 | 0.0 | 159M| -- |-1.000000e+10*|
>> Inf
>> 624800 |619781 | 2 | 0.0 | 159M| -- |-1.000000e+10*|
>> Inf
>> 624900 |619881 | 2 | 0.0 | 159M| -- |-1.000000e+10*|
>> Inf
>>
>>
>> Regards,
>> Yankai
>>
>>
>>> On Feb 20, 2017, at 3:37 AM, Gregor Hendel <hendel at zib.de
>>> <mailto:hendel at zib.de>> wrote:
>>>
>>> Dear Yankai,
>>>
>>> I would use the two limiting parameters for solution number and
>>> objective together:
>>>
>>> set limits objective -1e+17
>>> set limits solutions 1
>>>
>>> The solution limit internally respects the objective limit, and SCIP
>>> correctly stops. You can verify this from the output: (I solved the
>>> example problem check/instances/MIP/bell5.mps):
>>>
>>> SCIP Status : solving was interrupted [solution limit reached]
>>> Solving Time (sec) : 0.04
>>> Solving Nodes : 1
>>> Primal Bound : +8.98999851950592e+06 (3 solutions, 1 respecting the objective limit)
>>> Dual Bound : +8.95607775334990e+06
>>>
>>>
>>> Happy continuation with your experiments,
>>> Gregor
>>>
>>>
>>> Am 20.02.2017 um 00:04 schrieb Yankai Cao:
>>>> Hi, Gregor,
>>>>
>>>>
>>>> Thanks for your information. I have search the user parameters but
>>>> cannot find the right parameter.
>>>>
>>>> I am solving a number of (e.g. 1000) NLPs with different parameters
>>>> in the model. Many cases are unbounded. The following is the output
>>>> of SCIP for the smallest case:
>>>>
>>>> node | left |LP iter|LP it/n| mem | dualbound | primalbound
>>>> | gap
>>>> 1 | 0 | 1 | - | 209k| -- |-1.000000e+05
>>>> | Inf
>>>> (node 1) LP relaxation is unbounded (LP 1)
>>>> 1 | 2 | 4 | - | 210k| -- |-1.000000e+05
>>>> | Inf
>>>> * 2 | 1 | 6 | 5.0 | 211k| -- |-6.800000e+17
>>>> | Inf
>>>> 100 | 99 | 6 | 0.1 | 241k| -- |-6.800000e+17
>>>> | Inf
>>>>
>>>> …
>>>> node | left |LP iter|LP it/n| mem | dualbound | primalbound
>>>> | gap
>>>> 10575k| 9648k| 6 | 0.0 |2501M| -- |-1.000000e+18
>>>> | Inf
>>>> 10575k| 9648k| 6 | 0.0 |2501M| -- |-1.000000e+18
>>>> | Inf
>>>>
>>>> As you can see, at node 2, SCIP have already find a prime bound of
>>>> -6.8e17, which is so small that I can view it as unbounded for my
>>>> model. I want SCIP at node 2 to stop and return me this prime bound.
>>>> However, SCIP is still running after exploring more than 10 million
>>>> nodes. Setting a solution limit of 1 is not appropriate for my
>>>> problem, because the primal bound in the node 1 is not large enough
>>>> for me to declare that the problem is unbounded.
>>>>
>>>>
>>>> Regard,
>>>> Yankai
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>
>>>>> On Feb 17, 2017, at 10:23 AM, Gregor Hendel <hendel at zib.de
>>>>> <mailto:hendel at zib.de>> wrote:
>>>>>
>>>>> Hi Yankai,
>>>>>
>>>>> please read the documentation of SCIP, especially search the limits
>>>>> in the user parameters
>>>>>
>>>>> http://scip.zib.de/doc/html/PARAMETERS.php
>>>>>
>>>>> to find something that matches your purpose. IMHO, there is nothing
>>>>> to speed up the detection of unboundedness. What you should rather
>>>>> do, is set up a proper lower bound for your model, and set a
>>>>> solution limit of 1 to stop if feasibility of this modified model
>>>>> was proven.
>>>>>
>>>>> Happy scipping,
>>>>> Gregor
>>>>>
>>>>>
>>>>>
>>>>> Am 17.02.2017 um 17:02 schrieb Yankai Cao:
>>>>>> Dear Benjamin,
>>>>>>
>>>>>>
>>>>>> Thanks so much for your reply. Is there any parameter I can set to
>>>>>> help SCIP detect if the problem is unbound. For example, for my
>>>>>> model, if SCIP find an upper bound <= ub (e.g. -1e10), I want SCIP
>>>>>> to stop and declare the problem is unbound. Otherwise, it will
>>>>>> takes SCIP much much more time to continue. Thanks.
>>>>>>
>>>>>>
>>>>>> Regards,
>>>>>> Yankai
>>>>>>
>>>>>>
>>>>>>> On Feb 17, 2017, at 7:19 AM, Benjamin Müller
>>>>>>> <benjamin.mueller at zib.de> wrote:
>>>>>>>
>>>>>>> Dear Yankai,
>>>>>>>
>>>>>>> you can use
>>>>>>>
>>>>>>> set/limits/objective
>>>>>>>
>>>>>>> in order to set an objective limit. SCIP will then only look for
>>>>>>> solutions that have a better value than the given objective limit.
>>>>>>> You can think of it as an artificial upper bound for your
>>>>>>> (minimization) problem.
>>>>>>>
>>>>>>> As far as I can see it, there is no parameter to set an initial
>>>>>>> dual bound in SCIP. There is SCIPupdateLocalDualbound in the API
>>>>>>> that could be called during the SCIP_STAGE_PROBLEM stage.
>>>>>>>
>>>>>>> Regards,
>>>>>>> Benjamin
>>>>>>>
>>>>>>>
>>>>>>> On 02/17/2017 07:24 AM, Yankai Cao wrote:
>>>>>>>> Hi, All,
>>>>>>>>
>>>>>>>> I am new to SCIP. I want to know how to set a parameter ub
>>>>>>>> (e.g. -1e10) so that if SCIP find the upper bound is smaller than
>>>>>>>> ub SCIP can stop and declare that the problem is unbounded?
>>>>>>>>
>>>>>>>> Also, how to provide known upper/lower bounds before b&b, which
>>>>>>>> might help speed the solution time of SCIP?
>>>>>>>>
>>>>>>>> Thanks very much!
>>>>>>>>
>>>>>>>>
>>>>>>>> Regards,
>>>>>>>> Yankai
>>>>>>>>
>>>>>>>>
>>>>>>>> _______________________________________________
>>>>>>>> Scip mailing list
>>>>>>>> Scip at zib.de
>>>>>>>> http://listserv.zib.de/mailman/listinfo/scip
>>>>>>>>
>>>>>>> --
>>>>>>> ______________________________
>>>>>>> Benjamin Müller
>>>>>>> Zuse Institute Berlin
>>>>>>> Takustr. 7, 14195 Berlin
>>>>>>> benjamin.mueller at zib.de
>>>>>>> +49 30 841 85-195
>>>>>> _______________________________________________
>>>>>> Scip mailing list
>>>>>> Scip at zib.de
>>>>>> http://listserv.zib.de/mailman/listinfo/scip
>>>>>
>>>>> _______________________________________________
>>>>> Scip mailing list
>>>>> Scip at zib.de
>>>>> http://listserv.zib.de/mailman/listinfo/scip
>>> _______________________________________________
>>> Scip mailing list
>>> Scip at zib.de <mailto:Scip at zib.de>
>>> http://listserv.zib.de/mailman/listinfo/scip
>>
>>
>> _______________________________________________
>> Scip mailing list
>> Scip at zib.de
>> http://listserv.zib.de/mailman/listinfo/scip
>>
More information about the Scip
mailing list