How do I check the validity of a set of inequality constraints?

Question

I have a table of inequality constraints, each with an "x < y" relation. How can I check this table for contradictory logic such as a < b, b < c, c < a?

For example

library(data.table)
set.seed(0)
ineqs <- unique(data.table(
  X = sample(head(letters, 5), 5, replace = T),
  Rel = "<",
  Y = sample(head(letters, 5), 5, replace = T)
))

ineqs
   X Rel Y
1: e   < b
2: b   < e
3: c   < d
4: e   < d

In this case, a function like is_valid(constraints) should obviously return FALSE because the constraints e < b, and b < e are contradictory.

Answer 1

The relation matrix $M(R)$ is the binary indicator of the relation: in this case, the entry in $M(\lt)$ for variables $x,y$ is $1$ (true) when $x\lt y$ and $0$ (false) otherwise.

These individual relationships imply other relationships through the transitivity property $a\lt b$ and $b\lt c$ implies $a\lt c.$ The resulting transitive closure of the relation matrix must be consistent with antisymmetry: $M(R)[x,y]=1$ implies $M(R)[y,x]=0.$ The transitive closure is readily (if not entirely efficiently) found by taking powers of $M(R)$ until they stabilize, treating all values of $0$ as false and all nonzero values as true.

Thus, you can systematically check such a relation by (1) generating its matrix, (2) computing its transitive closure, and (3) checking that for (partial) antisymmetry. This is a general solution for any transitive, partially asymmetric relation, although it needs an (obvious) modification for reflexive relationships like $\le$ (where $M(R)[x,x]=1$ for all $x$).

Below is working R code to illustrate. It checks five relations defined by sets of inequalities (given as character strings involving alpha variables). Its output is

[1] "Invalid: FALSE"
[1] "Valid: TRUE"
[1] "Invalid.2: FALSE"
[1] "Valid.2: TRUE"
[1] "Invalid.3: FALSE"

The first term is my indication of whether the relation is valid and the second TRUE/FALSE is the code's determination. It and I agree. The first line of output corresponds to the example in the question.

constraint.to.matrix <- function(x) {
  ab <- sapply(x, function(s) strsplit(s, "[^[:alpha:]]+"))
  vars <- sort(unique(unlist(ab)))
  n <- length(vars)
  r <- matrix(0, n, n, dimnames=list(vars, vars))
  for (rel in ab) {
    r[rel[1], rel[2]] <- 1
  }
  r
}

is.antisymmetric <- function(r) all(c(t(r) + r + diag(nrow(r))) <= 1)

transitive.closure <- function(r) {
  s <- r + diag(nrow(r)) >= 1
  while(TRUE) {
    r1 <- r %*% s > 0
    if (all(r1 - r == 0)) break
    r <- r1
  }
  r
}

check <- function(constraints) 
  is.antisymmetric(transitive.closure(constraint.to.matrix(constraints)))

trials <- list(Invalid=list("e < b", "b < e", "c < d", "e < d"),
               Valid=list("a<b", "b<c", "c<d"),
               Invalid.2=list("a<b", "b<c", "c<d", "d<a"),
               Valid.2=list(),
               Valid.3=list("a<a"))

for (s in names(trials))  print(paste0(s, ": ", check(trials[[s]])))

Answer 2

The solution by @whuber is more complete than this one. However, if one accepts to use the igraph package, one can use the graph properties to test for transitivity, so that there is almost no code to write.

Transforming the list of inequalities into a list of edges of a directed graph, we can test whether the graph is acyclic (see here for a definition).

library(igraph)
## Form a graph out of the edge list
gg <- graph_from_edgelist(as.matrix(ineqs[,c(1,3)]), 
    directed = TRUE)
## Test if the graph is a DAG
is_dag(gg)

In the case of the data generated above, indeed, the graph is not acyclic and the test returns FALSE. (If you change the seed to 1 and keep the code above, you'll generate a DAG: the inequalities do not have any contradiction).