How to solve "linear multiset equations"?

Question

I have a bunch of linear forms in the same number of variables, with the number of linear forms much larger than the number of variables. Say, they are $\ell_i(x_1,...,x_n)=l_{i1}x_1+...+l_{in}x_n$, for $i=1,...,N$.

I also have a multiset of values, $c_k$ with multiplicity $m_k$, for $k=1,...,K$, with $\sum_{k=1}^Km_k=N$.

I need to find a solution, by which I mean find $x_1$, ..., $x_n$ such that the values $\ell_i(x_1,...,x_n)$, $i=1,...,N$ form this multiset. That is, there must be $m_k$ copies of $c_k$ among these values, for each $k=1,...,K$, regardless of specific places where they might occur.

Are there methods to impose conditions ensuring existence of a solution, and solve the system under these conditions?

Answer 1

Here's the outline of the ILP formulation:

Let $y_{ik}$ be binary variables such that $y_{ik} = 1$ if the linear form $i$ takes the value $c_k$ and $y_{ik} = 0$ otherwise. We want to find the values of $x_1, ..., x_n$ and $y_{ik}$ that satisfy the following constraints:

For each linear form $i$, exactly one $y_{ik}$ is equal to 1: $[\sum_{k=1}^K y_{ik} = 1, \quad i = 1, ..., N]$

The values of $c_k$ should appear exactly $m_k$ times: $[\sum_{i=1}^N y_{ik} = m_k, \quad k = 1, ..., K]$

The linear form $i$ takes the value $c_k$ only if $y_{ik} = 1$: $[l_{i1}x_1 + ... + l_{in}x_n - c_k = M(1 - y_{ik}), \quad i = 1, ..., N, \quad k = 1, ..., K]$

Here, $M$ is a large constant (greater than the maximum possible value of the linear form) to enforce the constraint when $y_{ik} = 0$.

Now you can use an ILP solver like IBM CPLEX, Gurobi, or the open-source SCIP solver to find the solution to this problem. This will give you the values of $x_1, ..., x_n$ and $y_{ik}$ that satisfy the constraints. For your problem size should be manageable.

If you want to explore multiple solutions, you can iteratively solve the ILP with additional constraints that exclude the previous solutions until no more feasible solutions are found or you have found enough solutions for your needs.

Answer 2

Denote: $\ell_{i}(x_{1},x_{2}\dots x_{i}) = v_{i}$

Find a set of $n$ indices $r_1, r_2, \dots r_n$ such that $\ell_{r_1}, \ell_{r_2}, \dots \ell_{r_n}$ are linearly independent. Let M be the matrix made of their coefficients.

We have: $M(x_{1},x_{2}\dots x_{i}) = (v_{r_1},v_{r_{2}}\dots v_{r_{i}})$

Since $\ell_{r_{i}}$ are linearly independent, the values that we choose for $(v_{r_1},v_{r_{2}}\dots v_{r_{i}})$ uniquely determine $(x_1,x_2\dots x_{n})$. We have:

$M^{-1} (v_{r_1},v_{r_{2}}\dots v_{r_{i}}) = (x_{1},x_{2}\dots x_{i})$
where $M^{-1}$ is the inverse matrix of $M$.

So, an algorithm would be:

1. Find a set of $n$ indices $r_1, r_2, \dots r_n$ such that $\ell_{r_1}, \ell_{r_2}, \dots \ell_{r_n}$ are linearly independent. Let M be the matrix made of their coefficients. Compute $M^{-1}$

2. Chose a set of values for $(v_{r_{i}}, v_{r_{2}}\dots v_{r_{n}})$ that make it a valid subset of your multi-set. (ie. the values must appear in your multi-set, and the number of times a given value appears must not be greater than the required multiplicity)

3. Compute $ (x_{1},x_{2}\dots x_{i}) = M^{-1} (v_{r_1},v_{r_{2}}\dots v_{r_{i}})$

4. Now that we know the values of $x_{i}$, we may compute the rest of $v_{i} = l_{i} (x_{1},x_{2}\dots x_{n})$ (where $i$ is not part of the set $\{r_1,r_2,\dots r_n\}$), and see if the resultant $v$s complete our multi-set.

If they fail to complete it properly, we go to step 2 and assign a different subset or a different ordering to $(v_{r_1},v_{r_{2}}\dots v_{r_{i}})$ and try again. We do this until we either find a solution or run out of ways to assign the subset values to $(v_{r_1},v_{r_{2}}\dots v_{r_{i}})$.

Edit: assume your rank is $m < n$. Then you select $n-m$ variables $x_{f_{1}},x_{f_{2}}\dots x_{f_{n-m}}$ which can be set to $0$ without lowering the rank (ie. the rank of the system of the remaining $m$ variables $x_{i}$ is still $m$. the system contains a rank $m$ minor) and set them to $0$. The algorithm can be applied to calculate the remaining $x$ .