  A kidney exchange is an organized barter market where patients in need of a
kidney swap willing but incompatible donors. Determining an optimal set of
exchanges is theoretically and empirically hard. Traditionally, exchanges took
place in cycles, with each participating patient-donor pair both giving and
receiving a kidney. The recent introduction of chains, where a donor without a
paired patient triggers a sequence of donations without requiring a kidney in
return, increased the efficacy of fielded kidney exchanges---while also
dramatically raising the empirical computational hardness of clearing the
market in practice. While chains can be quite long, unbounded-length chains are
not desirable: planned donations can fail before transplant for a variety of
reasons, and the failure of a single donation causes the rest of that chain to
fail, so parallel shorter chains are better in practice.
  In this paper, we address the tractable clearing of kidney exchanges with
short cycles and chains that are long but bounded. This corresponds to the
practice at most modern fielded kidney exchanges. We introduce three new
integer programming formulations, two of which are compact. Furthermore, one of
these models has a linear programming relaxation that is exactly as tight as
the previous tightest formulation (which was not compact) for instances in
which each donor has a paired patient. On real data from the UNOS nationwide
exchange in the United States and the NLDKSS nationwide exchange in the United
Kingdom, as well as on generated realistic large-scale data, we show that our
new models are competitive with all existing solvers---in many cases
outperforming all other solvers by orders of magnitude.
