[gecode-users] QuickXplain implementation for Gecode/Flatzinc

[Adriane Boyd]

Hi,

In case it could be useful for others, I wanted to share an implementation 
of QuickXplain that I wrote for Gecode/FlatZinc.  I've made it available 
as a patch for Gecode 3.4.2 here:

http://www.ling.ohio-state.edu/~adriane/code/gecode/fz-qx-3.4.2-0.1.patch

The patch adds the executable fz-qx, which implements the QuickXplain 
algorithm from Junker (2001).  fz-qx prints out the set of conflicting 
constraints as a list of constraint IDs, which correspond to the position 
of the constraints in the flatzinc input.  The patch extends the flatzinc 
parser and space so that constraints that have just been parsed can be 
stored as part of the space instead of being posted immediately.  This 
makes it possible for fz-qx to clone a space with its stored constraints 
and post subsets of constraints as needed for QuickXplain.

The output could certainly be more user-friendly, but I figured that most 
users would need to customize the output for their own applications 
anyway.  (An obvious next step would be to modify the flatzinc parser and 
data structures so that you can store/generate human-readable versions of 
constraints.)

Please feel free to let me know if you find any bugs or have suggestions 
for improvements!

Adriane Boyd