A two-stage integer linear programming-based droplet routing algorithm for pin-constrained digital microfluidic biochips

Tsung Wei Huang, Tsung Yi Ho

Research output: Contribution to journalArticlepeer-review

Abstract

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.

Original languageEnglish (US)
Article number5689349
Pages (from-to)215-228
Number of pages14
JournalIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
Volume30
Issue number2
DOIs
StatePublished - Feb 1 2011

Keywords

  • Broadcast-addressing biochips
  • integer linear programming
  • routing

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'A two-stage integer linear programming-based droplet routing algorithm for pin-constrained digital microfluidic biochips'. Together they form a unique fingerprint.

Cite this