[SCIP] Questions on detecting unbounded
Ambros Gleixner
gleixner at zib.de
Mon Feb 20 20:24:04 CET 2017
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
>
--
Ambros Gleixner, Zuse Institute Berlin, http://www.zib.de/gleixner
More information about the Scip
mailing list