Groupe d’études et de recherche en analyse des décisions

Different models lead to different algorithms: Two examples with logic-Benders and an ad hoc exact algorithm

Leandro C. Coelho Professeur agrégé, Département d’opérations et systèmes de décision , Université Laval, Canada

Leandro C. Coelho

Lien pour le webinaire
Nº du webinaire : 940 3824 3185
Code secret: 841095

Different models lead to different solution algorithms. Some models are more fit for row generation algorithms, while others are more prone to work well with column generation algorithms. Compact models are usually preferred for branch-and-bound-based algorithms, but this is not always the norm. In this talk, we take two examples from a fractional optimization problem arising in inventory-routing problem, and a time-dependent vehicle routing problem. We show how we designed and ad hoc exact algorithms for the fractional optimization problem, and a logic-Benders decomposition for the time-dependent one. We discuss how their formulations have led to different choices in designing algorithms, and we show that the smallest formulation is not always the best one. Computational results from both problems are used to illustrate the choices and their effects.