[Scip] Problem with Conflict Analysis
Alexander Schnell
alexander.schnell at univie.ac.at
Mon Oct 21 13:09:49 CEST 2013
Hi Stefan,
thank you very much for your information.
> @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.
> >
I ran SCIP in Debug mode and also tried valgrind to find memory errors
or uninitialized values. Both did not lead to any errors for the special
instance. I think there is a problem when calling members of a
SCIP-struct in the above way in my code, because I also found strange
values in elements of other structs. When calling this values directly
in the SCIP code or by SCIP functions (SCIPvarGetLBGlobal()), there seem
to be no problems.
> 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.
Thank you for this explanation. This helped me much and the situation is
now clear for me.
I did not think about repropagation and thought the bounds at
propagation time must be the same as in the situation when I resolve a
bound change.
Thanks, Alex.
On Fri, 2013-10-18 at 22:48 +0200, Stefan Heinz wrote:
> 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