Optimal Control Robot

Abstract

Mixed-integer model predictive control (MI-MPC) can be a powerful tool for con- linear or piecewise-linear system dynamics and inequality constraints, MI-MPC needs to solve a mixed-integer quadratic program (MIQP) at each sampling time step.

This paper presents a collection of exact block-sparse presolve techniques to effi- ciently remove decision variables, and to remove or tighten inequality constraints, approach based on a heuristic presolve algorithm to compute a feasible but possibly suboptimal MIQP solution. We present benchmarking results for a C code imple- mentation of the proposed BB-ASIPM solver, including a branch-and-bound (B&B) method with the proposed tailored presolve techniques and an active-set based inte- rior point method (ASIPM), compared against multiple state-of-the-art MIQP solvers on a case study of motion planning with obstacle avoidance constraints. Finally, we demonstrate the feasibility and computational performance of the BB-ASIPM solver in embedded system on a dSPACE Scalexio real-time rapid prototyping unit for a second case study of stabilization for an underactuated cart-pole with soft contacts.

Mixed-integer programming, Numerical optimization algorithms, Hybrid model predictive control

Ntroduction

Optimization-based motion planning and control techniques, such as model predictive control (MPC), allow a model-based design framework in which the dynamics, constraints and objectives are directly taken into account1. This framework has been extended to hybrid systems2, providing a powerful technique to model a large range of hybrid control problems, e.g., includ- ing switched dynamical systems3,4, discrete/quantized actuation5, motion planning with obstacle avoidance6, logic rules and temporal logic specifications7. However, the resulting optimal control problems (OCPs) are non-convex combinatorial opti- mization problems, because they contain variables that only take integer or binary values, and they are -hard to solve in general8. When using a linear-quadratic objective in combination with linear or piecewise-linear system dynamics and inequality constraints, the resulting OCP can be formulated as a mixed-integer quadratic program (MIQP).

†Tailored Presolve Techniques in Branch-and-Bound Method for Fast Mixed-Integer Optimal Control Applications

R. Quirynen Et Al

In the present work, we aim to solve MIQP problems of the following form:

Variables, I.E., The Cardinality |𝑖| ≤𝑛𝑖

u denotes the number of integer variables at each time step 𝑖∈{0, 1, … , 𝑁}. The objective in (1a) defines a linear-quadratic function with positive semi-definite Hessian matrix 𝐻𝑖⪰0 and gradient vectors 𝑞𝑖∈ℝ𝑛𝑖

𝑟𝑖∈ℝ𝑛𝑖

u. The constraints include state dynamic equality constraints in (1b), simple bounds in (1c), affine inequality constraints in (1d) and integer feasibility constraints in (1e). The optimization problem in (1) is an optimal control structured MIQP or a block-sparse MIQP due to the block-structured sparsity of the Hessian and constraint matrix, i.e., the objective in (1a) and inequality constraints in (1c)-(1d) are separable per time step 𝑖∈{0, 1, … , 𝑁} but the variables are coupled via the dynamics in (1b). Note that an initial state constraint 𝑥0 =̂ 𝑥0, wherê 𝑥0 is a current state estimate, can be enforced using the simple bounds in (1c). A compact notation is used to denote the optimization variables of the MIQP in (1) as the state 𝑋= [𝑥⊤

, … , 𝑢⊤

𝑁]⊤. In the present paper, we occasionally refer to all optimization variables in (1) as

𝑖, 𝑢⊤

𝑖]⊤for 𝑖∈{0, 1, … , 𝑁}. Unlike standard OCP formulations, the MIQP in (1) defines a mixed-integer OCP (MIOCP) that includes control variables on the terminal stage, 𝑢𝑁∈ℝ𝑛𝑁

U , Which May Include Auxiliary

variables to formulate the mixed-integer inequality constraints of the hybrid control system. A binary optimization variable 𝑢𝑖,𝑗∈{0, 1} can be defined as an integer variable 𝑢𝑖,𝑗∈ℤin (1e), including the simple bounds 0 ≤𝑢𝑖,𝑗≤1 in (1c). Without loss of generality and for simplicity of notation, the integer optimization variables in (1) are restricted to control variables, even though the methods in this paper can be trivially extended to MIOCPs with integer state variables. MPC for any hybrid system can be formulated as in (1), for example, by leveraging a mixed logical dynamical (MLD) model2. There are typically different ways to formulate a hybrid control problem in the form of the MIQP in (1), providing a tradeoff between the number of decision variables and strength of the formulation9. The strength of an MIQP corresponds to how close the convex relaxations are to the Mixed-integer MPC (MI-MPC) implementations for motion planning and control aim to solve the MIOCP in (1) at each sampling time step. This is challenging due to the -hard complexity of solving MIQPs in general8, and given the rela- tively small computational resources and available memory on embedded microprocessors for real-time control applications10.

Therefore, several tailored solution strategies have been proposed for MI-MPC. These approaches can generally be divided into heuristic techniques, which seek to efficiently find feasible but suboptimal solutions to the problem, and exact algorithms that solve the MIQPs to optimality. Examples of the former include rounding schemes11,12, the feasibility pump13, approximate opti- mization14,15, approximate dynamic programming16, and approximate explicit hybrid MPC17. Machine learning can be used to approximately solve combinatorial optimization problems18, e.g., using supervised learning to train a network architecture to quickly compute feasible but suboptimal solutions online as in19,20,21,22,23,24. The downside of fast heuristic approaches is often the lack of guarantees of finding an optimal, or even a feasible, solution.

Due to the complexity of solving MIQPs, explicit methods that compute offline the optimal control as a function of the system parameters have been developed, e.g., see25,26. The application of these explicit methods is generally limited to small- dimensional systems with few discrete variables. We therefore focus on the use of online solution methods in the present paper.

The MIQP in (1) is a mixed-integer convex program (MICP), i.e., it becomes a convex problem after relaxing the integer feasibility constraints in (1e). Most of the exact optimization algorithms for MIQPs are based on the classical branch-and- bound (B&B) technique27. Specifically for the structured MIQP in (1), the B&B strategy has been combined with tailored algorithms for solving the relaxed convex QPs. For example, a B&B algorithm for MI-MPC has been proposed in combination with a dual active-set solver in28, a primal active-set solver in29,30, an interior point algorithm in31, dual projected gradient methods in32,15, a nonnegative least squares solver in33, and with the alternating direction method of multipliers (ADMM) in34.

R. Quirynen Et Al

Machine learning could also be used to speed up the exact solution of combinatorial optimization problems, e.g., by improving the tree search in B&B methods18,35. B&B methods for solving mixed-integer nonlinear OCPs have also been studied, e.g., in36. The computational efficiency of B&B methods is affected by the node selection and branching rules37,38, and by the convex relaxation solutions39,40, but there are many other important factors that make state-of-the-art MIQP solvers like GUROBI41 and MOSEK42 successful. A crucial algorithmic ingredient is the presolve routine43, which typically is called in each node of the B&B method (see Figure 1) before solving the convex relaxation, and it performs a collection of operations to remove decision variables, and to remove or tighten constraints. In the present paper, we explicitly refer to these presolve techniques as exact operations to emphasize that they preserve feasibility and optimality, i.e., a feasible and optimal solution to the reduced problem exists as long as a feasible and optimal solution exists to the original MIQP. Exact presolve techniques are vital for the good performance of current state-of-the-art MICP solvers, such that B&B methods can often solve seemingly intractable problems in practice44. Especially for MI-MPC applications, warm starting strategies exist that aim to reuse the explored B&B tree at one time step to reduce the computational cost of the B&B method at the next control time step. In recent years, different variants of B&B warm starting have been proposed for MI-MPC, e.g., in33,29,45.

Unlike state-of-the-art mixed-integer solvers, e.g., GUROBI41 and MOSEK42, our aim is to propose a tailored algorithm and its solver implementation for fast embedded MI-MPC applications, i.e., running on microprocessors with considerably less computational resources and available memory10, while leveraging the special structure of the MIQP in (1). The optimization algorithm should be relatively simple to code with a moderate use of resources, while the software implementation is preferably compact and library independent. In the present paper, we will use a tailored active-set based interior point method (ASIPM) that was presented in46 to solve the block-sparse convex QP relaxations in the B&B method, resulting in an MIQP solver that will further be referred to as BB-ASIPM. The recent work in47 showed how infeasibility detection and early termination based on duality can be implemented efficiently for an infeasible primal-dual interior point method (IPM) based on a computationally efficient projection strategy that will be used within our BB-ASIPM solver.

Our Contributions: A first contribution of the present paper is an exact block-sparse presolve routine that is tailored to MIQPs of the form in (1). Our previous work in29,47 showed how domain propagation43,48 can be applied to the condensed form of (1). In the present paper, we propose an algorithm for domain propagation that can be applied directly to the MIQP in (1), based on a forward-backward propagation of variable bounds, in order to speed up the computation times of a B&B method. We additionally present tailored algorithms for other presolve techniques, including the removal of trivial constraints, dual fixings, constraint coefficient strengthening and binary variable probing. A second contribution involves the use of the proposed presolve routine in a heuristic procedure to compute a feasible but possibly suboptimal MIQP solution. This heuristic is an extension of the idea in24 for improving supervised learning of MICP solutions. A third contribution is the benchmarking results for a C code implementation of the BB-ASIPM algorithm against state-of-the-art MIQP solvers, including GUROBI41, MOSEK42, GLPK49, Cbc50, and Matlab’s intlinprog, based on a case study of mobile robot motion planning with obstacle avoidance constraints. A fourth and final contribution is the demonstration of the computational performance of the BB-ASIPM solver on a dSPACE Scalexio rapid prototyping unit, using a second case study of stabilization for an underactuated cart-pole with soft contacts.

The paper is organized based on each of the following algorithmic ingredients that are typically important for a good computational performance of a B&B method for mixed-integer optimal control applications: • variable branching decisions and node selection strategies (Section 2), • structure-exploiting convex solver for efficient QP solutions (Section 3), • exact presolve techniques for variable fixings and tight relaxations (Section 4), • fast primal heuristic algorithm to find integer-feasible solutions (Section 5), • warm starting and embedded software for mixed-integer MPC (Section 6).

The performance of our proposed MIQP solver is illustrated based on two MI-MPC case studies in Section 7, including hardware- in-the-loop simulations on a dSPACE Scalexio rapid prototyping unit. Finally, Section 8 concludes the paper.

Preliminaries On Mixed-Integer Quadratic Programming

We first introduce some of the basic concepts in mixed-integer quadratic programming (MIQP) solvers based on branch-and- bound (B&B) methods, such as convex QP relaxations, node selection and branching strategies.

R. Quirynen Et Al

FIGURE 1 Illustration of the branch-and-bound (B&B) method as a binary search tree. A selected node can be either branched, e.g., resulting in two partitions for each binary variable 𝑢𝑖,𝑗∈{0, 1}, or pruned based on feasibility or the current upper bound.

Branch-And-Bound Algorithm

The main idea of the B&B optimization algorithm is to sequentially create partitions of the original MIQP problem and attempt to solve each of these partitions. While solving each partition may still be challenging, it is fairly efficient to obtain local lower bounds on the optimal objective value, e.g., by solving convex relaxations of the MIQP subproblem. If we happen to obtain an integer-feasible solution while solving a relaxation, we can then use it to obtain a global upper bound for the solution to the original problem. This may help to avoid solving or branching certain partitions that were already created, i.e., such partitions or nodes can be pruned. The general algorithmic idea of partitioning is better illustrated as a binary search tree, see Figure 1.

A key step in this approach is how to create the partitions, i.e., which node to choose and which discrete variable to select for branching. Since we solve a convex relaxation at every node of the tree, it is natural to branch on one of the discrete variables with fractional values in the optimal solution of the relaxation. Therefore, if a binary variable, e.g., 𝑢𝑖,𝑗∈{0, 1} has a fractional value in a convex relaxation, we create two partitions where we add the equality constraints 𝑢𝑖,𝑗= 0 and 𝑢𝑖,𝑗= 1, respectively.

Another key choice is the order in which the created subproblems are solved. These steps have been extensively explored in the literature and various heuristics are implemented in state-of-the-art tools37.

Onvex Quadratic Program Relaxations

We use a B&B method to solve the MIQP (1) by solving convex quadratic programming (QP) relaxations that are constructed by dropping the integer feasibility constraints in (1e), e.g., 𝑢𝑖,𝑗∈{0, 1} is relaxed to a bounded continuous variable 0 ≤𝑢𝑖,𝑗≤1. Other convex relaxations for MIQPs have been studied in the literature such as moment or SDP relaxations that may be tighter than QP relaxations39,40, however they are often relatively expensive to solve, even if they may drastically reduce the nodes explored in a B&B method. In this paper, we restrict to standard QP relaxations and we present a tailored active-set based interior point method (ASIPM) in Section 3. The ASIPM solver has been shown to be competitive with state-of-the-art QP solvers for embedded MPC46, it benefits from warm-starting and it allows for an efficient implementation of infeasibility detection and early termination based on duality47. For using the ASIPM solver, the relaxations need to be convex, i.e., the Hessian matrices 𝐻𝑖need to be positive semi-definite in (1a) such that each solution to a QP relaxation is globally optimal.

Tree Search: Node Selection Strategies

A common implementation of the B&B method is based on a depth-first node selection strategy, which can be implemented by a last-in-first-out (LIFO) buffer. The next node to be solved is selected as one of the children of the current node and this process is repeated until integer feasibility or until a node is pruned because the node is either infeasible or dominated by the upper bound, which is followed by a backtracking procedure. Instead, a best-first strategy selects the node with the lowest local lower bound so far. In this paper, we will employ a combination of the depth-first and best-first node selection approach. This combination aims to find an integer-feasible solution quickly at the start of the B&B procedure (depth-first) to allow for early pruning, followed by a more greedy search for better feasible solutions (best-first).

Reliability Branching For Variable Selection

Many branching rules exist such as “most infeasible” branching which selects the integer variable with fractional part in the QP relaxation that is closest to 0.5. Even though this rule is used quite often, e.g., in33,34, it generally does not perform very well in practice37. We instead use reliability branching which is based on a combination of two concepts for variable selection: strong branching and pseudo-costs37. Strong branching relies on temporarily branching, both up (to higher integer) and down (to lower integer), for every integer variable that has a fractional value in the solution of a convex QP relaxation in a given node, before committing to the variable that provides the highest value for a particular score function. The increase in objective values Δ+

Δ−

𝑖,𝑗are computed when branching the integer variable 𝑢𝑖,𝑗, respectively, up and down. Given these quantities, a simple scoring function score(⋅, ⋅) is computed for each integer variable, such as the product score function38

(2)

given a small positive value 𝜖> 0. Full strong branching has been empirically shown to provide smaller search trees in practice37, but it is relatively expensive since several QP relaxations are solved in order to select one variable to branch on. The idea of pseudo-costs aims at approximating the increase of the objective function to decide which variable to branch on, without solving additional QP relaxations. This can be done by keeping statistic information for each integer variable, i.e., the pseudo-costs that represent the average increase in the objective value per unit change in that particular integer variable when branching. The current pseudo-cost values are computed based on branching decisions that occurred in different parts of the B&B tree37. Each variable has two pseudo-costs, 𝜙−

𝑖,𝑗when The Variable Is Branched “Down” And 𝜙+

𝑖,𝑗when it is branched “up”. However, at the beginning of the B&B algorithm, the pseudo-costs are not yet initialized, which is when branching decisions typically impact the tree size the most. Reliability branching uses strong branching to initialize the pseudo-costs until a certain condition of reliability is satisfied, e.g., it moves to using pseudo-costs for a particular variable once it has been branched on a specified number 𝜂𝑟𝑒𝑙of times37. Thus, reliability branching coincides with pseudo-cost branching if 𝜂𝑟𝑒𝑙= 0, with strong branching if 𝜂𝑟𝑒𝑙= ∞, but typically a value 1 ≤𝜂𝑟𝑒𝑙≤3 is chosen. This rule is further augmented by implementing a look ahead limit in the number of candidates, as well as a limit on the number of QP iterations in the strong branching step.

CONVEX RELAXATION SOLVER: ACTIVE-SET INTERIOR POINT METHOD (ASIPM) We reformulate the MIQP in (1) by the following compact notation

(3C)

where 𝒛includes all primal optimization variables and the index set denotes the integer variables. For many practical MPC

𝒚𝒚, Where 𝐻⪰0 And 𝑄≻0, By Partitioning

𝒛into 𝒗and 𝒚, entering in the linear-quadratic and linear-only terms, respectively. The objective of any MIQP (3) can be reformulated in the latter form by a change of variables, e.g., based on the eigenvalue decomposition for the Hessian 𝐻⪰0. We focus on the efficient solution of convex QP relaxations in a B&B optimization method. For a particular node of the B&B tree, a convex QP is obtained by relaxing the integer feasibility constraint in (3c) as̄ 𝒛𝑗≤𝒛𝑗≤̄ 𝒛𝑗, ∀𝑗∈̃ , where the index set̃ ⊆denotes each integer variable that has not been fixed due to branching, or due to the presolve routine, in the current node of the B&B tree. The values̄ 𝒛𝑗and̄ 𝒛𝑗denote the lower and upper bound values for each integer variable 𝑗∈̃ , respectively.

This section describes an overview of recent work on the efficient implementation of infeasibility detection and early termination based on duality47, applied to the active-set based interior point method (ASIPM) that was proposed in46.

(4C)

where 𝑄≻0 in the primal objective 𝜙(𝒗, 𝒚), and the inequality constraints (4b) include both the original inequalities from (3b) and the convex relaxations of the integer feasibility constraints. We additionally define the compact notation 𝒛∶= [𝒗⊤𝒚⊤]⊤,

(5C)

where 𝜆and 𝜇denote the Lagrange multipliers for the equality and inequality constraints, respectively, and̂ ℎ(𝜇, 𝜆) ∶= ℎ𝒗+

𝒗𝜇+ 𝐹⊤

𝒗𝜆is defined for simplifying the dual objective function 𝜓(𝜇, 𝜆) in (5a).

Primal-Dual Interior Point Method

A primal-dual IPM uses a Newton-type method to solve a sequence of relaxed Karush-Kuhn-Tucker (KKT) conditions for the convex QP in (4). An iteration of the IPM typically solves the reduced linear system51

𝑖∕𝜇𝑘

𝑖> 0, given current values of the slack variables 𝑠𝑘∈ℝ𝑛ieq and Lagrange multipliers 𝜇𝑘∈ℝ𝑛ieq for the inequality constraints in the 𝑘th iteration of the Newton-type method. The right-hand side in (6) denotes the residual value for the optimality conditions and reads as

(7)

based on the barrier parameter 𝜏𝑘→0 for 𝑘→∞, where 𝑀𝑘= diag (𝜇𝑘), 𝑆𝑘= diag (𝑠𝑘) and the slack variables are updated

As Δ𝑠𝑘= −(𝑊𝑘δ𝜇𝑘+ 𝑀𝑘−1𝑟𝑘

𝑠). We consider an infeasible primal-dual IPM for which the starting point {(𝒛0, 𝜇0, 𝜆0, 𝑠0)} may not be primal and/or dual feasible, but the slack variables and Lagrange multipliers are positive at each iteration, i.e., 𝑠𝑘≥0 and

Remark 1

Fixed variables, i.e.,̄ 𝒛𝑗=̄ 𝒛𝑗, and redundant constraints should be removed from each convex QP for computational efficiency.

N Some Cases, 𝑛0

x = 0 if an initial state value 𝑥0 =̂ 𝑥0 is imposed in (1), and many other variables are fixed due to exact presolve operations. Therefore, we require the QP solver to allow defining a varying number of state 𝑥𝑖∈ℝ𝑛𝑖

𝑢𝑖∈ℝ𝑛𝑖

u, and a varying number of inequality constraints 𝑛𝑖 c at each time step 𝑖= 0, 1, … , 𝑁in the prediction horizon.

Active-Set Based Inexact Newton Method

In this paper, we use the active-set based inexact Newton implementation of ASIPM from46, which allows for block-sparse structure exploitation, reduced computations, warm starting and improved numerical conditioning. For inequality constraints

𝑖> 0 Such That 𝑤𝑘

𝑖→∞for 𝑘→∞. Thus, the 𝑤-values become increasingly small and large for active and inactive inequality constraints, respectively, which highlights the well-known numerical ill-conditioning that

R. Quirynen Et Al

must be tackled when implementing IPMs52. Based on lower and upper bound values 0 < 𝑤min ≪𝑤max, at each IPM iteration, we classify the inequality constraints into the following three categories: • inactive: constraints that are likely to be inactive at the solution, with index set in ∶= { 𝑖∣𝑤𝑖≥𝑤max }, • active: constraints that are likely to be active at the solution, with index set act ∶= { 𝑖∣𝑤𝑖≤𝑤min }, • guessing: constraints that are uncertain, i.e., not in previous categories, with index set g ∶= { 𝑖∣𝑤min < 𝑤𝑖< 𝑤max }.

In the inexact Newton-type algorithm of ASIPM46, we solve the linearized KKT system in Eq. (6) approximately by solving the following reduced block-tridiagonal linear system

𝜇,In, By Using A Block-Tridiagonal

Cholesky factorization for the augmented Hessian matrix in (8). The inequality constraints and 𝑤-values have been reordered and grouped together according to their category, i.e., 𝑊𝑘

𝑖∈G. Similarly, We Split 𝐺

and̄ 𝑟𝜇into the corresponding blocks. The search directions for the Lagrange multipliers are computed as

(9B)

and the update to the slack variables as Δ𝑠𝑘= −𝑀𝑘−1(𝑆𝑘Δ𝜇𝑘+ 𝑟𝑘 𝑠). Early Termination based on Duality and Infeasibility Detection We do not need to solve a convex QP relaxation in the B&B method if

• The Convex Qp Relaxation Is Infeasible,

• the optimal solution has an objective value that exceeds the current global upper bound. In both cases, the node, and hence the corresponding subtree, can be pruned from the B&B tree. A considerable computational effort can be avoided if the above scenarios are detected early, i.e., more quickly than the time for solving the convex QP relaxations. Based on our work in47, we describe a tailored early termination strategy for infeasible primal-dual IPMs to handle both cases and to reduce the computational effort of the B&B method without affecting the quality of the optimal solution.

Due to duality properties, see, e.g.,53, for a dual feasible point (𝜇, 𝜆) that satisfies (5b)-(5c) and a primal feasible point (𝒗, 𝒚)

(10)

where 𝜙⋆and 𝜓⋆are the primal and dual optima, respectively. Based on (10), we propose an approach to find a dual feasible point that allows for early termination when 𝜓(𝜇, 𝜆) > UB for the current upper bound (UB) to the optimum of the MIQP.

Projection Strategy For Dual Feasibility

A dual feasible solution, i.e., (𝜇𝑘, 𝜆𝑘) satisfying (5b)-(5c) is required in order to perform early termination based on the duality result in (10). Since an infeasible IPM generally does not provide a solution that satisfies the equality constraint in (5b) until convergence, we proposed47 a projection step to compute new values (𝜇+, 𝜆+) = (𝜇𝑘+ Δ𝜇, 𝜆𝑘+ Δ𝜆) satisfying (5b) and (5c)

𝜇𝑘

𝑖> 0. There are three advantages for the projection (11) over a standard minimum-norm projection. Neither of these projections directly enforces the positivity constraints 𝜇𝑘+ Δ𝜇> 0, which would require solving an inequality constrained QP. A first

𝑖is Relatively Large, I.E., When 𝜇𝑘

𝑖> 0 is close to zero. This makes the step smaller when approaching the

R. Quirynen Et Al

positivity constraint, such that it is more likely to satisfy 𝜇𝑘 𝑖+ Δ𝜇𝑖> 0 without making the update step always small. Second, the solution (Δ𝜇, Δ𝜆) to the optimization problem (11) is equivalent47 to solving the symmetric system

(12)

which is an IPM iteration similar to (6) with the only differences being the right-hand side and the augmented Lagrangian type regularization 𝜖dual > 0. The equivalence means that the same block-tridiagonal matrix factorization for the solution of the reduced linear system (8) in each iteration of ASIPM46 can be reused to compute the projection step in (12). Third, the projection (12) aims at retaining the IPM progress towards the optimum, since the projection step does not increase the residual value for the remaining optimality conditions in (7), due to the zero elements in the right-hand side of (12).

Early Termination Strategy

We use the projection step in (12) for our early termination strategy, see Algorithm 1. As discussed later, one dual objective evaluation is computationally cheaper than a projection on a dual feasible point. Therefore, Algorithm 1 performs the projection in (12) if and only if the dual objective 𝜓(𝜇𝑘, 𝜆𝑘) is larger than the current UB (line 5). Multiple evaluations of the projection step in (12), reusing the same matrix factorization, may be needed to ensure dual feasibility ‖𝐹⊤

𝒚𝜇+ ℎ𝒚‖ < 𝑡𝑜𝑙when

using the inexact Newton implementation of46 in the ASIPM solver. Algorithm 1 Early termination for IPM in B&B method. Input: Warm start {(𝒛0, 𝜇0, 𝜆0, 𝑠0)}, 𝑡𝑜𝑙, and UB.

:

Compute projection step (Δ𝜇, Δ𝜆) in (12).

𝜇𝑘←𝜇, 𝜆𝑘←𝜆, 𝑟𝑘

𝒚←𝑟𝒚, and dual_feasible ←1.

:

if 𝜓(𝜇𝑘, 𝜆𝑘) > UB then break while loop.

:

Perform an IPM iteration (6), e.g., see46.

: End While

The standard iterates of an IPM can also be used to generate certificates of infeasibility54. Proposition 1, proved in47, states conditions such that the dual objective 𝜓(𝜇𝑘, 𝜆𝑘) is unbounded in the limit of the primal-dual IPM iterations. Therefore, our proposed early termination strategy is effective for infeasibility detection and, given a tight UB value from the B&B optimization method, it may lead to termination even before a certificate of infeasibility can be found.

Proposition 1. If the sequence of primal-dual iterates {(𝒛𝑘, 𝜇𝑘, 𝜆𝑘, 𝑠𝑘)} of the IPM satisfy 𝜇𝑘⊤𝑠𝑘≤𝜇0⊤𝑠0 and ‖𝜇𝑘‖ →∞, then the dual objective 𝜓(𝜇𝑘, 𝜆𝑘) →∞.

Omputational Complexity

The proposed early termination strategy requires two computational steps, i.e., the projection and the dual objective evaluation, which are typically not needed in a standard IPM. Considering the optimal control structured program (1), the evaluation of the dual objective value (5a) requires 𝑁(𝑛2 + 2 𝑛𝑚+ 2 𝑛𝑝) operations to compute 𝐿−1 (𝐺⊤

𝒗𝜆) Based On A Block-Diagonal

Cholesky factorization 𝑄= 𝐿𝐿⊤, in which 𝑛, 𝑚and 𝑝are the number of variables in 𝒗(see (4)), the number of equality and inequality constraints, respectively, per control interval, and 𝑁is the number of control intervals.

R. Quirynen Et Al

Based on (12), we can perform one projection step at the computational cost of one IPM iteration. This allows for reusing the corresponding matrix factorization in the subsequent IPM iteration if the projection is not successful. Based on the partic- ular ASIPM implementation from Section 3.3, as originally proposed in46, one iteration requires a block-tridiagonal Cholesky factorization for the matrix in (8), for which the dominant terms in the computational cost are

(13)

where 𝑛x and 𝑛u denote the number of state and control variables per interval in (1), respectively. Then, reusing this matrix factorization, the linear system for the projection step in (12) can be solved by

(14)

operations for the resulting block-structured forward and backward substitution. Since 𝑛≤(𝑛x + 𝑛u), and often 𝑛≪(𝑛x + 𝑛u) due to many auxiliary variables in hybrid systems2 for which the Hessian contribution is zero, the cost for a dual objective evaluation is considerably smaller than the projection cost (14), as anticipated.

Exact Presolve Techniques For Mixed-Integer Optimal Control

A presolve routine is a collection of computationally efficient operations that should be used in each node of the B&B method (see Figure 1) before solving the convex relaxation, in order to remove decision variables, and to remove or tighten constraints44. Presolve techniques are often crucial in strengthening convex relaxations such that typically fewer nodes need to be explored in a B&B optimization method, sometimes to such an extent that seemingly intractable problems become computationally tractable.

We present a collection of tailored variants of presolve techniques with block-sparse structure exploitation for mixed-integer optimal control, based on presolve routines in state-of-the-art solvers for general-purpose MIQPs, e.g., see43. We explicitly refer to these presolve techniques as exact operations, differentiating from the heuristic approach in Section 5, and to emphasize that all presolve methods in the present Section preserve feasibility and optimality, i.e., the reduced problem is infeasible or unbounded only if the original problem is infeasible or unbounded, and any feasible or optimal solution of the reduced problem can be mapped to a feasible or optimal solution of the original problem. For example, an exact presolve method will fix a binary variable to 0 or 1 only if the method can guarantee that this variable is fixed to that same value in an optimal solution.

Block-Structured Domain Propagation

Several strengthening techniques are implemented as part of “presolve” routines in state-of-the-art commercial solvers43. One technique that is particularly suitable to mixed-integer optimal control is based on domain propagation, in which the goal is to strengthen bound values based on the constraints of the MIQP in (1). In previous work29, we suggested to apply domain propagation to the inequality constraints of a condensed MIOCP formulation, i.e., to the smaller but dense problem formulation after numerically eliminating each of the state variables based on the state dynamic constraints in (1b). However, based on a simple illustrative example, we show that it can often be advantageous to apply each of the presolve operations, and domain propagation in particular, directly to the block-sparse MIQP formulation in (1), including the state variables and state dynamic equality constraints (1b). The key insight is that tight lower and upper bounds for state variables can be used to tighten lower and upper bounds on control variables and vice versa.

R. Quirynen Et Al

A standard bound strengthening procedure, as explained in43,29, can be applied to each of the inequality constraints in either the block-sparse MIQP formulation in (15) or the equivalent but condensed MIQP in (16). For example, the inequality in (15e) can be used to compute a bound on the binary variable 𝛿∈{0, 1} as follows:

𝛿= 1,

resulting in a fixing of the binary optimization variable 𝛿= 1. Alternatively, using the condensed inequality in (16d), the same

𝛿≥0,

which means that the binary optimization variable 𝛿∈{0, 1} cannot be eliminated in this case, even though the condensed MIQP in (16) is equivalent to the block-sparse MIQP formulation in (15).

Remark 2

In Example 1, for the condensed inequality in (16d), fixing of the binary variable 𝛿= 1 could be detected by exploiting a bound for the expression 𝑢0 + 𝑢1 ≤1 from (16c). However, as discussed in43, Section 5.4, a bound strengthening procedure con- sidering multiple constraints at once is typically too expensive for MIQP solvers, but more general optimization-based bound tightening (OBBT) techniques are common for mixed-integer nonlinear programming (MINLP).

Motivated by the above illustrative example, we propose a novel block-sparse variant of domain propagation as described in Algorithm 2 that is tailored to the MIQP formulation in (1). The method consists of a forward iterative procedure for 𝑖= 0, 1, … , 𝑁(see Line 1-14), followed by a backward iterative procedure for 𝑖= 𝑁−1, … , 0 (see Line 15-21). The general intuition behind the forward-backward propagation is to have a quick propagation of variable bounds from near the beginning of the prediction horizon towards the end of the prediction horizon, as well as a quick propagation of variable bounds from near the end of the prediction horizon towards the beginning. The proposed forward-backward implementation can reduce the amount of times that the domain propagation in Alg. 2 needs to be called in order to achieve a particular amount of bound strengthening in practice, even though such a performance improvement cannot be guaranteed in general. However, by design, it can be guaranteed that the updated bound values [̄𝑧+

𝑖,̄ 𝑧+

𝑖] that are computed by Alg. 2 are tighter than the original bound values

𝑖≤𝑧𝑖≤̄ 𝑧+

𝑖≤̄ 𝑧𝑖for 𝑖∈{0, 1, … , 𝑁}, without eliminating any feasible solution of the MIQP in (1) when replacing the bound values by the updated values [̄𝑧+

𝑖,̄ 𝑧+

𝑖] in (1c). Algorithm 2 can result in strengthening of bound values for both continuous and integer/binary optimization variables. In addition, the tailored block-sparse MIQP structure exploitation in Alg. 2 considerably reduces the computational cost for each operation in the domain propagation.

Each iteration of the forward procedure for 𝑖= 0, 1, … , 𝑁(Line 1-14) performs domain propagation for each variable 𝑧𝑖,𝑗 for 𝑗= 1, … , 𝑛x + 𝑛u based on the affine inequality constraints̄ 𝑐𝑖≤𝐸𝑖𝑧𝑖≤̄ 𝑐𝑖(see Line 2-6), followed by domain propagation for each state variable 𝑥𝑖+1,𝑗for 𝑗= 1, … , 𝑛x based on the state dynamic equality constraints 𝑥𝑖+1 = 𝑎𝑖+ 𝐹𝑖𝑧𝑖(see Line 7- 13). The computation of̄ 𝑧𝑖,𝑗and̄ 𝑧𝑖,𝑗on Line 3 and 4, respectively, is defined using a compact OBBT notation. However, as described in the next section, we instead perform a single-row approximation for each inequality constraint individually, in order to reduce the computational cost for each iteration of the domain propagation. An MIQP subproblem is detected to be infeasible whenever the gap between a lower and upper bound value is below a particular threshold value −𝜖, where 𝜖is a small positive value, for example, see Lines 5, 11 and 19. The computation of̄ 𝑎𝑖= min{𝑎𝑖+ 𝐹𝑖𝑧𝑖} = 𝑎𝑖+ (𝐹+

𝑖̄ 𝑧𝑖

) on Line 8 is used for domain propagation based on the state dynamics, where

𝑖, 𝐹−

𝑖contain all positive and negative elements of the matrix 𝐹𝑖= 𝐹+

𝑖, Respectively. Each Iteration Of The Backward

procedure 𝑖= 𝑁−1, … , 0 (see Line 15-21) performs domain propagation for each variable 𝑧𝑖,𝑗for 𝑗= 1, … , 𝑛x + 𝑛u based on the state dynamic equality constraints 𝑥𝑖+1 = 𝑎𝑖+ 𝐹𝑖𝑧𝑖. Similarly, OBBT is used to update the bound values̄ 𝑧𝑖,𝑗and̄ 𝑧𝑖,𝑗on Line 17 and 18, respectively, but a computationally efficient single-row approximation can be used.

Approximation of Optimization-based Bound Tightening The computation of bound values̄ 𝑧𝑖,𝑗,̄ 𝑧𝑖,𝑗on Lines 3-4 and Lines 17-18 of Alg. 2 require the solution of a linear program- ming (LP) problem. Since this operation needs to be performed for each variable on each time step in the horizon and for each domain propagation call in each iteration of the presolve routine, it is necessary to perform a computationally cheap single-row approximation instead as implemented in Alg. 3 based on the following lemma.

R. Quirynen Et Al

Algorithm 2 Block-sparse forward-backward operations for domain propagation and bound strengthening

], 𝐹𝑖= [𝐴𝑖𝐵𝑖

], 𝑖∈{0, … , 𝑁} and MIQP of the form (1).

:̄

𝑧𝑖,𝑗←min{𝑧𝑖,𝑗∶̄ 𝑐𝑖≤𝐸𝑖𝑧𝑖≤̄ 𝑐𝑖,̄ 𝑧𝑖≤𝑧𝑖≤̄ 𝑧𝑖}, see Alg. 3

:̄

𝑧𝑖,𝑗←max{𝑧𝑖,𝑗∶̄ 𝑐𝑖≤𝐸𝑖𝑧𝑖≤̄ 𝑐𝑖,̄ 𝑧𝑖≤𝑧𝑖≤̄ 𝑧𝑖}, see Alg. 3

:̄

𝑥𝑖+1,𝑗←max(̄𝑥𝑖+1,𝑗,̄ 𝑎𝑖,𝑗) and̄ 𝑥𝑖+1,𝑗←min(̄𝑥𝑖+1,𝑗,̄ 𝑎𝑖,𝑗).

:

if̄ 𝑥𝑖+1,𝑗−̄ 𝑥𝑖+1,𝑗< −𝜖then return infeasible_flag

𝑖,𝑗,̄ 𝑧+

𝑖,𝑗that are computed by Alg. 3 are a conservative approximation of optimization-based bound tightening, i.e., the following relationships hold̄

(17B)

where 𝐸𝑖,𝑘,∶denotes the 𝑘th row of the matrix 𝐸𝑖, and similarly for the updated upper bound values̄

(18B)

Proof. The relationships in (17b) follow directly from the following inequalities

Min{𝑧𝑖,𝑗∶(1B) −(1E)},

which holds for each 𝑘∈{1, … , 𝑛c}, due to the fact that an optimal objective value of a minimization problem only decreases after removing one or multiple constraints. The relationships in (18b) can be proved by a similar argument. A compact notation is used in Alg. 3 for matrices 𝐸+

𝑖, 𝐸−

𝑖which contain all positive and negative elements of the matrix

𝑖+ 𝐸−

𝑖, respectively. Line 10 of Alg. 3 includes rounding up ⌈̄𝑑⌉and rounding down ⌊̄𝑑⌋of the lower and upper bound values, respectively, if 𝑧𝑖,𝑗is an integer or binary optimization variable.

R. Quirynen Et Al

Algorithm 3 Single-row approximation of optimization-based bound tightening for variable 𝑧𝑖,𝑗

Nput: Bound Values [̄𝑧𝑖,̄ 𝑧𝑖], 𝐸𝑖= [𝐶𝑖𝐷𝑖

], 𝑖∈{0, … , 𝑁}, 𝑗∈{1, … , 𝑛z} and MIQP of the form (1).

: End For

10: if 𝑧𝑖,𝑗is integer then̄ 𝑑←⌈̄𝑑⌉and̄ 𝑑←⌊̄𝑑⌋.

𝑘∈{1,…,𝑛c}

(max{𝑧𝑖,𝑗∶̄ 𝑐𝑖,𝑘≤𝐸𝑖,𝑘,∶𝑧𝑖≤̄ 𝑐𝑖,𝑘,̄ 𝑧𝑖≤𝑧𝑖≤̄ 𝑧𝑖}).

Trivial Constraints And Dual Fixings

Algorithm 4 illustrates how single-row bounding for each of the affine inequality constraints can be used to detect an MIQP subproblem to be infeasible (see Line 3), for example, if

(19)

where 𝐸𝑖,𝑘,∶denotes the 𝑘th row of the matrix 𝐸𝑖, and similarly for the lower bound of̄ 𝑐𝑖,𝑘≤𝐸𝑖,𝑘,∶𝑧𝑖≤̄ 𝑐𝑖,𝑘, 𝑘∈{1, … , 𝑛c}. In addition, single-row bounding can be used to detect lower and/or upper bounds of an affine inequality constraint to be

(20)

and similarly for the lower bound of each affine inequality constraint̄ 𝑐𝑖,𝑘≤𝐸𝑖,𝑘,∶𝑧𝑖≤̄ 𝑐𝑖,𝑘, 𝑘∈{1, … , 𝑛c}. Finally, if an optimization variable does not enter the state dynamic equality constraints (see Line 9 of Alg. 4) and if the variable enters each of the non-redundant inequality constraints with a coefficient of the same sign, then the variable can be fixed to the lower (Line 10) or the upper bound (Line 11) value, depending on the sign of the constraint coefficients and the sign in the cost function.

Lines 7-13 of Alg. 4 form a tailored block-sparse variant of dual fixing, which is described more generally in43.

Onstraint Coefficient Strengthening

In coefficient strengthening, we aim to modify coefficients of the affine inequality constraints (1d) to tighten the convex QP relaxation without affecting the integer-feasible MIQP solutions. We present a block-sparse variant of coefficient strengthening in Alg. 5, as described more generally in48. Let us define constraint domination as follows:

(21)

i.e., the feasible region of the convex QP relaxation for 𝑒⊤ 1 𝑧≤𝑓1 is strictly contained in the feasible region for 𝑒⊤

𝑧≤𝑓2, Given

the variable bound values̄ 𝑧≤𝑧≤̄ 𝑧. Using the latter definition, the overall aim of coefficient strengthening is to reformulate one or multiple affine inequality constraints (1d) as constraints that dominate the original inequality constraints, without removing any feasible MIQP solution.

We demonstrate the idea of coefficient strengthening based on following simple illustrative example.

R. Quirynen Et Al

Algorithm 4 Block-sparse redundant inequality constraint detection and dual fixings

Nput: Bound Values [̄𝑧𝑖,̄ 𝑧𝑖], 𝐸𝑖= [𝐶𝑖𝐷𝑖

], [̄𝑐𝑖,̄ 𝑐𝑖], 𝑖∈{0, … , 𝑁} and MIQP of the form (1).

:

if ‖𝐵𝑖,∶,𝑗‖ < 𝜖∧‖𝐻𝑖,∶,𝑛x+𝑗‖ < 𝜖∧‖̄𝑢𝑖,𝑗−̄ 𝑢𝑖,𝑗‖ > 𝜖then

: End For

Output: Updated bound values [̄𝑧𝑖,̄ 𝑧𝑖] and [̄𝑐𝑖,̄ 𝑐𝑖], 𝑖∈{0, … , 𝑁}.

Example 4

Let us consider an MIQP with a continuous variable 𝑥∈ℝ, which is bounded 1 ≤𝑥≤3, and a binary variable 𝛿∈{0, 1}. Coefficient strengthening for an inequality constraint 2 ≤𝑥+ 100 𝛿then results in a dominating constraint 2 ≤𝑥+ 𝛿, i.e.,

⊂

{𝑥∈ℝ, 𝛿∈ℝ| 1 ≤𝑥≤3, 0 ≤𝛿≤1, 2 ≤𝑥+ 100 𝛿}.

(22)

Mixed-integer inequality constraints of the form in (22) are common, e.g., when using a “big-M” formulation55 in MIOCPs, such that coefficient strengthening can be used to automatically reduce the large coefficient value 𝑀> 0 and tighten the convex QP relaxations. Algorithm 5 describes a systematic approach to strengthen the coefficients of each affine inequality constraint̄ 𝑐𝑖,𝑘≤𝐸𝑖,𝑘,∶𝑧𝑖≤̄ 𝑐𝑖,𝑘, 𝑘∈{1, … , 𝑛c}, with respect to each integer or binary optimization variable 𝑢𝑖,𝑗, ∀𝑗∈𝑖in (1e).

Binary Variable Probing

The general idea of probing is to select a binary variable, which is set tentatively to zero or one in order to derive further variable fixings and/or tightened inequality constraints, see43,48. For example, let 𝑢𝑖,𝑗∈{0, 1} be a binary variable, and let us define the

𝑖≤𝑧𝑖≤̄ 𝑧0

𝑖for 𝑖= 0, … , 𝑁that have been deduced from setting 𝑢𝑖,𝑗= 0 using one or multiple iterations of presolve operations, e.g., using the forward-backward domain propagation in Alg. 2. Similarly, the lower and upper

𝑖≤𝑧𝑖≤̄ 𝑧1

𝑖for 𝑖= 0, … , 𝑁have been deduced from setting 𝑢𝑖,𝑗= 1. Our tailored implementation of binary variable probing in Alg. 6 is based on following observations: • If both 𝑢𝑖,𝑗= 0 and 𝑢𝑖,𝑗= 1 leads to an infeasible problem

𝑖,𝑘, 𝑖= 0, … , 𝑁, 𝑘= 1, … , (𝑛x + 𝑛u)

• Bound values updated for each variablē 𝑧𝑖,𝑘= min{̄𝑧0

𝑖,𝑘) 𝑢𝑖,𝑗

For simplicity, the last observation is not included in Alg. 6. Binary variable probing is a relatively simple strategy that can be very effective at reducing the B&B search tree, but it can become computationally expensive. Therefore, a limit on the number of probing iterations, 𝑛< 𝑛probing (see Line 5 and Line 11), and/or a timeout is needed to ensure computational efficiency.

R. Quirynen Et Al

Algorithm 5 Block-sparse inequality constraint coefficient strengthening

:

for 𝑗= 1, … , 𝑛u and if 𝑢𝑖,𝑗is integer ∧‖̄𝑢𝑖,𝑗−̄ 𝑢𝑖,𝑗‖ > 𝜖then do

:

𝐷𝑖,𝑘,𝑗←𝐷𝑖,𝑘,𝑗−̃ 𝑑and̄ 𝑐𝑖,𝑘←̄ 𝑐𝑖,𝑘−̃ 𝑑̄ 𝑢𝑖,𝑗.

:

𝐷𝑖,𝑘,𝑗←𝐷𝑖,𝑘,𝑗+̃ 𝑑and̄ 𝑐𝑖,𝑘←̄ 𝑐𝑖,𝑘+̃ 𝑑̄ 𝑢𝑖,𝑗.

: End For

Output: Updated constraint bound values [̄𝑐𝑖,̄ 𝑐𝑖] and matrices 𝐷𝑖, 𝑖∈{0, … , 𝑁}.

Exact Block-Sparse Presolve Procedure

Finally, we summarize our tailored block-sparse presolve procedure for optimal control structured MIQPs in Alg. 7, which should be called in each node of the B&B method (see Figure 1) before solving the convex relaxation. Each iteration of Alg. 7 includes the following block-sparse presolve operations: 1. Update variable bound values [̄𝑧𝑖,̄ 𝑧𝑖], using forward-backward domain propagation in Alg. 2 (Line 3).

2. Update bound values [̄𝑧𝑖,̄ 𝑧𝑖] and [̄𝑐𝑖,̄ 𝑐𝑖], using redundant inequality constraint detection in Alg. 4 (Line 4). 3. Update bound values [̄𝑐𝑖,̄ 𝑐𝑖] and matrices 𝐷𝑖, using constraint coefficient strengthening in Alg. 5 (Line 5). 4. If probing is enabled and allowed (see Line 6 of Alg. 7), use binary variable probing in Alg. 6 (Line 7).

The block-sparse presolve procedure in Alg. 7 is an iterative procedure that typically requires multiple iterations, because each operation may result in a tightening of a continuous or discrete variable bound or constraint that in turn may result in further tightenings in the subsequent iterations. The iterative procedure terminates immediately if any of the presolve operations detects an infeasibility. Alternatively, our termination condition on Line 2 of Alg. 7 is based on whether a particular measure of progress is sufficient or not. For example, progress can be measured by the number of variables that are fixed and/or the amount by which continuous or discrete variable bounds are tightened from one iteration to a next. The presolve procedure continues as long as one or multiple variable bounds are tightened sufficiently from one iteration to the next, i.e., if sufficient_progress is true on Line 2 of Alg. 7. However, after a minimum number of iterations, the algorithm may terminate if no new variable is fixed in the latest iteration, to avoid performing an excessive number of iterations for incremental tightening of the continuous variable bounds. Due to the relatively high computational cost of binary variable probing in Alg. 6, probing is performed only when the amount of progress that is made by other presolve operations is not sufficient and a maximum number of iterations has not been reached, see Line 6 of Alg. The overall goal of the presolve procedure is that the total time spent for removing variables and

Authors:

Peder EZ Larson 1, 2,* , Jenna ML Bernard1, James A Bankson 3, Nikolaj Bøgh 4, Robert A Bok1, Albert P. Chen 5, Charles H Cunningham 6,7, Jeremy Gordon1, Jan-Bernd Hövener 8, Christoffer Laustsen 4, Dirk Mayer 9,10, Mary A McLean11 12, Franz Schilling13, James Slater1, Jean-Luc Vanderheyden5, 14, Cornelius von Morze 15, Daniel B Vigneron1, 2, Duan Xu1, 2, and the HP 13C

94143, Usa.

Denmark. 5 GE Healthcare, Menlo Park, California, USA. 6 Physical Sciences, Sunnybrook Research Institute, Toronto, Ontario, Canada.

8 Section Biomedical Imaging, Molecular Imaging North Competence Center (MOIN CC), Medicine, Baltimore, MD, USA. Cambridge, United Kingdom.

14Jlvmi Consulting Llc, Dousman, Wi, Usa

#See Acknowledgements for a list of all HP 13C MRI Consensus Group Members This work was supported by the ISMRM Hyperpolarized Media MR Study Group, the ISMRM Hyperpolarization Methods & Equipment Study Group, and the Hyperpolarized MRI Technology Resource Center (NIH/NIBIB grant P41EB013598).

Abstract

MRI with hyperpolarized (HP) 13C agents, also known as HP 13C MRI, can measure processes such as localized metabolism that is altered in numerous cancers, liver, heart, kidney diseases, and more. It has been translated into human studies during the past 10 years, with recent rapid growth in studies largely based on increasing availability of hyperpolarized agent preparation methods suitable for use in humans. This paper aims to capture the current successful practices for HP MRI human studies with [1-13C]pyruvate - by far the most commonly used agent, which sits at a key metabolic junction in glycolysis. The paper is divided into four major topic areas: (1) HP 13C-pyruvate preparation, (2) MRI system setup and calibrations, (3) data acquisition and image reconstruction, and (4) data analysis and quantification. In each area, we identified the key components for a successful study, summarized both published studies and current practices, and discuss evidence gaps, strengths, and limitations. This paper is the output of the “HP 13C MRI Consensus Group” as well as the ISMRM Hyperpolarized Media MR and Hyperpolarized Methods & Equipment study groups. It further aims to provide a comprehensive reference for future consensus building as the field continues to advance human studies with this metabolic imaging modality.

Keywords: Hyperpolarized MRI, metabolic imaging, carbon-13, pyruvate, dissolution dynamic

Introduction

MRI with hyperpolarized 13C agents, also known as hyperpolarized (HP) 13C MRI, has shown great potential as a novel imaging modality, particularly for its ability to probe metabolic processes in real time. The first human studies with HP [1-13C]pyruvate were performed in 2011 in prostate cancer patients (1).

Since then, there have been over 60 papers published with imaging results of human subjects from 13 different sites, with applications including prostate cancer, brain tumors, breast cancer, kidney cancer, pancreatic cancer, metastatic disease, liver disease, ischemic heart disease, diabetes and cardiomyopathies. The vast majority of these studies used [1-13C]pyruvate (1–63), where [2-13C]pyruvate (64) and 13C-urea (56) have been demonstrated too.

As clinical HP 13C MRI advances, there is a growing need to build consensus for best practices, which are critical for comparing data across sites, performing multi-site trials,deploying methods to new sites, partnering with vendors, and potentially for obtaining broader regulatory approvals.

In March 2022, we initiated an effort to build consensus within the HP 13C MRI community with this opportunity in mind, and it was greeted with strong enthusiasm. The “HP 13C MRI Consensus Group”, containing over 55 members from 27 sites, identified the area of greatest need and opportunity for consensus building to be HP [1-13C]pyruvate human

●

Pyruvate is the most mature and widely used HP agent and has the most significant translational evidence emphasizing the potential clinical impact.

●

Clinical trials, particularly multi-site trials, have the strongest need for consensus methods to ensure that data can be combined across sites. This work is a Position Paper for which the goal is to describe current successful practices and study methods for HP [1-13C]pyruvate human studies along with justification to support those practices. This is divided into four major topic areas: (1) HP 13C-pyruvate preparation, (2) MRI system setup and calibrations, (3) data acquisition and image reconstruction, and (4) data analysis and quantification (Fig. 1). The current successful practices and study methods include a literature review of published peer-reviewed journal papers showing human HP [1-13C]pyruvate study data, up to September 2022 (1–63), as well as new unpublished information from surveys of HP 13C study sites. Based on this information, we also highlight the evidence gaps, strengths, and limitations of current practices which are summarized at the end of each section.

Figure 1: Illustration of the HP 13C MRI human study process, including the 4 major areas covered in this paper: Hyperpolarized 13C-pyruvate preparation, MRI system setup and calibration, Acquisition and Reconstruction, and Data Analysis and Quantification.

Figure 2: Anatomical targets of HP [1-13C]pyruvate MRI human studies published up to September 2022.

Hyperpolarized 13C-Pyruvate Preparation

This section covers the processes for creating the HP agent, 13C pyruvate, and will include many aspects and considerations that are needed to safely and effectively prepare doses for metabolic imaging studies in human subjects. These include material, personnel, equipment and facility, fluid path preparation, quality control, and release.

It is helpful to understand that the specifications of a dose of 13C pyruvate suitable for in vivo MR HP metabolic imaging were shaped in part by early preclinical studies performed by GE HealthCare summarized in Ref. (65). In short, the safety of the two novel drug components, 13C pyruvate and the electron paramagnetic agent (EPA) AH111501, were demonstrated in those studies. The more precise formulation of the dose suitable for human use was then determined from clinical studies (66) that included two Phase 1 clinical trials in young and elderly healthy volunteers without hyperpolarization of the 13C nuclei and another Phase 1/2a dose escalation and imaging feasibility study with HP 13C pyruvate in 31 prostate cancer patients at the With the exception of the first HP 13C imaging clinical trial, which utilized a prototype device in a cleanroom (1), all HP 13C studies performed in humans to date have utilized the SPINlab polarizer (manufactured by GE HealthCare). Consequently all doses of the HP 13C pyruvate delivered by SPINlab have been produced using the “SPINlab Pharmacy Kit” that serves as the container-closure system for the various drug components (13C pyruvic acid and EPA mixture, dissolution medium, and neutralization and dilution medium) during sample polarization, dissolution and quality control (QC) processes. Thus many aspects of the HP sample preparation considerations discussed below are related to the SPINlab instrument and the consumables designed to be used with it (67).

General Considerations

While more than 860 patients or healthy subjects having been injected with HP 13C pyruvate as of January 2022 without reports of any serious adverse events (68), HP 13C pyruvate injection remains an investigational MR contrast agent and can only be administered by those with Investigational New Drug (IND) exemption from the Food and Drug Administration (FDA) in the USA, a Clinical Trial Application (CTA) in Canada, approval from National Research Ethics Committee Services in the UK, or approval from the relevant local regulatory body. Thus, methods and processes involved to produce a dose should have patient safety as the first priority. Since utilizing dissolution dynamic nuclear polarization (dissolution-DNP) for human use is still a relatively new development, there are no existing published regulatory guidelines specifically for this method.

There are two major production styles that determine how various sites approach the agent preparation. In the US, the most common approach is to rely on a sterilizing filter (“Terminal Sterilization”) to ensure sterility of the final product, akin to PET tracer production, where a starting molecule with a radioisotope is processed using various other ingredients to make the final, desired and injectable contrast agent within a necessarily short amount of time (69). For these sites, sterilization of the components and accessories upstream of this filter are not required, although many of them were manufactured and tested following Good Manufacturing Practice (GMP) or Good Laboratory Practice (GLP) requirements. The filling process is usually performed under an ISO 5 laminar flow hood, but a clean room or an isolator is not required.

This approach is typically accompanied by testing the integrity of the sterilizing filter prior to release of the dose for injection. Typically, post release endotoxin and sterility tests are performed using an aliquot reserved from each released dose.

In the UK and EU, the most common approach is to more-closely follow sterile pharmaceutical compounding guidelines (70), where all components and ingredients are required to be sterile or manufactured under GMP guidelines and are assembled and filled within a clean room environment or an isolator system (“Sterile Preparation”). Typically a batch of Pharmacy Kits for HP 13C pyruvate injection are prepared together. The sterility of the final dose is also ensured by batch validation testing, in addition to the sterility of the ingredients and the sterile compounding process. The endotoxin and sterility testing are performed for the process validation but are not performed for each injected dose.

Some institutions fill and assemble the Pharmacy Kit required for a specific study on the same day or the day prior to polarization, dissolution, and patient administration, but others have also demonstrated the feasibility of preparing a batch of kits, keeping them in a -20ºC freezer and using them over a period of a few months.

Beyond the obvious requirements that the process and the facility has to ultimately produce a dose that is safe to inject into a human, regulatory authorities will also focus on the question “Are you in control of your processes?”. To be in control of your process requires an in-depth and broad understanding of all processes involved in pre, post, and during the production process.

Personnel

It is typical and may be required to have licensed personnel involved in the production process depending on local regulations.Typically a pharmacist, radiopharmacist or other similarly qualified person (QP), in charge of the facility where the Pharmacy Kit filling and preparation is taking place, is responsible for the overall process and the release of the injectable dose.

Qualified cleanroom technicians are often involved in the Pharmacy Kit filling under the supervision of the pharmacist or QP. As is required for pharmaceutical compounding or PET tracer production, training requirements and training records for all personnel need to be maintained and available for audit by the FDA or equivalent.

Equipment And Facility

The facility and all equipment need to have standard operating procedures (SOPs) that describe how equipment is used, maintained, and calibrated to comply with relevant legislation. Currently, almost all the filling of the Pharmacy Kit takes place within a compounding laminar flow hood or isolator (typically ISO 5). At some sites, the filling is conducted within a cleanroom, while at others, it is conducted in a dedicated non-cleanroom space, reflecting differences in cleanroom approach and specifications between regulators worldwide (71). Some equipment or facilities, such as the compounding hood or cleanroom, may require external certified laboratories for testing.

Material Handling

Material handling guidelines (69,70) require SOPs detailing a system to track all of the materials involved in the HP production process for a particular patient dose, similar to current good manufacturing practice (cGMP) requirements for material handling for drug compounding. This includes acceptance standards, storage conditions, amount used in the patient dose for each ingredient and materials used in the assembly of the fluid path and Pharmacy Kit. Currently some users choose to open and inspect and sometimes modify the Pharmacy Kits upon arrival, but some users keep them in the sealed packaging until they are required for dose preparation.

Pharmacy Kit Filling And Assembling

As required by an IND or its equivalent, the preparation of the doses of HP 13C agent are detailed in the Chemistry, Manufacturing, and Control (CMC) section of an applicable regulatory submission; an example of this has been made available (72). It describes the processes of filling the Pharmacy Kit with the different components that make up the final drug product, and of assembling the final kit for either storage or immediate use in the polarizer. Special attention should be given to the laser welding process in order to satisfy installation qualification (IQ) and operational qualification (OQ). Typically, the final developed process is validated by process qualification (PQ) runs, during which 3 or more Pharmacy Kits are filled and used and the final HP 13C products are tested for endotoxin and sterility and to confirm that they meet the dose specifications for injections (usually including pyruvate concentration, residual EPA concentration, pH, liquid state polarization level and dose temperature). The data from 3 consecutive PQ runs are submitted as part of the IND submission (or its equivalent), and are often also reviewed by the Institutional Review Board (IRB) where the studies are conducted.

Quality Control And Dose Release

The quality control (QC) and dose release can be separated into two aspects: one is the QC and release of the filled Pharmacy Kit, and second is the QC and release of the HP 13C agent for injection, after polarization and dissolution. For institutions filling a batch of kits and storing them to use over a period of time, typically the batch can be released based on initial validation, environmental monitoring data from the day of kit production, and if filters are used during preparation of any of the components, filter integrity testing. But in some cases one or more kits are used for validation before the batch of kits are released for future use. For institutions that fill only the kits required for specific studies shortly before the experiment, the filled kits often do not go through separate release tests before they are used.

The quality control of the HP 13C pyruvate solution post dissolution is primarily performed to ensure that the agent meets the dose specifications (Table 1) before it is administered to the subject. These specifications target both safety (pH, residual EPA, temperature) and efficacy (pyruvate concentration, polarization, volume). Typically, the pyruvate concentration, residual EPA concentration, pH, dose temperature, dose volume, and liquid state polarization are measured by the QC accessory associated with the SPINlab polarizer. Some users perform a secondary measurement for one of the parameters, such as pH, using a different instrument or pH paper. For sites that do not go through a separate release testing process for batch filled kits, the integrity of the sterilization assurance filter, a part of the Pharmacy Kit, is typically tested as a part of the dose release. It is also common for these users to preserve an aliquot of the final HP 13C pyruvate solution for post-release endotoxin and sterility testing. This testing cannot be completed fast enough to test an individual dose prior to injection, but this is why other processes such as PQ runs and validation testing are done to minimize the chance a subject could be injected with a contaminated dose.

The Final Dose Release And Injection

should be done under the supervision of a licensed professional, based on local regulations.

Some Key Challenges

Many of the challenges associated with HP 13C pyruvate preparation can be attributed to the conditions required for the dissolution-DNP method of high magnetic field (~3-7 T) and very low temperature (~1 K) during polarization, with pressurized and superheated water necessary for the rapid dissolution event. These extreme conditions are quite challenging for the design of the container-closure and fluid path system. In particular, the cryogenic temperature in the polarizer requires special attention to any moisture or ambient (moist) air introduced into that portion of the fluid path, which can form an ice block at ~1 K. This ice can lead to flow restriction during the dissolution event and reduce the strength of the laser welded bond between the cryovial and its cap. This can ultimately produce failures in the dissolution step, including variations in final pyruvate concentration and pH that may fail to meet QC release criteria as well as fluid path ruptures that provide no available dose and result in polarizer down-time.

The polarization of the HP 13C pyruvate sample decays quickly over the span of a few minutes after dissolution, and thus the process of dissolution, QC for release, and injection should be completed as fast as possible to preserve the high polarization level achieved. Any delays in the preparation process, such as transportation time or equipment malfunction, can significantly reduce the final polarization and result in lower quality imaging data.

Current Practices

A summary of data collected from all sites performing clinical trials with HP 13C-pyruvate is shown in Fig. 3 and Table 1, including the specification of the final dose and how the quality control and release of the final dose are performed. There is a split in the Production Style, described in the General Considerations section above, with 8/13 sites using Sterile Preparation versus 5/13 using Terminal Sterilization. While many of the dose specifications show notable differences in acceptable ranges, all of these variations listed in tables have been successfully and safely been used to perform HP 13C pyruvate studies in humans. Their differences depend on the institutions’ preferences, resources and their particular regulatory situation. There is high similarity in pyruvate ranges, temperature ranges, EPA limits, and volume limits. There is modest variability in pH ranges and large variability in the endotoxin test limit. There is a 3-fold difference in acceptable polarization levels, which are measured to ensure a futile dose is not injected since the polarization is directly proportional to SNR. This reflects the decision by several sites to believe that useful data can be still be obtained with suboptimal polarizations.

Figure 3: Hyperpolarized agent preparation methods reported by sites currently performing HP

In House

Table 1: HP 13C-pyruvate preparation parameters, methods, and dose specifications used for quality control testing and release as well as validation. These were obtained from a survey of all sites performing clinical trials with HP [1-13C]pyruvate. The parameters used for product release are noted in bold text, otherwise these parameters are measured for batch validation or other QC measurements. The endotoxin and sterility testing are performed during process validation of the batch and/or post-injection, and largely depends on the agent production approach.

Summary

The overall safety record of HP 13C-pyruvate has been very strong, and the SPINlab hyperpolarizer has proven to provide high polarizations at human sized doses while meeting numerous QC and release criteria. A weakness remains the failure modes of the SPINlab Phamacy Kits (e.g. ice blocks, path ruptures), which are placed under extreme requirements particularly during dissolution. The preparation process still requires a high degree of expertise.

Therefore, there is a significant need to improve the reliability, robustness, and ease of operation for generating HP 13C-pyruvate doses for human studies. Furthermore, there is a divide between manufacturing and sterile compounding style preparation as well as other site-specific practices, resulting in variations in SOPs and justification required to relevant regulatory bodies. There have also been no comparisons between these approaches. It is also unclear what release criteria and QC parameters are truly required to ensure patient safety.

However, all of the reported methods are acceptable and approved by the appropriate regulatory authorities, and have led to the rapid expansion of successful human studies in recent years.

Mri System Setup And Calibrations

This section covers the MRI system setup, including the imaging system, RF coils, phantoms, and prescan calibration methods.

Imaging System

The main prerequisite for a given MRI scanner to be capable of supporting studies with HP 13C is its “broadband” capability to transmit and receive radiofrequency (RF) signal at the frequency of 13C, which is around 4 times lower than 1H. This does not come as a default on clinical MR devices. The transmit power of the broadband amplifier should also be sufficient to support the intended flip angle and RF pulse shape with the employed transmission RF coil(s) for 13C. Most studies to date use relatively low flip angles (< 90 degrees) for HP 13C in order to preserve polarization for time-resolved imaging. The capability to receive 13C signal on multiple channels is also desirable to increase SNR, as discussed further in the “RF coils” section.

The choice of magnetic field strength is primarily dependent on the metabolites’ frequency separation due to chemical shift dispersion and 1H imaging. High field strengths do not enhance hyperpolarized 13C signal as they do for 1H because the signal strength in a HP experiment relies on manipulating the population of quantum energy states outside of the MRI scanner.

However, the injected HP 13C-pyruvate and its metabolic products have greater frequency separation at higher fields, and it may thus be easier to separate and quantify these resonances at higher fields. This comes at the cost of a reduction in the achievable T2* and often reduced T1. As the initial polarization is independent of the imaging field strength it has been proposed that the increased T2* at 1.5T can potentially be exploited to increase SNR by adapting the acquisition bandwidth or reduce off-resonance imaging effects in cases when the decay of the transverse magnetization is dominated by T2* (73). In practice, 3T has been used in all published human 13C-pyruvate studies surveyed (Supporting Table S1), and comprises the majority of scanners currently in use for human studies (Table 3). A field strength of 3T is well-suited for 1H MRI anatomical reference and correlative imaging.

Stronger and more rapidly slewing magnetic field gradients support more rapid spatial encoding, particularly for metabolite-specific single-shot imaging using echo-planar imaging (EPI) or spiral imaging (See “Acquisition and Reconstruction”). Although the spatial resolution acquired for HP 13C imaging is typically much coarser than for 1H MRI, the factor of ~4 in gyromagnetic ratio leads to the same reduction factor in performance of the gradient system, so 13C experiments are potentially more limited by gradient hardware performance. To date, all human studies have used the commercially-available integrated gradient systems provided in clinical MRI scanners.

Optimization of scanner design has understandably focused on minimization of artifacts in 1H MRI, where devices such as room lights, the gradient amplifiers, and the motors driving the patient bed are checked to ensure that they do not produce RF interference at the 1H frequency, but artifacts may arise at other frequencies. Eddy current compensation is also not always appropriately adjusted for nuclei at other frequencies (74). In order to optimize for 13C, many sites have performed checks on phantoms for RF interference, gradient artifacts, and eddy currents (74), including the use of post-hoc gradient impulse response function characterisation and correction, and some vendors have fixed these issues as well.

Rf Coils

For HP 13C imaging studies in humans, RF coils for both 1H and 13C nuclei are needed, with 1H MRI providing an anatomical reference for registration and optional additional multiparametric MRI readouts. At the Larmor frequency of 13C nuclei, the relative contributions from coil noise compared to sample noise increase compared to 1H (73,75), although sample noise still is likely the dominant contributor for human-sized coils at 32.1MHz - the resonance frequency of 13C nuclei at 3T.

The key requirement for human 13C-pyruvate RF coils are that the coil geometry and sensitive volume must cover the volume of interest in the subject. Table 2 and Figure 4 shows coil configurations that have been used and optimized for applications in different anatomic regions.

Volume resonators are most commonly used for transmit, as they surround the subject to

Provide B1 Transmit Across The Fov (B1

+). While 1H relies on a large birdcage (“body”) coil built into the scanner, 13C transmit coils must be placed inside the bore. This takes up valuable space within the magnet, and also has led to the use of designs with relatively inhomogeneous

B1

+. Many human studies have used Helmholz pair resonators for transmit, including the “clamshell coil”, which has a notably inhomogeneous B1

+ Profile But Has Been Used Because Of

relatively easy integration into the scanner bore. B1

+ Variation Results In Variations In The Flip

angles that control the use of the hyperpolarized magnetization and creates errors in common HP metrics (9,76). The exception are head coils, where birdcage designs with highly

Homogeneous B1

+ can be placed around the head while easily fitting inside the bore. As with 1H MRI, higher SNR can typically be achieved by smaller receive coil elements, such as surface coils or phased arrays, and the majority of 13C receive coils used have layouts similar to 1H phased arrays.

RF coil quality control is important to ensure proper functioning of the coils to provide consistent imaging quality, especially with limited natural abundance 13C signal in vivo. It typically involves 1) a physical integrity check of the coil cables and connectors and 2) phantom SNR tests to check the coil’s performance and to monitor it over time (see Phantoms below). An useful reference for RF coil quality control is outlined in the MRI accreditation program of the American College of Radiology (77) and can be adapted for 13C coils.

Notably, configurations for brain and prostate studies used dual-tuned 1H/13C coil designs, which greatly simplify workflow and registration of 1H and 13C images, as no switching of coils is needed.

(1)

Table 2: RF coil configurations reported for human HP [1-13C]pyruvate studies.

Tx = Transmit

coil, RX = receive coil. The commonly used “clamshell” TX coil is a Helmholz pair design. For 1H RF configurations, all used the Body coil for TX unless otherwise noted, and “repositioned” indicates the 13C coil was removed for 1H imaging. One representative reference is listed for each configuration. The RF coil configurations reported in the reviewed papers are shown in Supporting Table S1.

Figure 4: Examples of RF coil configurations used for human HP [1-13C]pyruvate brain studies. (A,B) 13C Clamshell TX (Helmholz pair) and 2× 4-channel paddle RX arrays. (C) 13C Birdcage volume TX and 32-channel RX array (RX array slides into TX coil). (D) 13C Birdcage volume TX and 24-channel RX array, combined with a 1H 8-channel RX array. Image reproduced with permission from Ref (16).

Phantoms

Since hyperpolarized magnetization is non-renewable, phantoms containing 13C nuclei are important to: 1) test the multi-nuclear capabilities of the imaging system, including all parts of the signal excitation and receive chain; 2) perform calibration measurements before a scan with hyperpolarized nuclei; and 3) perform necessary pre-scan adjustments (see “Prescan Calibration” section). The phantoms currently in use are listed in Table 3. Their composition must provide sufficient 13C signal, with additional considerations of conductivity, stability, chemical shift(s) present, potential for dynamic imaging, and cost. The phantom geometries are typically either compact, in order to be used alongside the subject during a HP scan, or large enough to mimic the inner volume of a RF coil for system testing.

One popular compact design contains enriched 13C-urea at high concentration, typically 8 M, which provides a single resonance, placed inside a small container ~1 mL. The most common recipe mixes 13C-urea in a 90% water/10% glycerol solution, with glycerol used to increase the urea solubility and doping with a Gd-based contrast agent to shorten T1 which increases the potential SNR per unit time. For example, when Dotarem is added at a 3:1000 volume ratio the 13C-urea T1 is around 500 ms and T2 is around 100 ms. However, when testing pulse sequences influenced by T1 and T2, doping should be used carefully. This phantom is suitable for frequency calibration, transmit gain calibration, sequence testing, and as a fiducial marker when placed next to a patient. However, enriched 13C-urea has a relatively high cost compared to natural abundance compounds.

For larger volumes (>100 ml), the phantoms most often used contain undiluted ethylene glycol, glycerol, or dimethyl silicone. These compounds have sufficiently high carbon concentrations to provide sufficient 13C signal even with the 1.1% natural abundance of 13C. These larger phantoms matching the inner volume of an RF coil are useful for coil testing, including transmit

+) And Receive (B1

-) coil profile mapping, as well as to mimic acquisitions using in vivo FOV requirements. In this case, size and conductivity should match the expected subject size in order to mimic coil loading and get a realistic estimation of B1+. Large-volume natural abundance urea phantoms have also been used by some sites, but suffer from higher conductivity compared to biological tissues. Typically, it is easier to increase the conductivity and hence coil loading of the non-conductive phantom by adding NaCl to match physiological loading (16,78).

Dynamic phantoms that aim to mimic metabolite kinetics have also been developed (79–81), and have the potential to more closely mimic the HP experiment, but so far these are not widely used.

Prescan Calibration

Prior to performing an MRI acquisition, the so-called prescan procedure is used to set the shim parameters to maximize B0 homogeneity over the field of view (FOV) or a specific region of interest (ROI), the scanner center frequency (CF), the RF transmit gain, and the receiver gain.

While this calibration procedure is usually automated for 1H, the lack of sufficient natural abundance 13C signal prevents use of automated methods. (Although natural abundance 13C lipid signal has been detected, there are so far no reports on using this signal for prescan.) Table 3 shows current practices across sites.

Maximizing B0 homogeneity is independent of the nucleus and is therefore performed prior to 13C imaging using the 1H water signal and existing shimming tools, such as by a standard automated process (“Auto Shimming”) or using high order shimming routines. Similarly, the 13C CF can be calculated from the 1H CF using a predetermined scaling factor that depends on the target chemical shift (82). Another common approach used is to have a small, high-concentration 13C phantom, e.g. 8M 13C-urea, integrated in the RF coil or placed next to the scan subject (1). The reference frequency can also be based on real-time measurements after the HP injection but prior to imaging (83). Both the CF and B0 shimming are critical when using spectrally-selective RF pulses, as inmetabolite-specific imaging methods, where the desired excitation bandwidths are typically very narrow and frequency offsets can lead to a failure mode that is only apparent after injection.

The calibration of the RF transmit power is typically performed on a small, high-concentration 13C phantom placed near the region of interest during the scan or on a large 13C phantom of similar size and coil loading as the subject, prior to the subject scan. Reference power is often done by sweeping the power in a pulse-acquire sequence (53,62), or the Bloch-Siegert method (52,84). When using a small phantom, the location of the phantom, B1

+ Inhomogeneity As Well

as any shielding effects, e.g., when the phantom is integrated into a coil (1), may degrade the accuracy. Other methods include real-time Bloch-Siegert method measurements after the HP injection (83), and using the stronger natural abundance 23Na signal that is close enough to the 13C resonance frequency to be detected by 13C coils (82).

The receiver gain is predetermined, either systematically based on independent phantom measurements and assuming the dose and polarization of the HP compound is known prior to injection, or based on past HP imaging studies.

Power [Kw]

Phantom(s) - during study Phantom(s) - before study 13C Frequency

8

13C-bicarbonate doped with dimethyl silicone, various

Power [Kw]

Phantom(s) - during study Phantom(s) - before study 13C Frequency

Maximum Values

Table 3: Summary of the imaging systems, phantoms, and prescan procedures used at sites currently performing HP 13C-pyruvate human studies. These were obtained from a survey of all sites performing clinical trials with HP [1-13C]pyruvate. *Previously performed studies with a Siemens 3T Tim Trio. The imaging systems, phantoms, and prescan procedures reported in the reviewed papers are shown in Supporting Table S1.

Summary

Commercially available 3T MRI systems are by far the most commonly used for human HP 13C-pyruvate studies, although a systematic investigation of the impact of B0 has only recently been investigated (73). The multi-nuclear RF transmit and receive chain has proven sufficient for current acquisition strategies, although many sites have observed artifacts due to RF interference, gradient interference, and residual eddy currents when operating at the 13C frequency. A variety of 13C RF coils, tailored for numerous anatomical targets, have been successfully demonstrated, with the main limitation that most transmit coils take up a lot of additional space inside the bore and provide relatively inhomogeneous B1

+ Profiles. The

phantoms used have converged into generally 2 categories - small phantoms containing 13C-enriched compounds that can be used during the study and human-sized phantoms containing compounds with high carbon concentrations but without 13C enrichment that are used to test and calibrate the coils. There are no standardized compositions or geometry, and dynamic phantoms that recapitulate in vivo kinetics would be desirable but are still an emerging area. Prescan calibration procedures were not well defined in most publications, so we surveyed individual sites to determine current practices. Calibration procedures for the B0 field (13C CF and shimming) for most sites take advantage of 1H signal and methods, while methods

For Calibration Of B1

+ is more variable across sites, likely a reflection of remaining challenges in how to perform this calibration. Standardization of both phantoms and calibration procedures would synergistically improve the robustness and reproducibility of HP 13C studies.

Acquisition And Reconstruction

Data acquisition strategies in human HP [1-13C]pyruvate MRI studies must account for multiple chemical shifts, efficiently utilize the non-renewable HP magnetization, and acquire data quickly relative to metabolism and relaxation decay processes. These studies require spectral encoding to separate metabolites, necessitating pulse sequences that efficiently encode up to 5D data (3 spatial + 1 spectral + 1 temporal dimension). RF pulses must efficiently sample without immediately saturating the non-renewable HP magnetization, and sequences must acquire data quickly and be robust to both experimental and physiologic variation (e.g. B1

+ Inhomogeneity,

variation in perfusion) to ensure reproducibility and minimize scan-to-scan variability. This section covers current successful practices for data acquisition in human [1-13C]pyruvate studies, and accompanying 1H imaging, from different anatomic regions, including scan parameters and image reconstruction.

Acquisition And Reconstruction Methods

The acquisition methods used in human [1-13C]pyruvate studies can be classified into 3 categories: 1) MR spectroscopy or MR spectroscopic imaging (“MRS/I”), 2) chemical shift encoding methods, and 3) metabolite-specific imaging (Fig. 5).

Mrs/I Methods Specifically

resolve a spectrum that can be analyzed to extract expected as well as unexpected resonances, making this approach very robust. It was used in many initial studies (1).

Chemical Shift

encoding methods, most commonly the Iterative Decomposition of water and fat with Echo Asymmetry and Least-squares estimation (IDEAL) method, use imaging sequences acquired with multiple TEs and rely on a model-based separation of expected chemical shifts (85).

Metabolite-specific imaging methods use specialized RF pulses that are spatially and spectrally selective to excite individual metabolites which are then typically imaged with fast k-space trajectories such as echo planar imaging (EPI) or spirals (86).

Their Application To Different

organ systems is described below. The image reconstruction methods used in human [1-13C]pyruvate studies have typically been conventional methods (e.g. FFT, non-uniform FFT, or equivalent). The incorporation of accelerated imaging and advanced reconstruction methods including parallel imaging (4,57,87) and compressed sensing (7) has also been applied in human studies for improved spatial resolution, temporal resolution and coverage, but have the potential for additional artifacts as well as SNR losses due to ill-conditioning of the reconstruction (e.g. g-factor).

The Majority Of

published studies do not use accelerated imaging indicating the resolution and coverage achievable without acceleration is currently adequate for successful data collection. Performing coil combination, even with fully sampled data has also been shown to have specific challenges for HP human images: using naive sum-of-squares methods suffer from high noise amplification in the relatively low SNR regime of HP [1-13C]pyruvate (compared to 1H), motivating several HP 13C-specific methods that include data-driven coil sensitivity estimation which have shown obvious improvements over sum-of-squares (11).

More recently denoising techniques have been applied as post-processing of human HP data(41,42,44). The techniques applied are based on spatial-temporal singular value decomposition for unsupervised estimation of signal and noise components. They have shown improvements in apparent SNR in the brain and liver, while care must be taken to choose parameters such as the rank threshold to avoid oversmoothing and overfitting to the estimated signal components.

Prostate Studies

Prostate cancer was the first human application of HP [1-13C]pyruvate (1), and data was acquired with MRS/I methods: 1D dynamic MRS, single-slice 2D dynamic echo-planar spectroscopic imaging (EPSI), and single time point 3D EPSI. Advances in imaging strategies led to the development and application of new acquisition schemes, including undersampled 3D EPSI with compressed-sensing (7), model-based chemical shift encoding methods that use a priori information (47,59), and metabolite-specific EPI (10), all of which can provide volumetric whole-organ coverage and dynamic acquisitions.

The pyruvate bolus arrival in the prostate can vary by ± 10 s between patients, necessitating dynamic imaging to reliably and consistently capture the pyruvate bolus (18). For this reason, all currently ongoing studies acquire dynamic data. While MRS/I, chemical shift encoding, and metabolite-specific imaging can all achieve dynamic imaging, chemical shift encoding and metabolite-specific imaging provide greater dynamic and volumetric coverage (85). For scan prescriptions, the FOV is designed to provide full prostate coverage and typically to match the orientation of the anatomic imaging used for registration. Flip angles used in current studies are constant through time, as quantification with a variable-through-time flip scheme is highly sensitive to bolus timing (8) and errors in the RF transmit (B1 +) field (76).

Heart Studies

Data acquisition methods for 13C imaging in the heart must be designed to meet the demands of significant cardiac motion and blood flow. To cope with the periodic cardiac motion, most human heart studies to date used gating to the diastolic window, the longest cardiac cycle interval, which has reduced motion (2,22,28,30,35,36,38,45,52). The duration of the diastolic window limits the available data sampling time, making cardiac acquisitions the most time-constrained of the HP 13C MRI applications. The most common acquisition approach is metabolite-specific imaging with spiral k-space trajectories (2). Their single-shot imaging capability makes these methods particularly robust to motion effects. Furthermore, spiral k-space trajectories provide rapid k-space coverage and relatively benign flow and motion artifacts. The majority of studies have used 2D multi-slice acquisitions, but 3D encoding has also been used successfully (35).

Brain Studies

For HP 13C MRI of the human brain, the majority of studies have also used 2D (slice selective) acquisitions (10–12,14,16,28,33,40,41,44,51,53,60), with a trend toward volumetric coverage using 2D multi-slice metabolite-specific imaging. 3D metabolite-specific imaging of the whole brain, with phase encoding of the slice direction (34,57), has been shown to provide similar SNR efficiency (88) compared with multislice imaging. A number of studies have employed MRS/I (5,6,29,31–33,50,55) resulting in a spectrum from each voxel, which has the advantage of not requiring a priori information about which peaks to encode. This was important in early brain studies when it was not known which peaks would be detectable. Chemical shift encoding, using a set of images with different echo times and an iterative reconstruction of the individual resonances (i.e. the IDEAL approach (85)), has also been used (12,49,54), with the drawback that coverage in the slice direction was limited due to the time required to acquire multiple echo time images.

Abdomen And Breast Studies

The fundamental approaches to data acquisition and reconstruction in the abdomen and breast are largely similar to the aforementioned applications, but demand attention to particular challenges associated with these anatomic regions, especially relating to respiratory motion.

Although it has been shown that a basic 2D MRSI approach based on phase encoding and FID readout can be successfully applied for HP 13C imaging in breast (15) and kidney (13), major advantages in terms of spatiotemporal resolution and coverage have been realized using tailored approaches based on metabolite-specific imaging (43,62) and chemical shift encoding (43), which have facilitated multi-slice or 3D dynamic acquisitions over large FOVs in the abdomen (4,37,46).

The significant respiratory motion encountered in these regions can directly blur 13C images, and has further favored these rapid acquisition strategies. Motion also degrades B0 homogeneity, which can shift frequency-selective excitation profiles and introduce artifacts into rapid imaging readouts. This makes accurate determination of the acquisition center frequency and shimming essential in these regions which often cover large FOVs. (See “Prescan Calibration” section for more information). In some studies, breath-holding was used to minimize motion effects and enforce frame-to-frame data consistency (42). A pragmatic and reasonably effective approach for dealing with respiratory motion during 13C data acquisition is an initial breath-hold (as long as can be tolerated), followed by free-breathing (46,62).

1H Imaging

Collection of 1H imaging data is essential both for prescribing the 13C acquisition and for interpretation of the resulting 13C data. Multi-planar 1H scouts are acquired prior to 13C acquisition to enable graphical prescription of the 13C imaging region. All human HP 13C-pyruvate imaging studies acquire conventional MRI scans (e.g. T1- and T2-weighted volumes) for anatomic reference, aiming to cover at least the full 13C FOV. Acquiring these anatomic scans as close as possible to the time of 13C imaging (immediately before or after) minimizes potential misregistration between the data sets. Depending on the application, other advanced 1H sequences are also acquired (e.g. diffusion-weighted imaging for cancer imaging).

When contrast-enhanced data is acquired, it is done after 13C imaging, as paramagnetic contrast agents will accelerate 13C relaxation.

Reported Study Parameters

Figures 5 and 6, and Supporting Table S2 shows the reported acquisition study parameters for human HP [1-13C]pyruvate studies published as of September 2022. Figure 5 shows a mixture of MRS/I, metabolite-specific imaging, and chemical shift encoding methods have been successfully used, where spectroscopy-based methods have become less prevalent in recent studies. Figure 6 shows the acquisition timing, including the important start time and interval/temporal resolution, is quite variable across studies.

Figure 5: Acquisition methods used in published HP [1-13C]pyruvate human studies published up to September 2022, classified into: MR spectroscopy and spectroscopy imaging (MRS/I); chemical shift encoding methods, such as IDEAL, that use multiple TEs and model-based reconstructions; and metabolite-specific imaging methods that use spectrally-selective excitation to image a single resonance at a time.

Figure 6: Temporal acquisition characteristics reported in HP [1-13C]pyruvate human studies published up to September 2022. (a) Reported referencing of acquisition start times.

(B)

Acquisition start times reported when using dynamic imaging and when timing was reported relative to the end of the injection. (c) Temporal resolutions. “Not Applicable” indicates dynamic imaging was not used.

Summary

Three general categories of acquisition strategies have been used successfully for human HP 13C-pyruvate studies: MRS/I, model-based chemical shift encoding (e.g. IDEAL) methods, and metabolite-specific imaging methods. These have enabled successful studies in the prostate, heart, brain, abdomen, and breast. Recent studies increasingly have used the imaging-based strategies of metabolite-specific imaging and chemical shift encoding which are the fastest methods, although a heads-to–head comparison between techniques has not been performed.

Metabolite-specific imaging is quite popular because of its speed and compatibility with single-shot imaging, but is sensitive to B0 field variations and thus requires careful calibrations. Nearly all studies surveyed acquired data dynamically, allowing measurement of the bolus and metabolite kinetics. The exact timings and associated flip angles vary quite widely across reported studies, with no consensus yet as to how to choose these parameters. Image reconstruction is typically done directly using Fourier Transform methods, and accelerated imaging strategies are uncommon.

Data Analysis And Quantification

This section covers the analysis of data from human HP [1-13C]pyruvate studies, including modeling and metrics, visualization, as well as considerations for how to store data and metadata. Depending on study design, the analysis may need to give quantitative or semi-quantitative output reflecting a biological process or may just reflect a contrast between different regions of interest for quantitative evaluation.

Metrics

Figure 7: HP [1-13C]pyruvate raw data (A) have typically been quantified using four categories of metrics depending on the acquisition. Data acquired as a single time point are often quantified using normalized metabolite images or metabolite ratios (B). Dynamic data can be quantified using normalized metabolite images or metabolite ratios (B), or with metabolite timings such as time-to-peak (TTP) or pharmacokinetic (PK) models (C). The latter two require the data to be time-resolved. [1-13C]alanine and 13C-bicarbonate are analyzed similarly to [1-13C]lactate but omitted here for display.

Metabolite images are commonly used as summary metrics for HP MRI data, often including some form of normalization as well as summed over time as an area under the time curve (AUC) (17). These are analogous to the visual evaluation that is most used for routine clinical work (89,90). In these metabolite images, we expect that the [1-13C]pyruvate AUC signal is predominantly weighted towards perfusion and uptake, while [1-13C]lactate, [1-13C]alanine and 13C-bicarbonate AUCs represent metabolic conversion. The strength of this approach lies in its simplicity and relatively few underlying assumptions. Limitations to the use of single-metabolite images or AUCs include sensitivity to inhomogeneous coil profiles (57,87,91), the acquisition strategy and acquisition parameters, pyruvate polarization and concentration level, and signal relaxation rates (92). Further, the reader must be careful to interpret all the images in conjunction to better understand the underlying biology; for example, increased [1-13C]lactate in the presence of decreased [1-13C]pyruvate delivery can have a very different meaning compared to increased [1-13C]lactate with increased [1-13C]pyruvate delivery.

In an attempt to address variations in coil sensitivity, polarization level, and pyruvate delivery, AUC images are often computed by normalizing to a specified parameter, such as the maximum pyruvate or average lactate signals, or presented as a ratio such as lactate/pyruvate or divided by “total Carbon” - the sum total of HP 13C signal observed across all metabolites. The AUC ratios between metabolites and pyruvate are proportional to the corresponding forward kinetic rates (81,93), but are not directly comparable to rate constants when magnetization loss rates (e.g. relaxation and losses due to signal excitation) differ between studies. Similarly, the ratios between the produced metabolites (e.g. bicarbonate/lactate) can reflect the balance between downstream metabolic pathways (12,55). Care must be taken to consider how AUC images are calculated and normalized before comparing values between studies.

To further quantify the interpretation, pharmacokinetic (PK) modeling approaches were developed to compute the apparent kinetics of pyruvate-to-metabolite exchange (92,94–99). These yield semi-quantitative to quantitative apparent rate constants, given in s-1. Some models require a vascular input function, while others avoid this requirement (95). PK models can explicitly account for acquisition-specific details such as excitation angle and repetition time, and thus may reduce the effects of these details on quantification. An input-less model, provided in the Hyperpolarized-MRI-Toolbox (https://github.com/LarsonLab/hyperpolarized-mri-toolbox) (100) and thus frequently employed for human data, has been shown to fit well and robustly to prostate and brain data (8,20). PK models are quantitative in nature, arguably provide more relevant biological information (8,20), and appear to be reproducible across sites (51). However, rate constants derived from PK models are still apparent rates, and likely do not reflect a single biological characteristic.

Some additional considerations include whether complex or magnitude data is used, as the noise behaviors will impact the analysis differently. Additionally, cut-off thresholds or other criteria may be used to identify and avoid voxels with insufficient SNR before analysis to improve robustness (20,41).

Regardless of the analysis approach, the underlying biology is not always clearly represented by the data; instead, the metrics may be influenced by perfusion, barrier permeability, intercellular shuttles, enzyme activities, co-substrate concentrations, or combinations thereof, depending on the organ and disease of interest (19,43,94,101–103). This may be addressed by incorporating complementary information. As an example, HP 13C pyruvate data is influenced by perfusion, and thus addition of perfusion MRI could be important for interpretation (98,104,105).

All the methods outlined above have been explored in clinical studies, described in Supporting Table 3 and summarized in Figure 8. As of September 2022, approximately 52% of studies involving human subjects report rate constants derived from a PK model with a few different models reported. A nearly equal fraction (51%) of the studies report AUC ratio values.

Approximately 66% of these studies report metabolite-specific images or AUC values. About 40% report SNR values; this metric is particularly frequent in manuscripts that describe technical developments for clinical HP MRI. Approximately 16% of these studies summarize model-free metrics, and 10% report measurements from a single timepoint. Most studies report a combination of quantities.

Figure 8: Reported metrics used for analysis in HP [1-13C]pyruvate human studies published up to September 2022.

Visualization

A wide variety of approaches have been used for visualizing data from human HP 13C-MRI studies. The challenges and practical considerations are: 1) choosing the appropriate metrics to display, 2) how to encode the parameters (e.g. the colormap), and 3) choosing how to provide anatomical context and other multi-parametric data. The choice of visualization also depends on the goal which could be for diagnostic interpretation, but also quality control, reproducibility among readers and publication.

Metrics

The choice of HP 13C metrics is described in detail above. At this stage in HP 13C development where there is no standardized metric, often a combination of metabolite images and ratios or PK model parameters are shown.

Parameter Encoding

The mapping function chosen should provide an adequate, often quantitative, impression of the parameter mapped. There is a consensus in the visualization field that perceptually uniform maps are best suited to visualize continuous parameters, like the greyscale typically used by radiologists as well as other monochrome (black to blue) and color ranges (fire-type, rainbow-type) (106,107). Multi-color heatmaps have been the most frequently employed method for HP 13C data, while greyscale has infrequently been used but it ensures there is no coloring-based bias as well as facilitating later reuse (Fig. 9a). Among the color schemes employed in the clinical HP 13C literature, fire-type scheme seems to be the most common [similar to “Plasma” or “Inferno” in matplotlib.org]. Next most commonly employed is the rainbow-type scheme [similar to “Rainbow” in matplotlib.org].

Anatomical Context

HP MRI faces the challenge that it does not necessarily depict the anatomical features, similar to PET, and thus requires an anatomical reference. Most often, a grayscale anatomical image is overlaid with a HP colormap (Fig. 9c,d). This approach is very intuitive, but can skew perception as the grey-scale anatomical reference may affect the brightness of the HP data (e.g. signal in the skull). This bias does not occur when showing adjacent maps (Fig. 9a, b). Here, anatomical outlines may help to provide reference (Fig. 9b).

Related Journal Articles & DOI Links

Selected peer-reviewed publications relevant to 12 Lead ECG Acquisition. Click the DOI to access the full paper (may require institutional access).

Why Choose Us?

Bangalore guidance for robotics, Spectre and autonomous systems projects.