Hardware Reference
In-Depth Information
column of the array is written as
EG
m,n
. In any electrode group
EG
m,n
, the number
of electrodes that are connected to any Pin i is defined as N
i,m,n
, which can be
written as:
N
i,m,n
D
x
i,m,n
C
x
i,m+1,n
C
x
i,m-1,n
C
x
i,m,n+1
C
x
i,m,n-1
:
(6.2)
Therefore, Constraint
1
of Sect.
6.1
can be written as the following set of
constraints: N
i,m,n
1,
8
1
i
L, 1
m
M; 1
n
N .
The Constraint
2
of Sect.
6.1
can be further derived as follows. For two electrode
groups
EG
m,n
and
EG
m+p,n+q
,ifp and q are integers and
j
p
jCj
q
j
3, then these two
electrode group are non-overlapping. Based on the definition given by Equation
6.2
,
for
EG
m+p,n+q
, the number of electrodes that are connected to Pin i is N
i,m+p,n+q
.
For
EG
m,n
and
EG
m+p,n+q
, the numbers of electrodes that are connected to another
Pin j are written as N
j,m,n
and N
j,m+p,n+q
, respectively. Assume that Constraint
2
in
Sect.
6.1
is violated, and
EG
m,n
and
EG
m+p,n+q
share Pin i and Pin j . Then there
will be: N
i,m,n
1, N
i,m+p,n+q
1, N
j,m,n
1,andN
j,m+p,n+q
1. Therefore, when
Constraint
2
is violated, there must exist integers i , j , m, n, p,andq, such that
N
i,m,n
C
N
i,m+p,n+q
C
N
j,m,n
C
N
j,m+p,n+q
4. In order to make sure Constraint
2
is
not violated, we have the following inequalities:
N
i,m,n
C
N
i,m+p,n+q
C
N
j,m,n
C
N
j,m+p,n+q
3;
8
1
i
ยค
j
L; 1
m
M; 1
n
N;
j
p
jCj
q
j
3:
(6.3)
Using standard techniques, the objective function given by (
6.1
) can be lin-
earized. This completes the ILP model for optimization. For the M
N microfluidic
array, the number of CEGs is
MN
. The number of inequalities derived from
Constraint
1
and Constraint
2
are O.MNL/ and O.M
2
N
2
L
2
/, respectively. Thus
for the ILP model introduced above, the number of variables in the ILP model is
O.MNL/, and the number of constraints is O.M
2
N
2
L
2
/. It is important to note
that, since L is a loose upper bound for the number of pins, we have L =O.MN /.
The ILP model is clearly not scalable for a large problem instance; nevertheless, we
use it to evaluate the quality of the heuristic solution that will be discussed in the
next section.
6.4
Heuristic Optimization Method
The ILP model introduced in Sect.
6.3
has high computational complexity. The
CPU time is unacceptable for large biochips. In this section, we discuss a heuristic
algorithm to efficiently generate a pin-assignment configuration; the pseudocode
for this algorithm is shown in Fig.
6.3
. The algorithm includes two phases; the
first phase is to establish a lower bound on the number of pins, and the second
phase is to construct the pin-assignment configuration in a greedy fashion. In order
