In[]:=
setupQP[g_Graph]:=Block{f,n,vars,objective,constraints,domain,a,b,x},f[a_,b_]=
1
2
(1-ab);n=Length[VertexList[g]];vars=Array[x,n];objective=Total[EdgeList[g]/.a_b_f[x[a],x[b]]];constraints=(-1≤#1≤1&)/@vars;domain=(#1∈&)/@vars;{objective,constraints,domain,vars};​​​​g=GridGraph[{5,5},VertexSize->Large];​​{objective,constraints,domain,vars}=setupQP[g];​​{solution,rules}=FindMinimum[{-objective,constraints},domain,Method->"InteriorPoint"];​​labels=vars/.rules;​​Print["Value of cut ",-solution];​​HighlightGraph[g,Pick[Range@Length@labels,Thread[labels>0]]]
Value of cut 40.
Out[]=