Built on research,
proven in practice.

A proven legacy in column generation performance

Column generation has long been the dominant technique for solving complex network optimisation problems. At Flowty, our team has helped define its modern evolution, combining theoretical depth with record-breaking practical performance.

The Vehicle Routing Problem with Time Windows (VRPTW) has been at the forefront of column generation research [1], providing a proving ground for many fundamental advances in the field. Our early contributions to the VRPTW helped set a new standard for exact algorithms. Introducing subset-row inequalities [2] marked a leap in model strength, closing long-open Solomon instances for the first time. This breakthrough was extended through Chvátal-Gomory rank-1 cuts [3] and clique inequalities [4]. Later, [5] formalized a unified framework for embedding cutting planes in branch-and-price algorithms — much of which is now standard practice.

But our work didn't stop with routing. We extended column generation and decomposition methods to domains like multi-commodity flows [6, 7], scheduling [8], cutting stock problems, and split delivery routing problems, where we developed a hybrid Benders decomposition approach that exploits multiple formulations simultaneously—preserving integrality where needed while leveraging structure for scalability [9].

Beyond column generation, our expertise spans the full spectrum of optimization approaches, such as large-scale heuristics [10, 11], Benders decomposition [12], and branch-and-cut [13, 14, 15]. This multi-faceted approach—combining exact methods, advanced heuristics, and cutting plane techniques—allows us to tackle real-world problems from multiple angles. When exact solutions are needed, we have the theoretical tools. When speed is paramount, we can deploy sophisticated heuristics. And when problems demand both optimality and efficiency, we know how to balance these approaches effectively.

What sets Flowty apart is not just technical capability but the depth of foundational expertise. Our solver architecture is grounded in research conducted over multiple Ph.Ds at the University of Copenhagen [16] and the Technical University of Denmark [17], followed by postdoctoral research, where we didn't just use advanced column generation and network optimisation techniques.

This research legacy ensures that Flowty's solver is a rigorously built engine that translates decades of optimization science into high-performance, scalable software that outperforms general-purpose solvers on network structured problems.

References
[1] Desaulniers, G., Desrosiers, J., & Spoorendonk, S. (2010). The Vehicle Routing Problem with Time Windows: State‐of‐the‐Art Exact Solution Methods. In Wiley Encyclopedia of Operations Research and Management Science (pp. 5742-5749). Wiley. https://doi.org/10.1002/9780470400531.eorms0944
[2] Jepsen, M. K., Ropke, S., Spoorendonk, S., & Pisinger, D. (2008). Subset-row inequalities applied to the vehicle routing problem with time windows. Operations Research, 56(2), 497–511. https://doi.org/10.1287/opre.1070.0462
[3] Petersen, B., Pisinger, D., & Spoorendonk, S. (2008). Chvátal-Gomory rank-1 cuts used in a Dantzig-Wolfe decomposition of the vehicle routing problem with time windows. In The Vehicle Routing Problem: Latest Advances and New Challenges (pp. 397-419). Springer, Boston, MA. https://link.springer.com/chapter/10.1007/978-0-387-77778-8_18
[4] Desaulniers, G. & Spoorendonk, S. (2010). Clique inequalities applied to the vehicle routing problem with time windows. INFOR: Information Systems and Operational Research 48 (1), 53-67. https://doi.org/10.3138/infor.48.1.053
[5] Desaulniers, G., Desrosiers, J., & Spoorendonk, S. (2011). Cutting planes for branch-and-price algorithms. Networks, 58(4), 301–310. https://doi.org/10.1002/net.20468
[6] Brouer, B. D., Pisinger, D., & Spoorendonk, S. (2011). Liner shipping cargo allocation with repositioning of empty containers. INFOR, 49(2), 109–124. https://doi.org/10.3138/infor.49.2.109
[7] Mette Gamst and Bjørn Petersen. Comparing Branch-and-Price Algorithms for the Multi-Commodity k-splittable Maximum Flow Problem, European Journal of Operational Research, 217(2):278–286, 2012. https://doi.org/10.1016/j.ejor.2011.10.001
[8] Reinhardt, L. B., Pisinger, D., Spoorendonk, S., & Sigurd, M. M. (2016). Optimization of the drayage problem using exact methods. INFOR: Information Systems and Operational Research, 54(1), 33-51. https://doi.org/10.1080/03155986.2016.1149919
[9] Lusby, R. M., Gamst, M., Ropke, S., & Spoorendonk, S. (2020). Simultaneously exploiting two formulations: An exact Benders decomposition approach. Computers & Operations Research, 123, 105041. https://doi.org/10.1016/j.cor.2020.105041
[10] Petersen, H. L., Larsen, A., Madsen, O. B. G., Petersen, B., & Ropke, S. (2013). The simultaneous vehicle scheduling and passenger service problem. Transportation Science, 47(4), 603-616. https://doi.org/10.1287/trsc.1120.0429
[11] Muller, L. F., Spoorendonk, S., & Pisinger, D. (2012). A hybrid adaptive large neighborhood search heuristic for lot-sizing with setup times. European Journal of Operational Research, 218(3), 614-623. https://doi.org/10.1016/j.ejor.2011.11.036
[12] Lusby, R. M., Muller, L. F., & Petersen, B. (2013). A solution approach based on Benders decomposition for the preventive maintenance scheduling problem of a stochastic large-scale energy system. Journal of Scheduling, 16(6), 605-628. https://doi.org/10.1007/s10951-012-0284-y
[13] Stidsen, T., Petersen, B., Spoorendonk, S., Zachariasen, M., & Rasmussen, K. B. (2010). Optimal routing with failure‐independent path protection. Networks: An International Journal, 55(2), 125-137. https://doi.org/10.1002/net.20322
[14] Jepsen, M., Spoorendonk, S., & Ropke, S. (2013). A branch-and-cut algorithm for the symmetric two-echelon capacitated vehicle routing problem. Transportation Science, 47(1), 23-37. https://doi.org/10.1287/trsc.1110.0399
[15] Jepsen, M. K., Petersen, B., Spoorendonk, S., & Pisinger, D. (2014). A branch-and-cut algorithm for the capacitated profitable tour problem. Discrete Optimization, 14, 78-96. https://doi.org/10.1016/j.disopt.2014.08.001
[16] Spoorendonk, S. (2008). Cut and Column Generation (PhD thesis). Copenhagen University, Denmark.
[17] Petersen, B. (2011). Shortest paths and vehicle routing (PhD thesis). Technical University of Denmark, Denmark.