TY - JOUR
T1 - A two-stage integer linear programming-based droplet routing algorithm for pin-constrained digital microfluidic biochips
AU - Huang, Tsung Wei
AU - Ho, Tsung Yi
N1 - Manuscript received June 2, 2010; revised August 17, 2010; accepted October 5, 2010. Date of current version January 19, 2011. This work was supported in part by National Science Council of Taiwan, under Grants NSC 99-2220-E-006-013 and NSC 99-2221-E-006-220. This paper was recommended by Associate Editor P. Saxena.
PY - 2011/2
Y1 - 2011/2
N2 - With the increasing design complexities, the design of pin-constrained digital microfluidic biochips (PDMFBs) is of practical importance for the emerging marketplace. However, solutions of current pin-count reduction are 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 reduction with droplet routing stage. Furthermore, our algorithm is capable of minimizing the number of control pins, the number of used cells, and the droplet routing time. We first present a basic integer linear programming (ILP) formulation to optimally solve the droplet routing problem for PDMFBs with simultaneous multiobjective 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 routing time, we obtain much better achievement than all the state-of-the-art algorithms in any aspect.
AB - With the increasing design complexities, the design of pin-constrained digital microfluidic biochips (PDMFBs) is of practical importance for the emerging marketplace. However, solutions of current pin-count reduction are 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 reduction with droplet routing stage. Furthermore, our algorithm is capable of minimizing the number of control pins, the number of used cells, and the droplet routing time. We first present a basic integer linear programming (ILP) formulation to optimally solve the droplet routing problem for PDMFBs with simultaneous multiobjective 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 routing time, we obtain much better achievement than all the state-of-the-art algorithms in any aspect.
KW - Broadcast-addressing biochips
KW - integer linear programming
KW - routing
UR - http://www.scopus.com/inward/record.url?scp=78951476744&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=78951476744&partnerID=8YFLogxK
U2 - 10.1109/TCAD.2010.2097190
DO - 10.1109/TCAD.2010.2097190
M3 - Article
AN - SCOPUS:78951476744
SN - 0278-0070
VL - 30
SP - 215
EP - 228
JO - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
JF - IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
IS - 2
M1 - 5689349
ER -