1
$\begingroup$

I have a group of logical conditions and need to deduce values that would NOT satisfy them. For example:

  1. City != New York && Location = Museum
  2. City = New York && Location = Store
  3. City != New York && Location != Subway
  4. Elevation = 100'

So some values that would NOT satisfy any of those conditions are:

  • City: New York, Location: Museum, Elevation: 110'
  • City: Moscow, Location: Subway, Elevation: 110'

I just need to derive values, any values, that will fail to satisfy all conditions. (Application: Generating manual tests.)

It's easy to figure out values to violate any one condition, but I'm having trouble coming up with an algorithm to generate values that will violate them all. I have all the logical conditions in a data format (JSON, e.g. { key: 'City', operator: '=', referenceValue = 'New York' }).


This solution worked for me, but I'm not making it an answer because it's not super-elegant and I'm not sure it would work in all cases.

  1. Create a value hash for each key, populating it with all possible values for that key.
  2. Each value for each key is marked ALLOWED initially, but can later be marked CONTINGENT or DISALLOWED. (I created a ValueDisposition class to manage this.)
  3. Find relevant conditions for each key, and analyze their effect on values. For example analyzing condition 4 above for elevation would mark 100' as DISALLOWED (because we are looking to find data that violate all the given conditions). Analyzing condition 2 above for City would mark New York as CONTINGENT because it is only a valid value if the contingent condition Location = Store is violated (I record contingent conditions in the ValueDisposition class as well).
  4. Do a first pass finding an ALLOWED value for as many keys as possible.
  5. Do a second pass on CONTINGENT values, violating the contingent conditions to derive acceptable value-sets (for example, with New York it's easy to violate Location = Store). I was able to do this easily for all of my condition-sets, but this could get challenging (requiring recursion?) if you had contingent conditions involving multiple keys.
$\endgroup$
8
  • $\begingroup$ Is each of the conditions either one simple predicate or the conjunction of two predicates? Are there other forms? $\endgroup$
    – John L.
    Jun 20, 2019 at 18:44
  • $\begingroup$ Yes, they are either simple predicates or the conjunction of multiple predicates (never more than 5 I'd say). $\endgroup$
    – ed94133
    Jun 20, 2019 at 18:45
  • 1
    $\begingroup$ Have you heard of boolean satisfiability problem (SAT) and SAT solver? $\endgroup$
    – John L.
    Jun 20, 2019 at 18:46
  • $\begingroup$ Unless most of the conditions involve only at most two predicates, your problem is likely to be really hard, NP-hard. $\endgroup$
    – John L.
    Jun 20, 2019 at 18:50
  • $\begingroup$ I hadn't. If my problem is equivalent to SAT, then it seems like randomized assignment of the values (the PPSZ algorithm) is the fastest way to look for a solution? $\endgroup$
    – ed94133
    Jun 20, 2019 at 18:51

1 Answer 1

1
$\begingroup$

As the comments indicated, if the goal is to invent fictional cities, and you allow more three or more conjuncts in a condition, then any SAT problem is reducible to your problem.

Depending on the type of constraints, this is probably a more general problem, called "SAT Modulo Theories" or SMT for short. It's the boolean satisfiability problem, plus the theory of whatever your constraints are.

For example, if you allow inequalities:

Elevation < 200

You now need to decide what kinds of constraints those are. If elevation is an integer, and you allow constraints between properties (e.g. number of subway stations is less than the number of suburbs), then solving the problem is, in general, an integer programming feasibility problem.

But chances are that you don't need to worry about that for your scale. If we allow the closed-world assumption, in the sense that the set of city names and locations etc is fixed, then backtracking search is probably good enough. A small Prolog program will do the job.

Here, I used GNU Prolog, and attached the finite domain solver for elevation:

city(new_york).
city(moscow).
city(london).
city(paris).

location(museum).
location(store).
location(subway).
location(grand_bazaar).

% The lowest city in the world is Jericho, and the highest city
% is La Paz.
elevation(Elevation) :- fd_domain(Elevation, -846, 11975).

satisfying_cities(City, Location, Elevation) :-
    city(City),
    location(Location),
    elevation(Elevation),
    (City = new_york ; \+ Location = museum),
    (\+ City = new_york ; \+ Location = store),
    (City = new_york ; Location = subway),
    (Elevation #\= 100).

And running the query:

?- satisfying_cities(City, Location, Elevation).

gives some answers, the first of which is:

City = new_york
Elevation = _#0(0..99:101..127@)
Location = museum

The FD constraint on elevation is a little hard to read, but it's essentially saying that any elevation between 0 and 99 or 101 and 127 will do.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.