A progressive-ILP based routing algorithm for cross-referencing biochips

Ping Hung Yuh, Sachin Sapatnekar, Chia Lin Yang, Yao Wen Chang

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

67 Scopus citations


Due to recent advances in microfluidics technology, digital microfluidic biochips and their associated CAD problems have gained much attention, most of which has been devoted to direct-addressing biochips. In this paper, we solve the droplet routing problem under the more scalable crossreferencing biochip paradigm, which uses row/column addressing scheme to activate electrodes. We propose the first droplet routing algorithm that directly solves the problem of routing in cross-referencing biochips. The main challenge of this type of biochips is the electrode interference which prevents simultaneous movement of multiple droplets. We first present a basic integer linear programming (ILP) formulation to optimally solve the droplet routing problem. Due to its complexity, we also propose a progressive ILP scheme to determine the locations of droplets at each time step. Experimental results demonstrate the efficiency and effectiveness of our progressive ILP scheme on a set of practical bioassays.

Original languageEnglish (US)
Title of host publicationProceedings of the 45th Design Automation Conference, DAC
Number of pages6
StatePublished - 2008
Event45th Design Automation Conference, DAC - Anaheim, CA, United States
Duration: Jun 8 2008Jun 13 2008

Publication series

NameProceedings - Design Automation Conference
ISSN (Print)0738-100X


Other45th Design Automation Conference, DAC
Country/TerritoryUnited States
CityAnaheim, CA


  • Biochip
  • Microfluidics
  • Progressive-ILP
  • Routing


Dive into the research topics of 'A progressive-ILP based routing algorithm for cross-referencing biochips'. Together they form a unique fingerprint.

Cite this