patternMinor
Constructing a list of functions/formulas which describes a set of grid points in a 3D matrix
Viewed 0 times
functionsgridpointsformulasconstructingwhichlistmatrixdescribesset
Problem
Given a 3D matrix of size $N \times N \times N$, let $\mathcal{S}$ be a set of points in the Matrix and $\mathcal{S}'$ be the complement of $\mathcal{S}$. Can we find a set of equations of the form:
$F: (f_1 \land f_2 \land \ldots \land fn)$
where $f_x$ is of the form
$f_x \implies ai + bj + ck + dN + e \text{ } \{,=,\neq\} \text{ } 0$
$f_x$ is true if a point satisfies the aforementioned function and false otherwise
where $i,j,k$ are the indices of the grid points in the Matrix (which vary from 1 to $N$) and $a,b,c,d,e$ are integers such that
$F(\text{all points in }\mathcal{S}) = True$
$F(\text{all points in }\mathcal{S}') = False$
For example:
If $N = 4$, and $S = \{(1,1,1),(2,2,2),(3,3,3),(4,4,4)\}$, we can say that the functions $f_1 \implies i-k=0$ and $f_2 \implies j-k=0$ are one solution for this set.
Ideally we are interested in a solution with the minimum number of equations, but this is not necessary.
$F: (f_1 \land f_2 \land \ldots \land fn)$
where $f_x$ is of the form
$f_x \implies ai + bj + ck + dN + e \text{ } \{,=,\neq\} \text{ } 0$
$f_x$ is true if a point satisfies the aforementioned function and false otherwise
where $i,j,k$ are the indices of the grid points in the Matrix (which vary from 1 to $N$) and $a,b,c,d,e$ are integers such that
$F(\text{all points in }\mathcal{S}) = True$
$F(\text{all points in }\mathcal{S}') = False$
For example:
If $N = 4$, and $S = \{(1,1,1),(2,2,2),(3,3,3),(4,4,4)\}$, we can say that the functions $f_1 \implies i-k=0$ and $f_2 \implies j-k=0$ are one solution for this set.
Ideally we are interested in a solution with the minimum number of equations, but this is not necessary.
Solution
Yes. You can. You can use linear algebra and linear programming to find a $F$ that is true for all points in $S$ and false for all points in $S'$.
Small simplifications.
Note that $d$ is unnecessary. $N$ is a constant, so without loss of generality we can assume $d=0$ (otherwise replace $e$ by $dN+e$). So, we will assume each $f$ has the form $ai+bj+ck+e \bowtie 0$. Also note that the contents of the matrix itself are irrelevant and all that matters is the set $S$. Finally, I will assume you are looking for integer values of $a,b,c,e$, with no limit on how large or small they are.
Finding a $f$.
Let's start by showing how, given $S$, you can find a $f$ that is true for all points in $S$. There are several cases, according to which relational operator $f$ uses:
-
Equality: For $f$ of the form $ai+bj+ck+e=0$, consider the $a,b,c,e$ as four unknowns. For each point $(i,j,k) \in S$, we obtain a linear equation on these four unknowns. You can use linear algebra to find a value for $a,b,c,e$ such that $ai+bj+ck+e=0$ is true for all $(i,j,k) \in S$, if one exists: basically, you use Gaussian elimination to invert the matrix resulting from this system of equations. Moreover, you can find a basis for the set of all $a,b,c,e$ that are valid solutions.
In this way, we either find zero, one, two, three, or four independent equality constraints $f$ that will be true for all points in $S$.
-
Less than or equal to: For $f$ of the form $ai+bj+ck+e \le 0$, we can use linear programming to find $a,b,c,e$ that make this inequality true for all $(i,j,k) \in S$. Each $(i,j,k) \in S$ yields a single linear inequality on the unknowns $a,b,c,e$. Form a system of inequalities obtained by all the points in $S$. Solving this then gives us a valid combination of values for $a,b,c,e$. There may be many solutions; linear programming will give you an arbitrary solution, not necessarily the best one.
You can improve this to check whether there exists a single linear inequality that separates $S$ from $S'$: simply add the linear inequality $ai+bj+ck+e \ge 1$ for each $(i,j,k) \in S'$ to the system of linear equations above, and check whether it has a valid solution. If yes, then you have a single linear inequality $f$ that yields a minimal solution (an $F$ containing only a single $f$), and you are done. If not, next try the following heuristic to find a $f$ that separates $S$ from $S'$ as well as possible:
Introduce unknowns $x_{i,j,k}$ for each $(i,j,k) \in S'$, and constrain them by $0 \le x_{i,j,k} \le 1$. Add constraints $ai+bj+ck+e \ge x_{i,j,k}$ for each $(i,j,k) \in S'$. Now use linear programming to search for values for $a,b,c,e$ that maximize the objective function $\sum_{(i,j,k) \in S'} x_{i,j,k}$. This will force $f$ to be true for all points in $S$ and aim to make it false for as many points in $S'$ as possible.
If you want $a,b,c,e$ to be integers, use integer linear programming instead of linear programming.
-
Less than: For $f$ of the form $ai+bj+ck+e
-
Inequality: Simply swap the roles of $S$ and $S'$ and then use the approach for equalities.
Finding $F$.
So, given sets $S,S'$, this shows how to find a single constraint $f$ that could be included in $F$. But how do we find a full $F$?
I don't know of any efficient way to find the optimal $F$. However, I can suggest a heuristic that I suspect will work well: use an iterative greedy algorithm, where at each iteration you find a $f$ that is true for all points in $S$ and that is false for as many points that haven't been covered yet as possible.
In particular, at each stage, we will have a candidate $F$ that is true for all points in $S$, and is false for some points in $S'$. Define $T = \{(i,j,k) \notin S : F(i,j,k)=\text{True}\}$. Our goal will be to find $f$ that is true for all points in $S$ and is false for as many points in $T$ as possible; then we will replace $F$ with $F \land f$.
Given $S,T$, how can we find $f$ that is true for all $S$ and false for as many points in $T$ as possible? Well, I've already described how. For each relational operator $\bowtie \in \{=,\ne,\}$, use the procedures above to find a candidate $f$ that uses that operator and is true for all of $S$ and false for as much of $T$ as possible. This gives you four candidates for $f$. For each candidate, count how many elements of $T$ it is false for, and keep the best one you find.
In this way, I expect you'll fairly rapidly converge to a $F$ that is either optimal (contains the minimal number of clauses) or is close to optimal.
Small simplifications.
Note that $d$ is unnecessary. $N$ is a constant, so without loss of generality we can assume $d=0$ (otherwise replace $e$ by $dN+e$). So, we will assume each $f$ has the form $ai+bj+ck+e \bowtie 0$. Also note that the contents of the matrix itself are irrelevant and all that matters is the set $S$. Finally, I will assume you are looking for integer values of $a,b,c,e$, with no limit on how large or small they are.
Finding a $f$.
Let's start by showing how, given $S$, you can find a $f$ that is true for all points in $S$. There are several cases, according to which relational operator $f$ uses:
-
Equality: For $f$ of the form $ai+bj+ck+e=0$, consider the $a,b,c,e$ as four unknowns. For each point $(i,j,k) \in S$, we obtain a linear equation on these four unknowns. You can use linear algebra to find a value for $a,b,c,e$ such that $ai+bj+ck+e=0$ is true for all $(i,j,k) \in S$, if one exists: basically, you use Gaussian elimination to invert the matrix resulting from this system of equations. Moreover, you can find a basis for the set of all $a,b,c,e$ that are valid solutions.
In this way, we either find zero, one, two, three, or four independent equality constraints $f$ that will be true for all points in $S$.
-
Less than or equal to: For $f$ of the form $ai+bj+ck+e \le 0$, we can use linear programming to find $a,b,c,e$ that make this inequality true for all $(i,j,k) \in S$. Each $(i,j,k) \in S$ yields a single linear inequality on the unknowns $a,b,c,e$. Form a system of inequalities obtained by all the points in $S$. Solving this then gives us a valid combination of values for $a,b,c,e$. There may be many solutions; linear programming will give you an arbitrary solution, not necessarily the best one.
You can improve this to check whether there exists a single linear inequality that separates $S$ from $S'$: simply add the linear inequality $ai+bj+ck+e \ge 1$ for each $(i,j,k) \in S'$ to the system of linear equations above, and check whether it has a valid solution. If yes, then you have a single linear inequality $f$ that yields a minimal solution (an $F$ containing only a single $f$), and you are done. If not, next try the following heuristic to find a $f$ that separates $S$ from $S'$ as well as possible:
Introduce unknowns $x_{i,j,k}$ for each $(i,j,k) \in S'$, and constrain them by $0 \le x_{i,j,k} \le 1$. Add constraints $ai+bj+ck+e \ge x_{i,j,k}$ for each $(i,j,k) \in S'$. Now use linear programming to search for values for $a,b,c,e$ that maximize the objective function $\sum_{(i,j,k) \in S'} x_{i,j,k}$. This will force $f$ to be true for all points in $S$ and aim to make it false for as many points in $S'$ as possible.
If you want $a,b,c,e$ to be integers, use integer linear programming instead of linear programming.
-
Less than: For $f$ of the form $ai+bj+ck+e
-
Inequality: Simply swap the roles of $S$ and $S'$ and then use the approach for equalities.
Finding $F$.
So, given sets $S,S'$, this shows how to find a single constraint $f$ that could be included in $F$. But how do we find a full $F$?
I don't know of any efficient way to find the optimal $F$. However, I can suggest a heuristic that I suspect will work well: use an iterative greedy algorithm, where at each iteration you find a $f$ that is true for all points in $S$ and that is false for as many points that haven't been covered yet as possible.
In particular, at each stage, we will have a candidate $F$ that is true for all points in $S$, and is false for some points in $S'$. Define $T = \{(i,j,k) \notin S : F(i,j,k)=\text{True}\}$. Our goal will be to find $f$ that is true for all points in $S$ and is false for as many points in $T$ as possible; then we will replace $F$ with $F \land f$.
Given $S,T$, how can we find $f$ that is true for all $S$ and false for as many points in $T$ as possible? Well, I've already described how. For each relational operator $\bowtie \in \{=,\ne,\}$, use the procedures above to find a candidate $f$ that uses that operator and is true for all of $S$ and false for as much of $T$ as possible. This gives you four candidates for $f$. For each candidate, count how many elements of $T$ it is false for, and keep the best one you find.
In this way, I expect you'll fairly rapidly converge to a $F$ that is either optimal (contains the minimal number of clauses) or is close to optimal.
Context
StackExchange Computer Science Q#62532, answer score: 2
Revisions (0)
No revisions yet.