maxcut.gms : Goemans/Williamson Randomized Approximation Algorithm for MaxCut
Let G(N, E) denote a graph. A cut is a partition of the vertices N
into two sets S and T. Any edge (u,v) in E with u in S and v in T is
said to be crossing the cut and is a cut edge. The size of the cut is
defined to be sum of weights of the edges crossing the cut.
This model presents a simple MIP formulation of the problem that is
seeded with a solution from the Goemans/Williamson randomized
approximation algorithm based on a semidefinite programming
relaxation.
The MaxCut instance tg20_7777 is available from the Biq Mac Library
and comes from applications in statistical physics.
References:
- Goemans M.X., and Williamson, D P, Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. Journal of the ACM 42 (1995), 1115-1145.
- Wiegele A., Biq Mac Library - Binary quadratic and Max cut Library.
Large Model of Type: MIP Includes: runcsdp.inc tg207777.inc
<![CDATA[
$Title Goemans/Williamson Randomized Approximation Algorithm for MaxCut (MAXCUT,SEQ=338)
$ontext
Let G(N, E) denote a graph. A cut is a partition of the vertices N
into two sets S and T. Any edge (u,v) in E with u in S and v in T is
said to be crossing the cut and is a cut edge. The size of the cut is
defined to be sum of weights of the edges crossing the cut.
This model presents a simple MIP formulation of the problem that is
seeded with a solution from the Goemans/Williamson randomized
approximation algorithm based on a semidefinite programming
relaxation.
The MaxCut instance tg20_7777 is available from the Biq Mac Library
and comes from applications in statistical physics.
Wiegele A., Biq Mac Library - BInary Quadratic and MAx Cut Library.
http://biqmac.uni-klu.ac.at/biqmaclib.html
Goemans M.X., and Williamson, D.P., Improved Approximation Algorithms
for Maximum Cut and Satisfiability Problems Using Semidefinite
Programming. Journal of the ACM 42 (1995), 1115-1145.
http://www-math.mit.edu/~goemans/maxcut-jacm.pdf
$offtext
Set n nodes; alias (n,i,j)
Parameter w(i,j) edge weights
Set e(i,j) edges;
$if not set instance $set instance tg207777.inc
* Simple AWK script to convert MAXCUT format to GAMS format
$onecho > maxcut.awk
NR==1 { print "set n /1*" $1 "/";
print "parameter w(n,n) /\n$ondelim" }
NR>1 { print $0 }
END { print "\n$offdelim\n/;" }
$offecho
$call awk -f maxcut.awk %instance% > %instance%.gms
$offlisting
$include %instance%.gms
$onlisting
$eval maxn card(n)
* We want all edges to be i-j with i<j;
e(i,j) = ord(i)<ord(j);
w(e(i,j)) = w(i,j) + w(j,i);
w(i,j)$(not e(i,j)) = 0;
Option e<w;
* Simple MIP model
Variable x(n) decides on what side of the cut
cut(i,j) edge is in the cut
z objective
Binary variables x
Equation 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);
model maxcut / all /;
$ontext
Set up the SDP
max W*Y s.t. Y_ii=1, Y>0
We need to pass on the dual to csdp
min x1+x2+...+xn s.t. X = F1*x1+F2*x2+...+Fn*xn - W, X>0
with F_i = 1 for F_ii and 0 otherwise
$offtext
Parameter
c(n) cost coefficients
F(n,i,j) constraint matrix
F0(i,j) constant term
Y(i,j) dual solution
L(i,j) Cholesky factor of dual solution Y;
c(n) = 1;
F(n,n,n) = 1;
F0(i,j) = -w(i,j);
execute_unload 'csdpin.gdx' n=m, n, c, F, F0;
execute 'gams runcsdp.inc lo=%gams.lo% && cholesky csdpout.gdx n Y cholesky.gdx L ';
abort$errorlevel 'Problems running RunCSDP. Check listing file for details.'
execute_load 'cholesky.gdx' L;
execute_load 'csdpout.gdx' Y;
Scalar SDPRelaxation;
SDPRelaxation = 0.5*sum(e, w(e)*(1-Y(e)));
display SDPRelaxation;
* Check if Cholesky factorization is correct
Parameter Y_, Ydiff;
Y_(i,j) = sum(n, L(i,n)*L(j,n));
Ydiff(i,j) = round(Y(i,j)-Y_(i,j),1e-6);
option Ydiff:8:0:1; abort$card(Ydiff) Ydiff;
* Now do the random hyperplane r
Parameter r(n);
Set S(n), T(n), bestS(n);
Scalar wS weight of cut S, maxwS best weight /-inf/, cnt;
for (cnt=1 to 10,
r(n) = uniform(-1,1);
S(n) = sum(i, L(n,i)*r(i)) < 0;
T(n) = yes; T(S) = no;
wS = sum(e(S,T), w(S,T) + w(T,S));
if (wS>maxwS, maxwS = wS; bestS(n) = S(n));
);
display maxwS;
option mip=cplex;
$echo mipstart 1 > cplex.opt
x.l(bestS) = 1;
maxcut.optfile = 1;
solve maxcut max z using mip;
]]></plaintext></body></div>