설명
자동 테이블 레이아웃 문제는 문서 처리 문제입니다. 여러 개의 행과 열이 있는 테이블이 주어지면 각 셀에 텍스트를 배치해야 합니다. 각 셀에 대해 텍스트를 여러 줄로 나누는 방법에 대한 여러 구성이 제공됩니다. 따라서 너비와 메가 슬롯가 다른 다양한 직사각형이 생성됩니다. 따라서 각 구성에 따라 셀의 메가 슬롯와 너비에 대한 요구 사항이 달라집니다. 따라서 셀이 속한 행의 메가 슬롯와 열의 너비에 따라 달라집니다. 열 너비는 해당 열의 모든 셀에 대해 동일해야 합니다. 해당 열의 모든 셀에 대해 선택한 구성의 최대 너비. 행도 마찬가지입니다. 페이지의 너비가 주어지면 테이블의 전체 메가 슬롯를 최소화하는 레이아웃을 찾는 것이 목표입니다. 자세한 내용은 다음을 참조하세요. 미하이 빌라우카와 패트릭 힐리(2010). 자동화된 테이블 레이아웃을 위한 새로운 모델입니다. 제10회 ACM 문서공학 심포지엄 논문집, pp 169-176. https://doi.org/10.1145/1860559.1860594 미하이 빌라우카(2012). 자동 테이블 레이아웃 및 서식 지정. University of Limerick 박사학위 논문 https://researchrepository.ul.ie/
소형 메가 슬롯 유형 :MIP
카테고리 : 메가 슬롯 모델 라이브러리
메인 파일 : 메가 슬롯gms 포함: tablelayout5x5.inc
$title 테이블 높이를 최소화하기 위해 테이블 셀의 텍스트 레이아웃 구성 (TABLELAYOUT,SEQ=402)
$onText
자동 테이블 레이아웃 문제는 문서 처리 문제입니다.
여러 개의 행과 열이 있는 테이블이 주어지면 각 셀에 텍스트를 배치해야 합니다.
각 셀에 대해 텍스트를 여러 줄로 나누는 방법에 대한 여러 구성이 제공됩니다.
따라서 너비와 높이가 다른 다양한 직사각형이 생성됩니다.
따라서 각 구성에 따라 셀의 높이와 너비에 대한 요구 사항이 달라집니다.
따라서 셀이 속한 행의 높이와 열의 너비에 따라 달라집니다.
열 너비는 해당 열의 모든 셀에 대해 동일해야 합니다.
해당 열의 모든 셀에 대해 선택한 구성의 최대 너비. 행도 마찬가지입니다.
페이지의 너비가 주어지면 테이블의 전체 높이를 최소화하는 레이아웃을 찾는 것이 목표입니다.
자세한 내용은 다음을 참조하세요.
미하이 빌라우카와 패트릭 힐리(2010).
자동화된 테이블 레이아웃을 위한 새로운 모델입니다.
제10회 ACM 문서공학 심포지엄 논문집, pp 169-176.
https://doi.org/10.1145/1860559.1860594
미하이 빌라우카(2012).
자동 테이블 레이아웃 및 서식 지정.
University of Limerick 박사학위 논문
https://researchrepository.ul.ie/
아래에서는 "cols", "rows" 및 "cp"라는 이름으로 문제에 대한 다양한 공식을 제공합니다.
--formulation 옵션을 사용하여 이들 중 하나를 선택할 수 있습니다. 기본값은 "행"입니다.
- "cols" 공식에서는 솔버가 가능한 너비 중에서 각 열의 너비를 선택하도록 합니다.
즉, 해당 열의 모든 셀에 있는 모든 구성의 너비입니다.
따라서 각 열에는 여러 개의 이진 변수가 있으며 그 중 정확히 하나는 1이어야 합니다.
열 너비를 결정합니다.
- "행" 공식은 유사하지만 대신 각 행의 높이를 선택합니다.
데이터를 살펴보면 모든 구성에서 사용되는 높이가 약 6개뿐이라는 것을 알 수 있습니다.
따라서 각 행의 높이를 선택하는 작업을 최적화하면 이진 변수가 훨씬 줄어듭니다.
각 열의 너비를 선택하는 것보다. (항상 행 수만큼 열이 있음)
따라서 이 공식은 "cols" 공식보다 더 나을 것으로 예상됩니다.
- "cp" 공식은 매우 간단한 공식으로, 정수 변수를 결정해야 합니다.
각 열의 너비와 각 행의 높이, 그리고 각 셀에 대해 다음과 같은 제약 조건이 있습니다.
선택한 열 너비와 행 높이에 맞는 구성이 하나 이상 있어야 합니다.
이는 아래 방정식 'cellconfig'로 공식화되며, 이는 메가 슬롯의 소수의 솔버에서만 처리할 수 있습니다.
이 모델의 모델 유형은 MINLP입니다.
마지막으로 "열" 및 "행" 공식에는 두 가지 변형이 있습니다. MINLP 변형에서는
--useMINLP 1 옵션을 통해 활성화하려면 smax를 사용하여 중간 변수를 정의합니다.
기본 MIP 변형 이 smax는 일반적인 방식으로 선형화됩니다(추가 변수는 없지만 더 많은 방정식이 필요함).
추가 사례는 http://www.localsolver.com에서 확인할 수 있습니다.
제공된 tablelayout5x5.inc 데이터 파일은 free_trial.in 파일에 해당합니다.
키워드: 혼합 정수 비선형 계획법, 자동 테이블 레이아웃, 공학
$offText
$인스턴스를 설정하지 않은 경우 $set 인스턴스 tablelayout5x5.inc
$if 존재하지 않는 경우 "%instance%" $abort 인스턴스 파일이 존재하지 않습니다.
$만약 공식이 설정되지 않은 경우 $set 공식 행
옵션 optCr = 0, limCol = 0, limRow = 0;
세트
r '행'
c '열'
w '너비'
h '높이';
스칼라
pw '페이지 너비';
$rcwh 저장
세트
rcwh(r,c,w,h) '구성 데이터(셀의 너비와 높이)';
* ===== 데이터 준비 =====
$onEmbeddedCode 메가 슬롯: 재시작=rcwh
올바른 정렬 순서를 위해 Universe(*)를 설정합니다.
별칭(*,rX,cX,wX,hX); rcwh(rX,cX,wX,hX)를 설정합니다.
$onEmbeddedCode.py 파이썬:
open('%instance%', 'r')을 f로 사용:
메가 슬롯set('pw',[int(f.readline())])
rcwh = [ tuple(l.split()) for l in f.readlines() if len(l.split()) > 3 ]
메가 슬롯set('universe',[ str(i) for i in range(1+max(int(x) for t in rcwh for x in t))])
메가 슬롯set('rcwh', rcwh);
$offEmbeddedCode.py 유니버스 rcwh 비밀번호
c(cX) = 합(rcwh(rX,cX,wX,hX), 1);
r(rX) = 합(rcwh(rX,cX,wX,hX), 1);
w(wX) = 합계(rcwh(rX,cX,wX,hX), 1);
h(hX) = 합(rcwh(rX,cX,wX,hX), 1);
$offEmbeddedCode r c w h rcwh pw
매개변수
nw(w) '수치적 폭'
nh(h) '수치적 높이';
nw(w) = w.val;
nh(h) = h.val;
* ===== 공식으로 이동 =====
$if %formulation% == cols $goTo formcols
$if %formulation% == 행 $goTo formrows
$if %formulation% == cp $goTo formcp
$abort 알 수 없는 공식 "%formulation%", 적절한 값은 "cols", "rows" 및 "cp"입니다.
* ===== 각 열에 대해 열 너비를 선택한 공식 =====
$label 양식 열
cw(c,w) '열의 너비'를 설정합니다.
cw(c,w) = sum(rcwh(r,c,w,h), 1);
별칭(w,ww);
* 셀 (r,c)가 너비 w를 사용하는 경우 (r,c)에 필요한 가장 작은 높이를 찾습니다.
* 즉, 너비 <= w인 모든 구성 중에서 높이가 가장 작은 구성을 선택합니다.
매개변수 minRCWh(r,c,w) 'c열이 너비 w를 가질 때 셀(r,c)에서 가능한 최소 높이';
minRCWh(r,cw(c,w)) = smin(rcwh(r,c,ww,h)$(nw(ww) <= nw(w)), nh(h));
* 실행 불가능한 레이아웃을 초래하는 열 너비 제거
* 즉, 열에 특정 너비를 할당하면 이 열의 특정 셀에 대해
* 열에는 이 너비에 맞는 구성이 없습니다(INF로 표시됨).
* smin 이상), 이 열에 너비 할당을 금지할 수 있습니다.
cw(c,w)$sum(r$(minRCWh(r,c,w) = inf), 1) = 아니오;
* 문제가 가능한지 확인
매개변수 minCw(c) '열의 가능한 최소 너비';
minCw(c) = smin(cw(c,w), nw(w));
abort$(sum(c, minCw(c)) > pw) '페이지 너비가 너무 작습니다.';
변수
bCW(c,w) 'c 열의 너비는 w'입니다.
xRCh(r,c) '셀 높이'
xRh(r) '행 높이'
총 페이지 높이';
이진 변수 bCW;
방정식
defbCW(c) '각 열은 정확히 하나의 너비를 갖습니다.'
defxRCh(r,c) '셀 높이 정의'
defxRhMINLP(r) '행 높이 정의'
defxRhMIP(r,c) '행 높이 정의'
defpw '페이지 너비로 레이아웃 제한'
능숙하게 '객관적인 전체 높이';
defbCW(c)..sum(cw(c,w), bCW(c,w)) =e= 1;
* 열 c가 너비 w를 선택한 경우 셀의 높이(r,c)가
* 위에서 미리 계산된 minRCWh(r,c,w)이므로 여기서는 올바른 것을 선택하면 됩니다.
defxRCh(r,c).. xRCh(r,c) =e= sum(cw(c,w), bCW(c,w)*minRCWh(r,c,w));
* 행 r의 높이는 행 r에 있는 셀 높이의 최대값으로 제공됩니다.
defxRhMINLP(r).. xRh(r) =e= smax(c, xRCh(r,c));
defxRhMIP(r,c).. xRh(r) =g= xRCh(r,c);
defpw.. sum(cw(c,w), bCW(c,w)*nw(w)) =l= pw;
* 목표는 모든 행의 높이의 합을 최소화하는 것입니다.
deftoth..toth =e= sum(r, xRh(r));
모델
레이아웃MINLP / 모두 - defxRhMIP /
레이아웃MIP / 모두 - defxRhMINLP /;
옵션 optCr = 0;
$if set useMINLP MINLP min toth를 사용하여 레이아웃MINLP를 해결합니다.
$설정되지 않은 경우 useMINLP는 MIP min toth를 사용하여 레이아웃MIP를 해결합니다.
$exit
* ===== 각 행에 대해 행 높이를 선택하는 공식 =====
$label 양식행
rh(r,h) '연속 높이'를 설정합니다.
rh(r,h) = sum(rcwh(r,c,w,h), 1);
별칭(h,hh);
* 셀 (r,c)가 높이 h를 갖는 경우 (r,c)에 필요한 가장 작은 너비를 찾습니다.
* 즉, 높이 <= h인 모든 구성 중에서 너비가 가장 작은 구성을 선택합니다.
매개변수 minRCHw(r,c,h) '행 r이 높이 h를 가질 때 셀 (r,c)에서 가능한 최소 너비';
minRCHw(r,c,h)$rh(r,h) = smin(rcwh(r,c,w,hh)$(nh(hh) <= nh(h)), nw(w));
* 실행 불가능한 레이아웃을 초래하는 행 높이 제거
* 즉, 행에 특정 높이를 할당하면 이 행의 특정 셀에 대해
* 행에는 이 높이에 맞는 구성이 없습니다(INF로 표시됨).
* smin 이상), 이 행의 높이 할당을 금지할 수 있습니다.
rh(r,h)$sum(c$(minRCHw(r,c,h) = inf), 1) = 아니오;
변수
bRH(r,h) '행 r은 높이 h를 취함'
xRCw(r,c) '셀 너비'
xCw(c) '열 너비'
총 페이지 높이';
이진 변수 bRH;
방정식
defbRH(r) '각 행은 정확히 하나의 높이를 갖습니다.'
defxRCw(r,c) '셀 너비 정의'
defxCwMINLP(c) '열 너비 정의'
defxCwMIP(r,c) '열 너비 정의'
defpw '페이지 너비로 레이아웃 제한'
능숙하게 '객관적인 전체 높이';
defbRH(r).. sum(rh(r,h), bRH(r,h)) =e= 1;
* 행 r이 높이 h를 선택한 경우 셀의 너비(r,c)는
* 위에서 미리 계산된 minRCHw(r,c,h)이므로 여기서는 올바른 것을 선택하면 됩니다.
defxRCw(r,c).. xRCw(r,c) =e= sum(rh(r,h), bRH(r,h)*minRCHw(r,c,h));
* c 열의 너비는 c 열에 있는 셀 너비의 최대값으로 지정됩니다.
defxCwMINLP(c).. xCw(c) =e= smax(r, xRCw(r,c));
defxCwMIP(r,c).. xCw(c) =g= xRCw(r,c);
defpw..sum(c, xCW(c)) =l= pw;
* 목표는 모든 행의 높이의 합을 최소화하는 것입니다.
deftoth.. toth =e= sum(rh(r,h), bRH(r,h)*nh(h));
모델
레이아웃MINLP / 모두 - defxCwMIP /
레이아웃MIP / 모두 - defxCwMINLP /;
옵션 optCr = 0;
$if set useMINLP MINLP min toth를 사용하여 레이아웃MINLP를 해결합니다.
$설정되지 않은 경우 useMINLP는 MIP min toth를 사용하여 레이아웃MIP를 해결합니다.
$exit
* ===== 열 너비와 행 높이가 선택된 CP 공식 =====
$라벨 형식cp
정수변수
iCW(c) 'c열의 너비'
iRH(r) 'r행의 높이';
* 열 c의 최소 너비는 다음의 최소 너비를 취하여 제공됩니다.
* 모든 구성을 연속으로 적용하고 이를 모든 행에서 최대화합니다.
iCW.lo(c) = smax(r, smin(rcwh(r,c,w,h), nw(w)));
iCW.up(c) = 비밀번호;
* 행 r의 최소 높이는
* 열의 모든 구성 및 모든 열에서 이를 최대화
iRH.lo(r) = smax(c, smin(rcwh(r,c,w,h), nh(h)));
* 행 r의 최대 높이는
* 행의 모든 열에 대한 모든 구성
iRH.up(r) = smax(rcwh(r,c,w,h), nh(h));
변수 tableH '테이블 높이';
방정식
deftableH '테이블 높이 정의'
maxtableW '테이블 너비 제한'
cellconfig(c,r) '선택한 너비와 높이에 맞춰 최소한 하나의 셀 구성이 필요합니다.';
* 이제 테이블 너비가 페이지 너비를 초과할 수 있습니다.
maxtableW..sum(c, iCW(c)) =l= pw;
* 테이블 높이는 행 높이의 합입니다.
deftableH.. tableH =e= sum(r, iRH(r));
* 각 셀에는 적합한 구성이 하나 이상 있어야 합니다.
* 선택한 열 너비와 행 높이에
cellconfig(c,r).. sum(rcwh(r,c,w,h), (nw(w) <= iCW(c)) and (nh(h) <= iRH(r))) =g= 1;
모델 레이아웃 / 모두 /;
minlp min tableH를 사용하여 레이아웃을 해결합니다.