An exact dynamic programming algorithm, lower and upper bounds, applied to the large block sale problem
Résumé
In this article, we address a class of non convex, integer, non linear mathematical programs using dynamic programming. The mathematical program considered may be used to model the optimal liquidation problem of a single asset portfolio. We show the problem can be solved exactly using Dynamic Programming (DP) in polynomial time. We also introduce dedicated heuristics and provide very thin admissible solutions, for medium sized and large instances (for which exact resolution is not efficient). We also derive an upper bound which however is not tight. Lastly, we benchmark our results against a commercial solver, such as LocalSolver.