설명
G(N, E)가 그래프를 나타냅니다. 컷은 꼭지점 N의 분할입니다. S와 T의 두 집합으로 나눕니다. S에 u가 있고 T에 v가 있는 E의 모든 모서리(u,v)는 다음과 같습니다. 컷을 교차하고 컷 가장자리라고 합니다. 컷팅 사이즈는 컷을 교차하는 모서리의 가중치 합으로 정의됩니다. 이 모델은 문제에 대한 간단한 MIP 공식을 제시합니다. Goemans/Williamson의 솔루션을 무작위로 사용하여 시딩 준정의 계획법을 기반으로 한 근사 알고리즘 휴식. 이 모델은 MOSEK를 사용하여 SDP를 해결합니다. MaxCut 인스턴스 tg20_7777은 Biq Mac 라이브러리에서 사용할 수 있습니다. 통계 물리학의 응용에서 비롯되었습니다.
대형 모델 유형 :MIP
카테고리 : 슬롯 머신 모델 라이브러리
메인 파일 : maxcut.gms 포함: tg207777.inc
$title Goemans/Williamson MaxCut에 대한 무작위 근사 알고리즘(MAXCUT,SEQ=338)
$onText
G(N, E)를 그래프로 나타냅니다. 컷은 꼭지점 N의 분할입니다.
S와 T의 두 집합으로 나눕니다. S에 u가 있고 T에 v가 있는 E의 모든 모서리(u,v)는 다음과 같습니다.
컷을 교차하고 컷 가장자리라고 합니다. 컷팅 사이즈는
컷을 교차하는 모서리의 가중치 합으로 정의됩니다.
이 모델은 문제에 대한 간단한 MIP 공식을 제시합니다.
Goemans/Williamson의 솔루션을 무작위로 사용하여 시딩
준정의 계획법을 기반으로 한 근사 알고리즘
휴식. 이 모델은 MOSEK를 사용하여 SDP를 해결합니다.
MaxCut 인스턴스 tg20_7777은 Biq Mac 라이브러리에서 사용할 수 있습니다.
통계 물리학의 응용에서 비롯됩니다.
Wiegele A., Biq Mac 라이브러리 - Binary Quadratic 및 Max Cut 라이브러리.
http://biqmac.uni-klu.ac.at/biqmaclib.html
Goemans M.X. 및 Williamson, D.P., 향상된 근사 알고리즘
반부정을 사용한 최대 컷 및 만족도 문제
프로그래밍. ACM 저널 42(1995), 1115-1145.
http://www-math.mit.edu/~goemans/PAPERS/maxcut-jacm.pdf
키워드: 혼합 정수 선형 계획법, 근사 알고리즘,
볼록 최적화, 무작위 알고리즘, 최대 절단 문제,
수학
$offText
$ifThen x%슬롯 머신LP% == x
옵션 lp=모섹;
$elseIfI가 %슬롯 머신LP%가 아니면 == mosek
$ log 선택한 LP 해결사 %슬롯 머신LP%는 SDP 문제를 해결할 수 없습니다.
$ 종료
$endIf
n개의 '노드'를 설정합니다.
별칭(n,i,j);
매개변수 w(i,j) '간선 가중치';
e(i,j) '가장자리'를 설정합니다.
$인스턴스를 설정하지 않은 경우 $set 인스턴스 tg207777.inc
$onEmbeddedCode 파이썬:
open("%instance%", "r")을 f로 사용:
n, _ = [f.readline().split()의 i에 대한 int(i)]
슬롯 머신set('n', [str(i+1) for i in range(n)])
슬롯 머신set('w', [(i,j,int(v)) for i,j,v in [l.split() for l in f.readlines()]])
$offEmbeddedCode n w
* 우리는 모든 가장자리가 i<j인 i-j가 되기를 원합니다.
e(i,j) = ord(i) < ord(j);
w(e(i,j)) = w(i,j) + w(j,i);
w(i,j)$(e(i,j) 아님) = 0;
옵션 e < w;
* 간단한 MIP 모델
변수
x(n) '컷의 어느 쪽을 결정합니다'
cut(i,j) '가장자리가 절단부에 있음'
z '목표';
이진변수 x;
방정식 obj, xor1(i,j), xor2(i,j), xor3(i,j), xor4(i,j);
obj.. z =e= sum(e, w(e)*cut(e));
xor1(e(i,j))..cut(e) =l= x(i) + x(j);
xor2(e(i,j)).. cut(e) =l= 2 - x(i) - x(j);
xor3(e(i,j))..cut(e) =g= x(i) - x(j);
xor4(e(i,j))..cut(e) =g= x(j) - x(i);
모델 maxcut / all /;
$onText
SDP 설정
최대 W*Y 표준 Y_ii = 1, Y 양수 준정부호(psd)
$offText
스칼라 SDPRelaxation;
매개변수 L(i,j) 'Y의 촐레스키 인자';
변수 Y(i,j) 'PSDMATRIX';
변수 sdpobj '목적함수 변수';
방정식 sdpobjdef '목적 함수 W*Y';
sdpobjdef.. sum(e(i,j),w(i,j)*(Y(i,j)+Y(j,i))/2.0) + sum((i,j),eps*Y(i,j)) =E= sdpobj;
Y.fx(i,i) = 1.0;
모델 sdp / sdpobjdef /;
옵션 리미로우 = 0;
sdp.solprint = 0;
lp를 사용하여 sdp min sdpobj를 해결합니다.
Parameter Yl(i,j) '모수인 Y의 수준 값';
Yl(i,j) = Y.l(i,j);
ExecuteTool.checkErrorLevel 'linalg.cholesky n Yl L';
* 기호 L은 ExecuteTool.checkErrorLevel에 의해 암시적으로 로드되었습니다. 컴파일러 명령어
* 다음 줄에서는 아마도 할당되지 않은 기호에 대한 오류를 억제합니다.
$onImplicitAssign
* Cholesky 인수분해가 올바른지 확인
매개변수 Y_, Ydiff;
Y_(i,j) = 합계(n, L(i,n)*L(j,n));
Ydiff(i,j) = round(Y.l(i,j) - Y_(i,j),1e-6);
옵션 Ydiff:8:0:1;
중단$card(Ydiff) Ydiff;
SDPRelaxation = 0.5*sum(e, w(e)*(1 - Y.l(e)));
SDPRelaxation을 표시합니다.
* 이제 무작위 초평면 r을 수행합니다.
매개변수 r(n);
S(n), T(n), bestS(n)을 설정합니다.
스칼라
wS '절삭 중량 S'
maxwS '최고의 무게' / -inf /
cnt;
for(cnt = 1 ~ 10,
r(n) = 균일(-1,1);
S(n) = 합(i, L(n,i)*r(i)) < 0;
T(n) = 그렇습니다;
T(S) = 아니오;
wS = 합(e(S,T), w(S,T)) + 합(e(T,S), + w(T,S));
if(wS > maxwS, maxwS = wS; bestS(n) = S(n););
);
maxwS를 표시합니다.
* 계산된 실현 가능 솔루션을 MIP 해결의 시작점으로 사용
x.l(최고S) = 1;
cut.l(e(i,j)) = x.l(i) xor x.l(j);
* SCIP 및 COPT는 기본적으로 이 작업을 수행하며, 다른 솔버의 경우 이를 활성화해야 합니다.
$set MIPSTART
$if %슬롯 머신mip% == cplex $set MIPSTART mipStart
$if %슬롯 머신mip% == cbc $set MIPSTART mipStart
$if %슬롯 머신mip% == 구로비 $set MIPSTART mipStart
$if %슬롯 머신mip% == 최고 $set MIPSTART mipStart
$if %슬롯 머신mip% == xpress $set MIPSTART loadmipsol
$ifThen x%MIPSTART% == x가 아님
$ echo %MIPSTART% 1 > %슬롯 머신mip%.opt
maxcut.optFile = 1;
$endIf
mip를 사용하여 maxcut max z를 해결합니다.