Primal-Dual Partnerships

Holmes and Watson, Calvin and Hobbes, Batman and Robin, Doc and Marty, Simon and Garfunkel: They are some of the most iconic duos in books, comics, movies and music. These partnerships show how unity is strength to solve riddles, improve the safety of a city, travel back in time, or compose and sing beautiful harmonies. But what about research? We can provide many examples of partners in crime. Better, we may call them partners in science.

For example, husband-and-wife duos Marie Skłodowska-Curie and Pierre Curie or Lillian Moller Gilbreth and Frank Bunker Gilbreth were pioneers in their fields [1, 2]. However, romantic love is not a necessary condition; for instance, think about Katalin Karikò and Drew Weissman – colleagues who made discoveries concerning nucleoside base modifications that enabled the development of effective mRNA (messenger ribonucleic acid) vaccines against COVID-19, leading to a Nobel Prize [3].

Despite the relatively short existence of the operations research (O.R.) field, we can mention some pairs who joined forces at some point in their careers, starting fantastic collaborations. Here, thanks to their interviews in the “Subject to” (s.t.) series, we tell the story of five of these O.R. pairs by delving into the details of how they met and describing the diversity and evolution of each partner’s roles at the beginning and during their collaboration.

M. Grazia Speranza and Claudia Archetti

An O.R. duo often starts traditionally: One is a professor teaching an O.R. course at a university, transmitting their knowledge and passion, while the other attends said course and becomes fascinated with the topic, the field and the thought leader.

Claudia Archetti met Grazia Speranza (INFORMS Fellow and EURO Gold Medalist) for the first time during her first exam session at the University of Brescia, during which Grazia was one of the supervisors in the room. A few years later, Claudia chose to attend a nonmandatory course in O.R. because “it was math” and the professor was known to be excellent. At the end of a lecture, Claudia asked a question, and Grazia thought: “I have to keep an eye on her!” Claudia also requested Grazia for a topic for her master’s thesis dissertation. But with a constraint: She was not interested in programming; she wanted to do something methodological. To “capture” her, Grazia agreed. Two months later, Claudia was nevertheless coding [4].

That was the beginning of their collaboration. Grazia became one of Claudia’s mentors and played a massive role in her professional life. Claudia further explored the topic of her thesis – a waste collection application – into an internship and a Ph.D. on split delivery vehicle routing problems. Claudia and Grazia published their first paper in 2003 [5]. Since then, they have co-authored four book chapters and 66 journal articles in more than 20 years.

In her s.t. episode, Claudia paid tribute to Grazia, highlighting how she was such a role model for her, such that Claudia almost did not realize that gender discrimination in academia was an issue. She described Grazia as strong, determined, engaged, dedicated, passionate and successful [6, 7]. Their professional partnership also benefits from their strong personal relationship, as revealed in several of Claudia’s funny stories about pranks, trips or gifts – a perfect example of a healthy partnership, a balance between work and friendship. “We have always worked perfectly together. We understand each other perfectly, ... she has always guided me. She has a lot of positive attitude,” says Claudia.

Panos Pardalos and Mauricio Resende

The paths of INFORMS Fellows Mauricio Resende and Panos Pardalos first crossed in June 1988 during the AMS-IMS-SIAM Joint Summer Research Conference on Mathematical Developments Arising from Linear Programming held at Bowdoin College in Maine [8]. At that time, Mauricio was working as a full-time consultant at AT&T Advanced Decision Support Systems, and Panos was a faculty member at Pennsylvania State University. Their Brazilian-Greek scientific partnership, rooted in a close friendship, formally began in 1990 when they decided to join forces to study the classic Quadratic Assignment Problem [9]. That same year, Panos began regularly visiting Mauricio at Bell Labs, where he had moved.

Mauricio and Panos collaborated in many ways throughout the years. For instance, Mauricio is known for his extensive contribution to the dissemination of the so-called Biased Random-Key Genetic Algorithm over the past two decades, and his first publication on the topic was co-authored with Panos and Martin Ericsson. As another notable example, Panos’ students Michael Hirsch and Claudio Meneses were involved in developing the Continuous Greedy Randomized Adaptive Search Procedure [10].

Mauricio and Panos have also maintained a long-term involvement with DIMACS (the Center for Discrete Mathematics and Theoretical Computer Science). After becoming permanent members of the center in 1994, they, with Ram Ramakrishnan, organized the DIMACS Workshop on Parallel Processing of Discrete Optimization Problems. Nearly 30 years later, in 2022, the duo was part of the organizing team of the 12th DIMACS Implementation Challenge and related workshop on vehicle routing problems, held in honor of the late David S. Johnson [11].

In addition to writing papers, and organizing and attending multiple events together, Mauricio and Panos also co-organized several handbooks on a variety of topics including applied optimization, massive datasets (with James Abello), optimization in telecommunications, and heuristics (with Rafael Martí). Their very fruitful partnership led to five books, 52 journal articles and book chapters, 11 conference papers and one patent.

Jan Karel Lenstra and Alexander Rinnooy Kan

On January 16, 1973, Alexander Rinnooy Kan walked into Jan Karel Lenstra’s office at the Mathematisch Centrum (presently, Centrum Wiskunde & Informatica) of the Dutch Science Council, where they talked for three hours. By following the advice of their common supervisor, Gijsbert “Gijs” de Leve, they started collaborating to complete their Ph.D. projects together. Little did they know that the door to a highly successful partnership had literally just opened. That year, Jan Karel and Alexander decided to concentrate their efforts on studying the theory of scheduling. However, they were still not aware of the breakthrough paper by Richard Karp on complexity theory published in 1972 [12] – they found out about it May 1974 when Mike Florian informed them [13]. When they attended the NATO Advanced Study Institute in 1974 (which led to a book organized by Bernard Roy titled “Combinatorial Programming: Methods and Applications” [14]), they were in the right place at the right time and equipped with an appropriate set of tools to make fundamental contributions and reshape the area of complexity of scheduling problems. They also introduced the famous three-field notation together with Ronald Graham and Eugene Lawler [15].

Jan Karel and Alexander traveled across North America and Europe presenting their remarkable findings and strengthening their bond [16]. In his s.t. episode, Alexander attributed the success of their partnership to the fact that they “were sufficiently similar and sufficiently different” [17]. He added that he would always produce the first draft quite quickly, with its main argument, and Jan Karel would take over from there and transform it into a serious publication [17]. Meanwhile, during his s.t. interview, Jan Karel shared that Alexander was ambitious: “He had a sense of purpose, and we were really complementary ... Alex had a global view, and he saw the long lines, he saw the horizon, and I’m the person for details.” By defining himself as “minimalist,” Jan Karel added that he and Alexander “implicitly decided to profit from each other’s strong points and not get irritated by our weak points … and that worked out pretty well” [18].

Jan Karel made a long, successful career in academia, receiving the EURO Gold Medal in 1997 and becoming an INFORMS Fellow in 2004, among other recognitions. After also being awarded the EURO Gold Medal in 1986, Alexander’s professional trajectory underwent a major shift in the early 1990s after finishing his term as rector of Erasmus University. He became the chair of the Association of Dutch Enterprises, then a member of the executive board of the International Netherlands Group (ING), before being named chair of the Social and Economic Council and finally becoming a member of the Senate in the Netherlands. When the duo was interviewed on the s.t. podcast, they had just celebrated the 50th anniversary of their interaction, friendship and work partnership. Together, they co-authored more than 43 journal articles, conference papers and book chapters. They also wrote three contributions to newsletters and newspapers and co-edited six books, often with other colleagues.

Emilio Carrizosa and Dolores Romero Morales

Having colleagues that help one another can make a big difference. Dolores Romero Morales understood she wanted an academic career in O.R. when she met some of her current co-authors during her master’s program. In her thesis, she studied a location problem considering some environmental issues. She wrote the related paper with Eduardo Conde and Emilio Carrizosa from the Universidad de Sevilla. Emilio was her master’s thesis supervisor, but, as he underlined in his s.t. interview, “In all our careers, we have been at the same level of academia, not the relation teacher-student” [19].

Theirs was an equal collaboration from the very beginning and became stronger despite time and space. Although Dolores initially moved to the Netherlands for a Ph.D. and then to Maastricht, Oxford and eventually Copenhagen, she and Emilio continued working together through the years and even increased their pace more recently.

Besides co-authoring 37 journal articles together in almost 30 years, they started co-supervising Ph.D. students and postdoctoral researchers in the intersection between optimization and machine learning by “trying to make the black box a little bit more gray” [20, 21]. In 2024, they were awarded the Spanish Statistics and O.R. Society and the BBVA Foundation Prize for the best contribution of O.R. in data science and big data, with their jointly supervised Ph.D. student Jasone Ramírez-Ayerbe.

Together, they developed the NeEDS project (Network of European Data Scientists; https://riseneeds.eu/), with Dolores as the project coordinator and Emilio as one of the leading experienced researchers. They are working on several additional outreach activities to promote our field.

Eduardo Uchoa and Artur Pessoa

Eduardo Uchoa and Artur Pessoa are two intellectual giants behind many state-of-the-art exact algorithms for different combinatorial optimization problems. They met in 1998 while attending graduate school at the Pontifical Catholic University of Rio de Janeiro, and both quickly developed mutual admiration for each other. In his s.t. episode, Artur recalled having interesting conversations with Eduardo during lunch at the university cafeteria. He enjoyed listening to Eduardo’s experiences on what kind of tricks could make algorithms efficient [22]. They also attended a course on combinatorial optimization together at PUC-Rio, teaming up to make a presentation for one of the exams, marking their first official partnership.

Some years later, in 2006, Eduardo was a faculty member at Universidade Federal Fluminense (UFF) when Artur joined him and decided to turn his attention to integer programming because of Eduardo’s enthusiasm for the field. Their first joint journal paper, published in Mathematical Programming, paved the way for groundbreaking contributions on efficient branch-cut-and-price algorithms for vehicle routing and scheduling solvers [23, 24]. Although Eduardo was one of the masterminds behind these approaches, Artur was crucial for their efficient development. Unfortunately, not many people know this. Eduardo noted that Artur is a “highly talented researcher, excellent programmer and not as well known in the community as he deserves” [25]. He also calls Artur a “hidden figure” with “comprehensive optimization knowledge and a brilliant mind behind many advances in column generation” [26].

The duo have much in common yet have distinct and complementary personalities. This became clear during the process of writing their recent book on column generation, with Lorenza Moreno [27]. “I tried to escape from it many times, but he did not let me leave, and I thank him for that. I thank Eduardo Uchoa for many things in my career, although we fight a lot!” revealed Artur [28]. He added that he would not be the scientist he is now without Eduardo. Despite their different point of view, they always manage to find a feasible solution to make ends meet, often converging to highly valuable scientific contributions, such as the new book and their 26 co-authored journal papers, 16 conference papers and one book chapter.

Key Components of Good Primal-Dual Algorithms

“[Paul] provided a lightness, an optimism, while I would always go for the sadness, the discords, the bluesy notes.” – John Lennon [29]

“When I write, there are times – not always – when I hear John [Lennon] in my head, ‘I'll think, OK, what would we have done here?’, and I can hear him gripe or approve.” – Paul McCartney [30]

In each of these pairs, who is the primal and who is the dual? It doesn’t matter. As we know in our field, the dual of the dual is the primal.

Teacher-student relationships and scientific partnerships turned into friendships; seniors supporting younger researchers; peers crossing paths in postgrad; or scholars curious to combine ideas regardless of being on opposite sides of the world – these pairs are just some examples of optimal alliances.

What are the key components of their primal-dual algorithms that make their execution possible and last throughout the years? Besides the common passion for research and O.R. topics, on each side of these duos, there is transparency and intellectual freedom; trust and admiration; confrontation and compromise; sometimes, even a pinch of good competition to encourage each other; and full acceptance of each other’s traits (i.e., diversity). Mostly, at the base, in the pair domain, we always find mutual, continuous respect. And this makes research collaborations, partnerships and friendships easier to grow.

References

1. https://blogs.loc.gov/headlinesandheroes/2022/02/famous-couples-marie-and-pierre-curie/
2. https://www.business.com/articles/management-theory-of-frank-and-lillian-gilbreth/
3. https://www.nobelprize.org/prizes/medicine/2023/press-release/
4. Maria Grazia Speranza, s.t. episode: https://youtu.be/rDshB06FaRk?feature=shared&t=3400
5. Archetti, C., Bertazzi, L., & Speranza, M. G., 2003, "Reoptimizing the traveling salesman problem," Networks: An International Journal, Vol. 42, No. 3, pp. 154-159, https://doi.org/10.1002/net.10091.
6. Claudia Archetti, s.t. episode: https://youtu.be/CkZP19i8N9s?feature=shared&t=2688
7. Claudia Archetti, s.t. episode: https://youtu.be/CkZP19i8N9s?feature=shared&t=4296
8. Mathematical Developments Arising from Linear Programming, https://www.ams.org/books/conm/114/conm114-endmatter.pdf
9. Li, Y., Pardalos, P. M., Ramakrishnan, K. G., & Resende, M. G., 1994, "Lower bounds for the quadratic assignment problem," Annals of Operations Research, Vol. 50, No. 1, pp. 387-410, https://doi.org/10.1007/BF02085649.
10. Mauricio Resende, s.t. episode: https://youtu.be/8Lrq-iIixp0?t=3651
11. DIMACS Implementation Challenge: Vehicle Routing, http://dimacs.rutgers.edu/programs/challenge/vrp/
12. Karp, R. M., 1972, "Reducibility among Combinatorial Problems," Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds), Complexity of Computer Computations, The IBM Research Symposia Series. Springer, Boston, MA, https://doi.org/10.1007/978-1-4684-2001-2_9. 
13. Jan Karel Lenstra, s.t. episode: https://www.youtube.com/watch?v=MrFc53FYkEA
14. Roy, B., ed., 1975, "Combinatorial Programming: Methods and Applications," D. Reidel Publishing Company, Dordrecht, Holland.
15. Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. R., 1979, "Optimization and approximation in deterministic sequencing and scheduling: a survey," Annals of Discrete Mathematics, Vol. 5, pp. 287-326.
16. Alexander Rinnooy Kan, “Bordjes duiken: Ervaringen van een optimist,” https://www.amazon.com/Bordjes-duiken-Ervaringen-optimist-Dutch/dp/9460038808
17. Alexander Rinnooy Kan, s.t. episode: https://youtu.be/TafKWgwcn1I?feature=shared&t=1293
18. Jan Karel Lenstra, s.t. episode: https://youtu.be/MrFc53FYkEA?feature=shared&t=1400
19. Emilio Carrizosa, s.t. episode: https://youtu.be/Se0XEZodXtg?feature=shared&t=2923
20. Dolores Romero Morales, s.t. episode: https://youtu.be/rn4zFZCwsrE?feature=shared&t=3108
21. Emilio Carrizosa, s.t. episode: https://youtu.be/Se0XEZodXtg?feature=shared&t=3397
22. Artur Pessoa, s.t. episode: https://www.youtube.com/watch?v=xWU3GCuy6FI
23. Uchoa, E., Fukasawa, R., Lysgaard, J., Pessoa, A., De Aragao, M. P., & Andrade, D., 2008, "Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation," Mathematical Programming, Vol. 112, No. 2, pp. 443-472, https://doi.org/10.1007/s10107-006-0043-y.
24. VRPSolver: https://vrpsolver.math.u-bordeaux.fr/
25. Eduardo Uchoa, s.t. episode: https://www.youtube.com/watch?v=9mNjqkUIZRk&t=1680s
26. Eduardo Uchoa, LinkedIn: https://www.linkedin.com/posts/eduardo-uchoa-b785a319_orms-optimization-analytics-activity-7262759580051402752-ukHE
27. Eduardo Uchoa, Artur Pessoa, and Lorenza Moreno: https://optimizingwithcolumngeneration.github.io
28. Artur Pessoa, s.t. episode: https://youtu.be/xWU3GCuy6FI?feature=shared&t=4906
29. https://www.beatleswiki.com/wiki/index.php?title=Lennon/McCartney
30. https://nypost.com/2005/09/05/paul-i-hear-johns-voice-in-my-head/