[SCIP] Questions on detecting unbounded
Yankai Cao
yankai.cao at gmail.com
Mon Feb 20 20:01:16 CET 2017
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> 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 <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> <mailto: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 <mailto:Scip at zib.de>
>>>>>> http://listserv.zib.de/mailman/listinfo/scip <http://listserv.zib.de/mailman/listinfo/scip>
>>>>>>
>>>>> --
>>>>> ______________________________
>>>>> Benjamin Müller
>>>>> Zuse Institute Berlin
>>>>> Takustr. 7, 14195 Berlin
>>>>> benjamin.mueller at zib.de <mailto:benjamin.mueller at zib.de>
>>>>> +49 30 841 85-195
>>>>
>>>> _______________________________________________
>>>> Scip mailing list
>>>> Scip at zib.de <mailto:Scip at zib.de>
>>>> http://listserv.zib.de/mailman/listinfo/scip <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 <http://listserv.zib.de/mailman/listinfo/scip>
>>
>
> _______________________________________________
> 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/20170220/8a9b5292/attachment.html>
More information about the Scip
mailing list