Programmation linéaire pour les calendriers d'exécution

Répartir un ordre dans le temps

Un programme linéaire minimise un objectif linéaire $\mathbf c^{T}\mathbf x$ sous des contraintes linéaires $A\mathbf x\le\mathbf b$ et $\mathbf x\ge0$. L'ensemble admissible est un polytope, une forme à faces plates et à sommets, et comme l'objectif est linéaire le meilleur point est toujours en un sommet de cette forme. Il n'y a pas de marche vers le bas : la méthode du simplexe saute de sommet en sommet et les méthodes de points intérieurs traversent l'intérieur ; les deux atteignent l'optimum exact d'un problème à des milliers de variables en une fraction de seconde.

Un calendrier d'exécution est un programme linéaire naturel. Pour vendre $Q$ actions sur $T$ intervalles, notons $x_t$ les actions vendues à l'intervalle $t$, $c_t$ le coût attendu par action à ce moment (écart plus impact, en points de base) et $u_t$ une capacité, par exemple un plafond de participation de 10 % du volume attendu. Avec une seule contrainte de budget la solution est gloutonne : remplir l'intervalle le moins cher jusqu'à son plafond, puis le suivant, jusqu'à ce que $Q$ soit exécuté. Le multiplicateur de la contrainte de budget, que la programmation linéaire fournit gratuitement, est le coût marginal d'une action de plus, soit le coût de l'intervalle le moins cher qui a encore de la place.

Les capacités peuvent venir des données. Sur les 250 dernières séances du jeu de données du cours, le volume quotidien médian d'AAPL est d'environ 45,5 millions d'actions ; un plafond de participation de 10 % vaut donc environ 4,55 millions d'actions par jour, et vendre 20 millions d'actions demande au moins $20/4.55=4.4$, soit cinq, séances. Un coût constant par action est une première approximation. L'impact réel croît avec la taille traitée dans un intervalle, ce qui rend le coût convexe en $x_t$ et transforme le calendrier en programme quadratique, le modèle du projet final.

• Solution en un sommet : l'optimum d'un PL est en un coin du polytope admissible.
• Calendrier glouton : avec une seule contrainte de budget, remplir d'abord la capacité la moins chère.
• Prix fantôme : le multiplicateur du budget est le coût marginal d'une action de plus.

Lab : ce qui est noté

• Le coût total15 pts
• Le coût moyen10 pts
• Actions dans l'intervalle le plus cher utilisé15 pts
• Le coût marginal15 pts
• Un ordre trop grand15 pts
• Où se trouve l'optimum d'un PL15 pts
• Formuler le calendrier15 pts