How to formulate: each pair of elements in $A$ has one common unit in $B$

Question

We have two sets, $A$ and $B$. Some elements of $A$ must be connected to some elements of $B$, but no element of a given set is connected to another element of the same set. (Think of a bipartite graph, and we are trying to establish the edges between the two sets.)

I have a constraint that says:

For every pair of elements of $A$, there is (at least/exactly) one element of $B$ that both elements of $A$ are connected to.

For now, I have formulated this constraint by introducing a binary variable $x_{a_1,a_2,b}$ that equals 1 if $a_1,a_2\in A$ are both connected to $b\in B$, and then adding a constraint that says:

$$\sum_{b\in B} x_{a_1,a_2,b} \ge 1 \qquad \forall a_1,a_2\in A$$

(Or replace $\ge$ with $=$ for the "exactly one" version.)

But I'd really like to avoid having these triply-indexed variables. Can anyone think of a way to enforce this constraint without the $x_{a_1,a_2,b}$ variables?

Answer 1

If you don’t require linear constraints, you can introduce (or reuse) binary variables $y_{a.b}$ and quadratic constraints $$\sum_{b\in B} y_{a_1,b} y_{a_2,b} \ge 1 \qquad \forall a_1,a_2\in A,$$ for which your triply-indexed formulation is a linearization. If you do need linear and are worried about the problem size, you can generate the violated constraints dynamically. Depending on your other constraints, you might also be able to use compact linearization a la Liberti.

Answer 2

Can you consider an extended formulation? In this case you could consider variables $x_{A',b} \in \{0,1\}$ with value 1 iff

$$ \begin{align} \{a,b\} \in E & \quad & \forall a \in A' \\ \{a,b\} \not\in E & \quad & \forall a \not\in A' \end{align} $$

(where $E$ is the edge set of the bipartite graph). In other words it determines which subset $A' \subseteq A$ is connected with vertex $b$.

Then, I believe, your constraint becomes: $$ \sum_{b \in B} \sum_{A' \supseteq \{a_1, a_2\}} x_{A',b} = 1 \quad \forall a_1,a_2 \in A \;\; (a_1 \neq a_2) $$

and you need to ensure that

$$ \sum_{A' \subseteq A} x_{A',b} = 1 \quad \forall b \in B $$

Of course enumerating the variables is not feasible, and you should resort to some column generation approach.

Answer 3

For the at-least variant, it seems you can write down this problem as propositional logic and convert your constraints into Conjunctive Normal Form, which gives you the constraints you need only using the edge-variables.

Given sets $A$ and $B$ and variables $\forall i\in A, j \in B: x_{i,j}$, the constraints can be written as $$\bigwedge_{i,j \in A} \bigvee_{k \in B} (x_{ik} \wedge x_{jk})$$ which are not the constraints of the language of Integer Programming. However, these constraints can be converted into the Conjunctive Normal Form to obtain constraints that are easily mapped to IP constraints.

I made a short Python script that uses the boolean algebra module of Sympy to automate this process.

from sympy.core import Symbol
from sympy.logic.boolalg import *

# Define the sizes of sets A and B
a_size = 3
b_size = 2

# Define sets A and B
A = [i for i in range(a_size)]
B = [i for i in range(b_size)]

# Build a dictionary for the variables
X = {i : {j : Symbol('x{}_{}'.format(i,j)) for j in B} for i in A}

# Construct a logic expression capturing all constraints
expr = True
for i in A:
    for j in A:
        if i != j:
            subExpr = False
            for k in B:
                subSubExpr = And(X[i][k],X[j][k])
                subExpr = Or(subExpr, subSubExpr)
            expr = And(expr, subExpr)

print('The logic expression is:')
print(expr)

# Convert the logic expression to CNF
cnf_expr = to_cnf(expr)

print('In CNF the logic expression is:')
print(cnf_expr)

# Iterate over the 'And' terms of the CNF expression
for conjunctive_term in cnf_expr.args:
    # Extract variable names of the terms
    varnames = [str(a) for a in conjunctive_term.args]
    # Print the IP-constraint corresponding to the conjunctive term
    lhs = ' + '.join(varnames)
    print(lhs + ' >= 1')

Applied to a case where $|A| = 3$ and $|B| = 2$, this gives us the logical constraint $$((x_{0,0} \wedge x_{1,0}) \vee (x_{0,1} \wedge x_{1,1})) \wedge ((x_{0,0} \wedge x_{2,0}) \vee (x_{0,1} \wedge x_{2,1})) \wedge ((x_{1,0} \wedge x_{2,0}) \vee (x_{1,1} \wedge x_{2,1}))$$

converted to CNF this constraint becomes

$$(x_{0,0} \vee x_{0,1}) \wedge (x_{0,0} \vee x_{1,1}) \wedge (x_{0,0} \vee x_{2,1}) \wedge (x_{0,1} \vee x_{1,0}) \wedge (x_{0,1} \vee x_{2,0}) \wedge (x_{1,0} \vee x_{1,1}) \wedge (x_{1,0} \vee x_{2,1}) \wedge (x_{1,1} \vee x_{2,0}) \wedge (x_{2,0} \vee x_{2,1})$$

And converted to linear constraints, this gives us $$ \begin{align*} x_{0,0} + x_{0,1} &>= 1 \\ x_{0,0} + x_{1,1} &>= 1 \\ x_{0,0} + x_{2,1} &>= 1 \\ x_{0,1} + x_{1,0} &>= 1 \\ x_{0,1} + x_{2,0} &>= 1 \\ x_{1,0} + x_{1,1} &>= 1 \\ x_{1,0} + x_{2,1} &>= 1 \\ x_{1,1} + x_{2,0} &>= 1 \\ x_{2,0} + x_{2,1} &>= 1 \end{align*} $$

Note that the number of constraints generated by this approach grows quite rapidly: for $|A|=3$ and $|B|$ is $3, 4, 5, 6$ the numbers of constraints generated by this script seem to be $21, 45, 93, 189$. The Online Encyclopedia of Integer Sequences seems to contain some information on this sequence which suggest some binomial-related growth, but I did not analyze this in more detail. It may thus be necessary to figure out the actual structure of the generated constraints and use a cutting plane method to solve larger instances in practice.

However, I do think does avoid the need to generate the triplet variables for the at-least variant.

Answer 4

How about we write your constraint, just replacing the tuple of $(a_1, a_2)$ with, say, $a'$. So, you'll have two indexed variables of $x_{a',b}$.

What I mean is, first enumerate all the pairs of $A$, and then, do your sum over those (and I think you'll have a faster write-time of your constraint in python, for instance, too)

Answer 5

If $B_i$ is the set whose elements are connected by $a_i$, then for the "at least" condition we want $$\sum_{b_k\in B_i\cap B_j\\\quad i\ne j}|b_k|>0\qquad\forall a_i,a_j\in A$$ where $k=1,\cdots,K$ with $K=|B_i\cap B_j|$.

For the "exactly one" condition we want $$-b_1+\sum_{b_k\in B_i\cap B_j\\\quad i\ne j}|b_k|=0\qquad\forall a_i,a_j\in A.$$

Answer 6

(edit: now I read more carefully, I see Rob Pratt already alluded to this approach, but might as well expand on it)

Another option is the lazy constraint method: solve the problem without bothering to implement the constraint, check whether the constraint is violated, and if it is add a new constraint that prevents those particular violations and repeat.

For instance, suppose I get a solution where $a_i$ and $a_j$ have no common connection. Let $S$ be the set of $k$ such that $a_i$ connected to $b_k$ in this particular (invalid) solution.

For that particular $i$ and $j$, I can then add a constraint: if $x_{i,k}=1 \forall {k\in S}$ and $x_{i,k}=0 \forall {k\notin S}$ then $\sum_{k\in S} x_{j,k} \ge 1$. This is very easily linearised.

Iterating on this will eventually give a solution that satisfies the "$\ge 1$" condition; a "$\le 1$" condition can be handled in a similar way if desired.

Whether this is an efficient way to do it depends on other aspects of the problem. If the other constraints and objective/s are such that solutions will mostly satisfy the condition even without being specifically constrained to do so, with only a few violations, then this might be a relatively painless way to deal with those exceptions. It might be useful since it avoids needing to create $O(n^3)$ extra DVs.

OTOH, if there are a lot of violations of this rule, then you may end up iterating for a long time. Especially if solution time per iteration is long, lazy constraints might not be your best bet.