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?
Instead of your slot-based approach, I have an arc-based formulation in mind. For $i\in\{1,\dots,n\}$, define nodes $p_i \in P$, $a_i \in D$, and $b_i \in D$ (three nodes per triple). Define a bipartite network with parts $D$ and $P$ with an arc $(d,p)\in A$ from donor node $d \in D$ to patient node $p \in P$ if $d$ is compatible with $p$. For $p\in P$, let binary variable $x_p$ indicate whether patient $p$ is matched. For $(d,p)\in A$, let binary variable $y_{d,p}$ indicate whether $d$ donates to $p$. The problem is to maximize $\sum_{p\in P} x_p$ subject to linear constraints: \begin{align} \sum_{(d,p)\in A} y_{d,p} &= 2 x_p &&\text{for all $p\in P$} \tag1\\ \sum_{(a_i,p)\in A} y_{a_i,p} &= x_{p_i} &&\text{for all $i$} \tag2\\ \sum_{(b_i,p)\in A} y_{b_i,p} &= x_{p_i} &&\text{for all $i$} \tag3\\ x_{p_i} &\le y_{a_i,p_i} &&\text{for all $i$ such that $(a_i,p_i)\in A$} \tag4\\ \end{align} Constraint $(1)$ enforces exactly two donors per matched patient. Constraints $(2)$ and $(3)$ enforce that $a_i$ and $b_i$ donate exactly once each if and only if $p_i$ is matched. Constraint $(4)$ enforces that $a_i$ donates to $p_i$ if they are compatible and $p_i$ is matched.
To account for altruistic donors $d\in D'$, introduce arcs $(d,p)\in A'$ to indicate compatibility and replace $(1)$ with $$\sum_{(d,p)\in A \cup A'} y_{d,p} = 2 x_p \quad\text{for all $p\in P$} \tag{1'}$$ For patients like $p_1$ that have already been matched but their donors $a_1$ and $b_1$ have not yet donated, you can omit $p_1$ from the problem and treat $a_1$ and $b_1$ as altruistic donors that must be used by imposing \begin{align} \sum_{(a_1,p)\in A} y_{a_1,p} &= 1 \tag5\\ \sum_{(b_1,p)\in A} y_{b_1,p} &= 1 \tag6\\ \end{align}
To account for patients without donors, introduce additional nodes $p\in P$ and additional arcs $(d,p)\in A$ to indicate compatibility. Include these new $p$ in $(1')$ and keep constraints $(2)$, $(3)$, and $(4)$ as is. If this is a patient without donors because the donors have already been used, then impose $x_p=1$ to force this patient to get matched.
The general framework for this network-based formulation is that each person is represented by a node, each compatibility between donor and patient is represented by an arc, and any rules are enforced by linear constraints among the binary node and arc variables.
Here is SAS code to solve the small instance linked in the comments. Maybe it will help you repair your AMPL code.
Note that the following three conditions in the DonateOnce constraint are equivalent to each other, and I used the first one because it is the shortest:
Also, the p2 in the summation that appears in the body of the DonateOnce constraint is a dummy index and does not need to be declared. Equivalently:
Expanding all the constraints yields: