! 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