[gecode-users] Re : Maximal consistent assignment

[Mikael Zayenz Lagerkvist]

On Tue, Oct 21, 2008 at 10:11 AM,  <benoitlaurent at neuf.fr> wrote:
> 1) I used the number of "unassigned variables" to constrain the search and
> to speed up
> the branch-and-bound process. If I do not use dummy values any more, I won't
> be able to do so.

I'm not sure how this is achieved: if you require at least x variables
assigned, then you won't know that you can't assign more variables
until an assignment fails, aborting the search anyway. As I don't have
any knowledge of what to use (maximal) partial assignments for, I'm
not really the person discuss this. Anyway, on to the next part...

> 2) As I said before, I am not an expert with GECODE. How can I record
> partial assignments ?

The definition of a partial assignment is just the set of assigned
variables as long as propagation does not detect failure. Thus
whenever a new node is explored and it is not failed, you have a
larger set. At his point in the search you should record it. Places to
insert your code could be in the search-procedure for example, or you
could write your own dfs-exploration. Gecode does not expose any APIs
for reacting to events during the search-process (see [1]).

You said you are searching for a maximal partial assignment, that is
the set of assignments in a node where assignment of any other
variable to any other value gives failure. You can get this
indirectly, for example, by having a standard search and testing the
nodes as you explore them. The test is if the node is directly above
only failures given that you try all possible assignment of variables
to values. Not sure about the efficiency of this method though.

Cheers,
Mikael

[1] http://article.gmane.org/gmane.comp.lib.gecode.user/1701

--
Mikael Zayenz Lagerkvist, http://www.ict.kth.se/~zayenz/