Originally posted by: SystemAdmin

[pierre schaus said:]

Hello,

I want to implement an incremental propagator but how
to know from my propagate() method if I have to be incremental (same node or children of previous node)
or not (after backtrack)?

IlcRevInt seems to be useful to this end because in the API it is written:
This value data member is automatically restored when Solver backtracks.

Is is the right way to detect backtracks or is there something simpler?

Thanks in advance,

Pierre.
#CPOptimizer
#DecisionOptimization

Originally posted by: SystemAdmin

[shaw said:]

Hello Pierre,

There are different ways of implementing incrementality.  The most common
way is to use reversible data structures which are automatically backtracked
on backtrack (IlcRevInt, IlcRevAny, IlcRevFloat).  When you use these, you only
have to worry about going "down".  When Solver backtracks, the values stored
in those data structures are restored to their previous values.  In additional,
you would normally use different demons and not the global "propagate()"
member function to do the domain filtering.
  If you can give some more information on what you want to do, we will better
be able to advise you.

Regards,


Paul
#CPOptimizer
#DecisionOptimization

Originally posted by: SystemAdmin

[pierre schaus said:]

Thank you for your answer.

I try to implement a propagator based on flows (very similar to the global cardinality constraint)
and I need to maintain incrementally the maximum flow.
What I wanted to do is:
- recompute from scratch the maximum flow when a backtrack occurs
- and otherwise maintain the max flow incrementally  when an arc is deleted like suggested in the paper of J-C. Régin: "Generalized Arc Consistency for Global Cardinality Constraint".

Do you think reversible data structures are possible to maintain a maximum flow in the variable-value graph?
I could keep the flow in each arc in an adjacency matrix of IlcRevInt.
But maintain the the adjacency lists seems more difficult to me (for example, the set of variables having a particular value inside their domain).

Regards,

Pierre.







#CPOptimizer
#DecisionOptimization

Originally posted by: SystemAdmin

[shaw said:]

Hello Pierre,

The solution you adopt will really depend on the efficiency of your algorithm vs.
the number of arcs which change value when you go down in the tree.  If you are
changing the values of many arcs, then this will incur an overhead in Solver to save
and restore their values on backtracking.  If you modify few arcs, it could be
very efficient.
  If you want to recompute on backtracking, you need just to store the number of
fails each time you compute the max flow.  If the current number of fails is different
from the number of fails the last time you computed the max flow, then it is out
of date and you need to recompute it.


Paul

PS You could you IlcIntSet to maintain the adjacency lists (IlcIntSet is reversible)
#CPOptimizer
#DecisionOptimization