• cryptocurrency
• trading
• blockchain
• defi
• cfmm
• routing
• optimization

This work addresses the practical application of optimal routing in blockchain trading, focusing on the challenge of dual decomposition when routing through Constant Function Market Makers (CFMMs) with linear trading functions. Those CFMMs, often called liquidity books, leverage concave but not strictly concave linear trading functions within each liquidity position. The study presents and evaluates two solutions suitable for the dual decomposition: sub-gradient methods and Nesterov's smoothing. We propose a Lagrangian heuristic for sub-gradient methods that provides a robust termination criterion in arbitrage instances. Furthermore, we demonstrate that Nesterov's smoothing generates strictly concave CFMMs capable of approximating linear ones, establishing sufficient conditions for valid approximations. New proximal functions specific to optimal routing are proposed, yielding better approximations compared to widely adopted proximal quadratic functions. Empirical evaluations on blockchain-derived data indicate the effectiveness of these approaches.