[26] Benjamin Plaut, John Dickerson, and Tuomas Sandholm. "Fast optimal clearing of capped-chain barter exchanges". In: *Proceedings of the AAAI Conference on Artificial Intelligence*. Vol. 30. 1. 2016.

[27] Benjamin Plaut, John P. Dickerson, and Tuomas Sandholm. *Hardness of the Pricing Problem for Chains in Barter Exchanges*. June 1, 2016. URL: http://arxiv.org/abs/1606.00117 (visited on 02/28/2021).

[28] Felix T Rapaport. In: *Transplantation proceedings*. Vol. 18. 3) Suppl. 2. 1986, pp. 5–9.

[29] Lizeth Carolina Riascos-Álvarez, Merve Bodur, and Dionne M. Aleman. *A Branch-and-Price Algorithm Enhanced by Decision Diagrams for the Kidney Exchange Problem*. Oct. 4, 2020. URL: http://arxiv.org/abs/2009.13715 (visited on 02/22/2021).

[30] A. E. Roth, T. Sonmez, and M. U. Unver. "Kidney Exchange". In: *The Quarterly Journal of Economics* 119.2 (2004), pp. 457–488.

[31] Alvin E Roth, Tayfun Sönmez, and M. Utku Ünver. "Efficient Kidney Exchange: Coincidence of Wants in Markets with Compatibility-Based Preferences". In: *American Economic Review* 97.3 (2007), pp. 828–851.

[32] Alvin E. Roth, Tayfun Sönmez, and M. Utku Ünver. "Pairwise Kidney Exchange". In: *Journal of Economic Theory* 125.2 (2005), pp. 151–188.

[33] Susan L. Saidman, Alvin E. Roth, Tayfun Sönmez, M Utku Ünver, and Francis L. Delmonico. "Increasing the Opportunity of Live Kidney Donation by Matching for Two- and Three-Way Exchanges". In: *Transplantation* 81.5 (Mar. 15, 2006), pp. 773–782.

[34] Bart Smeulders, Valentin Bartier, Yves Crama, and Frits C. R. Spieksma. "Recourse in Kidney Exchange Programs". In: *INFORMS Journal on Computing* 34.2 (2022), pp. 1191–1206.

[35] Leonardo Taccari. "Integer Programming Formulations for the Elementary Shortest Path Problem". In: *European Journal of Operational Research* 252.1 (July 2016), pp. 122–130.

[36] Robert Endre Tarjan. "Edge-Disjoint Spanning Trees and Depth-First Search". In: *Acta Informatica* 6.2 (1976), pp. 171–185.

# Statements and Declarations

## Funding

The authors declare that no funds, grants, or other support were received during the preparation of this manuscript.

## Conflict of interest

The authors declare that they have no conflict of interest.

## Availability of data and materials

The PrefLib instances studied in this article are publicly available. Other instances can be randomly generated using the Julia package available through our GitHub repository. URLs are included in this published article. The randomly generated instances used in this article as well as the analysed results are available through the corresponding author upon reasonable request.
[26] Benjamin Plaut, John Dickerson, and Tuomas Sandholm. "Fast optimal clearing of capped-chain barter exchanges". In: *Proceedings of the AAAI Conference on Artificial Intelligence*. Vol. 30. 1. 2016.

[27] Benjamin Plaut, John P. Dickerson, and Tuomas Sandholm. *Hardness of the Pricing Problem for Chains in Barter Exchanges*. June 1, 2016. URL: http://arxiv.org/abs/1606.00117 (visited on 02/28/2021).

[28] Felix T Rapaport. In: *Transplantation proceedings*. Vol. 18. 3) Suppl. 2. 1986, pp. 5–9.

[29] Lizeth Carolina Riascos-Álvarez, Merve Bodur, and Dionne M. Aleman. *A Branch-and-Price Algorithm Enhanced by Decision Diagrams for the Kidney Exchange Problem*. Oct. 4, 2020. URL: http://arxiv.org/abs/2009.13715 (visited on 02/22/2021).

[30] A. E. Roth, T. Sonmez, and M. U. Unver. "Kidney Exchange". In: *The Quarterly Journal of Economics* 119.2 (2004), pp. 457–488.

[31] Alvin E Roth, Tayfun Sönmez, and M. Utku Ünver. "Efficient Kidney Exchange: Coincidence of Wants in Markets with Compatibility-Based Preferences". In: *American Economic Review* 97.3 (2007), pp. 828–851.

[32] Alvin E. Roth, Tayfun Sönmez, and M. Utku Ünver. "Pairwise Kidney Exchange". In: *Journal of Economic Theory* 125.2 (2005), pp. 151–188.

[33] Susan L. Saidman, Alvin E. Roth, Tayfun Sönmez, M Utku Ünver, and Francis L. Delmonico. "Increasing the Opportunity of Live Kidney Donation by Matching for Two- and Three-Way Exchanges". In: *Transplantation* 81.5 (Mar. 15, 2006), pp. 773–782.

[34] Bart Smeulders, Valentin Bartier, Yves Crama, and Frits C. R. Spieksma. "Recourse in Kidney Exchange Programs". In: *INFORMS Journal on Computing* 34.2 (2022), pp. 1191–1206.

[35] Leonardo Taccari. "Integer Programming Formulations for the Elementary Shortest Path Problem". In: *European Journal of Operational Research* 252.1 (July 2016), pp. 122–130.

[36] Robert Endre Tarjan. "Edge-Disjoint Spanning Trees and Depth-First Search". In: *Acta Informatica* 6.2 (1976), pp. 171–185.

# Statements and Declarations

## Funding

The authors declare that no funds, grants, or other support were received during the preparation of this manuscript.

## Conflict of interest

The authors declare that they have no conflict of interest.

## Availability of data and materials

The PrefLib instances studied in this article are publicly available. Other instances can be randomly generated using the Julia package available through our GitHub repository. URLs are included in this published article. The randomly generated instances used in this article as well as the analysed results are available through the corresponding author upon reasonable request.
# Code availability

The full code was made available for review and is publicly available through our GitHub repository. We remark that a set of optimization packages were used in this study, that were either open source or available for academic use. Specific references are included in this published article.

# Appendix

## 6.1 Position-indexed chain-edge formulation (PICEF)

$$ \max \sum_{s \in S} \sum_{c \in C_K^s} w_c z_c + \sum_{(u,v) \in A} \sum_{l=1}^{L} w_{u,v} y_{u,v,l} \quad (32) $$

$$ \text{s.t.} \quad \sum_{s \in S} \sum_{c \in C_K^s(v)} z_c + \sum_{u|(u,v) \in A} \sum_{l=1}^{L} y_{u,v,l} \le 1 \quad \forall v \in V \quad (33) $$

$$ \sum_{v|(v,u) \in A} y_{v,u,l} \ge \sum_{v|(u,v) \in A} y_{u,v,(l+1)} \quad \forall u \in P, l = 1, \dots, L-1 \quad (34) $$

$$ \sum_{v|(u,v) \in A} y_{u,v,1} = 0 \quad \forall u \in P \quad (35) $$

$$ \sum_{v|(u,v) \in A} y_{u,v,l} = 0 \quad \forall u \in D, l = 2, \dots, L \quad (36) $$

$$ z_c \in \{0, 1\} \quad \forall s \in S, c \in C_K^s \quad (37) $$

$$ y_{u,v,l} \in \{0, 1\} \quad \forall (u, v) \in A, l = 1, \dots, L. \quad (38) $$

Here, constraints (33) impose that each vertex is involved in at most one chain or cycle, (34) are flow balance constraints and ensure that a chain is formed by the chain-flow (y) variables, (35)-(36) impose that only non-directed donors can initiate a chain and therefore appear in position $l = 1$ and only in position $l = 1$.

## 6.2 Detailed numerical results

<table><caption>Table 4: Average solution time (for instances solved to optimality) using each compact MIP formulation.</caption><thead><tr><th rowspan="2"></th><th rowspan="2">L</th><th colspan="2">128</th><th colspan="2">256</th><th colspan="2">512</th><th colspan="2">1024</th></tr><tr><th>EE</th><th>HPIEF</th><th>EE</th><th>HPIEF</th><th>EE</th><th>HPIEF</th><th>EE</th><th>HPIEF</th></tr></thead><tbody><tr><td rowspan="2">het</td><td>4</td><td>3</td><td>3</td><td>13</td><td>16</td><td>633</td><td>193</td><td>1330</td><td>-</td></tr><tr><td>6</td><td>3</td><td>3</td><td>16</td><td>17</td><td>226</td><td>217</td><td>1426</td><td>-</td></tr><tr><td rowspan="2">Said</td><td>4</td><td>2</td><td>2</td><td>18</td><td>15</td><td>197</td><td>237</td><td>-</td><td>3925</td></tr><tr><td>6</td><td>3</td><td>2</td><td>21</td><td>19</td><td>391</td><td>363</td><td>-</td><td>-</td></tr><tr><td rowspan="2">spa</td><td>4</td><td>1</td><td>0</td><td>2</td><td>2</td><td>11</td><td>17</td><td>3584</td><td>1033</td></tr><tr><td>6</td><td>1</td><td>1</td><td>3</td><td>3</td><td>16</td><td>20</td><td>-</td><td>-</td></tr></tbody></table>
# Code availability

The full code was made available for review and is publicly available through our GitHub repository. We remark that a set of optimization packages were used in this study, that were either open source or available for academic use. Specific references are included in this published article.

# Appendix

## 6.1 Position-indexed chain-edge formulation (PICEF)

$$ \max \sum_{s \in S} \sum_{c \in C_K^s} w_c z_c + \sum_{(u,v) \in A} \sum_{l=1}^{L} w_{u,v} y_{u,v,l} \quad (32) $$

$$ \text{s.t.} \quad \sum_{s \in S} \sum_{c \in C_K^s(v)} z_c + \sum_{u|(u,v) \in A} \sum_{l=1}^{L} y_{u,v,l} \le 1 \quad \forall v \in V \quad (33) $$

$$ \sum_{v|(v,u) \in A} y_{u,v,l} \ge \sum_{v|(u,v) \in A} y_{u,v,(l+1)} \quad \forall u \in P, l = 1, \dots, L-1 \quad (34) $$

$$ \sum_{v|(u,v) \in A} y_{u,v,1} = 0 \quad \forall u \in P \quad (35) $$

$$ \sum_{v|(u,v) \in A} y_{u,v,l} = 0 \quad \forall u \in D, l = 2, \dots, L \quad (36) $$

$$ z_c \in \{0, 1\} \quad \forall s \in S, c \in C_K^s \quad (37) $$

$$ y_{u,v,l} \in \{0, 1\} \quad \forall (u, v) \in A, l = 1, \dots, L. \quad (38) $$

Here, constraints (33) impose that each vertex is involved in at most one chain or cycle, (34) are flow balance constraints and ensure that a chain is formed by the chain-flow (y) variables, (35)-(36) impose that only non-directed donors can initiate a chain and therefore appear in position $l = 1$ and only in position $l = 1$.

## 6.2 Detailed numerical results

<table><caption>Table 4: Average solution time (for instances solved to optimality) using each compact MIP formulation.</caption><thead><tr><th rowspan="2"></th><th rowspan="2">L</th><th colspan="2">128</th><th colspan="2">256</th><th colspan="2">512</th><th colspan="2">1024</th></tr><tr><th>EE</th><th>HPIEF</th><th>EE</th><th>HPIEF</th><th>EE</th><th>HPIEF</th><th>EE</th><th>HPIEF</th></tr></thead><tbody><tr><td rowspan="2">het</td><td>4</td><td>3</td><td>3</td><td>13</td><td>16</td><td>633</td><td>193</td><td>1330</td><td>-</td></tr><tr><td>6</td><td>3</td><td>3</td><td>16</td><td>17</td><td>226</td><td>217</td><td>1426</td><td>-</td></tr><tr><td rowspan="2">Said</td><td>4</td><td>2</td><td>2</td><td>18</td><td>15</td><td>197</td><td>237</td><td>-</td><td>3925</td></tr><tr><td>6</td><td>3</td><td>2</td><td>21</td><td>19</td><td>391</td><td>363</td><td>-</td><td>-</td></tr><tr><td rowspan="2">spa</td><td>4</td><td>1</td><td>0</td><td>2</td><td>2</td><td>11</td><td>17</td><td>3584</td><td>1033</td></tr><tr><td>6</td><td>1</td><td>1</td><td>3</td><td>3</td><td>16</td><td>20</td><td>-</td><td>-</td></tr></tbody></table>