A two-stage ILP-based droplet routing algorithm for pin-constrained digital microfluidic biochips

Tsung-Wei Huang, Tsung Yi Ho

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationISPD'10 - Proceedings of the 2010 ACM International Symposium on Physical Design
Pages201-208
Number of pages8
DOIs
StatePublished - May 19 2010
Externally publishedYes
Event2010 ACM International Symposium on Physical Design, ISPD'10 - San Francisco, CA, United States
Duration: Mar 14 2010Mar 17 2010

Publication series

NameProceedings of the International Symposium on Physical Design

Other

Other2010 ACM International Symposium on Physical Design, ISPD'10
CountryUnited States
CitySan Francisco, CA
Period3/14/103/17/10

    Fingerprint

Keywords

  • Biochip
  • ILP
  • Microfluidic
  • Routing

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Cite this

Huang, T-W., & Ho, T. Y. (2010). A two-stage ILP-based droplet routing algorithm for pin-constrained digital microfluidic biochips. In ISPD'10 - Proceedings of the 2010 ACM International Symposium on Physical Design (pp. 201-208). (Proceedings of the International Symposium on Physical Design). https://doi.org/10.1145/1735023.1735068