Lindo Systems
! Given the nonzero structure of a matrix, identify a set of
linking rows,
linking cols, and
two independent blocks, so as to
maximize the weighted combination of minimum rows and cols in a block;
! Keywords: Decomposition, Matrix decomposition;
SETS:
ROW: ISROW;
COL: ISCOL;
NONZ(ROW, COL);
BLK: NR, NC;
BXR( BLK, ROW): yr;
BXC( BLK, COL): yc;
ENDSETS
DATA:
wgtr = 64; ! Weight on maximizing min rows in a block;
wgtc = 64; ! Weight on maximizing min cols in a block;
wgtb = 64; ! Weight on maximizing min(rows,cols) in a block;
BLK = 1..2;
! Matrix from Catalyurek, Aykanat, and Ucar (2010), SIAM J. of Scientific Computing;
ROW = 1..16;
COL = 1..16;
NONZ=
1,1 1,10
2,2 2,5
3,3 3,6
4,2 4,4 4,11 4,14 4,16
5,1 5,5 5,13
6,5 6,6
7,2 7,5 7,7 7,9
8,4 8,8
9,9 9,12 9,15
10,1 10,7 10,9 10,10 10,13
11,3 11,11 11,14
12,12 12,16
13,5 13,13
14,4 14,5 14,6 14,12 14,14
15,9 15,15
16,4 16,8 16,16;
! Matrix from Fig. 2 of Catalyurek and Aykanat;
! ROW = 1..10;
! COL = 1..10;
! The (i,j)'s of the nonzero structure;
! NONZ =
1,1 1,2 1,6
2,2 2,3 2,5
3,2 3,3 3,5
4,1 4,3 4,4 4,7 4,8
5,5 5,7
6,6 6,7 6,9
7,4 7,5 7,6 7,7
8,4 8,8 8,9
9,8 9,9 9,10
10,7 10,8 10,9 10,10 ;
! A trivial matrix;
! ROW = 1..3;
! COL = 1..3;
! NONZ =
1,1 1,2 1,3
2,1 2,2
3,1 3,3;
! Another small matrix;
! row = 1..9;
! col = 1..14;
! NONZ =
1,1 1,3 1,4 1,8 1,12
2,5 2,6 2,7 2,9 2,10 2,14
3,1 3,7 3,8
4,3 4,6 4,14
5,4 5,5 5,8 5,11 5,14
6,2 6,7 6,9 6,13
7,2 7,5 7,8
8,1 8,5 8,9 8,10 8,13
9,3 9,4 9,12;
! Weil & Kettler matrix ( 1971, Management Science, vol. 18, no. 1);
! ROW = 1..26;
! COL = 1..38;
! NONZ =
1,30
2,1 2,7 2,12 2,35
3,2 3,10
4,1 4,2 4,3 4,4 4,6 4,7 4,8 4,10 4,11 4,12 4,14 4,15 4,20 4,21 4,22 4,25 4,28 4,31 4,35
5,5 5,12 5,19 5,29 5,34 5,35
6,28
7,3 7,6 7,8 7,9 7,11 7,22
8,10 8,30
9,14 9,21 9,25
10,1 10,2 10,3 10,4 10,5 10,6 10,7 10,8 10,9 10,10 10,11 10,12 10,13 10,14 10,15
10,16 10,17 10,18 10,19 10,20 10,21 10,22 10,23 10,24 10,25 10,26 10,27 10,28 10,29 10,30
10,31 10,32 10,33 10,34 10,35 10,36 10,37 10,38
11,25
12,27
13,2, 13,10 13,30
14,14 14,32 14,33
15,21 15,32
16,18
17,5 17,9 17,13 17,15 17,16 17,17 17,18 17,19 17,23 17,24 17,26 17,27 17,29 17,30 17,32 17,33 17,34 17,36 17,37 17,38
18,20 18,27
19,6 19,17 19,22 19,23 19,26 19,36
20,14 20,21 20,33
21,16 21,28
22,20 22,28
23,18 23,31
24,3 23,8 23,9 23,11 23,17 23,22 23,23 23,26 23,36
25,31
26,2 26,10 ;
ENDDATA
SUBMODEL DECOMP:
! Variables:
yr(b,i) = 1 if row i assigned to block b, for b = 1 or 2,
yc(b,j) = 1 if row i assigned to block b, for b = 1 or 2,
zr = number rows in block with least rows,
zc = number cols in block with least cols,
zrc = smallest number rows or cols in any block
NC(b) = number cols in block b,
NR(b) = number rows in bloock b;
! Criterion 1: Maximize (min rows in a block + min cols in a block)
Criterion 2: (rows in any block + cols in any block;
MAX = wgtb*zrc + wgtr* zr + wgtc* zc
+ NR(1) + NC(1) + NR(2) + NC(2); ! Break ties by total rows+cols in blocks;
! Constraints;
! Each row can be assigned to at most one block;
@FOR( ROW(i):
yr(1,i) + yr(2,i) <= 1;
@BIN(yr(1,i)); @BIN(yr(2,i));
);
! Each col can be assigned to at most one block;
@FOR( COL(j):
yc(1,j) + yc(2,j) <= 1;
@BIN(yc(1,j)); @BIN(yc(2,j));
);
! For every nonzero (i,j), if row i is in block b, then column j cannot
be in block 3-b;
@FOR( NONZ(i,j):
yr(1,i) + yc(2,j) <= 1;
yr(2,i) + yc(1,j) <= 1;
);
! If rows i and k are in col j, then cannot have all of:
i in 1, k in 2 and j in any block or
i in 2, k in 1 and j in any block;
@FOR(COL(j):
@FOR(NONZ(i,j):
@FOR(NONZ(k,j) | k #GT# i:
[C1] yr(1,i) + yr(2,k) + yc(1,j) + yc(2,j) <= 2;
[C2] yr(2,i) + yr(1,k) + yc(1,j) + yc(2,j) <= 2;
);
);
);
! If cols j and k are in row i, then cannot have all of:
j in 1, k in 2 and i in any block or
j in 2, k in 1 and i in any block;
@FOR(ROW(i):
@FOR(NONZ(i,j):
@FOR(NONZ(i,k) | k #GT# j:
[R1] yc(1,j) + yc(2,k) + yr(1,i) + yr(2,i) <= 2;
[R2] yc(2,j) + yc(1,k) + yr(1,i) + yr(2,i) <= 2;
);
);
);
! Totals;
@FOR( BLK(b):
NR(b) = @SUM( ROW(i): yr(b,i));
NC(b) = @SUM( COL(j): yc(b,j));
! Compute zr and zc;
zr <= NR(b);
zc <= NC(b);
);
! Minimum dimension;
zrc <= zr;
zrc <= zc;
! Cuts;
! Kill some symmetry. Row 1 cannot be in block 2;
yr(2,1) = 0;
ENDSUBMODEL
CALC:
@SOLVE(DECOMP);
! Assign an ordering to the rows;
NRT = @SIZE(ROW);
NRC = NRT;
! Block 2 last;
@FOR( ROW(i) | yr(2,i) #GT# .5:
ISROW(i) = NRC;
NRC = NRC - 1;
);
! Block 1 second last;
@FOR( ROW(i) | yr(1,i) #GT# .5:
ISROW(i) = NRC;
NRC = NRC - 1;
);
NRU = NRC;
! Unassigned rows first;
@FOR( ROW(i) | yr(1,i) + yr(2,i) #LT# .5:
ISROW(i) = NRC;
NRC = NRC - 1;
);
! Assign an ordering to the cols;
NCT = @SIZE(COL);
NCC = NCT;
! Block 2 last;
@FOR( COL(i) | yc(2,i) #GT# .5:
ISCOL(i) = NCC;
NCC = NCC - 1;
);
! Block 1 second last;
@FOR( COL(i) | yc(1,i) #GT# .5:
ISCOL(i) = NCC;
NCC = NCC - 1;
);
NCU = NCC;
! Unassigned cols first;
@FOR( COL(i) | yc(1,i) + yc(2,i) #LT# .5:
ISCOL(i) = NCC;
NCC = NCC - 1;
);
@WRITE(' The first ',NRU,' rows and first ',NCU,' cols are linking.',@NEWLINE(1));
! A brute force way of printing the reordered matrix;
@WRITE(' ');
@FOR( COL(jr):
@FOR(COL(j) | iscol(j) #EQ# jr: @WRITE(@FORMAT(j,"3.0f")););
);
@WRITE(@NEWLINE(1));
! First the linking rows;
@FOR(ROW(ir) | ir #LE# NRU:
@FOR(ROW(i) | isrow(i) #EQ# ir: @WRITE(@FORMAT(i,"4.0f"),':'););
@FOR( COL(jr):
MT = 1;
@FOR(NONZ(i,j) | ISROW(i) #EQ# ir #AND# ISCOL(j) #EQ# jr:
@WRITE(' 1');
MT = 0;
);
@IFC(MT: @WRITE(' .'));
);
@WRITE(@NEWLINE(1));
);
! Now rows in block 1;
NR1 = @SUM(ROW(i) | yr(1,i) #GT# .5: 1);
NC1 = @SUM(COL(j) | yc(1,j) #GT# .5: 1);
@FOR(ROW(ir) | ir #GT# NRU #AND# ir #LE# NRU + NR1:
@FOR(ROW(i) | isrow(i) #EQ# ir: @WRITE(@FORMAT(i,"4.0f"),':'););
@FOR( COL(jr) | jr #LE# NCU + NC1:
MT = 1;
@FOR(NONZ(i,j) | ISROW(i) #EQ# ir #AND# ISCOL(j) #EQ# jr:
@WRITE(' 1');
MT = 0;
);
@IFC(MT: @WRITE(' .'));
);
@WRITE(@NEWLINE(1));
);
! Now rows in block 2;
@FOR(ROW(ir) | ir #GT# NRU + NR1:
@FOR(ROW(i) | isrow(i) #EQ# ir: @WRITE(@FORMAT(i,"4.0f"),':'););
@FOR( COL(jr) | jr #LE# NCU: ! Linking columns in rows of block 2;
MT = 1;
@FOR(NONZ(i,j) | ISROW(i) #EQ# ir #AND# ISCOL(j) #EQ# jr:
@WRITE(' 1');
MT = 0;
);
@IFC(MT: @WRITE(' .'));
);
@FOR( COL(jr) | jr #GT# NCU #AND# jr #LE# NCU + NC1: ! Blank cols of block 1, rows of block 2;
@WRITE(' ');
);
@FOR( COL(jr) | jr #GT# NCU + NC1: ! Cols in rows of block 2;
MT = 1;
@FOR(NONZ(i,j) | ISROW(i) #EQ# ir #AND# ISCOL(j) #EQ# jr:
@WRITE(' 1');
MT = 0;
);
@IFC(MT: @WRITE(' .'));
);
@WRITE(@NEWLINE(1));
);
ENDCALC