Research Area C3

Combinatorial optimization, complexity, and chip design

Research Area Leaders: Heiko Röglin, Jens Vygen

PIs: Heiko Röglin, Jens Vygen

Contributions by Ulrich Brenner, Anne Driemel, Jens Franke, Stephan Held, Philipp Hieronymi, Stefan Hougardy, Marek Karpinski, Thomas Kesselheim, Bernhard Korte, Kelin Luo, Dirk Müller, Petra Mutzel, Martin Nägele, Lisa Sauermann, Vera Traub, Laura Vargas Koch

The impact of combinatorial optimization to real-world applications can hardly be overestimated. We study fundamental combinatorial optimization problems (such as the traveling salesman problem) and their complexity, and we devise and analyze efficient algorithms. We also design and implement algorithms for real-world applications and benefit from the interplay between theory and practice. We have industrial cooperations with IBM and DHL, leading companies in two key application areas: chip design and logistics. On the one hand, we show that mathematics makes the difference in such applications, leading to better solutions. On the other hand, practical needs lead to new theoretical questions and to a refocusing of fundamental research. The theoretically best algorithms are often not the same as those that work best in practice; we aim to explain this phenomenon rigorously in order to narrow the gap between theory and practice.

Understanding and exploiting the combinatorial structure of algorithmic problems that arise in numerous applications is the defining theme of combinatorial optimization [KV18]. While there has often been a separation between theory and provably good algorithms on one side, and heuristics for practical needs on the other, we aim to bridge this gap: our work spans from core theory to implementation for industrial use.      

Fundamental combinatorial optimization problems. The famous traveling salesman problem (TSP) has been the most influential combinatorial optimization problem. It serves as a prototype of an NP-hard problem, and progress on the TSP has usually also had impact on many other optimization problems. While Christofides’ algorithm from 1976 is still the best approximation algorithm for the classical TSP, there has recently been remarkable progress on many TSP variants, somewhat unexpected after decades of stagnancy. Over the last six years, the best known upper bounds on integrality gap and approximation guarantee have been obtained by Sebö–Vygen [SV14] for the graph TSP and by Traub–Vygen [TV18] for the s-t-path TSP. We also improved lower bounds on approximability and integrality gaps. Our techniques also lead to better algorithms for related network design problems [SV14, HV17].      

Beyond worst-case analysis. Concerning running time or quality of results, many algorithms are better than a worst-case analysis tells because bad instances occur only rarely. Spielman and Teng introduced in 2001 the framework of smoothed analysis, in which adversarial inputs are perturbed by a small amount of random noise. They provided the first rigorous explanation for the practical success of the simplex algorithm by proving that its expected running time is polynomial in this model. Röglin and coauthors made major contributions on smoothed analysis of combinatorial optimization problems and gave rigorous explanations for the practical success of local search for the TSP, k-means clustering [AMR11], and the maximum cut problem [ER17]. These results have significantly narrowed the gap between theory and practice for these important optimization problems. Röglin et al. also initiated smoothed analysis of multiobjective optimization [BR15]. Interestingly, their methods for the min-cost flow problem [BCM+15] also lead to novel bounds on the diameter of certain polytopes. In particular, they gave the first constructive improvement for the diameter of totally unimodular polytopes after more than 20 years. Similar beyond-worst-case approaches have also turned out to be a suitable way of modeling in online optimization. Kesselheim and coauthors significantly extended and improved existing results, assuming random arrival orders, known distributions [DFKL17], or both.      

Algorithms for chip design and vehicle routing. Based on a long-term cooperation with IBM we have been developing algorithms for layout and optimization of integrated circuits. Our BonnTools have been used to design thousands of the most complex chips in industry. We recently devised the first global router that inherently obeys timing constraints; a breakthrough in combining two of the most important subtasks in chip design [HMR+18]. IBM is currently adapting its flow to this innovation, and unexpected new applications in chip planning have already arisen. Other recent successes include the first fully-automated transistor-level layout algorithm [CHSS17] and near-optimal re-synthesis of adders and critical logic paths [HS17]. However, technological advances and ever-increasing instance sizes continue to pose many challenges. Vygen recently started a new cooperation with DHL on optimizing delivery services. There is an abundance of heuristics and mixed-integer linear programming relaxations for vehicle routing, but a lack of theoretical bounds. This is not surprising as the problem not only contains the TSP, but also includes partitioning to tours and obeying time windows, capacities, and other constraints.

Fundamental combinatorial optimization problems. Our recent new techniques have already led to better approximation algorithms for variants of the TSP, but they have the potential to yield more, also for a wider class of problems. Proving the conjectured integrality gap is not necessarily the end of the story. For instance, we think that for the s-t-path TSP in graphs, our ear-decomposition approach from [SV14], together with dynamic programming from [TV18] and new techniques, could lead to a better bound than Vygen et al. will also explore which of our new techniques can be applied to the classical TSP where Christofides’ algorithm is still unbeaten. There are several good candidates now (‘weighted ear-decompositions’ is one of them) and, after 40 years, improving the approximation ratio could finally be within reach. Another challenge is improving the recent constant-factor approximation algorithm for the asymmetric TSP. Although it requires new ideas, a drastic simplification and a much better approximation ratio should be possible. We will also continue advancing network design and other key problems. For instance, improving on the best approximation algorithms for Steiner tree, Steiner forest, or general network design, are prominent open questions where some of our new techniques might prove useful.      

Beyond worst-case analysis. Although in the last decade many deep and intriguing results have been obtained in the area of probabilistic analysis, the techniques and proofs are still mostly custom-made and there is a lack of general methods. We have now accumulated enough experience to develop more general techniques, which will broaden the scope of applications. In particular, Röglin plans to rigorously characterize which structural properties of a combinatorial optimization problem make it easy for local search. Ultimately, this will lead to a better understanding of many combinatorial optimization problems and likely also result in better algorithms. Understanding the maximum diameter of polytopes is a long-standing challenge in discrete mathematics. Even though the Hirsch conjecture has been disproved, it is still conceivable that the diameter of every polytope can be bounded by a small polynomial in the number of facets and the dimension. We discovered that the shadow vertex algorithm yields small diameter bounds for totally unimodular polytopes, using methods that we developed for the smoothed analysis of the min-cost flow problem. There is hope that our approach can be extended to even yield improved bounds for general polytopes. This might also lead to a better analysis of the network simplex algorithm for the min-cost flow problem. To deal with uncertain inputs, for combinatorial allocation problems, it is useful to define prices on the goods to be allocated. It is then sufficient to argue in the setting of full certainty. Kesselheim plans to investigate if other combinatorial optimization problems, particularly minimization problems, admit such a pricing-based approach for good approximations and to what extent this technique is general, meaning that any (good) algorithm has to follow this paradigm. Kesselheim’s study of pricing-based mechanisms and Röglin’s work on local search dynamics have important connections with questions studied in RA C2 on learning dynamics, auctions, and decentralized markets. We will also advance our techniques to approach some key NP-hard problems, finding optimal or near-optimal solutions much faster than worst-case analysis predicts. Explaining why dynamic programming algorithms such as the theoretically fastest exact algorithms for TSP and Steiner tree are usually much faster than the worst-case bound tells [HSV17] is another goal. With Franke’s work [FKBJ17] in algorithmic number theory, we will further expand the scope of complexity analysis beyond the worst case. Moreover, Neeman’s research on planted bisection models (RA B3) and the research on stochastic dynamics and multi-agent bandit problems (RA B1) have the potential to yield novel tools for beyond-worst-case analysis.  

Algorithms for chip design and vehicle routing. Held, Hougardy, and Vygen will continue developing the BonnTools, algorithms for chip design that are being used in industry for designing the most complex structures ever. After our recent global routing algorithm with timing constraints [HMR+18], a unified global optimization would be the natural next step, but is an ambitious goal. We have ideas for integrating transistor sizing and buffering, so integrating placement will probably be the main challenge. This certainly requires a generalization of the underlying resource sharing approach, from which other applications would benefit as well. We also aim to develop faster exact algorithms for small but hard subproblems, such as in logic optimization and transistor-level layout, and to analyze their complexity. Overall, this will enable next-generation chips (in 7nm technology and beyond) to consume much less power while squeezing more functionality on the same area than ever. In vehicle routing, which contains the TSP as a special case, there are many practical approaches but so far much less theory than for the TSP itself. Together with our new partner DHL with headquarter in Bonn, Held and Vygen are currently exploring innovative delivery models in order to use fewer resources while serving increasing customer demands. This involves sameday delivery, heterogeneous pickup and deliveries, and customer-chosen delivery times. We plan to study such models theoretically and devise efficient algorithms for practical use.

Our research agenda aims to answer some of the most important open questions in the theory of combinatorial optimization, and to respond to the practical needs as we observe them in some crucial applications. Our close interaction between industrial practice and mathematical theory is constantly leading to new insights and will enable us to further reduce the gap between theory and practice.

[AMR11] D. Arthur, B. Manthey, and H. Röglin. Smoothed analysis of the k-means method. J. ACM, 58(5):19:1–19:31, 2011.

[BCM+15] T. Brunsch, K. Cornelissen, B. Manthey, H. Röglin, and C. Rösner. Smoothed analysis of the successive shortest path algorithm. SIAM J. Comput., 44(6):1798–1819, 2015.

[BR15] T. Brunsch and H. Röglin. Improved smoothed analysis of multiobjective optimization. J. ACM, 62(1):4:1–4:58, 2015.

[CHSS17] P. Cremer, S. Hougardy, J. Schneider, and J. Silvanus. Automatic cell layout in the 7nm era. In Proc. of the 2017 ACM Int. Symp. on Physical Design (ISPD), pages 99–106, 2017.

[DFKL17] P. Dütting, M. Feldman, T. Kesselheim, and B. Lucier. Prophet inequalities made easy: Stochastic optimization by pricing non-stochastic inputs. In Proc. of the 58th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pages 540–551, 2017.

[ER17] M. Etscheid and H. Röglin. Smoothed analysis of local search for the maximum-cut problem. ACM Trans. Algorithms, 13(2):25:1–25:12, 2017.

[FKBJ17] J. Franke, T. Kleinjung, J. Büthe, and A. Jost. A practical analytic method for calculating (x). Math. Comp., 86:2889–2909, 2017.

[HMR+18] S. Held, D. Müller, D. Rotter, R. Scheifele, V. Traub, and J. Vygen. Global routing with timing constraints. IEEE Trans. on CAD of Integr. Circuits Syst., 37:406–419, 2018.

[HS17] S. Held and S. T. Spirkl. Binary adder circuits of asymptotically minimum depth, linear size, and fan-out two. ACM Trans. Algorithms, 14(1):4:1–4:18, 2017.

[HSV17] S. Hougardy, J. Silvanus, and J. Vygen. Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm. Math. Program. Comput., 9(2):135–202, 2017.

[HV17] K. Heeger and J. Vygen. Two-connected spanning subgraphs with at most 10/7OPT edges. SIAM J. Discrete Math., 31(3):1820–1835, 2017.

[KV18] B. Korte and J. Vygen. Combinatorial Optimization: Theory and Algorithms. Springer, 6th edition, 2018.

[SV14] A. Seb˝o and J. Vygen. Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs. Combinatorica, 34(5):597– 629, 2014.

[TV18] V. Traub and J. Vygen. Approaching 3/2 for the s-t-path TSP. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1854–1864, 2018.