March 2024
The Special Focus on Bridging Continuous and Discrete Optimization bridged not only the two large communities within computational and mathematical optimization, but also the two shores of the COVID-19 shutdown that canceled events around the world in 2020. 
The special focus was part of the DIMACS/Simons Collaboration on Bridging Continuous and Discrete Optimization, a formal partnership between DIMACS and the Simons Institute for the Theory of Computing funded by the National Science Foundation (NSF). The NSF-sponsored Collaboration supported activities at both DIMACS and the Simons Institute that were devoted to advancing the theoretical foundations of optimization methods and their performance in challenging real-world settings. It began with an intensive program on Bridging Continuous and Discrete Optimization at the Simons Institute during the fall semester of 2017, and it continued with a multi-year special focus at DIMACS that launched in 2018, spanned the nearly two-year COVID hiatus, and drew to a close in the summer of 2023.
The program at the Simons Institute was its first-ever “jumbo” program, meaning that it did not run concurrently with another program, allowing it to be roughly twice the size of a typical program. In all, the program involved 121 people visiting the Simons Institute for an extended period during the program. The large number of researchers generated intense discussion, energetic collaboration, and a host of new results and subsequent publications. The Simons program also featured five workshops, several single-day symposia, and many community-building activities that were especially beneficial to students and postdocs, such as reading groups, a seminar series, and industry field trips.
The DIMACS special focus began in 2018 to build on the program at the Simons Institute and expand it to include more people and more topics. The Special Focus on Bridging Continuous and Discrete Optimization launched with plans to hold seven research workshops, but it ultimately held ten workshops—eight in-person and two online—over an expanded time period. The special focus also hosted the annual Mixed Integer Programming (MIP) workshop in 2022, after planning to host in 2020 and 2021 when COVID forced the event online. The full list of special focus events is as follows:
- DIMACS Workshop on ADMM and Proximal Splitting Methods in Optimization
- DIMACS/TRIPODS Workshop on Optimization and Machine Learning
- DIMACS Workshop on Optimization in Distance Geometry
- DIMACS Workshop on Randomized Numerical Linear Algebra, Statistics, and Optimization
- CRM/DIMACS Workshop on Mixed-Integer Nonlinear Programming
- Mixed Integer Programming Workshop 2020 (online)
- Mixed Integer Programming Workshop 2021 (online)
- 12th DIMACS Implementation Challenge Workshop: Vehicle Routing Problems (online)
- DIMACS Workshop on Entropy and Optimization (online)
- Mixed Integer Programming Workshop 2022 featuring DANniversary
- Reconnect 2022: Optimization
- IBM/DIMACS/DATA-INSPIRE Workshop on Bridging Game Theory and Machine Learning for Multi-party Decision Making
- DIMACS Workshop on Computational Approaches to Vehicle Routing with a Tribute to David S. Johnson
The events above involved roughly 600 participants attending in person and hundreds more attending online. Two of the events involved coordination with TRIPODS institutes and a third was jointly held in association with the Centre de Recherches Mathématique’s month-long program on Mixed Integer Nonlinear Programming. Two others were associated with the 12th Implementation Challenge on Vehicle Routing Problems. Adding to the events, the special focus also hosted ten longer-terms visits by researchers at DIMACS and its partner institutions.
Over the course of the DIMACS/Simons Collaboration on Bridging Continuous and Discrete Optimization, authors of more than 200 papers told us that these works benefitted from activities of the project. Participants reported many important results stemming from activities of the Collaboration, with several settling long-standing open questions. The program at the Simons Institute yielded the first efficient method for counting the bases of any matroid; a new NC algorithm for finding a perfect matching in planar graphs, settling the long-standing question of whether the problem is in NC; new connections between competitive analysis and interior point methods for optimization; a new general method for rounding semi-definite programs that delivers performance guarantees competitive with best-known results for several classic constraint satisfaction problems; a proof affirming Mason’s 1972 conjecture that, for any matroid, the sequence of the number of independent sets of given sizes is ultra log-concave; and a new practical algorithm for sampling from a polytope that improved theoretical bounds. Activities at DIMACS also contributed new results and insights, with a highlight being the intense focus on vehicle routing during the Implementation Challenge, which illuminated the state of the art in solving classic variants of the vehicle routing problems and led to new tools and test instances.
The DIMACS/Collaboration on Bridging Continuous and Discrete Optimization was the second of three partnerships between the two institutes. Each began with a semester-long program at the Simons Institute followed by a DIMACS special focus on the same theme. The DIMACS/Simons Collaboration in Cryptography ran from 2015 to 2020, and the DIMACS/Simons Collaboration on Lower Bounds in Computational Complexity began in 2019 and will hold its concluding workshop in July. Activities at DIMACS and the Simons Institute enabled researchers to share information and ideas, form new collaborations, build communities across disciplines and institutions, nurture the development of early-career researchers, and contribute to the integration of research and education.
Printable version of this story: [PDF]