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

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 cross-referencing 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 bio assays.