MPC 2024 - Issue 1
KidneyExchange.jl: a Julia package for solving the kidney exchange problem with branch-and-price
(2024)
The kidney exchange problem (KEP) is an increasingly important healthcare man-
agement problem in most European and North American countries which consists of
matching incompatible patient-donor pairs in a centralized system. Despite the signif-
icant progress in the exact solution of KEP instances in recent years, larger instances
still pose a challenge especially when non-directed donors are taken into account. In
this article, we present a branch-and-price algorithm for the exact solution of KEP
in the presence of non-directed donors. This algorithm is based on a disaggregated
cycle and chains formulation where subproblems are managed through graph copies.
We additionally present a branch-and-price algorithm based on the position-indexed
chain-edge formulation as well as two compact formulations. We formalize and ana-
lyze the complexity of the resulting pricing problems and identify the conditions under
which they can be solved using polynomial-time algorithms. We propose several algo-
rithmic improvements for the branch-and-price algorithms as well as for the solution
of pricing problems. We extensively test all of our implementations using a bench-
mark made up of different types of instances. Our numerical results show that the
proposed algorithm can be significantly faster compared to the state-of-the-art. All
models and algorithms presented in the paper are gathered in an open-access Julia
package, KidneyExchange.jl.
In this paper, we develop a self-adaptive ADMM that updates the penalty parame-
ter adaptively. When one part of the objective function is strongly convex i.e., the
problem is semi-strongly convex, our algorithm can update the penalty parameter
adaptively with guaranteed convergence. We establish various types of convergence
results including accelerated convergence rate of O(1/k2), linear convergence and
convergence of iteration points. This enhances various previous results because we
allow the penalty parameter to change adaptively. We also develop a partial proximal
point method with the subproblems being solved by our adaptive ADMM. This enables
us to solve problems without semi-strongly convex property. Numerical experiments
are conducted to demonstrate the high efficiency and robustness of our method.
The Clique Partitioning Problem is a fundamental and much-studied N P-hard combi-
natorial optimisation problem, with many applications. Several families of benchmark
instances have been created in the past, but they are scattered across the literature and
hard to find. To remedy this situation, we present CP-Lib, an online resource that
contains most of the known instances, plus some challenging new ones.
Domain-Driven Solver (DDS) is a MATLAB-based software package for convex opti-
mization. The current version of DDS accepts every combination of the following
function/set constraints: (1) symmetric cones (LP, SOCP, and SDP); (2) quadratic
constraints that are SOCP representable; (3) direct sums of an arbitrary collection of
2-dimensional convex sets defined as the epigraphs of univariate convex functions
(including as special cases geometric programming and entropy programming); (4)
generalized Koecher (power) cone; (5) epigraphs of matrix norms (including as a
special case minimization of nuclear norm over a linear subspace); (6) vector rela-
tive entropy; (7) epigraphs of quantum entropy and quantum relative entropy; and (8)
constraints involving hyperbolic polynomials. The infeasible-start primal-dual algo-
rithms used for DDS rely heavily on duality theory and properties of Legendre-Fenchel
conjugate functions, and are designed to rigorously determine the status of a given
problem. We discuss some important implementation details and techniques we used
to improve the robustness and efficiency of the software. The appendix contains many
examples.
We present new methods for solving a broad class of bound-constrained nonsmooth
composite minimization problems. These methods are specially designed for objec-
tives that are some known mapping of outputs from a computationally expensive
function. We provide accompanying implementations of these methods: in particular,
a novel manifold sampling algorithm (MS-P) with subproblems that are in a sense
primal versions of the dual problems solved by previous manifold sampling methods
and a method (GOOMBAH) that employs more difficult optimization subproblems. For
these two methods, we provide rigorous convergence analysis and guarantees. We
demonstrate extensive testing of these methods. Open-source implementations of the
methods developed in this manuscript can be found at https://github.com/POptUS/
IBCDFO/.