Bitmask Dynamic Programming for Optimal Basket Execution

An algorithmic trade execution router at Jane Street and Citadel must execute a basket of $N$ correlated assets ($N \le 16$).

Executing asset $i$ alters the order book depth and spreads of related assets due to cross-asset market impact. If asset $j$ is executed immediately after asset $i$, an empirical cross-impact cost $C[i][j]$ is incurred.

You are provided with an $N \times N$ non-negative integer transition impact cost matrix cost_matrix ($C[i][i] = 0$). You may begin execution with any asset at zero initial transition penalty.

Your Task

Implement min_basket_execution_cost(cost_matrix: list[list[int]]) -> tuple[int, list[int]] that returns:

1. min_cost: The minimum possible total transition impact cost required to execute all $N$ assets.
2. optimal_sequence: The permutation list of asset indices $[a_1, a_2, \dots, a_N]$ achieving this minimum cost.

Constraints

• $1 \le N \le 16$
• $0 \le cost\_matrix[i][j] \le 10^5$
• $cost\_matrix[i][i] == 0$

Examples

cost_matrix = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]
# Path 1 -> 0 -> 2 -> 3: cost = 10 + 15 + 30 = 55
# Path 2 -> 0 -> 1 -> 3: cost = 15 + 10 + 25 = 50
# Optimal sequence achieves min_cost 50