[Scip] Problem with Conflict Analysis

Stefan Heinz heinz at zib.de
Fri Oct 18 22:48:35 CEST 2013 

Hi Alex,

I got a little bit lost during this discussion. But here some comments :-).

On 10/11/2013 04:16 PM, Alexander Schnell wrote:
> Hi Michael and Ambros,
>
> thank you for the helpful suggestions.
> I will try valgrind and run SCIP with OPT=dbg.
>
> @Michael:
> When I check the global upper bound of the variable
> with SCIPvarGetUbGlobal() it gives me the value 1,
> but var->glbdom.lb = 1 and var->glbdom.ub = 0 in my program.
This sound really strange and should not happen at all. If you run SCIP 
in debug mode there should be asserts checking this and failing.
>    
>
> @Ambros:
> I am sure that my problem is not globally infeasible.
I think Ambros does not meant that your problem got infeasible. The example
just showed that the bound change t >= 6 which was done as result of s >= 3
is now globally valid since s >= 5 was globally detected. In that case the
reason for t >= 6 is empty. In case of SCIP you would call
SCIPaddConflictLb(scip, "s", bdchgidx) and SCIP would handle that case
automatically.
> I call SCIPvarGetUbAtIndex() in the following way:
> SCIPvarGetUbAtIndex(var,bdchgidx,FALSE),
> where var is the respective variable and bdchgidx is a pointer
> to the bound change index.
>
> I have analyzed the problem in more detail:
>
> I queried the bound change information (BCI) for the specific
> bound change index with
> SCIPvarGetUbchgInfo(var, bdchgidx, FALSE)
> for the variable var responsible for the bound change
>
> The depth of the bdchgidx is 9 and the depth of the respective bound
> change information is 3 for the variable responsible for the bound
> change.
Sounds good.
>
> At the bound change index for the BCI (depth 3) which does not equal
> bdchgidx the upper bound of the variable was set to 0 by a conflict
> constraint (cf1_333).
Does that happen after you made your bound change in depth 9?
> But at the time the propagation which I resolve took place (depth 9),
> the upper bound of the variable is 1 and the lower bound is 0.
If the conflict constraint was created/added after you made the bound
change in depth 9. Repropagation can lead to bound changes which were not
present during your propagation. This allows sometimes to construct better
reasons.

Best Stefan


>
> Thanks,
> Alex
>
>
>
>
>
>
> On Fri, 2013-10-11 at 15:42 +0200, Ambros Gleixner wrote:
>> Hi,
>>
>> it could be ok if your problem is globally infeasible, otherwise not.
>>
>> Also, can you tell us your exact call of SCIPvarGetLb/UbAtIndex().
>>
>> Running valgrind as suggested by Micha is a good idea.  Also, have you
>> compiled with OPT=dbg?
>>
>> ambros
>>
>>
>>
>>
>> Am 11.10.2013 15:31, schrieb michael.winkler at zib.de:
>>> Hi Alex,
>>>
>>>> Hi Ambros,
>>>>
>>>> thank you again for your answer. This is now clear for me.
>>>> Now I have the same problem with an upper bound.
>>>>
>>>> The upper bound of a variable at the time of the bound change
>>>> is 1. When I try to explain the bound change the upper bound
>>>> of the same variable is 0 (with SCIPvarGetUbAtIndex()).
>>>>
>>>> But the global upper bound of this variable is 1 and not 0.
>>>> I also queried the value var->glbdom.lb and var->glbdom.ub
>>>> of the same variable.
>>>>
>>>> Is it normal that var->glbdom.lb = 1 and var->glbdom.ub = 0?
>>>> Note that the domain of this variable is {0,1}.
>>>>
>>> you say that the global upper bound is not 1 but zero and now you say
>>> var->glbdom.ub = 0; can you please check again, what happens.
>>>
>>> Contradicting global bounds should be not possible. Did you try to run
>>> your program with valgrind; it can find invalid writes and many more
>>> things. (www.valgrind.org)
>>>
>>> Best, Michael
>>>
>>>> Thanks,
>>>> Alex
>>>>
>>>>
>>>>
>>>> On Thu, 2013-10-10 at 18:46 +0200, Ambros Gleixner wrote:
>>>>> Hi Alex,
>>>>>
>>>>> this is a good remark.  The point is that it is a tighter *global*
>>>>> bound.  Hence in your example,  if s has a lower bound of 5, the reasons
>>>>> "s >= 3" and "s >= 5" are equivalent: an empty list of bound changes.
>>>>> (I.e., t >= 6 should be globally valid.)
>>>>>
>>>>> Thanks,
>>>>>
>>>>> Ambros
>>>>>
>>>>>
>>>>> PS: Maybe you want to confirm for your safety that the tighter value
>>>>> from SCIPvarGetLbAtIndex() is the same as SCIPvarGetLbGlobal().
>>>>>
>>>>>
>>>>>
>>>>> Am 10.10.2013 18:31, schrieb Alexander Schnell:
>>>>>> Thank you for this information. This helped very much but
>>>>>> I have another remark.
>>>>>>
>>>>>> I agree on the part that the tighter bound may be used
>>>>>> as a reason for the propagation, but i think the old lower
>>>>>> bound would lead to a better explanation:
>>>>>>
>>>>>> assume that s >= 3 lead to the bound change of t >= 6
>>>>>> and the tighter global lower bound 5 is introduced for s.
>>>>>>
>>>>>> Then the old explanation s>= 3 -> t >= 6 is stronger than
>>>>>> s>= 5 -> t >= 6.
>>>>>>
>>>>>> Alex
>>>>>>
>>>>>>
>>>>>> On Thu, 2013-10-10 at 17:50 +0200, Ambros Gleixner wrote:
>>>>>>> That means you may use the tighter bound when computing a reason for
>>>>> the
>>>>>>> propagation.  This is preferable since it can give you a smaller
>>>>> reason
>>>>>>> than the bound that was known when the propagation was actually
>>>>>>> performed; smaller meaning a reason with less changes compared to the
>>>>>>> global bounds now.
>>>>>>>
>>>>>>> Hope that helps,
>>>>>>>
>>>>>>> ambros
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> Am 10.10.2013 17:44, schrieb Alexander Schnell:
>>>>>>>> Hi Ambros,
>>>>>>>>
>>>>>>>> yes, the lower bound is tighter.
>>>>>>>>
>>>>>>>> Alex
>>>>>>>>
>>>>>>>>
>>>>>>>>
>>>>>>>> On Thu, 2013-10-10 at 17:20 +0200, Ambros Gleixner wrote:
>>>>>>>>> Hi Alexander,
>>>>>>>>>
>>>>>>>>> is the value of the variable responsible for the lower bound change
>>>>>>>>> tighter than the value that was stored in inferinfo?
>>>>>>>>>
>>>>>>>>> I think this could be correct, if global bound changes have occured
>>>>> in
>>>>>>>>> the meantime.  Can somebody confirm this?
>>>>>>>>>
>>>>>>>>> Ambros
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>>
>>>>>>>>> Am 10.10.2013 17:15, schrieb Alexander Schnell:
>>>>>>>>>> Dear Marc,
>>>>>>>>>>
>>>>>>>>>> my problem is not about the variable
>>>>>>>>>> for which the lower bound change is applied (infervar) but about
>>>>> the
>>>>>>>>>> variable responsible for the lower bound change
>>>>>>>>>> (i.e. the lower bound of this variable).
>>>>>>>>>>
>>>>>>>>>> For this variable SCIPvarGetLbAtIndex(...,...,TRUE) and
>>>>>>>>>> SCIPvarGetLbAtIndex(...,...,FALSE) are the same values.
>>>>>>>>>>
>>>>>>>>>> I integrate the lower bound of this variable as an integer
>>>>> inferinfo
>>>>>>>>>> in the function SCIPinferVarLbCons(). Moreover, if I query
>>>>>>>>>> the lower bound of this variable in the CONS_RESPROP function
>>>>>>>>>> by SCIPvarGetLbAtIndex(), this does not correspond to the
>>>>>>>>>> inferinfo value.
>>>>>>>>>>
>>>>>>>>>> Note, that I can be sure that the value returned
>>>>>>>>>> from SCIPvarGetLbAtIndex() is integer (I tested it by
>>>>>>>>>> SCIPisFeasIntegral()).
>>>>>>>>>>
>>>>>>>>>> Best regards,
>>>>>>>>>> Alexander
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>>
>>>>>>>>>> On Thu, 2013-10-10 at 16:09 +0200, Marc Pfetsch wrote:
>>>>>>>>>>> Dear Alexander,
>>>>>>>>>>>
>>>>>>>>>>> the function SCIPvarGetLbAtIndex() contains a parameter in which
>>>>> you can
>>>>>>>>>>> specify whether the bound change in questions has already been
>>>>> applied.
>>>>>>>>>>> To which value have you set this value? In principle, you should
>>>>> be able
>>>>>>>>>>> to reconstruct the bound change at that time (using infervar and
>>>>> the
>>>>>>>>>>> above function).
>>>>>>>>>>>
>>>>>>>>>>> Please also check whether the bound change via
>>>>> SCIPinferVarLbCons()
>>>>>>>>>>> actually changed the bound (check return values infeasible and
>>>>> tightened).
>>>>>>>>>>> You can look at other examples of conflict resolution, e.g.,
>>>>>>>>>>> cons_linearordering.c in examples/LOP. Please note that
>>>>> implementing
>>>>>>>>>>> conflict resolution always is a tricky thing.
>>>>>>>>>>>
>>>>>>>>>>> If this does not explain the problem, we would need more details
>>>>> from
>>>>>>>>>>> you in order to be able to reconstruct the problem. Possibly off
>>>>> this
>>>>>>>>>>> list ...
>>>>>>>>>>>
>>>>>>>>>>> Best
>>>>>>>>>>>
>>>>>>>>>>> Marc
>>>>>>>>>>>
>>>>>>>>>>>
>>>>>>>>>>> On 10.10.2013 15:32, Alexander Schnell wrote:
>>>>>>>>>>>> Dear SCIP team,
>>>>>>>>>>>>
>>>>>>>>>>>> I implemented a Constraint Handler for a special
>>>>>>>>>>>> project scheduling problem.
>>>>>>>>>>>>
>>>>>>>>>>>> In the CONS_RESPROP function, I try to explain the bound
>>>>>>>>>>>> changes processed through the propagation algorithm implemented
>>>>> in
>>>>>>>>>>>> the CONS_PROP function.
>>>>>>>>>>>>
>>>>>>>>>>>> In the function for the explanation generation, I observed a
>>>>> problem
>>>>>>>>>>>> with the function SCIPvarGetLbAtIndex(...):
>>>>>>>>>>>>
>>>>>>>>>>>> In the propagation algorithm, the lower bound is propagated with
>>>>>>>>>>>> the function SCIPinferVarLbCons(). I integrate the integer lower
>>>>> bound
>>>>>>>>>>>> of the variable responsible for the processed bound change as an
>>>>>>>>>>>> inferinfo in this function.
>>>>>>>>>>>>
>>>>>>>>>>>> In the CONS_RESPROP function, I compare the latter value with
>>>>> the actual
>>>>>>>>>>>> lower bound of the responsible variable given by
>>>>>>>>>>>> SCIPvarGetLbAtIndex(...) at the given bound change index.
>>>>>>>>>>>>
>>>>>>>>>>>> My problem is that these values are not the same, which should
>>>>> not be
>>>>>>>>>>>> the case in my understanding.
>>>>>>>>>>>>
>>>>>>>>>>>> Thank you in advance for your help.
>>>>>>>>>>>>
>>>>>>>>>>>> Best regards,
>>>>>>>>>>>> Alexander Schnell
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>>
>>>>>>>>>>>> _______________________________________________
>>>>>>>>>>>> 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
>>>>>>>>>> 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
>>>> http://listserv.zib.de/mailman/listinfo/scip
>>>>
>>>
>>> _______________________________________________
>>> Scip mailing list
>>> Scip at zib.de
>>> http://listserv.zib.de/mailman/listinfo/scip
>>>
>> -- 
>> ____________________________________________________________
>> Ambros M. Gleixner
>> Zuse Institute Berlin - Matheon - Berlin Mathematical School
>> http://www.zib.de/gleixner
>
> _______________________________________________
> Scip mailing list
> Scip at zib.de
> http://listserv.zib.de/mailman/listinfo/scip

More information about the Scip mailing list