Linear Optimization for Cash-Flow Matching

Why Formulate Cash-Flow Matching as an Optimization Problem?

A liability-funding ladder organizes assets by the dates on which they provide cash. When there are several candidate assets, more than one portfolio may cover every liability. The decision is then not only whether coverage is possible, but which feasible portfolio meets the liabilities at the lowest initial cost.

Linear optimization gives a systematic way to make that decision. The model represents each asset holding as a decision variable, adds its cost to an objective, and requires the portfolio's cash flow at each liability date to be at least the amount due. Holding limits and other restrictions become additional constraints. The result is a precise statement of the selection problem, not a guarantee that a feasible portfolio exists.

Definition: A cash-flow matching linear program chooses nonnegative quantities of available assets to minimize their total acquisition cost, subject to dated cash-flow coverage requirements and any stated holding restrictions. In the basic model, asset cash flows, prices, and liabilities are known and deterministic, and holdings may be fractional unless the problem says otherwise.

Building the Linear Program

Suppose there are $n$ assets and $T$ liability dates. Let $x_j$ be the quantity held of asset $j$, $c_j$ its acquisition cost per unit, $a_{tj}$ its cash flow per unit at date $t$, and $L_t$ the liability due at that date. If asset $j$ has an upper holding limit $u_j$, the basic model is:

\begin{aligned} \text{Minimize}\quad & \sum_{j=1}^{n} c_jx_j\\ \text{subject to}\quad & \sum_{j=1}^{n}a_{tj}x_j\geq L_t,\quad t=1,\ldots,T,\\ & 0\leq x_j\leq u_j,\quad j=1,\ldots,n. \end{aligned}

Each coverage inequality applies at one date: it compares asset cash flows available on that date with the liability due then. The basic version does not count an earlier surplus as if it were cash available at a later date. If the model is intended to carry earlier surplus forward, it must represent that process explicitly, for example with a cash-balance variable and a stated accumulation assumption.

The cost objective is linear because each unit of an asset has a fixed stated cost, so holding $x_j$ units costs $c_jx_j$. Coverage is linear because each unit contributes a fixed amount $a_{tj}$ at date $t$, so the portfolio contributes $\sum_j a_{tj}x_j$. A budget, a minimum holding, or a restriction on total holdings can also be expressed as a linear constraint when it is proportional to the decision variables.

Why the Coverage Constraints Have This Form

At a particular date $t$, holding $x_j$ units of asset $j$ supplies $a_{tj}x_j$ in cash. Adding the contributions from all assets gives $\sum_j a_{tj}x_j$. To pay the liability $L_t$ from those dated cash flows, the total must satisfy $\sum_j a_{tj}x_j\geq L_t$. Equality means exact coverage; a strict excess means there is a surplus at that date.

The objective follows by the same additive reasoning. If the investor buys $x_j$ units at cost $c_j$ per unit, the initial outlay on that asset is $c_jx_j$. The total outlay is the sum across assets. Minimizing this sum among portfolios satisfying all the inequalities selects a least-cost feasible solution. It does not minimize market risk or guarantee that future cash flows will be realized when those cash flows are uncertain; those issues require assumptions or constraints beyond this basic deterministic model.

Define units and variables.
State what one unit of each asset means and let each decision variable represent the quantity purchased.

Set up the dated cash-flow table.
For each asset, record its cash flow at every liability date, including zero where it pays nothing.

Write objective and restrictions.
Minimize total acquisition cost, then add one coverage inequality per date and every applicable holding constraint.

Check the proposed optimum.
Substitute the holdings into every constraint, calculate the cost, and identify which constraints hold with equality.

Worked Examples

Worked Example: Minimizing Cost with a Mixed-Payment Asset

A hypothetical investor must pay $6$ thousand dollars at each of years 1 and 2. All entries below are in thousands of dollars. Asset A costs $0.90$ per unit and pays $1$ at year 1; asset B costs $0.85$ and pays $1$ at year 2; asset C costs $0.95$ and pays $0.60$ at each date. The investor can hold at most $4$ units of A, $3$ units of B, and $7$ units of C. Find the minimum-cost portfolio.

Method. Let $x_A,x_B,x_C$ denote the quantities held. The objective and constraints are:

\begin{aligned} \text{Minimize}\quad &0.90x_A+0.85x_B+0.95x_C\\ \text{subject to}\quad &x_A+0.60x_C\geq 6,\\ &x_B+0.60x_C\geq 6,\\ &0\leq x_A\leq4,\quad 0\leq x_B\leq3,\quad 0\leq x_C\leq7. \end{aligned}

For a fixed $x_C$, a least-cost solution uses no unnecessary A or B, since both have positive costs. If both coverage constraints are exact, then $x_A=6-0.60x_C$ and $x_B=6-0.60x_C$. The B limit requires $6-0.60x_C\leq3$, so $x_C\geq5$. The A limit requires $6-0.60x_C\leq4$, so $x_C\geq 2/0.60=3.333\ldots$. Thus the more restrictive lower bound is $x_C\geq5$, while the stated upper bound is $x_C\leq7$.

Substituting the exact-coverage holdings into the objective gives:

$$ 0.90(6-0.60x_C)+0.85(6-0.60x_C)+0.95x_C =10.50-0.10x_C. $$

This cost decreases as $x_C$ increases, so the minimum occurs at $x_C=7$. Then $x_A=6-0.60(7)=1.8$ and $x_B=6-0.60(7)=1.8$. The holding limits are satisfied: $1.8\leq4$, $1.8\leq3$, and $7\leq7$.

The cost is $0.90(1.8)+0.85(1.8)+0.95(7)=1.62+1.53+6.65=9.80$ thousand dollars, or $9,800. At each date, the cash flow is $1.8+0.60(7)=6$ thousand dollars, exactly matching the liability. The C holding limit and both coverage constraints bind; the A and B upper limits do not. The method avoids assuming that a mixed-payment asset is necessarily more expensive: its cash flows can make it valuable across multiple dates.

Worked Example: Reading Binding Constraints in an Optimum

A hypothetical portfolio must pay $12$ thousand dollars at year 1 and $15$ thousand dollars at year 2. Asset A costs $0.92$ thousand dollars per unit and pays $1$ at year 1, with a limit of $8$ units. Asset B costs $0.84$ per unit and pays $1$ at year 2, with a limit of $10$. Asset C costs $1.70$ per unit and pays $1$ at each date, with a limit of $5$. Find the minimum-cost holdings and interpret the binding constraints.

Method. Let $x_A,x_B,x_C$ be the holdings. The model is:

\begin{aligned} \text{Minimize}\quad &0.92x_A+0.84x_B+1.70x_C\\ \text{subject to}\quad &x_A+x_C\geq12,\quad x_B+x_C\geq15,\\ &0\leq x_A\leq8,\quad0\leq x_B\leq10,\quad0\leq x_C\leq5. \end{aligned}

For any feasible $x_C$, the least-cost holdings of A and B are $x_A=12-x_C$ and $x_B=15-x_C$, provided they meet their limits. The B limit gives $15-x_C\leq10$, hence $x_C\geq5$. Since C is limited to $5$, this forces $x_C=5$. The A limit is then satisfied because $12-5=7\leq8$. Thus $x_A=7$ and $x_B=10$.

The total cost is $0.92(7)+0.84(10)+1.70(5)=6.44+8.40+8.50=23.34$ thousand dollars, or $23,340. The year 1 cash flow is $7+5=12$, and the year 2 cash flow is $10+5=15$, so both liabilities are exactly covered.

The year 1 and year 2 coverage constraints bind. The upper limits on B and C also bind, while A's upper limit is slack by $8-7=1$ unit. This portfolio is least-cost because the year 2 requirement and B's cap force the full 5 units of C; with that choice, positive asset costs make any extra A or B unnecessary. The trap to avoid is treating the C limit as optional simply because C's cost is stated per unit: the B capacity constraint makes at least 5 units of C necessary.

Worked Example: Proving Infeasibility at a Liability Date

A hypothetical fund owes $6$ thousand dollars at year 1 and $7$ thousand dollars at year 2. Asset A pays $1$ thousand dollars at year 1 per unit and is limited to $4$ units. Asset B pays $1$ thousand dollars at year 2 per unit and is limited to $6$ units. Asset C pays $1$ thousand dollars at each date per unit and is limited to $1$ unit. Can the liabilities be covered?

Method. Let the holdings be $x_A,x_B,x_C$. The year 1 constraint is $x_A+x_C\geq6$, while the limits imply $x_A+x_C\leq4+1=5$. These inequalities cannot both hold: they would require $6\leq5$. Therefore the model is infeasible, regardless of asset prices or the year 2 constraint.

For completeness, the year 2 maximum is $x_B+x_C\leq6+1=7$, which equals the year 2 liability. That date alone is coverable, but it does not repair the shortfall at year 1. The key check is date-specific: enough total cash over the entire horizon is not sufficient if it arrives on the wrong date. The common mistake is to add all asset cash flows across dates and compare their sum with all liabilities; that comparison discards the timing constraints that define matching.

Binding Constraints, Feasibility, and Model Limits

A constraint is binding at a proposed solution when it holds with equality. In a matching model, a binding coverage constraint means the assets provide exactly the liability amount at that date. A binding holding limit means the portfolio uses the full permitted quantity of that asset. A nonbinding constraint has slack: for example, an upper holding limit of $8$ with a holding of $7$ has slack $1$.

Binding constraints help explain why the selected portfolio has its particular composition. They also provide a useful arithmetic check. After finding a proposed solution, calculate every date's total cash flow and check every lower and upper holding bound. A portfolio that meets the objective calculation but fails one coverage date is not feasible.

If no portfolio meets all the constraints, the model is infeasible. A quick way to establish infeasibility is to find one date where the maximum possible asset cash flow is below the liability. More complex infeasibility can result from combinations of restrictions, even where each date appears coverable when considered separately.

The basic model treats holdings as divisible quantities. If assets can only be purchased in whole units, the model needs integer restrictions on the relevant variables; it is then an integer optimization problem rather than an ordinary linear program. The model also assumes the listed cash flows and acquisition costs are the correct inputs. It does not account automatically for uncertain payments, transaction costs, taxes, or surplus reinvestment. Such features must be represented explicitly if the problem includes them.

Key takeaway: Minimize total asset cost only after writing a coverage inequality for every liability date and every stated holding restriction. Check feasibility date by date, then verify the portfolio's cost, cash flows, and binding constraints.

Check Your Understanding

For each problem, formulate or assess the stated dated matching model. Amounts and costs are in thousands of dollars unless otherwise stated.

Liabilities are $7$ at year 1 and $10$ at year 2. Asset A costs $0.97$, pays $1$ at year 1, and has a limit of $5$. Asset B costs $0.90$, pays $1$ at year 2, and has a limit of $8$. Asset C costs $1.80$, pays $1$ at both dates, and has a limit of $4$. Find the minimum-cost holdings. (Answer: $x_A=3,\ x_B=6,\ x_C=4$; minimum cost $15.51$, or $15,510.)
Liabilities are $8$ at year 1 and $10$ at year 2. Asset X costs $0.88$, pays $1$ at year 1, and is limited to $6$. Asset Y costs $0.91$, pays $1$ at year 2, and is limited to $7$. Asset Z costs $1.75$, pays $1$ at both dates, and is limited to $4$. Find the minimum-cost portfolio. (Answer: $x_X=4,\ x_Y=6,\ x_Z=4$; minimum cost $15.98$, or $15,980.)
Liabilities are $9$ at year 1 and $11$ at year 2. Asset A pays $1$ at year 1 and is limited to $7$; asset B pays $1$ at year 2 and is limited to $8$; asset C pays $1$ at both dates and is limited to $3$. Is the model feasible? Give one feasible portfolio. (Answer: Yes; $x_A=6,\ x_B=8,\ x_C=3$ covers $9$ and $11$, respectively.)
Liabilities are $6$ at year 1 and $8$ at year 2. Asset A pays $1$ at year 1 and is limited to $5$; assets B and C each pay $1$ at year 2 and are limited to $8$ and $4$, respectively. Can all liabilities be covered? (Answer: No; year 1 cash flow is at most $5<6$, so the model is infeasible.)
In the second worked example, identify all binding constraints at the minimum-cost solution and state the slack in asset A's upper holding limit. (Answer: Both dated coverage constraints, B's upper limit, and C's upper limit bind; A's upper limit has slack $1$ unit.)

What You'll Learn