Given $n$ triples $(p_i, a_i, b_i)$ in an exchange. Each of these triples has at least one of $a_i$, $b_i$ which is incompatible with $p_i$ (for example, $a_i$ can be matched with $p_i$ but $b_i$ cannot). Each $p_i$ needs to be matched with exactly two of $a_j$, $b_k$ for $1\leq j, k\leq n$ (the indices $j, k$ might be the same, depending on the given compatibility conditions). If $a_i$ is compatible with both $p_i$ and $p_j$, $a_i$ must be matched with $p_i$, rather than $p_j$, because $(p_i, a_i)$ belong to the same triple initially. Define two triples $(p_i, a_i, b_i)$ and $(p_j, a_j, b_j)$ as one-way compatible IFF $p_i$ can be matched by exactly two elements (i.e., three is not allowed) of the triple $(a_i, a_j, b_j)$ or $(b_i, a_j, b_j)$ or $p_j$ can be matched by the remaining two (for example, one case would be when $p_i$ can be matched with $a_i$ and $a_j$. Another case is $p_j$ can be matched with $b_i$ and $b_j$). Finally, note that if $a_i$ or $b_i$ can be matched with $p_i$ and $p_j$, it is always the case that $a_i$ or $b_i$ is matched with $p_i$, because they belong to the same initial triple.
Now, my goal is to use Mixed-Integer Linear Programming to find the longest path (aka. no cycle allowed, only sequentially connected). This is equivalent to finding the path with the most number of triples that can be connected one-way among the $n$ triples (i.e., not all $n$ triples have to be connected, although that is the best-case scenario), assuming we know the compatibility among every $n\choose 2$ pairs $(a_i, p_j)$ and $n\choose 2$ pairs $(b_k, p_j)$ (i.e., we know exactly which $a_i, b_k$ can be matched with which $p_j$ (there can be more than one $p_j$ that can be matched with $a_i$ or $b_k$). Same for either $a_i$ or $b_k$).
Example of two longest paths with lengths $4$ (top) and $3$ (bottom), respectively, given two sets of $5$ triples with different compatibilities
My attempt
It is easy to see that the possibly longest length of the path is $n-1$, so this is an upper bound (the best-case scenario is all $n$ triples can be connected sequentially). Now, start with a path that has $n-1$ empty slot (call these 1st, 2nd, ... (n-1)-th position). Our objective is to fill in as many of these slots as possible with one (or maximum two, see reason below) from the $n$ triples, such that the preceding triple is one-way compatible with the triple followed after.
Now, for $1\leq i, j\leq n$, define $p_{ij} = 1$ if both $(a_i, b_i)$ are incompatible with $p_i$, and $p_i$ is scheduled in the $j$-th position. Call this Type-1 triple. Similarly, define $p_{ij} = 0$ if exactly one of $a_i, b_i$ is incompatible with $p_i$ (which means the remaining one is compatible with $b_i$), and $p_i$ is scheduled in the $j$-th position. Now, define $x^{(1)}_j$ and $x^{(2)}_j$ = the number of Type-1 and Type-2 triples in the $j-$th position, respectively. To track whether a position $j$ is filled, define $x_j = 1$ if the $j-$th position is non-empty, and $0$ otherwise.
Given the above definitions, note that at each $j$-th position, it is not possible that $p_{ij}= 1$ and $p_{tj} = 0$ for some $i\neq t$. In addition, at every positions, there is either one Type-1 triple or at most two Type-2 triples. This implies $\sum_{i=1}^{n} p_{ij} = x^{(1)}_{j}$. However, note that $\sum_{i=1}^{n} p_{ij} \neq x^{(0)}_{j}$, because the LHS is always $0$ if the $j$-th position contains only Type-2 triple, while the RHS is at least $1$ in that case.
From the above observations, the longest chain, given the compatibility results of $n$ triples, can be obtained by solving the following IP problem, \begin{eqnarray} max\ {\sum_{j = 1}^{n}}\ x_j \nonumber \\ \nonumber \end{eqnarray}
Subject to:
\begin{eqnarray} \sum_{i=1}^{n} p_{ij}\ = \ x^{(1)}_{j}\ \forall\ \ j=1,2,\ldots, n\\ p_{t,j+1}\leq p_{ij}, \ \ \forall\ \ 1\ \leq i,\ t\ \leq n\ ; j=1,2,\ldots, n-1\\ \sum_{t\ \neq\ m}^{n} (p_{tj} + p_{m,j+1})\leq\ x^{(1)}_{j} + x^{(1)}_{j+1}\ \ \forall\ \ j=1,2,\ldots, n-1\\ x^{(1)}_{j} + x^{(2)}_{j}\ \leq\ \max(x^{(1)}_{j},\ x^{(2)}_{j}) \ \ \forall\ \ j=1,2,\ldots, n\\ 1 - x_{j}\ \leq\ p_{ij}\ \leq \ x_j \ \ \forall\ \ i,\ j=1,2,\ldots, n\\ \sum_{j=1}^{n} (x^{(1)}_{j} + x^{(2)}_{j})\ \leq n\\ x^{(2)}_{j+1} + x^{(1)}_{j+1}\leq (2x^{(1)}_{j} + x^{(2)}_{j})x_j\ \ \forall\ \ j=1,2,\ldots, n-1\\ x^{(1)}_{j+1}\leq\ x^{(1)}_{j}\leq\ x_j\ \ \forall\ \ j=1,2,\ldots, n-1 \end{eqnarray}
Question: The formulation above seems not to account for the case of one triple in a sequence skipping the next triple (as shown in the sample Length-4 path). However, I think it does account for the case in Length-3 path, where there is a separate two sub-paths after the 2nd position. Can anyone please help me with the suitable constraint for governing the first case?
