(4/52) Fred Gardi - 8 Apr 2024

Introduction
Imagine yourself in a giant maze searching for the shortest way out. Imagine this maze is so huge that trying every possible path would take forever, even with the fastest computer. This maze parallels the challenges of most problems we must solve in various forms when planning resources in transportation, logistics, manufacturing and many other industries. These problems are marked by their extreme computational complexity, and as they grow in scale, the time needed to find an exact solution rises exponentially. Consequently, we often resort to heuristic and approximation techniques to find a solution that is good enough, if not optimal. Hexaly is one of the notable leaders in the industry focused on solving mathematical optimization problems, particularly known for its speed and capability in problems related to routing, scheduling and packing. I recently had the privilege of interviewing Fred Gardi, founder and CEO of Hexaly, where he leads the development of a solver that has revolutionized the approach to mathematical optimization. His story highlights the crucial role of adaptability and strategic thinking in translating technical expertise into successful business outcomes.

Early Life
Post World War II, France’s education system has seen major reforms, recognizing education as a driver for economic recovery and growth. Born to farmer parents in a small village in southern France, Fred discovered his passion for mathematics and science early on. However, his access to computers was restricted until France implemented a policy mandating a computer in every school. Fred learned programming small snippets of code in BASIC, a programming language popular on the first PCs. This sparked his interest in computer science, and he relocated to Marseille to pursue his undergraduate and master’s degrees in computer science and mathematics at Aix-Marseille University.

Graduate Education
During his master’s program, Fred was fascinated by a course in Discrete Optimization. Delving into the theory of the domain, grappling with the complexities and bounds of complex combinatorial problems motivated him to pursue a PhD specializing in this area. His doctoral research was inspired by a business problem he encountered while interning at Prologia. The goal was to devise simple, efficient algorithms for graph coloring for specific classes of graphs. Graph coloring is a challenging NP-hard problem. Although Fred’s efforts were rooted in a very practical business problem, he quickly recognized the significant disconnect between academic theories and their application in the real world.

He grew to appreciate the realm of heuristics as a tool for solving real-world NP hard problems. Local search techniques, such as simulated annealing and tabu search, aim to locate a global optimum, primarily differing in their methods for circumventing local optima. While conceptually straightforward, they can theoretically produce poor results with no guarantee of convergence or optimality. The success of these heuristic solutions depends on the diversity of the neighborhoods explored and the speed of these explorations. Fred emphasized the importance of high-performance “evaluation machinery” to evaluate moves across numerous neighborhoods to ensure fast convergence. While the quality of these techniques can be measured against theoretical bounds, they are particularly prized for their low running time in fast paced business environments, even in the absence of these bounds.

Throughout his PhD, Fred extensively explored local search heuristics. By day, he developed practical solutions for Prologia, and by night, he focused on the theoretical aspects of his dissertation. A fundamental discovery for him was realizing that real-world problems are much more complex and messier, and demand extensive software engineering. This experience not only deepened his technical skills but also enhanced his understanding of business needs, improving his ability to communicate and collaborate effectively with stakeholders.

“In many cases, a quick, good-enough solution is far more valuable for the business than an optimal one that takes hours to obtain.”, Fred stated.

Fred, along with his PhD colleagues, participated in competitions hosted by the French Operations Research Society (ROADEF) tackling real-world problems. They developed local search algorithms that delivered impressive results, enabling them to win against renowned researchers worldwide. Convinced of the potential of these algorithmic techniques, Fred believed they should be integrated into a mathematical solver, although he still needed to figure out how.

LocalSolver
In 2007, Fred relocated to Paris to join the Operations Research team at Bouygues, a prominent French conglomerate. Local search heuristics continued to prove effective in solving diverse problems across the construction, energy, telecom, and media sectors. Fred convinced Thierry, the team’s lead, to develop a software library to help industrialize the implementation of local search heuristics for their projects at Bouygues. After more than a year of prototyping in their spare time, the team saw the potential to develop a solver “akin to CPLEX”, which would eventually be known as LocalSolver.

CPLEX is an optimization solver that excels in solving “nearly linear” problems but can fall short when faced highly combinatorial problems. They observed that the CPLEX modeling APIs for mixed integer linear programming were too simplistic and lacked structural features. This spurred them to explore set-oriented constructs, often discussed in constraint programming. The team also compiled their expertise and ideas into a book titled “Mathematical Programming Solver Based on Local Search,” outlining a roadmap for the future development of LocalSolver.

They developed the vision of a hybrid solver combining heuristic techniques like local search with exact techniques in mixed integer linear programming, constraint programming and nonlinear programming. By the end of 2009, a working beta version of LocalSolver was ready, and was extensively used at Bouygues, providing invaluable feedback to the team. Launching LocalSolver as open-source software was judged unviable considering the need for extensive support and a small potential contributing community. In 2011, Fred and the team made a significant move by launching LocalSolver as a spinoff company from Bouygues, simply bootstrapping from their original consulting and service activity.

Hexaly
LocalSolver was named after the first C++ class Fred implemented, but the name proved really confusing to clients who often mistook it for a tool that only searches for local optima rather than the global ones. The name was later changed to Hexaly. “Technical people are often not the best marketers”, Fred remarked.

The product received encouraging feedback from early adopters who found it both intriguing and promising. However, broader interest was still limited. The academic community found the tool too practical, while the business users were primarily looking for a faster MILP solver. In response, the team focused on enhancing the solver for specific problem areas but with a profound market demand —routing, scheduling, and packing—common in supply chain and workforce management. The team reinvested company’s profit margins to fund the ongoing research and development. After years of dedicated work, the company developed state-of-the-art benchmarks for these problems, outperforming other tools in the market, also reflected in company’s accelerated growth in user base and revenue in recent years.

A critical lesson for him, Fred mentioned, was realizing the importance of sales skills that he had initially underestimated. He was confident in their product’s quality but realized that sales and marketing, while not entirely scientific, are crucial for business growth. Initially, LocalSolver was staffed with technical experts who lacked both interest and expertise in marketing. Confronted with concerns about the company’s survival, Fred took it upon himself to learn and adopt these skills.

Future
Over the years, LocalSolver has shifted from a purely consulting firm to deriving 90% of its revenue from software licensing. The team excels at delivering products and solutions that closely align with business needs and continuously adapt to customer feedback. Motivated to leverage their R&D and repurpose the solver across various problems, they focused on making their local search algorithms very generic while following their original roadmap toward global optimization, coupling local search with sophisticated exact techniques like spatial branch-and-bound and branch-cut-price. Today, Hexaly has transformed into one of the fastest optimization solvers for routing, scheduling, and packing problems, offering a comprehensive suite of tools under Hexaly Studio, tailored to various development needs.

Looking ahead, Fred emphasized that despite extensive research, the field of Mathematical Optimization is still evolving and far from being mature, both as a practice and technology. He predicts that decades of effort remain to democratize it and establish it as a mainstream tool in business and industry. While Generative AI holds promise for making problem modeling more accessible to data scientists, it also poses a significant challenge being a bigger “black box” for clients to trust when making critical operational or strategic decisions. Fred contends that Decision Optimization is and will continue to be a journey for companies and the people in them. He argues that optimization softwares need to be more transparent about the mathematical models implemented inside and business users should be able to engage with and control these optimization engines. To achieve this, Fred advocates for integrating Mathematical Optimization into basic scientific education as an extension of algebra and calculus.

“Democratizing mathematical optimization is about learning and practicing the basics of mathematical modeling for solving business problems, not learning how the simplex algorithm works.”, he insisted.