Recent work has shown that machine-learned predictions can provably improve the performance of classic algorithms. In this work, we propose the first minimum-cost network flow algorithm augmented with a dual prediction. Our method is based on a classic minimum-cost flow algorithm, namely ε-relaxation. We provide time complexity bounds in terms of the infinity norm prediction error, which is both consistent and robust. We also prove sample complexity bounds for PAC-learning the prediction. We empirically validate our theoretical results on two applications of minimum-cost flow, i.e., traffic networks and chip escape routing, in which we learn a fixed prediction, and a feature-based neural network model to infer the prediction, respectively. Experimental results illustrate 12.74× and 1.64× average speedup on two applications.

Wirelength is the fundamental metric for VLSI routing. With the advancement of new technologies, wire delay has also become a significant factor for timing performances. It is thus necessary to consider both wirelength and delay in routing tree construction, i.e., timing-driven routing trees. Prior methods propose various heuristics to balance wirelength and delay with a tunable parameter, which cannot compute the full Pareto frontier. In this work, we propose PatLabor, a practical method for timing-driven routing. PatLabor directly optimizes the Pareto set, which obtains tighter Pareto curves than prior methods and does not require parameter tuning. PatLabor obtains all Paretooptimal solutions on small-degree nets up to 9 pins and is theoretically guaranteed by provable time complexity and approximation bounds. Experimental results verify our theoretical findings and show that PatLabor obtains tighter Pareto curves than state-of-the-art methods on ICCAD-15 benchmarks. For example, PatLabor obtains up to 58.5% more Pareto-optimal solutions than prior methods for degree-9 nets.

Triple patterning lithography (TPL) has been recognized as one of the most promising solutions to print critical features in advanced technology nodes. A critical challenge within TPL is the effective assignment of the layout to masks. Recently, various layout decomposition methods and TPL-aware routing methods have been proposed to consider TPL. However, these methods typically result in numerous conflicts and stitches, and are mainly designed for 2-pin nets. This paper proposes a multipin net routing method in triple patterning lithography, called Mr.TPL. Experimental results demonstrate that Mr.TPL reduces color conflicts by 81.17%, decreases stitches by 76.89%, and achieves up to $5.4 \times$ speed improvement compared to the state-of-the-art TPL-aware routing method.

Multi-objective optimization problems arise widely in various fields. In practice, multi-objective optimization is generally solved by heuristics with tunable parameters that are highly application-specific. Tuning parameters based on real-world instances (a.k.a. algorithm configuration) are generally empirical without theoretical guarantees. In this work, we establish the theoretical foundation of data-driven multi-objective optimization through the lens of machine learning theory. We provide generalization guarantees on selecting parameters for multi-objective optimization algorithms based on sampled problem instances. Moreover, if the performance metric of the algorithm is the Pareto volume, we can PAC-learn the approximately optimal configuration in polynomial time. We apply our framework to various algorithms, including approximation algorithms, local search, and linear programming. Experiments on multiple problems verify our theoretical findings.

Algorithm configuration, which involves selecting algorithm parameters based on sampled problem instances, is a crucial step in applying modern algorithms such as SAT solvers. Although prior work has attempted to understand the theoretical foundations of algorithm configuration, we still lack a comprehensive understanding of why practical algorithm configurators exhibit strong generalization performances in real-world scenarios. In this paper, through the lens of machine learning theory, we provide an algorithm-dependent generalization bound for the widely used model-based algorithm configurators under mild assumptions. Our approach is based on the algorithmic stability framework for generalization bounds. To the best of our knowledge, this is the first generalization bound that applies to a model closely approximating practical model-based algorithm configurators.

Ordered escape routing is a critical stage for printed circuit board design. State-of-the-art solutions to ordered escape routing are either heuristic and non-optimal, or trapped in exponential time complexity. In this work, for the first time, we prove that ordered escape routing is not only NP-hard, but also hard to approximate in polynomial time, indicating the limitation of optimal algorithms. We further present NeuroEscape, an efficient ordered escape routing method, which is based on reinforcement learning with a Monte-Carlo tree search (MCTS) and heuristic rollouts for design space exploration. A neural policy model is incorporated to further enhance the MCTS process. Theoretical results show that the number of samples required to train the model is upper bounded by a polynomial. Experimental results show that NeuroEscape solves 69% more testcases, with an average acceleration of 19.4x compared with state-of-the-art methods.

Programmable microfluidic devices (PMDs) have emerged as a new software-controlled architecture for next-generation flow-based biochips. These devices can be dynamically reconfigured to perform different bioassays flexibly and efficiently owing to their 2-D regularly arranged valve structure. However, PMDs are confronted with critical contamination issues due to the matrix-like structure with intersecting channels. In this article, a block-flushing method is proposed for contamination removal, based on which an overall contamination-aware synthesis flow is proposed. In the proposed block-flushing approach, contaminated areas are first collected according to specific patterns and then flushed as a whole to increase washing efficiency. Then, the synthesis flow integrating the block-flushing method is further optimized such that functional bioassay operations and washing operations can be performed simultaneously for higher efficiency. Experimental results demonstrate that the proposed washing approach reduces the washing time by 28% on commonly used bioassays. Equipped with the proposed washing method, our contamination-aware synthesis flow effectively reduces 30% of the completion time of the bioassays compared with the baseline method.

Escape routing, especially ordered escape routing, is a critical design stage for both printed circuit boards (PCBs) and integrated fan-out (InFO) wafer-level chip-scale packages. Previous works formulate ordered escape routing as boolean satisfiability (SAT) or integer linear programming (ILP) problems. Although optimal routing solutions can be obtained by above-mentioned approaches, the runtime is unacceptable for large-scale designs due to the exponential time complexity of SAT and ILP solvers. In this paper, we first attempt to address ordered escape routing problems with machine learning. We propose a learning-based method to accelerate existing solvers by reducing the solution space of the original problem. The proposed method is flexible, which can be combined with different ordered escape routing algorithms. Specifically, a fully convolutional neural network is trained to predict the probability of each routing grid to be occupied by routing paths. Thus, routing grids with low-probability usage can be removed to reduce the solution space. Experimental results show that the proposed method is effective for both SAT and ILP solvers of ordered escape routing. It achieves an acceleration of 4∼ 370x on average, with a slight increase in the total wirelength. Also, our model has a strong generalization ability. Although it is trained on $10\times 10$ pin array problems, it works well on larger problem sizes such as 14 x 14.