A Two-Stage ILP-Based Droplet Routing Algorithm for Pin-Constrained Digital Microfluidic Biochips

摘要

With the increasing design complexities, the design of pin-constrained digital microfluidic biochips (PDMFBs) is of practical importance for the emerging marketplace. However, the solution of current pin-count aware technique is inevitably limited by simply adopting it after the droplet routing stage. In this paper, we propose the first droplet routing algorithm for PDMFBs that can integrate pin-count technique with droplet routing stage. Furthermore, our algorithm is capable of simultaneously minimizing the number of control pins, the number of used cells, and the latest arrival time. We first present a basic integer linear programming (ILP) formulation to optimally solve the droplet routing problem for PDMFBs with simultaneous multi-objective optimization. Due to the complexity of this ILP formulation, we also propose a two-stage technique of global routing followed by incremental ILP-based routing to reduce the solution space. To further reduce the runtime, we present a deterministic ILP formulation that casts the original routing optimization problem into a decision problem, and solve it by a binary solution search method that searches in logarithmic time. Extensive experiments demonstrate that in terms of the number of the control pins, the number of the used cells, and the latest arrival time, we acquire much better achievement than all the state-of-the-art algorithms in any aspect.