1. LocalSolverホーム
  2. LocalSolver製品概要
  3. LocalSolver例題集
  4. Table Layout(テーブル・レイアウト問題)

Table Layout(テーブル・レイアウト問題)

自動テーブルレイアウト  提供 Mihai Bilauca, University of Limmerick

自動テーブルレイアウト問題はドキュメント処理問題です。です。この問題はm行とn列を含むテーブルレイアウトを見つけることから成り立ちます。
このテーブルの各セルは連続的な行で分割できるテキストを含んでいるため、矩形または幅w及び高さhを用いた配列で生成されます。あるレイアウトはテーブルを陳列する際に使用するため、各セルの配列を選択することで定義されます。ページの幅を所与として、オブジェクトはテーブルの全高さを最小化することでレイアウトが見つかります。

詳細情報 Bilauca & Patrick, 2010. "A new model for automated table layout", in Proceedings of the 10th ACM symposium on Document engineering, pp 169--176, ACM..

データファイルのフォーマットは下記の通りです。

  • 1行目:ページの幅
  • 2行目:行の数
  • 3行目:列の数
  • その後、各行r、c、w、hは行r及び列cのセルのために、幅wおよび高さhの配列を定義します。(行と列インデックスは0からスタートします。)

この問題に関して、様々なモデルをイメージすることが可能です。配列がセルに対して1と同等と選択された場合、各セルで各配列向けに、1つの意思決定変数で定義することが最もシンプルです。その後、全ての行と全ての列の高さおよび幅は行の全ての高さ、または列の全ての幅の最大化として定義されます。このシンプルなモデルは小規模なインスタンスには適用できますが、実は列の幅から各セルの最小の高さを推測できる場合、意思決定変数のさらに小規模な集合もここで選択することが可能です。従って、各セルに対する全ての任意の幅の和として各列に対する全ての可能な幅を再計算します。その後、各セルに対して、各可能な幅のためにその最小の高さを再計算します。これらの再計算されたテーブルは、この幅がこの列に対して1と同等と選択された場合、各列の各可能な幅として1つの意思決定変数を定義することが可能です。その一方、各セルの最大の高さそして最終的なページの最大の高さはこの列の幅から推測されます。この問題は意思決定変数の集合を選択するための重要な代表的な例題です。:この例題では、単一列の幅を変更することで、LocalSolverは高さおよび、この列の全てのセルの幅を正確に調整します。

モデリング言語に関して、この例題で下記のことがわかります。

  • ユーザーは自身の関数を定義することが可能
  • キーワード"local"は、このブロックに変数の可視性を制限する
  • 下記の表現式として1行でシンプルな条件を計算するために、モデリング演算子およびインタックスの繰り返しを使用できる

min[k in 0..nbConfigurations[row][col]-1 : configurationsWidths[row][col][k] <= width](configurationsHeights[row][col][k])

LSP ソースファイル


/********** table_layout.lsp **********/

/* Reads instance data in the following format:
 * 1st line: page width.
 * 2nd line: number of rows
 * 3rd line: number of columns
 * Then each line r, c, w, h define a configuration of width w and height h, for cell at row r and column c
 * (row and column indices start at 0). 
 */
function input() {  
  if (instancefile == nil || solutionfile == nil) 
    error("Usage: localsolver tablelayout.lsp instancefile=myfile.in solutionfile=myfile.out");  
  instance = openRead(instancefile);

  maxW = readInt(instance);
  nbRows = readInt(instance);
  nbCols = readInt(instance);
  
  println("nbRows="+nbRows+", nbCols="+nbCols);
  
  bigInt = 1000000;
  cellMinWidth[r in 0..nbRows-1][c in 0..nbCols-1] = bigInt;
  nbConfigurations[r in 0..nbRows-1][c in 0..nbCols-1] = 0;
  minWidthConfig[r in 0..nbRows-1][c in 0..nbCols-1] = -1;  
  
  while (!eof(instance)) {
    row = readInt(instance);
    col = readInt(instance);    
    width =  readInt(instance);
    height = readInt(instance);        
    local k = nbConfigurations[row][col];        
    configurationsHeights[row][col][k] = height;
    configurationsWidths[row][col][k] = width;
    if (width < cellMinWidth[row][col]) {
      cellMinWidth[row][col] = width;
      minWidthConfig[row][col] = k;
    }
    nbConfigurations[row][col] = k+1;
  }
  precompute();
}
  
/* Precompute tables allowing to know for each possible colum width, the height of each of its cells. */  
function precompute() {  
  // build the union of widths for each column
  minPossibleWidth[c in 0..nbCols-1]=getMinPossibleWidth(c); 
  maxPossibleWidth[c in 0..nbCols-1]=getMaxPossibleWidth(c); 
  computeColWidths();
  
  // check that the problem is feasible
  sumOfMinWidths = sum[c in 0..nbCols-1](minPossibleWidth[c]);      
  if (sumOfMinWidths > maxW) error("On this instance page width cannot be smaller than "+sumOfMinWidths);
  
  // coompute possible heights
  minPossibleHeight[r in 0..nbRows-1]=getMinPossibleHeight(r);  
  computeRowHeights();

  // for each cell: the height attached to each possible width
  minHeightForWidthIndex[r in 0..nbRows-1][c in 0..nbCols-1][n in 0..nbWidths[c]-1] = 
    getMinHeightForWidth(r,c,colWidths[c][n]);  
}


/* Returns the min height for cell [row,col] when the width is set to 'width'. */
function getMinHeightForWidth(row,col,width) {
  return min[k in 0..nbConfigurations[row][col]-1 : configurationsWidths[row][col][k] <= width]
    (configurationsHeights[row][col][k]);
}

/* Returns the min with for cell [row,col] (min over all configurations for this cell). */
function getMinWidth(row,col) {
  return min[k in 0..nbConfigurations[row][col]-1](configurationsWidths[row][col][k]);
}

/* Returns the min width for this column (max over all minWidth for cells of this column). */
function getMinPossibleWidth(col) {
  return max[row in 0..nbRows-1](getMinWidth(row,col));
}

/* Returns the max width for this column (max over all configurations for cells of this column). */
function getMaxPossibleWidth(col) {
  return max[row in 0..nbRows-1][k in 0..nbConfigurations[row][col]-1](configurationsWidths[row][col][k]);
}

/* Returns true if the given width is one of the possible width of this column. */
function containsWidth(col,width) {
  return nbWidths[col]>0 && or[n in 0..nbWidths[col]-1](colWidths[col][n]==width);
}

/* Returns the min height for cell [row,col]  (min over all configurations for this cell). */
function getMinHeight(row,col) {
  return min[k in 0..nbConfigurations[row][col]-1](configurationsHeights[row][col][k]);    
}

/* Returns the min possible height for this row (max over all minHeight for this row. */
function getMinPossibleHeight(row) {
  return max[col in 0..nbCols-1](getMinHeight(row,col));    
}

/* Returns true if the given height is one of the possible height for this row. */
function containsHeight(row,height) {
  return nbHeights[row]>0 && or[n in 0..nbHeights[row]-1](rowHeights[row][n]==height);  
}

/* Compute the set of possible widths for each column. */
function computeColWidths() {
  for[c in 0..nbCols-1] {
    nbWidths[c]=0;  
    for [r in 0..nbRows-1][k in 0..nbConfigurations[r][c]-1] {
      local w = configurationsWidths[r][c][k];
      if (w >= minPossibleWidth[c] && !containsWidth(c,w)) {
        local n = nbWidths[c];        
        colWidths[c][n]=w;
        if (w == minPossibleWidth[c]) indexOfMinWidth[c]=n;
        if (w == maxPossibleWidth[c]) indexOfMaxWidth[c]=n;
        nbWidths[c] = n + 1;
      }
    }
  }
}

/* Compute the set of possible heights for each row. */
function computeRowHeights() {
  for[r in 0..nbRows-1] {
    nbHeights[r]=0;  
    maxh=0;
    for [c in 0..nbCols-1][k in 0..nbConfigurations[r][c]-1] {
      local h = configurationsHeights[r][c][k];
      if (h >= minPossibleHeight[r] && !containsHeight(r,h)) {
        local n = nbHeights[r];        
        rowHeights[r][n]=h;
        if (h > maxh) {
          indexOfMaxHeight[r]=n;
          maxh=h;
        }
        nbHeights[r] = n + 1;
      }
    }
  }
}

/* Declares the optimization model. */
function model() {
  // decision variables xcol[c][n]=1 if column c takes its nth width. 
  xcol[c in 0..nbCols-1][n in 0..nbWidths[c]] <- bool();
  
  // each column takes exactly one width
  for[c in 0..nbCols-1] 
    constraint sum[n in 0..nbWidths[c]-1](xcol[c][n])==1;
  
  // from these decisions we infer the height and width of each cell and the height of each row
  xColWidth[c in 0..nbCols-1] <- sum[n in 0..nbWidths[c]-1](xcol[c][n] * colWidths[c][n]);
  xCellHeight[r in 0..nbRows-1][c in 0..nbCols-1] <- 
    sum[n in 0..nbWidths[c]-1](xcol[c][n] * minHeightForWidthIndex[r][c][n]);
  xRowHeight[r in 0..nbRows-1] <- max[c in 0..nbCols-1](xCellHeight[r][c]);
  
  // we get the dimensions of the page
  totalWidth <- sum[c in 0..nbCols-1](xColWidth[c]);
  totalHeight <- sum[r in 0..nbRows-1](xRowHeight[r]);
  
  // the objective is to minimize the total height, subject to the total width constraint.
  constraint totalWidth <= maxW;
  minimize totalHeight;
  
  // Note: due to the presence of large plateaus on some loosy constrained instances, 
  //       adding a surrogate objective may pay off. For example the following auxiliary 
  //       objective minimizes the number of cells responsible for the height of their row, 
  //       thus guiding the search toward a decrease of the totalHeight.  
  //minimize sum[r in 0..nbRows-1][c in 0..nbCols-1](xCellHeight[r][c] == xRowHeight[r]);
}

/* Parameterizes the solver and set the initial solution. */
function param() {
  // Basic greedy initialization: for each colum select the smallest width
  // unless selecting the maximum width is possible.
  local initialWidth = sumOfMinWidths;
  for[c in 0..nbCols-1] {
    local selected = indexOfMinWidth[c];
    local delta = maxPossibleWidth[c] - minPossibleWidth[c];
    if (initialWidth + delta <= maxW) {
      selected = indexOfMaxWidth[c]; 
      initialWidth = initialWidth + delta;
    }
    for [n in 0..nbWidths[c]]     
      setValue(xcol[c][n], n == selected); 
  }  
  
  // we can stop the search once each row takes its smaller possible height.
  globalMinPossibleHeight = sum[r in 0..nbRows-1](minPossibleHeight[r]);
  println("MIN TOTAL HEIGHT = "+ globalMinPossibleHeight);  
  setObjectiveBound(0,globalMinPossibleHeight);      
}

/* Retrieve the index of the configuration selected for a given cell. */
function getOutputConfig(row,col) {
  local cw = getValue(xColWidth[col]);
  local rh = getValue(xRowHeight[row]);
  for [k in 0..nbConfigurations[row][col]-1]
    if (configurationsWidths[row][col][k] <= cw &&
      configurationsHeights[row][col][k] <= rh) return k;
  error("No Valid configuration for "+row+","+col+"!");
  return -1;
}

/* Writes the solution in a file, as an nbRows x nbCols table 
 * containing for each cell the index of the selected configuration. */
function output() {
  println("BEST SOLUTION FOUND >>>>>>>>>>>>>>>>>>>>>>>> "+getValue(totalHeight));
  solution = openWrite(solutionfile);
  for[row in 0..nbRows-1] {
    for[col in 0..nbCols-1] {
      print(solution,getOutputConfig(row,col)+" ");      
    }
    println(solution);
   }
}    

例題コンテンツ

  • table_layout/
  • table_layout/instances/
  • table_layout/instances/100x100.in
  • table_layout/instances/10x10.in
  • table_layout/instances/200x200.in
  • table_layout/instances/20x20.in
  • table_layout/instances/300x300.in
  • table_layout/instances/30x30.in
  • table_layout/instances/400x400.in
  • table_layout/instances/40x40.in
  • table_layout/instances/50x50.in
  • table_layout/instances/60x60.in
  • table_layout/instances/free_trial.in
  • table_layout/README.txt
  • table_layout/sol.txt
  • table_layout/table_layout.lsp

このページの先頭へ