Linear programming for execution schedules

Splitting an order over time

A linear program minimises a linear objective $\mathbf c^{T}\mathbf x$ subject to linear constraints $A\mathbf x\le\mathbf b$ and $\mathbf x\ge0$. The feasible set is a polytope, a shape with flat faces and corners, and because the objective is linear the best point is always at a corner (a vertex) of that shape. There is no downhill walking: the simplex method hops from vertex to vertex and interior-point methods cut through the middle, and both reach the exact optimum of a problem with thousands of variables in a fraction of a second.

An execution schedule is a natural linear program. To sell $Q$ shares over $T$ intervals, let $x_t$ be the shares sold in interval $t$, $c_t$ the expected cost per share there (spread plus impact, in basis points) and $u_t$ a capacity such as a participation cap of 10% of the expected volume. With one budget constraint the solution is greedy: fill the cheapest interval to its cap, then the next cheapest, until $Q$ is done. The multiplier of the budget constraint, which linear programming reports for free, is the marginal cost of one more share, namely the cost of the cheapest interval that still has room.

The capacity numbers can come from data. Over the last 250 sessions in the course dataset, the median daily volume of AAPL is about 45.5 million shares, so a 10% participation cap is about 4.55 million shares a day, and selling 20 million shares needs at least $20/4.55=4.4$, that is five, sessions. A constant cost per share is a first approximation. Real impact grows with the size traded in an interval, which makes the cost convex in $x_t$ and turns the schedule into a quadratic program, the model of the capstone.

• Vertex solution: an LP optimum sits at a corner of the feasible polytope.
• Greedy schedule: with one budget constraint, fill the cheapest capacity first.
• Shadow price: the budget multiplier is the marginal cost of one more share.

Lab · what's graded

• The total cost15 pts
• The average cost10 pts
• Shares in the dearest interval used15 pts
• The marginal cost15 pts
• An order that is too large15 pts
• Where an LP optimum sits15 pts
• Formulating the schedule15 pts