%
% SECOND EXAMPLE for ICCAD:  Combined wire sizing and spacing
%

% circuit parameters
n = 6;         % number of nodes per wire
N = 3*n;       % total number of nodes
m = n-1;       % number of segments per wire 
alpha = 1;     % conductance per segment is is alpha*size 
beta = 0.5;    % capacitance per segment is twice beta*size 
gamma = 2;     % coupling capacitance is twice gamma*distance
G0 = 100;      % source conductance
C01 = 10;      % load of first wire
C02 = 20;      % load of second wire
C03 = 30;      % load of third wire    
wmin = 0.1;    % minimum width
wmax = 2.0;    % maximum width 
smin = 1.0;    % minimum distance between wires
smax = 50;     % upper bound on s1 and s2  (meant to be inactive)

% capacitance matrix
CC = zeros(N*N, 5*m+3);

% constant terms
CC(N*(n-1)+n,1) = C01;
CC(N*(2*n-1)+2*n,1) = C02;
CC(N*(3*n-1)+3*n,1) = C03;

% capacitances to ground
for i=1:m 

   % first wire
   CC([(i-1)*N+i, i*N+i+1], i+1) = beta*[1;1];

   % second wire
   CC([(n+i-1)*N+n+i, (n+i)*N+n+i+1], m+i+1) = beta*[1;1];

   % third wire
   CC([(2*n+i-1)*N+2*n+i, (2*n+i)*N+2*n+i+1], 2*m+i+1) = beta*[1;1];

end;

% coupling capacitors
for i=1:m

   % between first and second wire
   CC([(i-1)*N+i, (i-1)*N+n+i, ...
       (n+i-1)*N+i, (n+i-1)*N+n+i], 3*m+1+i) ...
   = CC([(i-1)*N+i, (i-1)*N+n+i, ...
         (n+i-1)*N+i, (n+i-1)*N+n+i], 3*m+1+i) + gamma*[1;-1;-1;1];

   CC([i*N+i+1, i*N+n+i+1, (n+i)*N+i+1, (n+i)*N+n+i+1], 3*m+1+i) ...
   = CC([i*N+i+1, i*N+n+i+1, (n+i)*N+i+1, (n+i)*N+n+i+1], 3*m+1+i) ...
      + gamma*[1;-1;-1;1];

   % between second and third wire
   CC([(n+i-1)*N+n+i, (n+i-1)*N+2*n+i, (2*n+i-1)*N+n+i, ...
       (2*n+i-1)*N+2*n+i], 4*m+1+i) ...
   = CC([(n+i-1)*N+n+i, (n+i-1)*N+2*n+i, (2*n+i-1)*N+n+i, ...
         (2*n+i-1)*N+2*n+i], 4*m+1+i) + gamma*[1;-1;-1;1];

   CC([(n+i)*N+n+i+1, (n+i)*N+2*n+i+1, ...
       (2*n+i)*N+n+i+1, (2*n+i)*N+2*n+i+1], 4*m+1+i) ...
   = CC([(n+i)*N+n+i+1, (n+i)*N+2*n+i+1, ...
         (2*n+i)*N+n+i+1, (2*n+i)*N+2*n+i+1], 4*m+1+i) ...
     + gamma*[1;-1;-1;1];

end;


% conductance matrix
GG = zeros(N*N, 5*m+3);

% constant terms
GG(1,1) = G0; 
GG(n*N+n+1,1) = G0;
GG(2*n*N+2*n+1,1) = G0;

% segment conductances
for i=1:m

   % first wire
   GG([(i-1)*N+i, (i-1)*N+i+1, i*N+i, i*N+i+1], i+1) ...
   = GG([(i-1)*N+i, (i-1)*N+i+1, i*N+i, i*N+i+1], i+1) ...
     + alpha*[1;-1;-1;1];

   % second wire
   GG([(n+i-1)*N+n+i, (n+i-1)*N+n+i+1, ...
       (n+i)*N+n+i, (n+i)*N+n+i+1], m+i+1) ...
   = GG([(n+i-1)*N+n+i, (n+i-1)*N+n+i+1, ...
         (n+i)*N+n+i, (n+i)*N+n+i+1], m+i+1) + alpha*[1;-1;-1;1];

   % third wire
   GG([(2*n+i-1)*N+2*n+i, (2*n+i-1)*N+2*n+i+1, ...
       (2*n+i)*N+2*n+i, (2*n+i)*N+2*n+i+1], 2*m+i+1) ...
   = GG([(2*n+i-1)*N+2*n+i, (2*n+i-1)*N+2*n+i+1, ...
         (2*n+i)*N+2*n+i, (2*n+i)*N+2*n+i+1], 2*m+i+1) ...
     + alpha*[1;-1;-1;1];

end;


% LMI constraints
% 
%  G(x) - (1/delay)*C(x) (+t*I) >= 0   (LMI of size NxN)
%  
%  [(t1i+s1-w1i-0.5*w2i) 0                    2                    ]
%  [0                    (t1i+s1-w1i-0.5*w2i) (t1i-s1+w1i+0.5*w2i) ]
%  [2                    (t1i-s1+w1i+0.5*w2i) (t1i+s1-w1i-0.5*w2i) ]
%     (+t*I) >= 0 for i=1,...,m        (m LMIs of size 3x3) 
%
%  [(t2i+s2-w3i-0.5*w2i) 0                    2                    ]
%  [0                    (t2i+s2-w3i-0.5*w2i) (t2i-s2+w3i+0.5*w2i) ]
%  [2                    (t2i-s2+w3i+0.5*w2i) (t2i+s2-w3i-0.5*w2i) ]
%     (+t*I) >= 0 for i=1,...,m        (2m LMIs of size 3x3) 
%
%  s1 - w1 - 0.5*w2 (+t) .> smin; 
%  s2 - w3 - 0.5*w2 (+t) .> smin;      (2m scalars) 
%
%  w1,w2,w3 >= wmin
%  t1,t2  >= 0
%  s1,s2  >= 0                         (5m+2 scalars)
%
%  w1,w2,w3 <= wmax
%  t1,t2  <= 1/smin 
%  s1,s2  <= smax                      (5m+2 scalars)
%
 
% 5m+2 variables:
%
% x(1:m):      sizes of first wire  (w1 in paper)
% x(m+1:2m):   sizes of second wire (w2 in paper)
% x(2m+1:3m):  sizes of third wire (w3 in paper)
% x(3m+1:4m):  inverse of distances between wire 1 and 2 (t1 in paper)
% x(4m+1:5m):  inverse of distances between wire 2 and 3 (t2 in paper)
% x(5m+1):     s1
% x(5m+2):     s2


FF = zeros(N*N + 2*m*9 + 2*m + 2*(5*m+2), 5*m+4);
blck_szs = [N; 3*ones(2*m,1); ones(12*m+4,1)]; 

% identity matrix in last column
FF(1:N*N,5*m+4) = reshape(eye(N),N*N,1);
for i=1:m
   FF(N*N+(i-1)*9+[1:9],5*m+4) = reshape(eye(3),9,1);
   FF(N*N+m*9+(i-1)*9+[1:9],5*m+4) = reshape(eye(3),9,1);
end
FF(N*N+m*18+[1:2*m],5*m+4) = ones(2*m,1);

% hyperbolic constraints
%  [(t1i+s1-w1i-0.5*w2i) 0                    2                    ]
%  [0                    (t1i+s1-w1i-0.5*w2i) (t1i-s1+w1i+0.5*w2i) ]
%  [2                    (t1i-s1+w1i+0.5*w2i) (t1i+s1-w1i-0.5*w2i) ]
%     (+t*I) >= 0 for i=1,...,m        (m LMIs of size 3x3) 
%
%  [(t2i+s2-w3i-0.5*w2i) 0                    2                    ]
%  [0                    (t2i+s2-w3i-0.5*w2i) (t2i-s2+w3i+0.5*w2i) ]
%  [2                    (t2i-s2+w3i+0.5*w2i) (t2i+s2-w3i-0.5*w2i) ]
%     (+t*I) >= 0 for i=1,...,m        (2m LMIs of size 3x3) 

for i=1:m

   % constant term in position 3 and 7
   FF(N*N+(i-1)*9+[3,7],1) = [2;2];
   FF(N*N+m*9+(i-1)*9+[3,7],1) = [2;2];

   % s1, s2 term
   FF(N*N+(i-1)*9+[1,5,6,8,9],5*m+2) = [1;1;-1;-1;1];
   FF(N*N+m*9+(i-1)*9+[1,5,6,8,9],5*m+3) = [1;1;-1;-1;1];

   % w1 terms
   FF(N*N+(i-1)*9+[1,5,6,8,9],1+i) = [-1;-1;1;1;-1];

   % w2 terms
   FF(N*N+(i-1)*9+[1,5,6,8,9],1+m+i) = 0.5*[-1;-1;1;1;-1];
   FF(N*N+m*9+(i-1)*9+[1,5,6,8,9],1+m+i) = 0.5*[-1;-1;1;1;-1];

   % w3 terms
   FF(N*N+m*9+(i-1)*9+[1,5,6,8,9],1+2*m+i) = [-1;-1;1;1;-1];

   % t1 terms
   FF(N*N+(i-1)*9+[1,5,6,8,9],1+3*m+i) = [1;1;1;1;1];

   % t2 terms
   FF(N*N+m*9+(i-1)*9+[1,5,6,8,9],1+4*m+i) = [1;1;1;1;1];

end;

%  s1 - w1 - 0.5*w2 .> smin; 
%  s2 - w3 - 0.5*w2 .> smin;    (2m scalars) 

FF(N*N+m*18+[1:m],1+[1:m]) = -eye(m);          %w1
FF(N*N+m*18+[1:m],m+1+[1:m]) = -0.5*eye(m);    %w2
FF(N*N+m*18+[1:m],5*m+2) = ones(m,1);          %s1

FF(N*N+m*18+m+[1:m],1+2*m+[1:m]) = -eye(m);    %w3
FF(N*N+m*18+m+[1:m],m+1+[1:m]) = -0.5*eye(m);  %w2
FF(N*N+m*18+m+[1:m],5*m+3) = ones(m,1);        %s1

% lower bounds 
FF(N*N+m*18+2*m+[1:5*m+2],1+[1:5*m+2]) = eye(5*m+2);
FF(N*N+m*18+2*m+5*m+2+[1:5*m+2],1+[1:5*m+2]) = -eye(5*m+2);

% cost function
c = [zeros(5*m,1); 1; 1];


%%%%%%%%%%  compute two solutions  %%%%%%%%%%

% tolerances for SP
abstol = 1e-6;
reltol = 1e-6;

% two points on the tradeoff curve
delays = [130 90];
sizes = zeros(5*m+2,2);

for j=[1,2]
   
   delay = delays(j);
   disp([' ']);
   disp(['Compute solution ', int2str(j), ...
        ' (delay = ', num2str(delay), ').']);

   % first block of F(x) = G(x) - (1/delay)*C(x)
   FF(1:N*N,1:5*m+3) = GG - (1/delay)*CC;

   % try very thick wire
   x0 = 0.99*[wmax*ones(3*m,1); (1/smin)*ones(2*m,1); smax; smax];  
   t = min(eig(reshape(FF(1:N*N,1:5*m+3)*[1;x0],N,N)));
   for i=1:2*n
      t = min(t, min(eig(reshape(FF(N*N+(i-1)*9+[1:9],1:5*m+3) ...
         * [1;x0],3,3))));
   end;

   feasible = 1;
   if (t <= 0)  % x0 is infeasible, run phase 1

      disp([' ']);  disp(['Phase 1.']);

      % use slightly tighter bounds on x to ensure strict feasibility
      FF(N*N+18*m+2*m+[1:3*m],1) = -(1-1e-5)*wmin*ones(3*m,1);
      FF(N*N+18*m+2*m+3*m+[1:2*m+2],1) = -1e-5*ones(2*m+2,1);

      FF(N*N+18*m+2*m+5*m+2+[1:3*m],1) = (1-1e-5)*wmax*ones(3*m,1);
      FF(N*N+18*m+2*m+8*m+2+[1:2*m],1) = (1-1e-5)*(1/smin)*ones(2*m,1);
      FF(N*N+18*m+2*m+10*m+2+[1:2],1) = (1-1e-5)*smax*ones(2,1);
     
      % dual feasible solution
      Z0 = zeros(sum(blck_szs.^2),1);
      Z0(1:N*N) = reshape(eye(N)/(N+6*m+2*m),N*N,1);
      for i=1:2*m
         Z0(N*N+9*(i-1)+[1:9]) = reshape(eye(3)/(N+6*m+2*m),9,1);
      end;
      Z0(N*N+18*m+[1:2*m]) = ones(2*m,1)/(N+6*m+2*m);
      z = FF(1:(N*N+18*m+2*m),2:5*m+3)' * Z0(1:N*N+18*m+2*m);
      Z0(N*N+18*m+2*m+[1:10*m+4]) = [-min(z,0)+1e-3; max(z,0)+1e-3 ];

      % call SP
      [x,Z,ul,info,time] = sp(FF, blck_szs, [zeros(5*m+2,1);1], ...
          [x0; -1.1*t], Z0, 10.0, abstol, -1.0, 0.0, 100);

      if (ul(1) >= 0),
         if (ul(2) >= 0),
            disp(['Infeasible.']);
         else
            disp(['Feasibility could not be determined.']);
         end;
         feasible = 0;
      else x0 = x(1:5*m+2);    % initial point for phase 2.
      end;

   end;

   if (feasible) % use x0 as starting point, run phase 2

      disp([' ']); disp(['Phase 2.']);

      % use original bounds on x again
      FF(N*N+18*m+2*m+[1:3*m],1) = -wmin*ones(3*m,1);
      FF(N*N+18*m+2*m+3*m+[1:2*m+2],1) = zeros(2*m+2,1);

      FF(N*N+18*m+2*m+5*m+2+[1:3*m],1) = wmax*ones(3*m,1);
      FF(N*N+18*m+2*m+8*m+2+[1:2*m],1) = (1/smin)*ones(2*m,1);
      FF(N*N+18*m+2*m+10*m+2+[1:2],1) = smax*ones(2,1);

      % dual feasible point
      Z0 = zeros(sum(blck_szs.^2),1);
      Z0(1:N*N) = reshape(eye(N)/(N+6*m+2*m),N*N,1);
      for i=1:2*m
         Z0(N*N+9*(i-1)+[1:9]) = reshape(eye(3)/(N+6*m+2*m),9,1);
      end;
      Z0(N*N+18*m+[1:2*m]) = ones(2*m,1)/(N+6*m+2*m);
      z = FF(1:(N*N+18*m+2*m),2:5*m+3)' * Z0(1:N*N+18*m+2*m) - c;
      Z0(N*N+18*m+2*m+[1:10*m+4]) = [-min(z,0)+1e-3; max(z,0)+1e-3 ];

      % call SP
      [sizes(:,j),Z,ul,info,time] = sp(FF(:,1:5*m+3), blck_szs, c, ...
          x0, Z0, 10.0, abstol, reltol, 0.0, 100);

      % optimal value

   end;

end;


%%%%%%%%%%  show first solution  %%%%%%%%%%

figure(1); 
hold off;
colormap(gray);

w1 = sizes(1:m,1);
w2 = sizes(m+[1:m],1);
w3 = sizes(2*m+[1:m],1);
s1 = sizes(5*m+1,1);
s2 = sizes(5*m+2,1);

x = zeros(10,1);
x([1:2:2*m-1],:) = [0:m-1]';
x([2:2:2*m],:) = [1:m]';

width1 = zeros(2*m,1);
width1([1:2:2*m-1]) = s1+s2-w1;
width1([2:2:2*m]) = s1+s2-w1;

width2a = zeros(2*m,1);
width2a([1:2:2*m-1]) = s2+w2/2;
width2a([2:2:2*m]) = s2+w2/2;
width2b = zeros(2*m,1);
width2b([1:2:2*m-1]) = s2-w2/2;
width2b([2:2:2*m]) = s2-w2/2;

width3 = zeros(2*m,1);
width3([1:2:9]) = w3;
width3([2:2:10]) = w3;

plot([x;flipud(x);0], [width1;(s1+s2)*ones(size(x));width1(1)],'-', ...
     [x;flipud(x);0], [width2a;flipud(width2b);width2a(1)], '-', ...
     [x;flipud(x);0], [width3;zeros(size(x));width3(1)], '-');
axis([-0.1, m+0.1,-0.1, s1+s2+0.1]);
hold on
fill([x;m;0]',[width1;s1+s2;s1+s2]', 0.9*ones(size([x;m;0]')));
fill([x;flipud(x)]',[width2a;flipud(width2b)]', ...
     0.9*ones(size([x;x]')));
fill([x;m;0]',[width3;0;0]', 0.9*ones(size([x;0;0]')));
caxis([-1,1])
plot([x;flipud(x);0], [width1;(s1+s2)*ones(size(x));width1(1)],'-', ...
     [x;flipud(x);0], [width2a;flipud(width2b);width2a(1)], '-', ...
     [x;flipud(x);0], [width3;zeros(size(x));width3(1)], '-');

set(gca,'XTick',[0 1 2 3 4 5 ]);
set(gca,'YTick',[0 1 2 3 4 5 6]);
title('Solution 1.');


%%%%%%%%%%  step responses for first solution  %%%%%%%%%%

% conductance and capacitance
G = reshape(GG*[1;sizes(:,1)],N,N);
C = reshape(CC*[1;sizes(:,1)],N,N);

% state space model
A = -inv(C)*G;
B = inv(C)*G*[ones(n,1), zeros(n,2); zeros(n,1), ones(n,1), zeros(n,1);
              zeros(n,2), ones(n,1)];
CCC = eye(N);
D = zeros(N,3);

% calculate response to step at 1st input
figure(2); hold off;

T = linspace(0,2*delays(1),1000);
[Y1,X1] = step(A,B,CCC,D,1,T);
hold off; plot(T,Y1(:,[n,2*n,3*n]),'-');  hold on;
text(T(1000),Y1(1000,n),'v1');
text(T(1000),Y1(1000,2*n),'v2');
text(T(1000),Y1(1000,3*n),'v3');
axis([0 2*delays(1) -0.1 1.1]); 

% show dominant time constant
plot(delays(1)*[1;1], [-0.1;1.1], '--');

set(gca,'XTick',[0 100 200]);
set(gca,'YTick',[0 0.5 1]);
title('1st solution.  Step at 1st input.');



% response to step at 2nd input
figure(3);  hold off;

[Y2,X2] = step(A,B,CCC,D,2,T);
hold off; plot(T,Y2(:,[n,2*n,3*n]),'-');  hold on;
text(T(1000),Y2(1000,n),'v1');
text(T(1000),Y2(1000,2*n),'v2');
text(T(1000),Y2(1000,3*n),'v3');
axis([0 2*delays(1) -0.1 1.1]); 

plot(delays(1)*[1;1], [-0.1;1.1], '--');

set(gca,'XTick',[0 100 200]);
set(gca,'YTick',[0 0.5 1]);
title('1st solution.  Step at 2nd input.');


% response to step at 3rd input
figure(4);  hold off;

[Y3,X3] = step(A,B,CCC,D,3,T);
hold off; plot(T,Y3(:,[n,2*n,3*n]),'-');  hold on;
text(T(1000),Y3(1000,n),'v1');
text(T(1000),Y3(1000,2*n),'v2');
text(T(1000),Y3(1000,3*n),'v3');
axis([0 2*delays(1) -0.1 1.1]); 

plot(delays(1)*[1;1], [-0.1;1.1], '--');

set(gca,'XTick',[0 100 200]);
set(gca,'YTick',[0 0.5 1]);
title('1st solution.  Step at 3rd input.');



%%%%%%%%%%  show second solution  %%%%%%%%%%

figure(5); hold off;
colormap(gray);

w1 = sizes(1:m,2);
w2 = sizes(m+[1:m],2);
w3 = sizes(2*m+[1:m],2);
s1 = sizes(5*m+1,2);
s2 = sizes(5*m+2,2);

x = zeros(10,1);
x([1:2:2*m-1],:) = [0:m-1]';
x([2:2:2*m],:) = [1:m]';

width1 = zeros(2*m,1);
width1([1:2:2*m-1]) = s1+s2-w1;
width1([2:2:2*m]) = s1+s2-w1;

width2a = zeros(2*m,1);
width2a([1:2:2*m-1]) = s2+w2/2;
width2a([2:2:2*m]) = s2+w2/2;
width2b = zeros(2*m,1);
width2b([1:2:2*m-1]) = s2-w2/2;
width2b([2:2:2*m]) = s2-w2/2;

width3 = zeros(2*m,1);
width3([1:2:9]) = w3;
width3([2:2:10]) = w3;

plot([x;flipud(x);0], [width1;(s1+s2)*ones(size(x));width1(1)],'-', ...
     [x;flipud(x);0], [width2a;flipud(width2b);width2a(1)], '-', ...
     [x;flipud(x);0], [width3;zeros(size(x));width3(1)], '-');
axis([-0.1, m+0.1,-0.1, s1+s2+0.1]);
hold on
fill([x;m;0]',[width1;s1+s2;s1+s2]', 0.9*ones(size([x;m;0]')));
fill([x;flipud(x)]',[width2a;flipud(width2b)]', ...
     0.9*ones(size([x;x]')));
fill([x;m;0]',[width3;0;0]', 0.9*ones(size([x;0;0]')));
caxis([-1,1])
plot([x;flipud(x);0], [width1;(s1+s2)*ones(size(x));width1(1)],'-', ...
     [x;flipud(x);0], [width2a;flipud(width2b);width2a(1)], '-', ...
     [x;flipud(x);0], [width3;zeros(size(x));width3(1)], '-');

set(gca,'XTick',[0 1 2 3 4 5 ]);
set(gca,'YTick',[0 2 4 6 8 10 12 14]);
title('Solution 2.');


%%%%%%%%%%  step responses for second solution  %%%%%%%%%%

% conductance and capacitance
G = reshape(GG*[1;sizes(:,2)],N,N);
C = reshape(CC*[1;sizes(:,2)],N,N);

% state space model
A = -inv(C)*G;
B = inv(C)*G*[ones(n,1), zeros(n,2); zeros(n,1), ones(n,1), zeros(n,1);
              zeros(n,2), ones(n,1)];
CCC = eye(N);
D = zeros(N,3);


% calculate response to step at 1st input
figure(6); hold off;

T = linspace(0,2*delays(2),1000);
[Y1,X1] = step(A,B,CCC,D,1,T);
hold off; plot(T,Y1(:,[n,2*n,3*n]),'-');  hold on;
text(T(1000),Y1(1000,n),'v1');
text(T(1000),Y1(1000,2*n),'v2');
text(T(1000),Y1(1000,3*n),'v3');
axis([0 2*delays(2) -0.1 1.1]); 

% show dominant time constant
plot(delays(2)*[1;1], [-0.1;1.1], '--');

set(gca,'XTick',[0 50 100 150]);
set(gca,'YTick',[0 0.5 1]);
title('2nd solution.  Step at 1st input.');




% response to step at 2nd input
figure(7);  hold off;

[Y2,X2] = step(A,B,CCC,D,2,T);
hold off; plot(T,Y2(:,[n,2*n,3*n]),'-');  hold on;
text(T(1000),Y2(1000,n),'v1');
text(T(1000),Y2(1000,2*n),'v2');
text(T(1000),Y2(1000,3*n),'v3');
axis([0 2*delays(2) -0.1 1.1]); 

plot(delays(2)*[1;1], [-0.1;1.1], '--');
text(delays(2),-0.1,'T');
set(gca,'XTick',[0 50 100 150]);
set(gca,'YTick',[0 0.5 1]);
title('2nd solution.  Step at 2nd input.');



% response to step at 3rd input
figure(8);  hold off;

[Y3,X3] = step(A,B,CCC,D,3,T);
hold off; plot(T,Y3(:,[n,2*n,3*n]),'-');  hold on;
text(T(1000),Y3(1000,n),'v1');
text(T(1000),Y3(1000,2*n),'v2');
text(T(1000),Y3(1000,3*n),'v3');
axis([0 2*delays(2) -0.1 1.1]); 

plot(delays(2)*[1;1], [-0.1;1.1], '--');

set(gca,'XTick',[0 50 100 150]);
set(gca,'YTick',[0 0.5 1]);
title('2nd solution.  Step at 3rd input.');
