[eclipse-clp-users] Find all of THESE such that there exist THOSE

From: <mskala_at_...206...>
Date: Tue, 1 Oct 2013 18:16:41 -0500 (CDT)
I have a constraint program with 25 main variables (and several hundred
others that depend on them).  I would like to make a list of all vectors
of values for 9 of the variables such that at least one solution exists
for all the variables; but I don't care about the satisfying values of the
other 16, nor how many solutions exist for them, only the fact that some
satisfying assignment exists given the first 9.  I expect the list of
results to have maybe a few thousand entries on it, but that's only a
guesstimate; the ones I've generated so far vary wildly in length and how
long they turn out to be is one of my research questions.  It takes a few
seconds to a minute to solve each constraint problem (also varying
wildly) so I'm looking at a few CPU-hours to CPU-days to generate each
list, and that's acceptable, but more speed is always welcome.

What I've been doing is this:

* Search for any solution to the whole problem and capture the 9 variables
  I care about; call the vector of them S.
* Recursively search for solutions with the constraint that the 9
  variables, as a vector,  are lexicographically less than S.
* Return S on backtracking through this point.
* Recursively search for solutions with the constraint that the 9
  variables, as a vector, are lexicographically greater than S.

That gives me the whole list of vectors of my 9 variables for which
satisfying assignments to the entire problem exist; in lexicographic
order, even.  The main point is NOT to do more than one search through all
assignments of the remaining variables once we have one to return.  And it
works pretty well.  In particular, it works better than searching just the
9 variables first and then searching the rest of the problem inside of
once/1, because that approach messes up the variable selection heuristic
in the search.  But it still seems like I may be doing extra work because
of searching from the top of the tree on every recursive call, even with
the lexicographic constraint pruning those trees.  It seems like maybe
there ought to be something possible akin to what the branch and bound
library does, restarting searches in the middle as solutions are
accumulated.

So my question is, is there a known clever way to do this sort of thing
efficiently?
-- 
Matthew Skala
mskala_at_...206...                 People before principles.
http://ansuz.sooke.bc.ca/
Received on Tue Oct 01 2013 - 23:16:51 CEST

This archive was generated by hypermail 2.3.0 : Thu Feb 22 2024 - 18:13:20 CET