9. Toward the tax problem
Draft
This section states the problem the post that follows this series will build a solver for, in the vocabulary of the preceding eight. It needs that vocabulary now because the problem is small in every dimension except one. Its continuous part is a convex quadratic program with a factor model, which Section 8 placed in the solved corner. Its integers are the directions of trades and the boundaries of lots, a few hundred of them. Its one nonconvexity in the ordinary course of business is a kink at zero in the tax of each asset. Its one nonconvexity in the extraordinary course is a bilinear clause of the tax code. The section gives the rules with their statute references, the formulation, and the structure as a MINLP. It then gives the eight-lot figure with every number it displays, the mapping of the plan to the machinery of Sections 2 to 7, and the research plan reframed around the GPU agenda of Section 7.8. Every tax rule here is a reading of the statute and regulations as they stood on 4 and 5 October 2026, made for a model and not for advice, and it stays flagged as unverified for any other purpose.
The rules
An account holds tax lots, and the rules that price a sale are rules about lots. This section states the four rules the model of Section 9.2 needs and no others: what a lot is and how a sale from it is taxed (Definition 9.1.1); who chooses which lot a sale comes from, with the two rules of thumb that make the choice by hand; the wash-sale rule, which disallows a loss when the position is bought back too soon (Definition 9.1.2); and the netting of gains against losses, with the annual allowance and the carryover (Definition 9.1.3). Each rule is followed by what a model keeps of it and what it leaves out, because the formulation of Section 9.2 is a one-period model with fixed rates, and a reader needs to know which rules it simplifies away before reading its numbers.
Definition 9.1.1 (tax lot, basis, holding period, rates). A tax lot of a security is a parcel of \(q\) shares acquired on one date at one price. Its basis \(\beta\) is the cost per share, adjusted as the Code requires (26 U.S.C. §1012). Selling \(s\) shares of the lot at a price \(p\) realizes a gain of \(s\,(p - \beta)\), a loss when the number is negative. The lot is short-term if held for not more than one year and long-term if held for more than one year (§1222(1)–(4)). The holding period begins on the day after acquisition. Short-term gains are taxed at the ordinary rate \(\rho_{\mathrm{st}}\) and long-term gains at the preferential rate \(\rho_{\mathrm{lt}} \le \rho_{\mathrm{st}}\). With the top federal brackets and the 3.8 per cent net investment income tax of §1411 added, \(\rho_{\mathrm{st}} = 0.408\) and \(\rho_{\mathrm{lt}} = 0.238\), which are the rates Moehle, Kochenderfer, Boyd and Ang use and the rates the lots figure labels.26 U.S.C. §1012 (basis of property), §1222 (other terms relating to capital gains and losses), §1223 (holding period), §1411 (imposition of the net investment income tax), all at law.cornell.edu/uscode/text/26; Internal Revenue Service, Publication 550, Investment Income and Expenses, for the day-after rule, irs.gov/publications/p550; N. Moehle, M. J. Kochenderfer, S. Boyd and A. Ang, "Tax-aware portfolio construction via convex optimization", Journal of Optimization Theory and Applications 189 (2021), Section 6.1. Read 4 and 5 October 2026.
(The identification of the lot, and two rules of thumb) Which lot a sale comes from is the taxpayer's choice within rules, and the choice is what makes loss harvesting possible: realizing a loss deliberately so that it offsets gains elsewhere. Absent an adequate identification the shares sold are the earliest acquired, which is first in, first out. Specific identification requires that the taxpayer specify the lot to the broker at the time of the sale and receive written confirmation within a reasonable time, or hold a standing order.26 CFR §1.1012-1(c)(1) and (c)(3), law.cornell.edu/cfr/text/26/1.1012-1, read 5 October 2026. The effect of the accounting method on the losses a portfolio can harvest is the subject of A. L. Berkin and J. Ye, "Tax management, loss harvesting, and HIFO accounting", Financial Analysts Journal 59 (2003); the post quotes none of its numbers. Two rules of thumb for the identification recur below. Highest basis first (HIFO) sells the lot with the largest basis first, and least tax first out (LTFO) sells lots in increasing order of the tax per dollar they realize.
Definition 9.1.2 (wash sale). A loss on a sale of stock or securities is disallowed if the taxpayer acquires substantially identical stock or securities, or enters into a contract or option to acquire them, within a period beginning 30 days before the sale and ending 30 days after it (§1091(a)). The period is 61 days counting the day of the sale. If fewer shares are acquired than were sold at a loss, only the loss on the matched shares is disallowed. The acquired shares are matched, in the order of their acquisition, with an equal number of the shares sold. When several loss sales are involved, the sales are taken in the order of their disposition, and same-day sales in the order of original acquisition (§1091(b); Reg. §1.1091-1(b)–(c)). The disallowed loss is added to the basis of the replacement shares (§1091(d)), and the holding period of the shares sold is added to that of the replacement shares (§1223(3)).26 U.S.C. §1091, law.cornell.edu/uscode/text/26/1091; 26 CFR §1.1091-1, law.cornell.edu/cfr/text/26/1.1091-1; IRS Publication 550, "Wash Sales". Example 2 of the regulation: 100 shares sold at a loss of 1,000 dollars and 75 replacement shares bought inside the window; the loss on 75 shares (750 dollars) is disallowed, the loss on 25 shares (250 dollars) is allowed, and the 75 replacement shares take the disallowed loss into their basis. Read 5 October 2026.
(What a model keeps of the wash-sale rule) For a model the operative points are these. The securities must be substantially identical, which is a wider class than the same security. The window is 61 days. Only the loss on as many shares as were acquired is disallowed. The disallowed loss is deferred into the replacement basis rather than lost. And the matching order is prescribed, so an optimizer cannot route the disallowance to the cheapest lot.
Definition 9.1.3 (netting, the annual allowance and the carryover). Short-term gains and losses are netted against each other, long-term gains and losses likewise, and the two nets are then netted against each other (§1222(5)–(11)). A noncorporate taxpayer deducts a net capital loss against other income only up to 3,000 dollars a year, 1,500 if married filing separately (§1211(b)). The excess carries forward and keeps its character (§1212(b)(1)). The excess of net short-term loss over net long-term gain is a short-term loss in the next year, and the excess of net long-term loss over net short-term gain is a long-term loss.26 U.S.C. §1211(b) and §1212(b)(1), at the same site, read 5 October 2026.
Definition 9.1.3: netting, the annual allowance and the carryover
short-term gains and losses long-term gains and losses
| |
v v
net short-term net long-term
| |
+---> netted against each other <--+
(sec. 1222(5)-(11))
|
| a net capital loss
v
a noncorporate taxpayer deducts it against other
income only up to 3,000 dollars a year (1,500 if
married filing separately; sec. 1211(b))
|
| the excess
v
carried forward to the next year, keeping its
character (sec. 1212(b)(1)):
the excess of net short-term loss over net
long-term gain -> a short-term loss
the excess of net long-term loss over net
short-term gain -> a long-term loss
(Why a loss is not worth its rate times its size) The consequence for a model is that the value of a realized loss is not its rate times its size. It depends on the account's other gains in the year and on the carryover. Its character matters too: a short-term loss netted against a short-term gain saves tax at the ordinary rate, while the same loss netted against a long-term gain saves it at the lower rate, and which netting happens depends on the rest of the year's gains. A harvested loss also lowers the basis of whatever is bought with the proceeds, so it defers tax rather than removing it. A one-period objective with fixed rates \(\rho_{\mathrm{st}}\) and \(\rho_{\mathrm{lt}}\), which is what this post and the two Boyd-group papers use, is therefore already a modelling choice. The deferral and the character of the loss are the two things it leaves out.N. Sosner, M. Gromis and S. Krasner, "The tax benefits of direct indexing: not a one-size-fits-all formula", The Journal of Beta Investment Strategies 13 (2022), separate the benefit of loss harvesting into a deferral component and a character component (short-term losses offsetting short-term gains taxed at the higher rate). The multi-period convex framework in which the deferral can be modelled is S. Boyd, E. Busseti, S. Diamond, R. N. Kahn, K. Koh, P. Nystrup and J. Speth, "Multi-period trading via convex optimization", Foundations and Trends in Optimization 3 (2017); S. Boyd, K. Johansson, R. Kahn, P. Schiele and T. Schmelzer, "Markowitz portfolio construction at seventy", Journal of Portfolio Management 50 (2024), is the same group's account of when the added machinery is worth invoking.
The two rules of thumb disagree exactly when the rates differ.
Proposition 9.1.4 (least tax first and highest basis first). Let the lots of one asset have rates \(\rho_\ell\) and bases \(\beta_\ell\), and let the price be \(p\). The tax per dollar of proceeds from lot \(\ell\) is \(T_\ell = \rho_\ell\,(1 - \beta_\ell / p)\). If all the lots carry the same rate, \(T_\ell\) is a decreasing function of \(\beta_\ell\) and the two orders coincide. With two rates they can differ, and then highest basis first is suboptimal for the immediate liability.
Proof. For a common \(\rho\), \(T_\ell = \rho - \rho\beta_\ell/p\) decreases in \(\beta_\ell\), so increasing \(T\) is decreasing \(\beta\). The second claim is the example. ∎
Take a price of 100 dollars, a lot A of 100 shares with basis 95 held two years, and a lot B of 100 shares with basis 97 held three months, and raise 10,000 dollars. Lot A realizes a gain of 500 dollars taxed at 23.8 per cent, 119.00 dollars, which is 1.19 per cent of the proceeds. Lot B realizes 300 dollars taxed at 40.8 per cent, 122.40 dollars, which is 1.224 per cent. Highest basis first sells B. Least tax first sells A and saves 3.40 dollars on the first 10,000. The script at the end of Section 9.3 prints these numbers. Moehle and coauthors make the same point and note that the two rules coincide when every lot of an asset carries one rate.Moehle, Kochenderfer, Boyd and Ang (2021), Section 1 and Section 3.2, where the LTFO order is introduced; they cite J. M. Dickson, J. B. Shoven and C. Sialm, "Tax externalities of equity mutual funds", National Tax Journal 53 (2000), and Berkin and Ye (2003) for the effect of the accounting method.
(Deferral under the wash-sale rule, and the monthly convention) The wash-sale rule, in the same arithmetic, is a deferral. Buy 100 shares at 100 dollars on day 0 and sell them at 90 on day 20, a loss of 1,000 dollars. Buy 100 shares at 92 on day 35, which is 15 days after the sale and inside the window. The loss is disallowed, and the replacement shares take a basis of 92 + 1,000/100 = 102 dollars a share. Sell them later at 110 and the gain is 800 dollars, not the 1,800 the raw basis would give. The disallowed loss has been recovered, later and at whatever rate then applies. Move the purchase to day 51, which is 31 days after the sale, and the loss stands. In a monthly trading calendar the rule is avoided by two conventions: never buy and sell the same name in one trade list, and trade on the first business day more than 31 calendar days after the last trade. That is the convention of Moehle and coauthors and of this post's formulation in its basic form.Moehle, Kochenderfer, Boyd and Ang (2021), abstract and Section 6.2: "we trade monthly, and cannot simultaneously buy and sell the same asset"; "monthly trading means we trade on the first business day more than 31 calendar days after the last trade". The convention presumes no acquisition of substantially identical securities inside the window from any other source, dividend reinvestment and the taxpayer's other accounts included; whether the model should see those is a question for the post that follows this series.
The formulation
This section writes the problem down as (9.2.1) in three steps, the portfolio terms, then the lots and the tax, then the two lines that make it an integer program; it then isolates the one function the whole plan turns on, the liability \(L_i\) of a sale, and the one structure that keeps the problem small, the factor form of the risk. Section 9.3 classifies the result.
(The three portfolio terms) The portfolio side of the problem is the mean–variance problem of Section 4.4 with the account's holdings in dollars. Write \(h \in \mathbb{R}^n\) for the dollar holdings after the trade and \(u\) for the trade itself. The manager wants three things. The first is expected return, \(\alpha^\top h\), where \(\alpha_i\) is a forecast of the next period's return per dollar held in asset \(i\). The pre-trade holdings are fixed, so it is enough to reward the trade, \(\alpha^\top u\), and in a minimization the forecast enters with a minus sign. The second is a low variance of the deviation from a target portfolio \(h_b\): \((h - h_b)^\top V (h - h_b)\), with \(V\) the covariance matrix of returns. The target is called the benchmark in portfolio language, and the word means a portfolio here, not a solver benchmark as in Section 8. The third is a low trading cost, \(\kappa^\top |u|\), where \(\kappa_i\) is the half-spread of asset \(i\), half the gap between its bid and ask prices, which is what one trade pays per dollar relative to the mid price. The weights \(\gamma_{\mathrm{risk}}\), \(\gamma_{\mathrm{tc}}\) and \(\gamma_{\mathrm{tax}}\) are the manager's exchange rates between variance, trading cost and tax on one side and expected return on the other.
(The lots, and the two integer lines) Now add the lots. Asset \(i\) has price \(p_i\), pre-trade holding \(h^{\mathrm{init}}_i \ge 0\), and lots \(\ell \in i\) with \(q_\ell\) shares and basis \(\beta_\ell\). The decision is a purchase \(b_i \ge 0\) of asset \(i\) and a sale \(s_\ell \in [0, q_\ell p_i]\) from each of its lots, both in dollars (Definition 9.1.1 counted shares). The trade is \(u_i = b_i - \sum_{\ell \in i} s_\ell\), the post-trade holding is \(h = h^{\mathrm{init}} + u\), and the cash raised must meet a target, \(\sum_i u_i = c^{\mathrm{init}} - c^{\mathrm{des}}\). In the minimization form of this series, the tax-aware problem is
\[\begin{aligned} \min_{b,\,s,\,h,\,u}\ & \gamma_{\mathrm{risk}}\,(h - h_b)^{\top} V\,(h - h_b) \;+\; \gamma_{\mathrm{tc}}\,\kappa^{\top}\lvert u \rvert \;+\; \gamma_{\mathrm{tax}} \sum_{\ell} T_\ell\, s_\ell \;-\; \alpha^{\top} u \\ \text{subject to}\ & u_i = b_i - \sum_{\ell \in i} s_\ell, \qquad h = h^{\mathrm{init}} + u, \qquad \mathbf 1^{\top} u = c^{\mathrm{init}} - c^{\mathrm{des}}, \\ & 0 \le s_\ell \le q_\ell\, p_{i(\ell)}, \qquad b_i \ge 0, \qquad u \in \mathcal U,\ h \in \mathcal H, \\ & b_i \cdot \sum_{\ell \in i} s_\ell = 0 \qquad \text{(no purchase and sale of one name in one list)}, \\ & s_\ell \in \{0,\ q_\ell p_{i(\ell)}\} \ \text{ or } \ s_\ell \in p_{i(\ell)}\,\mathbb{Z} \qquad \text{(whole lots, or whole shares)}, \end{aligned} \tag{9.2.1}\]with \(\mathcal U\) and \(\mathcal H\) polyhedral (position limits, sector bounds) and \(T_\ell\) the tax per dollar of lot \(\ell\) from Proposition 9.1.4. Moehle and coauthors write the same problem as the maximization of a utility, the negative of this objective, and call it the tax-aware Markowitz problem. Their numbers below are utilities in basis points of account value, where a basis point (bp) is one hundredth of one per cent, 0.01 per cent of the account, and the text says so when it quotes them.Moehle, Kochenderfer, Boyd and Ang (2021), equations (4) and (5), with the lot-level liability of their Section 3. Without the last two lines the problem is a convex quadratic program. The last two lines are the subject of this section.
The terms of (9.2.1) on a lot, on an asset and on the account
lot l of asset i sale s_l in dollars, 0 <= s_l <= q_l p_i
tax term gamma_tax T_l s_l
last line: s_l in {0, q_l p_i} or s_l in p_i Z
|
| sum over the lots l of asset i
v
asset i trade u_i = b_i - sum s_l, purchase b_i >= 0
holding h_i = h^init_i + u_i
trading cost gamma_tc kappa_i |u_i|
forecast -alpha_i u_i
next-to-last line: b_i * sum s_l = 0
|
| all the assets together
v
the account cash 1'u = c^init - c^des; u in U, h in H
risk gamma_risk (h - h_b)' V (h - h_b)
without its last two lines, (9.2.1) is a convex quadratic program
Definition 9.2.1 (lot tax rate and liability function). The tax per dollar sold from lot \(\ell\) of asset \(i\) is \(T_\ell = \rho_\ell\,(1 - \beta_\ell / p_i)\), positive for a lot at a gain and negative for a lot at a loss. For a sale of \(-u_i > 0\) dollars of asset \(i\), the liability function is the least tax any allocation across the lots achieves,
\[L_i(u_i) \;=\; \min_{s}\Big\{ \sum_{\ell \in i} T_\ell\, s_\ell \;:\; \sum_{\ell \in i} s_\ell = -u_i,\ \ 0 \le s_\ell \le q_\ell p_i \Big\}, \qquad L_i(u_i) = 0 \ \text{ for } u_i \ge 0,\]and \(L_i(u_i) = +\infty\) when the sale exceeds the holding. The total liability \(L(u) = \sum_i L_i(u_i)\) is separable across assets.
Proposition 9.2.2 (least tax first out, and the shape of \(L_i\); Moehle, Kochenderfer, Boyd and Ang 2021). For a fixed sale, the allocation that sells lots in increasing order of \(T_\ell\), each lot exhausted before the next is touched, attains \(L_i(u_i)\). On \(u_i \le 0\) the function \(L_i\) is continuous, piecewise affine and convex, with a breakpoint at each lot boundary, and on \(u_i \ge 0\) it is zero. It is convex on all of \(\mathbb{R}\) if and only if no lot of asset \(i\) is held at a loss.
Proof sketch. The inner problem is a continuous knapsack: a linear objective, one equality and box constraints. If an optimal allocation sold a dollar from a lot with larger \(T\) while a lot with smaller \(T\) had room, moving the dollar would lower the objective, so the greedy order is optimal. The marginal tax of the \(s\)-th dollar sold is the \(T_\ell\) of the lot it comes from, which is nondecreasing in \(s\), so \(s \mapsto L_i(-s)\) is convex, which is convexity of \(L_i\) on \(u_i \le 0\). Across \(u_i = 0\) the left derivative is \(-T_{(1)}\), the negative of the smallest lot rate, and the right derivative is \(0\). Convexity at the kink requires \(-T_{(1)} \le 0\), that is, no lot at a loss. ∎
(Where the nonconvexity sits) In a picture: selling a loss lot pays the investor, so the graph of \(L_i\) dips below zero to the left of the origin and is flat to the right, a concave kink at zero. Everything nonconvex about tax-aware trading in the ordinary course is in that kink, once per asset that holds a loss. Within the half-line the function is as convex as a piecewise-linear function can be. The λ-model of Section 4.6 represents it exactly, since its LP relaxation is the convex hull of the breakpoints and the breakpoints lie on a convex curve. In other words, on the selling half-line the function can be written with weights on its breakpoints and no binary variable at all, because dropping the integrality there costs nothing; the only binary decision the tax term forces is whether the asset is sold or bought, the two sides of the kink.
(The factor form of the risk, and what it costs) The risk term has a structure the whole plan depends on, and Section 4.4 set it out. Definition 4.4.6 gives the factor form \(V = X \Omega X^{\top} + D\), with \(X \in \mathbb{R}^{n \times k}\) the exposures to \(k \ll n\) factors, \(\Omega\) the factor covariance and \(D\) the diagonal of specific variances, so that the risk of a deviation \(d = h - h_b\) splits into a systematic part \(d^{\top} X \Omega X^{\top} d\) and a specific part \(\sum_i D_{ii} d_i^2\) that is separable across assets. Proposition 4.4.7 gives the cost. With a Cholesky factor \(C C^{\top} = \Omega\) and the exposure variables \(y = C^{\top} X^{\top} h \in \mathbb{R}^k\) added, the systematic part is \(\lVert y - y_b \rVert^2\) and the KKT system of a quadratic program with \(m_c\) linear equalities is solved in \(O\big(n (k + m_c)^2 + (k + m_c)^3\big)\) operations, and the same proposition gives the Woodbury form of \(V^{-1}\), under which each product \(V^{-1} r\) costs \(O(nk)\). Moehle and coauthors use a commercial model with \(k = 72\) factors for 998 assets, and every linear-algebra step of their solves scales with \(n k^2\) rather than \(n^3\).Moehle, Kochenderfer, Boyd and Ang (2021), equations (2) and (3); N. Moehle, J. Gindi, S. Boyd and M. J. Kochenderfer, "Portfolio construction as linearly constrained separable optimization", Optimization and Engineering 24 (2023), equation (7) and Appendix A, for the exposure variables. Three uses follow. The direction-fixed subproblems of Section 9.3 are such programs and solve in milliseconds. The specific-risk diagonal \(D\) is exactly the diagonal the perspective split of Section 4.5 needs, and the largest one the model can justify. And the number of coupling constraints in the separable form of Section 9.3 is \(k + 1\), not \(n\), which is what makes the duality gap small (Proposition 9.3.3 states the bound).
(What a cardinality rule costs in tracking error) The specific part is also what a cardinality rule costs, and the arithmetic of the tracking error, the volatility of the deviation \(h - h_b\), is worth doing once. Take four names held at equal weight, one factor with exposure 1 for each name so that the factor exposure of the portfolio is 1 whatever the weights, and specific volatilities of 10, 10, 20 and 30 per cent. Dropping one name and reweighting the other three to a third each preserves the factor exposure. The tracking error against the four-name portfolio is then pure specific risk, with deviations \((1/12, 1/12, 1/12, -1/4)\) in some order. Dropping the 30 per cent name gives a variance of \((0.30/4)^2 + (1/12)^2 (0.01 + 0.01 + 0.04) = 0.005625 + 0.000417\), a tracking error of 7.8 per cent. Dropping a 10 per cent name gives 4.0 per cent, and dropping the 20 per cent name 5.7 per cent. The names a limit forces out are chosen by this arithmetic, and the exact version of that choice is a mixed-integer program. Canakgoz and Beasley formulate index tracking and enhanced indexation with a cardinality limit in that form.N. A. Canakgoz and J. E. Beasley, "Mixed-integer programming approaches for index tracking and enhanced indexation", European Journal of Operational Research 196 (2009). The arithmetic is printed by the script at the end of Section 9.3.
Dropping the 30% name of four equal weights (one factor, exposure 1)
specific volatility 10% 10% 20% 30%
weight before 1/4 1/4 1/4 1/4
weight after 1/3 1/3 1/3 0
after - before 1/12 1/12 1/12 -1/4
the factor exposure is 1 before and after: the deviation is pure
specific risk, with variance
(0.30/4)^2 + (1/12)^2 (0.01 + 0.01 + 0.04)
= 0.005625 + 0.000417, a tracking error of 7.8%
dropping a 10% name instead: 4.0%; the 20% name: 5.7%
What kind of MINLP it is
This section classifies (9.2.1) by four structural facts, each a term in the taxonomy of Sections 2 to 4: the problem is convex once the direction of each trade is fixed (Proposition 9.3.1); its remaining integers are indicators with the perspective structure of Sections 4.3 to 4.5; its one bilinear clause is a disjunction whose hull is a triangle (Proposition 9.3.2); and the gap between the problem and its convexification is bounded by a count that depends on the number of factors, not on the number of assets (Proposition 9.3.3). Section 9.5 turns the four facts into a plan. The first is the one everything else rests on.
Proposition 9.3.1 (convexity under fixed directions; Moehle, Kochenderfer, Boyd and Ang 2021). Let \(I_-\) be the set of assets with at least one lot held at a loss. For any sign vector \(z \in \{-1, +1\}^{I_-}\), problem (9.2.1) without its last two lines and with the constraints \(z_i u_i \ge 0\) for \(i \in I_-\) added is a convex program. It is a quadratic program in \((u, h, s)\) once each \(L_i\) on its half-line is written through the lot variables. It is a second-order cone program if a market-impact cost \(c_i \lvert u_i \rvert^{3/2}\) is added, the usual model of the price a trade moves against itself, since the epigraph of \(\lvert u \rvert^{3/2}\) is representable by second-order cones (Section 4.8). The problem is therefore the minimum over \(2^{\lvert I_- \rvert}\) convex programs, and it is a mixed-integer quadratic program with one binary per asset in \(I_-\).
Proof sketch. By Proposition 9.2.2 each \(L_i\) is convex on each half-line, so with the sign of \(u_i\) fixed the tax term is convex. The risk term, the spread term and the forecast term are convex, and the constraints are polyhedral. Assets outside \(I_-\) have convex \(L_i\) on all of \(\mathbb{R}\) and need no sign. ∎
(The only combinatorial decision, and the two-stage method) The only decision that is combinatorial in the ordinary course is therefore "buy or sell this name this month" for the names that hold a loss. Once that is known, which lots to sell is settled by a sort, in least-tax-first order, and how much to sell falls out of a quadratic program. This is the observation on which Moehle and coauthors' two-stage method rests: solve a convex relaxation to guess the signs, then solve the convex program the signs define, and read off a certificate from the relaxation's value: the relaxation's value is a lower bound in the sense of Proposition 1.1.4, so when the convex program's answer matches it, the answer is proved optimal without any search. The two convex solves take under a second for several hundred assets and several dozen factors, and they were several hundred times faster than the exact solve on their instances. On their 744 monthly instances with 998 assets and 72 factors, the exact mixed-integer solve by CPLEX 12.9 under a 300-second limit finished on 565. The heuristic's answer matched the relaxation bound, and so was certified optimal to the solver tolerance of about 0.05 basis points, on 678 of the 744. Their abstract says the exact route is available "at the cost of very long solve times for some problem instances".Moehle, Kochenderfer, Boyd and Ang (2021), abstract, Sections 5 and 6, and Table 1: of the 565 instances CPLEX solved within 300 seconds the heuristic matched the optimum to within 0.05 basis points in 549 and was never more than 0.3 basis points worse in the other 16; on the 179 instances where CPLEX hit the limit the heuristic was better by more than 0.05 basis points in 68 cases and worse in 22. The paper reports 744 instances in its text and Table 1 and "720 problem instances" in the caption of its Figure 5; this series uses 744 throughout.
Proposition 9.3.1: a minimum over 2^|I_-| convex programs
a sign z_i for each asset i in I_-, the assets with a lot at a
loss: z_i = -1 adds u_i <= 0 (sell), z_i = +1 adds u_i >= 0 (buy)
(9.2.1) without its last two lines
z_i = -1 / \ z_i = +1
/ \
/ \
/ \
o o
z_j = -1 / \ z_j = +1 z_j = -1 / \ z_j = +1
/ \ / \
o o o o
: : : :
2^|I_-| leaves, one per sign vector z, each a convex program: a QP
in (u, h, s), an SOCP with an impact cost c_i |u_i|^(3/2); the
problem is the minimum over the leaves
in a leaf, the allocation across lots is settled by a sort in
least-tax-first order (Proposition 9.2.2), and the amounts by a
quadratic program
Moehle and coauthors' two-stage method solves one leaf, the one
whose signs a convex relaxation guesses; the relaxation's value
bounds the answer. On their 744 monthly instances (998 assets,
72 factors):
the answer matched the bound, to about 0.05 bp, on 678
the exact solve (CPLEX 12.9, 300-second limit) finished on 565
(The second fact: indicators with perspective structure) The second structural fact is that the remaining integers are indicators with the perspective structure of Sections 4.3 to 4.5. A minimum trade size is a semicontinuous variable, \(x \in \{0\} \cup [a, u]\), written \(a z \le x \le u z\). A fixed charge per trade with a proportional part, \(\phi(x) = 0\) at \(x = 0\) and \(\beta + \alpha\lvert x\rvert\) otherwise, has as its convex envelope on \([-l, u]\) the linear cost \((\beta/u + \alpha)\,x\) for \(x \ge 0\) and \(-(\beta/l + \alpha)\,x\) for \(x \le 0\). That envelope is the big-M relaxation in disguise, and it is exact only at \(x \in \{-l, 0, u\}\): the big-M model \(\phi \ge \beta z + \alpha\lvert x\rvert\) with \(-l z \le x \le u z\) lets the relaxed indicator take the fractional value \(\lvert x\rvert / u\) (or \(\lvert x\rvert / l\)), so the fixed charge is paid in proportion to the trade instead of in full, and that proportional charge is exactly the envelope's line. Lobo, Fazel and Boyd analyse it and tighten it by the bounds the variance constraint implies.M. S. Lobo, M. Fazel and S. Boyd, "Portfolio optimization with linear and fixed transaction costs", Annals of Operations Research 152 (2007), equations (16) and (17) and Section 2.3; their reweighting heuristic is the ancestor of the two-stage method. A limit on the number of names is the cardinality constraint of Section 4.4. In every case the quadratic the indicator multiplies is the specific risk \(D_{ii}(h_i - h_{b,i})^2\), so the perspective reformulation of Section 4.3 applies with a diagonal the factor model supplies. On the three-asset instance of Section 4.4 that diagonal closed 72 per cent of the big-M gap at \(\rho = 0.3\) and all of it at \(\rho = 0\), where a uniform diagonal closed 43 and 61 per cent. SCIP 8 generates the perspective cuts itself once the model exposes \(D_{ii} x_i^2\) with its indicator. For the commercial MIQP solvers the documentation read for this series describes no automatic perspective reformulation, so the modeller writes the rotated cone or supplies the cuts.K. Bestuzheva, A. Chmiela, B. Müller, F. Serrano, S. Vigerske and F. Wegscheider, "Global optimization of mixed-integer nonlinear programs with SCIP 8", Journal of Global Optimization 91 (2025), Section 2.6; K. Bestuzheva, A. Gleixner and S. Vigerske, "A computational study of perspective cuts", Mathematical Programming Computation 15 (2023). Whether Gurobi derives perspective cuts internally could not be verified from its documentation. The diagonal-split result is X. Zheng, X. Sun and D. Li, "Improving the performance of MIQP solvers for quadratic programs with cardinality and minimum threshold constraints: a semidefinite program approach", INFORMS Journal on Computing 26 (2014), and its generalization A. Frangioni, C. Gentile and J. Hungerford, "Decompositions of semidefinite matrices and the perspective reformulation of nonseparable quadratic programs", Mathematics of Operations Research 45 (2020).
The second figure draws the two indicator structures of the paragraph with illustrative numbers: above, a minimum trade size, which leaves a hole around zero; below, a fixed charge with a proportional part and its convex envelope on \([-l, u]\), the two lines from the origin to the ends of the graph. The sliders move the charge, the proportional part, the box and the minimum trade, and the cases narrow and widen the box, which shows what tightening the bounds does to the envelope.
The third fact concerns the one clause that is bilinear, and it says that no bilinear term is needed.
Proposition 9.3.2 (the wash-sale clause is a disjunction, and its hull is a triangle). Let \(b \in [0, B]\) and \(s \in [0, S]\). The set \(\{(b, s) : b\,s = 0\}\) is the union of the two segments \(\{b = 0\}\) and \(\{s = 0\}\), and its convex hull is the triangle \(\{b, s \ge 0,\ b/B + s/S \le 1\}\). The McCormick under-estimator of \(w = b\,s\) on the box, read at \(w = 0\), and the indicator formulation \(b \le B z\), \(s \le S(1 - z)\) with \(z \in [0, 1]\), projected onto \((b, s)\), both describe exactly that triangle. At \((B/2, S/2)\) all three relaxations report the point feasible, and a single branch on \(z\) resolves it.
Proof. The two segments meet at the origin and end at \((B, 0)\) and \((0, S)\), so their convex hull is the triangle with those three vertices, which is \(\{b, s \ge 0,\ b/B + s/S \le 1\}\). The McCormick planes under \(w = bs\) on \([0, B] \times [0, S]\) are \(w \ge 0\) and \(w \ge S b + B s - BS\). At \(w = 0\) the second reads \(S b + B s \le BS\), which is the triangle's hypotenuse. The indicator model gives \(b/B \le z\) and \(s/S \le 1 - z\), and adding them eliminates \(z\) to the same inequality. Conversely any point of the triangle takes \(z = b/B\). At \((B/2, S/2)\) the hypotenuse holds with equality while \(bs = BS/4 \ne 0\). ∎
(What the clause captures, and what the statute adds) No product variable is needed. The clause "do not buy and sell one name in one list" is a two-term disjunction, Section 4.2, and the direction binary that Proposition 9.3.1 already introduces is its indicator. The McCormick relaxation of the product and the hull of the disjunction coincide here because the two pieces are segments through the origin. The branching the search needs is a branch on the direction, which it would do anyway. What the clause does not capture is the rule itself. The statute's window extends 30 days after the sale as well as before, so a sale this month constrains a purchase next month and a purchase last month constrains a loss this month. The disallowed amount is a piecewise-linear function of the matched shares in the regulation's order, not of the modeller's choosing. The disallowed loss moves into the replacement basis, which links the periods. Moehle, Gindi, Boyd and Kochenderfer note that the liability function "is especially complicated when the asset has been traded within the past 30 days" and remains piecewise affine. Both Boyd-group papers keep the rule out of the model by the calendar. In preparing this series no published treatment of §1091 inside an exact optimization model was found, with its share matching and its basis adjustment. This is an open problem, listed in the research plan of Section 9.6.Moehle, Gindi, Boyd and Kochenderfer (2023), Section 2.2; Moehle, Kochenderfer, Boyd and Ang (2021), Section 6.2.
What the clause b s = 0 does not capture: the window crosses months
last month this month next month
+--------------+--------------+--------------+
x a sale at a loss
|<--- 30 days -x- 30 days --->|
^ ^
a purchase here, a purchase here,
last month, next month, is
constrains constrained by
the loss the sale
b s = 0 forbids a purchase and a sale of one name in one list,
one month at a time; the disallowed amount is a piecewise-linear
function of the matched shares, in the regulation's order, and
the disallowed loss moves into the replacement basis, which links
the periods
(The fourth fact: a gap bounded by the number of factors) The fourth fact is about the gap, and it is why a tree over directions is small in practice. Fix the directions and the problem is convex. Relax the kink of each \(L_i\) to its convex envelope instead and the problem is also convex, with a value that bounds the optimum from below. The two values differ by a duality gap, in the sense of Section 2.2, and for separable problems with few coupling constraints the gap is bounded independently of the number of assets. Theorem 5.4.8 (Udell and Boyd) bounds the duality gap of a separable problem \(\min \sum_i f_i(x_i)\) with \(\tilde m\) coupling constraints by the sum of the \(\tilde m\) largest nonconvexities \(\rho(f_i) = \sup_x \big(f_i(x) - \operatorname{vex} f_i(x)\big)\). Here \(\tilde m\) counts the equality rows together with the largest number of inequality rows that can be active at one point. Theorem 5.4.7 (Shapley–Folkman) is the geometric reason. With \(\hat z\) the value of the convexified problem, which equals the Lagrangian dual value \(d^\star\), and \(z^\star\) the true value, the inequality that the proposition below uses is
\[\hat z \;\le\; z^\star \;\le\; \hat z + \sum_{i=1}^{\min(\tilde m,\, n)} \rho_{(i)}, \qquad \rho_{(1)} \ge \rho_{(2)} \ge \cdots \ge \rho_{(n)}\]the \(\rho_{(i)}\) being the nonconvexities in decreasing order. The hypothesis matters. The nonconvexity \(\rho(f_i)\) is taken with \(f_i = +\infty\) off the block's domain \(S_i\), so the bound is vacuous when \(S_i\) is nonconvex and the convexified optimum leaves it. A block with integer coordinates, whole lots or whole shares, placed at a fractional point has \(\rho(f_i) = +\infty\). Udell and Boyd's setting is a convex \(S_i\) with a nonconvex \(f_i\), which is the tax problem's case once the lot variables are continuous. In a picture, the image of a separable feasible set under \(k + 1\) coupling rows is nearly convex, because a vertex of the convexified feasible set can lie off the original pieces in at most \(\tilde m\) blocks. The convexified problem's value is therefore close to the true one. Not every solution of the convexified problem is close. Udell and Boyd give an instance where the symmetric solution is off by a quantity growing with \(n\) while an extreme-point solution satisfies the bound with equality. That is why the theorem speaks of a particular solution, and why an ADMM run on the convexified problem (the alternating direction method of multipliers, Section 5.4) is used only as an initialization in the heuristic below.M. Udell and S. Boyd, "Bounding duality gap for separable problems with linear constraints", Computational Optimization and Applications 64 (2016), Theorems 1 and 2 and the display after Theorem 1, together with Examples 1 and 2 of Section 2 and the discussion of Section 7; Moehle, Gindi, Boyd and Kochenderfer (2023), Section 6. The lemma behind the theorem is R. M. Starr, "Quasi-equilibria in markets with non-convex preferences", Econometrica 37 (1969); the earlier bound \(\min(m + 1, n)\,\rho(f_1)\) is J.-P. Aubin and I. Ekeland, "Estimates of the duality gap in nonconvex optimization", Mathematics of Operations Research 1 (1976). The statement and proof are in Section 5.4.
Proposition 9.3.3 (the bound for the tax problem). Consider (9.2.1) without its last line, so that the sales are continuous and the directions are the only nonconvexity. Take a factor model, and reduce \(\mathcal U\) and \(\mathcal H\) to bounds on single assets. In the separable–affine form the variables are \(x = (h, c, y)\) with \(c\) the cash and \(y\) the factor exposures, the coupling constraints are the \(k\) exposure equalities \(y = C^{\top} X^{\top} h\) and the cash equality, and every other constraint is on a single block. Hence \(\tilde m = m = k + 1\), and with \(f_i\) the per-asset piece of the objective (forecast, specific risk, spread and tax),
\[0 \;\le\; z^\star - \hat z \;\le\; \sum_{i=1}^{\min(k+1,\, n)} \rho_{(i)}, \qquad \rho_{(i)} \ \text{the } i\text{-th largest of } \rho(f_i) = \sup_u \big(f_i(u) - \operatorname{vex} f_i(u)\big),\]where \(\hat z\) is the value of the relaxation with each \(f_i\) replaced by its envelope and \(z^\star\) the true optimal value, both in the minimization form of (9.2.1). Moehle and coauthors maximize the utility, which is \(-z\), so their basis-point numbers below are the same gaps read with the sign reversed. Each \(\rho(f_i)\) is at most \(\gamma_{\mathrm{tax}}\) times the size of the kink of \(L_i\) and shrinks as the curvature \(\gamma_{\mathrm{risk}} D_{ii}\) grows, because the envelope of a parabola plus a kink cuts only a sliver. The relaxation's value is also the Lagrangian dual value, so it is a certified bound for any heuristic.Moehle, Kochenderfer, Boyd and Ang (2021), Section 4.2: the gap "can be bounded in terms of \(k\), the number of factors in the risk model, and the distances between the separable functions \(f_i\) and their convex envelopes"; Moehle, Gindi, Boyd and Kochenderfer (2023), Sections 3.1 and 4 and Appendix A for the separable–affine form with \(m = k + 1\). The ADMM heuristic and its convex-envelope bound are the 2023 paper's, the Shapley–Folkman reading is the JOTA paper's Section 4, and the theorem is Udell and Boyd's; the earlier version of this post attributed all three to the JOTA paper.
Proof. Apply Theorem 5.4.8 to the separable–affine form. Its coupling matrix has \(k\) exposure rows and one cash row, all equalities, and the per-asset bounds are absorbed into the blocks, so \(\tilde m = k + 1\). ∎
Proposition 9.3.3: the separable-affine form, continuous sales
(9.2.1) without its last line, with a factor model, and with U
and H reduced to bounds on single assets
h_1 h_2 h_3 . . . h_n y c
+------+------+------+-----+------+---------+------+
k rows: | * | * | * | ... | * | * | |
y = C'X'h | | | | | | | |
+------+------+------+-----+------+---------+------+
1 row: | * | * | * | ... | * | | * |
the cash | | | | | | | |
+------+------+------+-----+------+---------+------+
f_1 f_2 f_3 . . . f_n
h_i: one block per asset, with its bounds and its piece f_i of
the objective (forecast, specific risk, spread and tax);
y: the k factor exposures; c: the cash
m~ = k + 1 coupling rows, all equalities, so
0 <= z* - z^ <= the sum of the min(k + 1, n) largest rho(f_i)
72 factors and 998 assets: 73 rows, the 73 largest rho(f_i)
(Two qualifications) Two qualifications go with the proposition. Sector bounds in \(\mathcal U\) or \(\mathcal H\) are coupling inequality rows, and each one that can be active at the optimum adds one to \(\tilde m\). With whole-lot or whole-share blocks the a priori bound is \(+\infty\) unless the convexified solution happens to be lot-integral. What survives in that case is the structural fact of the proof: at most \(\tilde m\) blocks sit outside their \(S_i\), and that fact is what the direction-and-lot tree of Section 9.5 branches on.
(The measured gap against the a priori count) With 72 factors and 998 assets the a priori bound sums the 73 largest nonconvexities, each a few basis points at most, and it is loose. The measured gaps are much smaller. On 692 generated instances with about 1,000 securities and 72 factors, the ADMM heuristic's utility differed from the certified bound \(d^\star\) by 0 to 10 basis points of account value. The mean was 0.6 and the standard deviation 1.1. The nonconvex problem took 251 milliseconds on average and the convexified one 152.Moehle, Gindi, Boyd and Kochenderfer (2023), Section 7: 692 instances; gaps \(p_{\mathrm{admm}} - d^\star\) of 0 to 10 basis points, mean 0.6, standard deviation 1.1; 251 ms (standard deviation 159) and 152 ms (standard deviation 67). The abstract rounds the sizes to "around 1000 securities and 100 risk factors". The convex-envelope bound says how far from optimal the heuristic can be on a given instance. The Shapley–Folkman lemma says why that bound is tight when the lots are many and the coupling constraints few. The worked example of Section 5.4 is this count with numbers: three fixed-charge blocks and one coupling row give a gap of \(0.5\) against the a priori bound \(1\) from Udell and Boyd's count and \(2\) from Aubin and Ekeland's.
The script below prints the three small computations of Sections 9.1 and 9.2: the two lots of Proposition 9.1.4, the wash-sale deferral, and the tracking error of dropping one of four names.
# Three small checks, for the examples of Sections 9.1 and 9.2.
#
# Least tax first against highest basis first on the two lots of
# Proposition 9.1.4, a wash-sale deferral, and the tracking error of
# dropping one of four names. numpy only.
import numpy as np
R_ST, R_LT = 0.408, 0.238
# Two lots of 100 shares, price $100, raise $10,000: A has basis 95,
# held two years; B has basis 97, held three months.
tax_A = 100 * (100 - 95) * R_LT
tax_B = 100 * (100 - 97) * R_ST
print(f"lot A: tax {tax_A:.2f} = {tax_A / 10_000:.2%} of proceeds; "
f"lot B: tax {tax_B:.2f} = {tax_B / 10_000:.3%}")
print(f"highest basis first sells B; "
f"least tax first sells A and saves {tax_B - tax_A:.2f}")
# A wash sale defers the loss: buy 100 at 100 (day 0), sell at 90
# (day 20), buy 100 at 92 (day 35).
loss = 100 * (100 - 90)
basis = 92 + loss / 100
print(f"\nloss {loss:.0f} realized on day 20; "
f"purchase on day 35 is inside the window:\n"
f" disallowed, replacement basis {basis:.0f}")
print(f" sold later at 110: gain {100 * (110 - basis):.0f} "
f"instead of {100 * (110 - 92):.0f};\n"
f" a purchase on day 51 leaves the loss allowed")
# Four equal-weight names, one factor with beta 1 each, specific
# volatilities 10, 10, 20, 30 percent.
spec = np.array([0.10, 0.10, 0.20, 0.30])
w = np.full(4, 0.25)
for drop in (3, 0, 2):
v = np.full(4, 1 / 3)
v[drop] = 0.0
# weights still sum to 1: factor exposure unchanged
d = v - w
te = np.sqrt((d ** 2 * spec ** 2).sum())
print(f"drop the {spec[drop]:.0%} name: "
f"deviations {np.round(d, 4)},\n"
f" tracking error {te:.1%}")
lot A: tax 119.00 = 1.19% of proceeds; lot B: tax 122.40 = 1.224%
highest basis first sells B; least tax first sells A and saves 3.40
loss 1000 realized on day 20; purchase on day 35 is inside the window:
disallowed, replacement basis 102
sold later at 110: gain 800 instead of 1800;
a purchase on day 51 leaves the loss allowed
drop the 30% name: deviations [ 0.0833 0.0833 0.0833 -0.25 ],
tracking error 7.8%
drop the 10% name: deviations [-0.25 0.0833 0.0833 0.0833],
tracking error 4.0%
drop the 20% name: deviations [ 0.0833 0.0833 -0.25 0.0833],
tracking error 5.7%
(What parallelizes in the real problem) Each computation is a handful of scalar operations. Nothing here needs to be parallel, and the point of printing them is that every number in the prose can be checked. The structure they illustrate is what parallelizes in the real problem. The per-asset pieces \(f_i\), their envelopes, their lot orders and their proximal maps (Definition 7.2.3), the one-dimensional minimizations \(\operatorname{prox}_{f_i}(v) = \arg\min_x \big(f_i(x) + \tfrac12 (x - v)^2\big)\) that the ADMM heuristic of Section 9.5 performs once per asset and per iteration, are independent across assets and across accounts. The only coupling is through \(k + 1\) rows.
Eight lots
The lots figure is the running example R6, and it is the smallest instance of (9.2.1) that shows the integrality of lots. One stock, eight lots, a price of 100 dollars today, and a sum of cash to raise. The question is which whole lots to sell so as to pay the least tax, or to harvest the largest loss, which is the same objective. The section reads the figure view by view, proves the formula for its gap (Proposition 9.4.1), states the two conventions the figure takes that the regulation does not, and ends with a script that recomputes every number quoted. The data are these.
| lot | shares | basis | days held | term | gain | tax | tax per dollar raised |
|---|---|---|---|---|---|---|---|
| 1 | 100 | 62 | 900 | LT | 3,800 | 904.40 | +0.0904 |
| 2 | 150 | 118 | 400 | LT | −2,700 | −642.60 | −0.0428 |
| 3 | 80 | 95 | 340 | ST | 400 | 163.20 | +0.0204 |
| 4 | 120 | 131 | 45 | ST | −3,720 | −1,517.76 | −0.1265 |
| 5 | 60 | 88 | 500 | LT | 720 | 171.36 | +0.0286 |
| 6 | 200 | 104 | 200 | ST | −800 | −326.40 | −0.0163 |
| 7 | 90 | 71 | 1,200 | LT | 2,610 | 621.18 | +0.0690 |
| 8 | 50 | 99 | 30 | ST | 50 | 20.40 | +0.0041 |
(What the figure draws, and its controls) Three lots are at a loss, lots 2, 4 and 6. Together they are worth 2,486.76 dollars of tax, and they raise 47,000 dollars between them. Every dollar raised beyond that is a gain realized, and the cheapest gains per dollar are lots 8, 3 and 5 in that order. The figure draws all 256 subsets of the eight lots as dots, with the cash raised on the horizontal axis and the tax due on the vertical axis. A vertical line marks the cash required, and the optimum is the lowest dot to the right of the line, in blue. Three rings mark the three other answers: least tax first in green, highest basis first in grey, and in orange the convex-envelope relaxation, which replaces each whole-lot constraint \(x_\ell \in \{0, 1\}\) by \(0 \le x_\ell \le 1\) and may sell part of a lot. Its side panel lists the lots with three dot columns showing which lots each of the three sales takes. The controls are these. The cash to raise runs from 5,000 to 85,000 dollars and the price today from 60 to 140. A calendar shift moves every holding period by up to 200 days either way. A switch declares a recent purchase of 100 shares, with a slider for how many days before today it happened, from 0 to 60. The two rates sit under the assumptions fold. Four case buttons jump to the views described below.
(The default view: a third of a lot) What to look for is the vertical distance between the blue dot and the orange ring. In the default view, raising 62,000 dollars, the optimum sells lots 2, 3, 4, 5, 6 and 8, raises 66,000 dollars and pays \(-2{,}132\) dollars, a net loss harvested. Least tax first, taking lots 4, 2, 6, 8, 3 and 5 in that order, and highest basis first both arrive at the same six lots, so the three marks sit on one point and share one label. The relaxation sells the three loss lots whole, then lots 8 and 3, then 2,000 of lot 5's 6,000 dollars, raising exactly 62,000 for \(-2{,}246\) dollars. The 114 dollars between them is the integrality of lots: the relaxation sells a third of a lot, and rounding it either way costs money. Of the 256 subsets, 34 raise enough.
The gap has a formula, and the formula is the one-dimensional case of everything in Section 4.6. To see the eight lots as an instance of (9.2.1), take one asset, no purchase (\(b = 0\)), drop the risk, spread and forecast terms, which have nothing to say about one name, and keep the tax term \(\sum_\ell T_\ell s_\ell\) with the whole-lot line \(s_\ell \in \{0, q_\ell p\}\); the cash row becomes "raise at least \(C\)", since the figure lets a sale overshoot. Writing \(x_\ell = s_\ell / (q_\ell p)\), so that \(x_\ell = 1\) sells the lot and \(0\) keeps it, the proceeds of lot \(\ell\) are \(p_\ell = q_\ell p\) and its tax is \(t_\ell = T_\ell q_\ell p\), the table's tax column, and the problem is the 0–1 program of the proposition. Its LP relaxation, \(0 \le x_\ell \le 1\), is the convex-envelope relaxation the figure's orange ring marks: a relaxation in the sense of Definition 1.1.3, with \(f_R = f\) and the feasible set enlarged from the \(256\) corners of the cube to the cube itself.
Proposition 9.4.1 (the LP relaxation of whole-lot selection). Let lot \(\ell\) have proceeds \(p_\ell > 0\) and tax \(t_\ell\), negative for a loss, and consider \(\min \sum_\ell t_\ell x_\ell\) subject to \(\sum_\ell p_\ell x_\ell \ge C\) and \(x \in \{0, 1\}^L\). Its LP relaxation \(0 \le x \le 1\) has an optimal solution with \(x_\ell = 1\) for every lot with \(t_\ell \le 0\), the gain lots taken whole in increasing order of \(t_\ell / p_\ell\), and at most one fractional lot \(f\). Rounding \(x_f\) up to 1 gives a feasible whole-lot sale, so
\[z_{\mathrm{LP}} \;\le\; z^\star \;\le\; z_{\mathrm{LP}} + (1 - x_f)\, t_f \;\le\; z_{\mathrm{LP}} + \max_\ell t_\ell .\]Proof sketch. A loss lot lowers the objective and helps the constraint, so it is taken whole. Among gain lots the problem is a fractional covering knapsack, and the ratio rule is optimal by the exchange argument of Proposition 9.2.2. A dollar moved from a lot with a larger ratio to one with a smaller ratio and room lowers the objective at equal proceeds. The rounded solution is feasible because it raises more. ∎
(The gap on the figure's data, and whole shares) On the data of the figure the fractional lot is lot 5 with \(x_5 = 1/3\), so the proposition bounds the gap by \((1 - 1/3) \times 171.36 = 114.24\) dollars. The rounded-up solution happens to be optimal here, and the bound is attained with equality. The figure reports the gap as the optimum minus the relaxation rounded to the dollar, so it can differ by a dollar from the difference of the two rounded stats. The proposition also says what integrality costs in one name. If whole shares may be sold from any lot, every share sells at the same price, so the problem is a selection of the cheapest items of equal weight. The share-level optimum sells every loss share and then the cheapest gain shares until \(\lceil C / p \rceil\) shares are sold, and its value equals \(z_{\mathrm{LP}}\) whenever \(C/p\) is an integer. Here it sells 20 shares of lot 5 for exactly the relaxation's \(-2{,}246.04\). In one asset the integrality that matters is whole lots, not whole shares. Across many assets the coupling is through risk and not through cash alone, and Theorem 5.4.8 takes over: the risk term ties every asset's trade to every other's through the \(k\) factor exposures, so no single-name sort settles the amounts, and what bounds the gap is no longer one fractional lot but the count of Proposition 9.3.3, the \(k + 1\) largest nonconvexities.
| sale | of lot 5 (60 shares, 6,000 dollars) | cash raised | tax |
|---|---|---|---|
| relaxation | \(x_5 = 1/3\): 2,000 of its 6,000 dollars | 62,000 | −2,246.04 |
| whole shares | 20 of its 60 shares | 62,000 | −2,246.04 |
| whole lots, the optimum | all of it, \(x_5 = 1\) | 66,000 | −2,131.80 |
(The other views: zero gap, the cliff, the wash sale) The figure's other views are each one fact about the rules. Raise 30,000 dollars and the three loss lots alone raise 47,000 for \(-2{,}487\) dollars. The relaxation coincides with the optimum, the gap is zero, and 198 of the 256 subsets raise enough. Move the calendar 30 days later and lot 3 crosses from short-term to long-term. Its tax falls from 163.20 to 95.20 dollars, and the optimum improves by exactly 68.00 dollars with the same six lots, to \(-2{,}200\) against a relaxation of \(-2{,}314\) and the same 114-dollar gap. The holding-period cliff is fixed by the calendar and not by a parameter of the model, and the slope of the tax jumps on that day. Declare a purchase of 100 shares 12 days before today and the optimum is the same six lots, but the loss on 100 shares of lot 2, 1,800 dollars, is disallowed. That raises the tax by 428.40 to \(-1{,}703\) dollars. The relaxation is \(-1{,}818\), the gap is 114 again, and the disallowed loss is deferred into the basis of the purchased shares, which becomes 100 + 1,800/100 = 118 dollars a share. Move the purchase slider to 31 days or more and every number returns to the default, because the purchase is outside the window.
(Two conventions of the figure's own) Two of the figure's conventions are its own, and the prose has to say so. First, the regulation matches the acquired shares against the loss shares sold in the order of disposition, and for a same-day sale in the order of original acquisition. The figure matches in the order the lots are sold and takes that order to be the table order, lot 1 first. At a price of 100 dollars the two orders agree, because lot 2 is both the first loss lot in the table and the earliest acquired of the three loss lots sold (400 days against 200 and 45). At a price of 80 dollars with a purchase 20 days before today they disagree. Six lots are then at a loss, and the earliest acquired of them is lot 5, at 500 days. The regulation's order matches 60 shares to lot 5 and 40 to lot 2, disallows 2,000 dollars of loss and gives an optimum of \(-5{,}706\). The figure's table order matches all 100 shares to lot 2, disallows 3,800 dollars and gives \(-5{,}278\) against a relaxation of \(-5{,}599\), a gap of 321. Second, the figure models a purchase in the 30 days before the sale only. The statute's window runs 30 days after it as well. Both conventions are stated in the caption's last sentence and here, and neither changes the lesson of the figure, which is about the integrality of lots.
| the regulation (§1.1091-1(b)), where the order of same-day loss sales cannot be determined: original acquisition, earliest first | the figure: the lots in table order, lot 1 first | |
|---|---|---|
| the 100 purchased shares matched to | 60 of lot 5 (held 500 days), then 40 of lot 2 (held 400 days) | 100 of lot 2's 150 shares |
| loss disallowed | 60 × (88 − 80) + 40 × (118 − 80) = 2,000 | 100 × (118 − 80) = 3,800 |
| optimum | −5,706.22 | −5,277.82 |
| relaxation | −6,027.52 | −5,599.12 |
| gap | 321.30 | 321.30 |
| replacement basis | 100.00 | 118.00 |
(Where the rules of thumb fail) Another view shows the rules of thumb failing. Raise 55,000 dollars and the optimum sells lots 2, 3, 4 and 6, raising exactly 55,000 for \(-2{,}324\) dollars. Both rules take lot 8 before lot 3, then need lot 3 as well, raise 60,000 and pay \(-2{,}303\). The optimum skips the cheapest gain lot because the second-cheapest fits the cash exactly. The relaxation there sells three eighths of lot 3 for \(-2{,}405\), a gap of 82 dollars. And when the cash exceeds what the eight lots can raise, at a price of 80 dollars and 85,000 to raise, the lots raise at most 68,000. The optimum and the relaxation are then reported as dashes, and both rules stop short of the cash at \(-6{,}182\).
The script below recomputes every number quoted above under the figure's conventions. It enumerates the 256 subsets, computes the relaxation of Proposition 9.4.1 in closed form and the two rules, and applies the wash-sale penalty with table-order matching to every sale, to both rules and to the relaxation alike. For the one view in which the two matching orders differ it also prints the regulation's order.
# Eight lots of one stock and a sum of cash to raise.
#
# As the lots figure computes it: the whole-lot optimum by enumeration
# of the 256 subsets, the convex-envelope (LP) relaxation, the two rules
# of thumb, and the wash-sale rule under the figure's conventions, with
# the regulation's matching order shown for comparison. numpy only;
# deterministic.
import numpy as np
# The lots in table order: shares, basis per share, days held today.
SH = np.array([100, 150, 80, 120, 60, 200, 90, 50])
BAS = np.array([ 62, 118, 95, 131, 88, 104, 71, 99.0])
DAYS = np.array([900, 400, 340, 45, 500, 200, 1200, 30])
# The rates, and a purchase of W shares.
R_ST, R_LT, W = 0.408, 0.238, 100
N = len(SH)
# The figure matches the lots in table order; the regulation matches
# the earliest acquired first.
ORDER = {'table': list(range(N)),
'acquired': sorted(range(N), key=lambda l: -DAYS[l])}
def lots(price, shift=0):
"""Rate, gain, tax and proceeds of every lot at a price."""
# long-term after one year
rate = np.where(DAYS + shift > 365, R_LT, R_ST)
gain = SH * (price - BAS)
return dict(rate=rate, gain=gain, tax=gain * rate, proc=SH * price)
def wash(L, x, price, b, order):
"""Extra tax when W shares were bought b <= 30 days before today.
The loss on at most W of the loss shares sold is disallowed, the
sold loss lots are matched in the given order, and the disallowed
loss D goes into the basis of the W new shares.
"""
if b is None or b > 30:
return 0.0, 0.0
left, extra, D = W, 0.0, 0.0
for l in ORDER[order]:
if left and x[l] > 0 and L['gain'][l] < 0:
k = min(left, SH[l])
left -= k
D += k * (BAS[l] - price)
extra += k * (BAS[l] - price) * L['rate'][l]
return extra, D
def sale(L, x, price, b, order):
"""The tax, wash-sale penalty included, and the proceeds of x."""
return L['tax'] @ x + wash(L, x, price, b, order)[0], L['proc'] @ x
def optimum(L, C, price, b, order):
"""The best whole-lot sale raising C, by enumeration.
Returns (best, feas): best = (tax, proceeds, x), or None when no
subset raises C, and feas the number of subsets that do.
"""
best, feas = None, 0
for m in range(1 << N):
x = np.array([(m >> l) & 1 for l in range(N)], float)
t, p = sale(L, x, price, b, order)
if p >= C - 1e-9:
feas += 1
# a lower tax, or an equal tax that raises less
if best is None or t < best[0] - 1e-9:
best = (t, p, x)
elif abs(t - best[0]) < 1e-9 and p < best[1]:
best = (t, p, x)
return best, feas
def rule(L, lot_order, C, price, b, order):
"""Whole lots in a fixed order until the cash is raised."""
x, p = np.zeros(N), 0.0
for l in lot_order:
if p >= C - 1e-9:
break
x[l] = 1.0
p += L['proc'][l]
taken = [l + 1 for l in lot_order if x[l] > 0]
return sale(L, x, price, b, order)[0], taken, p >= C - 1e-9
def relaxation(L, C, price, b, order):
"""0 <= x_l <= 1: loss lots whole, then gain lots by tax per dollar
raised, the last in part."""
t, p = L['tax'], L['proc']
x = np.zeros(N)
x[t <= 0] = 1.0
raised = p @ x
for l in sorted(np.where(t > 0)[0], key=lambda l: t[l] / p[l]):
if raised >= C - 1e-9:
break
x[l] = min(1.0, (C - raised) / p[l])
raised += x[l] * p[l]
if raised < C - 1e-9:
return None, x
return sale(L, x, price, b, order)[0], x
def view(title, C=62_000.0, price=100.0, shift=0, b=None, order='table'):
"""One view of the figure: the optimum, the relaxation, the rules."""
L = lots(price, shift)
best, feas = optimum(L, C, price, b, order)
tr, xr = relaxation(L, C, price, b, order)
by_basis = sorted(range(N), key=lambda l: -BAS[l])
by_tax = sorted(range(N), key=lambda l: L['tax'][l] / L['proc'][l])
hifo = rule(L, by_basis, C, price, b, order)
ltfo = rule(L, by_tax, C, price, b, order)
in_window = b is not None and b <= 30
matched = f", matched in {order} order" if in_window else ""
print(f"\n{title}{matched}")
if best is None:
print(f" no subset raises the cash: the lots raise at most "
f"${L['proc'].sum():,.0f};\n"
f" optimum, relaxation and gap are dashes")
else:
t, p, x = best
frac = [(l + 1, round(float(xr[l]), 4))
for l in range(N) if 0 < xr[l] < 1]
sold = [l + 1 for l in range(N) if x[l]]
print(f" optimum sells lots {sold}, raises ${p:,.0f},\n"
f" tax {t:,.2f}; {feas} of 256 subsets raise enough")
print(f" relaxation {tr:,.2f}, fractional lot {frac}, "
f"gap {t - tr:,.2f}")
if in_window:
extra, D = wash(L, x, price, b, order)
print(f" wash sale: ${D:,.0f} of loss disallowed, "
f"tax up by {extra:,.2f},\n"
f" replacement basis {price + D / W:.2f}")
for name, (t, taken, ok) in (("highest basis first", hifo),
("least tax first", ltfo)):
print(f" {name} {t:,.2f} (lots {taken})"
+ ("" if ok else ",\n short of the cash"))
L0 = lots(100.0)
print("lot shares basis days rate gain tax tax per $ raised")
for l in range(N):
print(f"{l + 1:3d} {SH[l]:6d} {BAS[l]:5.0f} {DAYS[l]:5d} "
f"{L0['rate'][l]:.3f} {L0['gain'][l]:6.0f} "
f"{L0['tax'][l]:9.2f} {L0['tax'][l] / L0['proc'][l]:+.5f}")
view("raise $62,000")
view("raise $30,000", C=30_000.0)
view("$62,000, thirty days later", shift=30)
view("$62,000 after buying 100 shares 12 days ago", b=12)
view("raise $55,000", C=55_000.0)
view("price $80 after buying 100 shares 20 days ago", price=80.0, b=20)
view("price $80 after buying 100 shares 20 days ago", price=80.0, b=20,
order='acquired')
view("price $80, raise $85,000", C=85_000.0, price=80.0)
lot shares basis days rate gain tax tax per $ raised
1 100 62 900 0.238 3800 904.40 +0.09044
2 150 118 400 0.238 -2700 -642.60 -0.04284
3 80 95 340 0.408 400 163.20 +0.02040
4 120 131 45 0.408 -3720 -1517.76 -0.12648
5 60 88 500 0.238 720 171.36 +0.02856
6 200 104 200 0.408 -800 -326.40 -0.01632
7 90 71 1200 0.238 2610 621.18 +0.06902
8 50 99 30 0.408 50 20.40 +0.00408
raise $62,000
optimum sells lots [2, 3, 4, 5, 6, 8], raises $66,000,
tax -2,131.80; 34 of 256 subsets raise enough
relaxation -2,246.04, fractional lot [(5, 0.3333)], gap 114.24
highest basis first -2,131.80 (lots [4, 2, 6, 8, 3, 5])
least tax first -2,131.80 (lots [4, 2, 6, 8, 3, 5])
raise $30,000
optimum sells lots [2, 4, 6], raises $47,000,
tax -2,486.76; 198 of 256 subsets raise enough
relaxation -2,486.76, fractional lot [], gap 0.00
highest basis first -2,486.76 (lots [4, 2, 6])
least tax first -2,486.76 (lots [4, 2, 6])
$62,000, thirty days later
optimum sells lots [2, 3, 4, 5, 6, 8], raises $66,000,
tax -2,199.80; 34 of 256 subsets raise enough
relaxation -2,314.04, fractional lot [(5, 0.3333)], gap 114.24
highest basis first -2,199.80 (lots [4, 2, 6, 8, 3, 5])
least tax first -2,199.80 (lots [4, 2, 6, 8, 3, 5])
$62,000 after buying 100 shares 12 days ago, matched in table order
optimum sells lots [2, 3, 4, 5, 6, 8], raises $66,000,
tax -1,703.40; 34 of 256 subsets raise enough
relaxation -1,817.64, fractional lot [(5, 0.3333)], gap 114.24
wash sale: $1,800 of loss disallowed, tax up by 428.40,
replacement basis 118.00
highest basis first -1,703.40 (lots [4, 2, 6, 8, 3, 5])
least tax first -1,703.40 (lots [4, 2, 6, 8, 3, 5])
raise $55,000
optimum sells lots [2, 3, 4, 6], raises $55,000,
tax -2,323.56; 63 of 256 subsets raise enough
relaxation -2,405.16, fractional lot [(3, 0.375)], gap 81.60
highest basis first -2,303.16 (lots [4, 2, 6, 8, 3])
least tax first -2,303.16 (lots [4, 2, 6, 8, 3])
price $80 after buying 100 shares 20 days ago, matched in table order
optimum sells lots [1, 2, 3, 4, 5, 6, 7, 8], raises $68,000,
tax -5,277.82; 3 of 256 subsets raise enough
relaxation -5,599.12, fractional lot [(1, 0.25)], gap 321.30
wash sale: $3,800 of loss disallowed, tax up by 904.40,
replacement basis 118.00
highest basis first -5,277.82 (lots [4, 2, 6, 8, 3, 5, 7, 1])
least tax first -5,277.82 (lots [4, 6, 2, 8, 3, 5, 7, 1])
price $80 after buying 100 shares 20 days ago, matched in acquired order
optimum sells lots [1, 2, 3, 4, 5, 6, 7, 8], raises $68,000,
tax -5,706.22; 3 of 256 subsets raise enough
relaxation -6,027.52, fractional lot [(1, 0.25)], gap 321.30
wash sale: $2,000 of loss disallowed, tax up by 476.00,
replacement basis 100.00
highest basis first -5,706.22 (lots [4, 2, 6, 8, 3, 5, 7, 1])
least tax first -5,706.22 (lots [4, 6, 2, 8, 3, 5, 7, 1])
price $80, raise $85,000
no subset raises the cash: the lots raise at most $68,000;
optimum, relaxation and gap are dashes
highest basis first -6,182.22 (lots [4, 2, 6, 8, 3, 5, 7, 1]),
short of the cash
least tax first -6,182.22 (lots [4, 6, 2, 8, 3, 5, 7, 1]),
short of the cash
(What the enumeration shows, and what it cannot) The enumeration costs 256 evaluations of a sum, and it is embarrassingly parallel: each subset is independent, which is the structure the post that follows this series exploits across accounts rather than within one name. The relaxation and the rules are each one sort. What the script cannot do is scale. With hundreds of lots in a thousand names, \(2^L\) subsets are out of reach. That is why the search of Section 3 and the relaxation of Section 9.3 exist, and why the enumeration here is a check rather than a method.
The plan, in the vocabulary of this series
The plan for the solver, in plain words, is this: fix the directions by the relaxation's sign, sort the lots least tax first, round, polish with a local search over directions, branch on directions and lot boundaries, batch the relaxations on a GPU, share nodes through a pool, and stop at a gap of a few dollars. Every step of that plan has a name in Sections 2 to 7, a paper, and a worked example in this series, and the table gives the mapping. Each name in its second column is defined where its third column points; the paragraph after the table gives the one sentence each needs here, and the two figures and the sizes table that follow it put numbers on the two rows that are easiest to misjudge, symmetry and the stopping rule.
| step in the plan | named machinery | section | the small example |
|---|---|---|---|
| guess every asset's direction from the relaxation's sign | Undercover: fix a vertex cover of the nonlinear interaction graph so that the rest is convex | 3.2 | the row \(b_i \cdot S_i = 0\) is one edge per asset; a cover is one variable per asset, and fixing it is fixing the direction |
| solve the direction-fixed problem | sub-NLP: fix the integers, solve the convex remainder | 3.2, 3.6 | Moehle et al.: the second of two convex solves, a factor-model QP (Proposition 4.4.7) |
| round the partial lot | RENS: fix what the relaxation leaves integral, search the rest | 3.2 | relaxation \((2.4, 1.7, 3.0)\): \(x_3\) fixed at 3, the other two in \(\{2, 3\}\) and \(\{1, 2\}\): four candidates |
| flip one direction | local branching with \(k = 1\) | 3.2 | incumbent \((1, 0, 1, 0)\): the point itself and its four single flips are the neighbourhood |
| polish | ADMM on the separable-affine form | 5.4 | Moehle, Gindi, Boyd and Kochenderfer: 251 ms mean at ~1,000 names and 72 factors |
| treat identical lots once | symmetry handling: orbital branching, or a count variable in place of indicators | 2.5 | four identical lots, sell two: \(C(4, 2) = 6\) equivalent sales; ten lots, sell five: 252; with a count \(n \in \{0, \dots, 4\}\): one |
| probe a direction | probing: fix, propagate, detect infeasibility | 2.5 | fix \(z = 0\), propagate, find the cash constraint violated, so \(z = 1\) at the root |
| fix a direction by its reduced cost | reduced-cost fixing | 2.5, 2.6 | gap 5 between bound and incumbent: a direction at its bound with reduced cost 6 is fixed; one with reduced cost 2 and range 10 is cut to 2 |
| learn from a pruned node | conflict analysis and dual proofs | 3.6 | a pruned direction pattern becomes a clause over directions, valid for the whole tree |
| bound a frontier of nodes at once | batched first-order LP/QP with the safe bound | 7.3, 7.4 | 256 node relaxations: 228 of 230 prunable nodes pruned after 10 iterations |
| share nodes, broadcast incumbents | work-stealing pool; deterministic logical clock | 6.2, 6.3 | the parallel figure: 7.86x on 8 workers, 42.63x on 64 with incumbents shared, 26.51x without |
| stop at a few dollars | absolute gap tolerance; directed rounding on the bound | 8.4, 7.3 | \(10^{-4}\) relative on $720,000 is $72; in Section 9.4 the lots differ by $114 from their relaxation, and at $55,000 of cash the rules of thumb miss the optimum by $20.40 |
(The rows that need a sentence) A few of the rows need a sentence each. Undercover is Berthold and Gleixner's heuristic for MINLP. It builds the graph whose vertices are the variables and whose edges join two variables that appear together in a nonlinear term. It chooses a minimum vertex cover, fixes the covered variables at their relaxed values, and solves the sub-MIP that remains, which is linear.T. Berthold and A. M. Gleixner, "Undercover: a primal MINLP heuristic exploring a largest sub-MIP", Mathematical Programming 144 (2014). The worked example of Section 3.2: constraints \(x_1 x_2 \le 1\), \(x_2 x_3 \le 2\), \(x_3^2 + x_4 \le 3\) have edges \(x_1\)–\(x_2\), \(x_2\)–\(x_3\) and a loop at \(x_3\), and the smallest cover is \(\{x_2, x_3\}\) or \(\{x_1, x_3\}\). In the tax problem the only nonlinear row is \(b_i \cdot \sum_{\ell \in i} s_\ell = 0\), one edge per asset between the purchase and the sales, so a cover is one variable per asset and fixing it is fixing the direction. What remains is the convex program of Proposition 9.3.1, which is the sub-NLP of the heuristics catalogue, solved by the two-stage method's second step. RENS is Berthold's "optimal rounding": fix every integer variable the relaxation already has integral and search the rest. A relaxation whose lot variables are integral except one leaves a sub-problem with two candidates for that lot.T. Berthold, "RENS: the optimal rounding", Mathematical Programming Computation 6 (2014); the four-candidate example is from Section 3.2. Local branching with \(k = 1\) is the neighbourhood of single flips, which is what "a local search over directions" means in solver terms, and RINS fixes the directions on which the incumbent and the relaxation agree.M. Fischetti and A. Lodi, "Local branching", Mathematical Programming 98 (2003); E. Danna, E. Rothberg and C. Le Pape, "Exploring relaxation induced neighborhoods to improve MIP solutions", Mathematical Programming 102 (2005). The ADMM polish is Moehle, Gindi, Boyd and Kochenderfer's heuristic on the separable–affine form. Its only operation on the nonconvex pieces is their proximal map (Definition 7.2.3), which is closed-form for a piecewise quadratic, and its coupled step is one solve with a cached factorization of a \((k + 1) \times (k + 1)\) system. It is initialized at the convexified problem's solution, which also supplies the bound \(d^\star\).Moehle, Gindi, Boyd and Kochenderfer (2023), Sections 5 and 6; the proximal maps of fixed-charge and piecewise-quadratic pieces are also in R. Takapoui, N. Moehle, S. Boyd and A. Bemporad, "A simple effective heuristic for embedded mixed-integer quadratic programming", International Journal of Control 93 (2020), and S. Diamond, R. Takapoui and S. Boyd, "A general system for heuristic minimization of convex functions over non-convex sets", Optimization Methods and Software 33 (2018). Identical lots are a symmetry of the model. A solver that does not see it explores \(\binom{4}{2} = 6\) equivalent ways of selling two of four identical lots, or 252 ways of selling five of ten. Orbital branching or an integer count in place of the indicators removes the symmetry at the formulation.F. Margot, "Symmetry in integer linear programming", in 50 Years of Integer Programming 1958–2008 (Springer, 2010); J. Ostrowski, J. Linderoth, F. Rossi and S. Smriglio, "Orbital branching", Mathematical Programming 126 (2011). Probing and reduced-cost fixing are the presolve devices of Sections 2.5 and 2.6, and conflict analysis turns a pruned node into a clause the rest of the tree can use.M. W. P. Savelsbergh, "Preprocessing and probing techniques for mixed integer programming problems", ORSA Journal on Computing 6 (1994); H. Crowder, E. L. Johnson and M. Padberg, "Solving large-scale zero-one linear programming problems", Operations Research 31 (1983); T. Achterberg, "Conflict analysis in mixed integer programming", Discrete Optimization 4 (2007); J. Witzig, T. Berthold and S. Heinz, "Computational aspects of infeasibility analysis in mixed integer programming", Mathematical Programming Computation 13 (2021). Whether a conflict clause learned in one account transfers to another that holds the same names at the same prices is a question and not a result: the lot rates are shared, the cash constraint and the holdings are not.
The sizes the plan has to meet are those the literature reports.
| quantity | value | source |
|---|---|---|
| names in the universe | about 500 to 3,200 (S&P 500, Russell 1000, Wilshire 5000); Moehle et al.: 998 | Bertsimas and Cory-Wright 2022; Moehle et al. 2021 |
| risk factors | 72 (a commercial risk model) | Moehle et al. 2021, Section 6 |
| lots | share-level lots in 998 names (the papers); 8 whole lots in one name (this post's figure) | Moehle et al. 2021; this post |
| instances in the published tests | 744 monthly instances from 12 six-year backtests; 692 generated instances | Moehle et al. 2021, Table 1; Moehle et al. 2023, Section 7 |
| exact MIQP (CPLEX 12.9) | 565 of 744 solved within 300 s | Moehle et al. 2021, Section 6 |
| two convex solves | under a second for several hundred assets and several dozen factors; certified optimal on 678 of 744 to the solver tolerance of about 0.05 bp | Moehle et al. 2021, Sections 6 and 7 |
| ADMM heuristic | 251 ms mean (nonconvex), 152 ms (convexified) | Moehle et al. 2023, Section 7 |
| accounts | "possibly over hundreds of thousands of individualized accounts", in backtesting and Monte Carlo simulation | Moehle et al. 2021, Section 7 |
| precision | dollars; the tax itself in cents | Section 8.4 |
Where this is used
What the solvers do with such a model today is the convex MIQP of Proposition 9.3.1. CPLEX, Gurobi, Xpress and MOSEK solve it by branch and bound over quadratic or conic relaxations, and Moehle and coauthors used CPLEX 12.9 for both the exact solve and the two convex stages. SCIP strengthens the indicator pieces by the perspective on its own. BARON, Couenne, ANTIGONE and the other global solvers of Section 5.3 are not the natural tool for a convex MIQP with a few hundred binaries. They become relevant only when the wash-sale coupling or an impact cost makes the problem nonconvex. NVIDIA's cuOpt offers, as of release 26.08, a GPU QP solver and convex quadratic, second-order-cone and rotated-cone constraints in its barrier method, and no mixed-integer quadratic problem. What it offers the plan is a GPU solver for the batched convex relaxations, with the rotated cones of the perspective now expressible.Moehle, Kochenderfer, Boyd and Ang (2021), Section 6 (CPLEX 12.9; MOSEK listed among the mixed-integer convex solvers); NVIDIA cuOpt release notes, entries 25.12 (QP, beta), 26.02 (QP generally available), 26.06 (convex quadratic, SOC and rotated SOC constraints in the barrier solver; semicontinuous variables) and 26.08 (the latest entry, with no quadratic item), read 5 October 2026.
What parallelizes
The per-asset pieces \(f_i\), their envelopes, their lot orders and their proximal maps are independent across assets and across accounts, and the only coupling is through the \(k + 1\) rows of Section 9.3. A frontier of direction-fixed quadratic programs shares the \(n \times k\) exposure matrix, so a batch of them is one batched matrix product, an elementwise proximal kernel and a batched \((k + 1) \times (k + 1)\) solve, the shape Section 7.6 gave the portfolio QP on a device. The enumeration within one name and the accounts across a book are independent work. The tree over directions is the irregular part, and the frontier batch of Section 6.4 is what handles it.
A frontier batch of direction-fixed QPs on a device
shared by every node: the n x k exposure matrix, one copy
node 1 node 2 node 3 . . . node B
+------+ +------+ +------+ +------+
per-asset | f_1 | | f_1 | | f_1 | | f_1 |
pieces, | f_2 | | f_2 | | f_2 | | f_2 |
independent | : | | : | | : | | : |
| f_n | | f_n | | f_n | | f_n |
+------+ +------+ +------+ +------+
coupling [k + 1] [k + 1] [k + 1] [k + 1]
rows
one batched matrix product with the shared exposures, one
elementwise proximal kernel over every piece of every node, one
batched (k + 1) x (k + 1) solve
The research plan
The post that follows this series builds the solver, and its plan is now the agenda of Section 7.8 specialized to one problem. The specialization is what makes the problem a good first target. The relaxations are convex quadratic programs with a shared factor model, and the nonconvexities are separable and univariate. The integers are a few hundred directions and lot boundaries. The duality gap is bounded by Proposition 9.3.3 and is zero on most instances, and the accounts are independent. Ten items follow, each with what is known, the first experiment and the risk, in the form of Section 7.8.
The first is the one that decides the rest: batched direction-fixed QPs with safe bounds (agenda items 1 and 6). A frontier of \(B\) open nodes of the direction tree is \(B\) convex quadratic programs that differ only in sign constraints and bounds and share the \(n \times k\) exposure matrix. One batched first-order run, ADMM (Section 5.4) or a restarted PDHG (the primal–dual hybrid gradient method of Section 7.2), advances all of them at once: the exposure products are a batched matrix multiplication, the proximal steps an elementwise kernel, and the \((k + 1) \times (k + 1)\) Schur systems a batched small solve. The bound is made safe by the device of Section 7.3 in its Lagrangian form. The dual function \(q(\lambda)\) evaluated at the returned multipliers is a valid lower bound for any \(\lambda\), and it costs one pass over the separable pieces. The first experiment takes Moehle and coauthors' instance sizes and generates a frontier of a few hundred direction patterns. For each node it records the iteration at which the safe bound first crosses the incumbent and the iteration at which it comes within a dollar of the exact QP value. The risk is the one Section 8.2 named: the nodes that matter are the ones within the gap, and those need near-exact solves.
The first item: one batched first-order run over B open nodes
B direction-fixed QPs that differ only in sign constraints and
bounds, and share the n x k exposure matrix
+--> one iteration of ADMM or a restarted PDHG, all B at once:
| exposure products a batched matrix product
| proximal steps an elementwise kernel
| (k + 1) x (k + 1) Schur a batched small solve
| systems
| |
| v
| the dual function q(lambda) at the multipliers: one pass
| over the separable pieces, a valid lower bound for any
| lambda, the safe bound
| |
+------------------+
recorded for each node: the iteration at which the safe bound
first crosses the incumbent, and the iteration at which it comes
within a dollar of the exact QP value
The second is frontier batching and its inflation (agenda item 4). The direction tree has at most \(2^{\lvert I_- \rvert}\) leaves and in practice few are visited, so the frontier is small. The batch must then be filled by processing many accounts at once rather than many nodes of one account. The first experiment is the batch figure of Section 6.4 run on a thousand accounts with one node each, then on one hard account with many nodes, measuring nodes wasted to incumbent lag as a function of the batch size. The risk is that heterogeneous accounts pad badly, which is the lane-efficiency question of Section 6.4.
The second item: two ways to fill one batch of B lanes
a thousand accounts, one node each
lane 1 2 3 . . . B
[account 1] [account 2] [account 3] . . . [account B]
one hard account, many nodes of its tree
lane 1 2 3 . . . B
[ node 1 ] [ node 2 ] [ node 3 ] . . . [ node B ]
measured: nodes wasted to incumbent lag, against the batch size;
the risk: heterogeneous accounts pad badly
The third is the primal side on the device (agenda item 5): the ADMM polish of Moehle, Gindi, Boyd and Kochenderfer batched across accounts, and a Feasibility-Jump-style local search over directions (Section 3.2) with the restricted QP as the move evaluation. The first experiment is to reproduce the 251-millisecond ADMM solve for a thousand accounts in one kernel launch. The risk is that one-variable jumps over directions are weak moves when the directions are coupled through the cash constraint, and a line search or a pairwise flip may be needed.
The fourth is reduced precision for the iterations and full precision for the bound (agenda item 9). cuOpt runs PDLP in single and mixed precision since release 26.04, and the stopping rule of a few dollars argues against single precision anywhere near the bound. The first experiment evaluates the safe bound in double with directed rounding on single-precision iterates and measures the bound lost. The risk is that the loss exceeds the dollars the stopping rule allows.
The fifth is determinism (agenda item 8). A production tax engine must give the same trade list twice. Section 8.3 gave the recipe: fixed-schedule reductions, directed rounding and a fixed batch schedule with round-boundary incumbents. The first experiment is the opportunistic variant against the deterministic one on the same accounts, ten runs each, reporting time, idle lanes, node counts and whether the two agree. cuOpt exposes the switch for its MILP solver and publishes no number, and Xpress's 2 to 9 per cent is the CPU reference. The risk is small in arithmetic and real in design, since a deterministic incumbent exchange across heuristic threads needs a synchronous pool, which brings back the incumbent lag.
The sixth is exactness to the cent (Section 8.4, and agenda item 13). The tax term is linear with integer coefficients in cents and can be computed exactly in integer arithmetic. The risk term cannot. The first experiment is a certificate format for the direction tree in which every node bound is a safe bound in double precision and every incumbent is checked in integer cents. The risk is the bookkeeping, not the mathematics.
The seventh is the wash-sale rule inside the model (Section 9.3). Trading more often than monthly, or coordinating several accounts of one taxpayer, puts the disjunction of Proposition 9.3.2 and the regulation's matching order into the problem. The deferred loss is then a piecewise-linear function of the matched shares, and the replacement basis links the periods. The first experiment is a two-period model with the window spanning the boundary on the eight lots of Section 9.4, solved by enumeration, against the one-period model. The risk is representability, since the matching order is a lexicographic rule and Section 4.10 says not every rule is a mixed-integer convex set.
The eighth is instances and a benchmark (agenda item 12). No public instance library exists for tax-lot problems. Moehle and coauthors' instances are proprietary. A synthetic generator with realistic lot histories, purchases over three years with random prices, contributions and withdrawals, is a prerequisite, and the empirical literature says which features drive the harvest: volatility, dividends, cash flows.A. L. Berkin and J. Ye (2003); L. R. Goldberg, P. Hand and T. Cai, "Tax-managed factor strategies", Financial Analysts Journal 75 (2019); K. Khang, T. Paradise and A. Cummings, "Expected loss harvest from tax-loss harvesting with direct indexing", The Journal of Beta Investment Strategies 14 (2023). The post quotes none of their alpha figures, several of which could not be read behind publisher pages. The protocol is Section 7.8's: both integrals with their symbols, the solved count at an absolute gap in dollars, dates, hardware, one time limit for every code, every configuration run twice, and no virtual best without the computation. The risk is that a synthetic generator reproduces the features its author thought of and none of the ones that make real accounts hard.
The ninth is a condition for exactness of the relaxation. Moehle and coauthors' rounding was certified optimal by the relaxation bound on 678 of 744 instances, and Bertsimas and Cory-Wright give a sufficient condition for the tightness of the Boolean relaxation (Section 4.9) in the cardinality case. An analogous condition for the tax problem, in terms of the lot structure, the curvature \(\gamma_{\mathrm{risk}} D_{ii}\) and the kink sizes, would tell the solver when no tree is needed at all.Bertsimas and Cory-Wright (2022), Proposition 2 and Corollary 3, on when the regularized problem's support agrees with the unregularized one. The first experiment computes Bertsimas and Cory-Wright's condition, adapted to the direction relaxation, on synthetic instances of the kind the eighth item generates. It then compares the instances the condition certifies with those the relaxation bound certifies, which on the published instances were 678 of 744. The risk is that the condition is sufficient only, so that it certifies a subset of the instances the bound already certifies and adds nothing to the solver.
The tenth is learning the directions (Section 8.5, and agenda item 7). The relaxation assigns each direction a fractional value that the two-stage method already reads as a probability, the labels cost milliseconds, since the direction-fixed QP is the label, and the structure is fixed across months. This is where a learned component has its best chance of transferring. The first experiment is a logistic predictor of the direction from lot features on synthetic accounts, the features being the kink size, the curvature, the deviation from the benchmark and the relaxation's value. It is scored by how many names it leaves uncertain and therefore in the tree. The risk is the held-out distribution problem of Section 8.5: an account unlike the training accounts, or a month of unusual prices, puts the predictor off its distribution exactly when the tree is largest.
What to measure is the vocabulary of this series, and the series' figures are its small versions. The first is the time to the first incumbent. The second is the primal gap at a hundred milliseconds and the primal integral \(P(T)\) with its normalization stated. The third is the dual integral, which is 1 for any method that produces no bound. The fourth is the number of nodes against the sequential run, which is the inflation of Section 6.4. The fifth is the efficiency curve against the number of workers, with the determinism check as a column. The last is the final gap in dollars, which is the precision of the problem. The figures were built first so that every large number of the post that follows this series has a small one, checked in its page, to be compared with.