Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Quadratic programming in Mathematica

I'm looking at quadratic relaxation of maximum independent set problem (p.22 here), and found that FindMaximum fails for every graph I try, unless I give it optimal solution as the starting point. These quadratic programmes have 10-20 variables, so I expect them to be solvable.

  1. Is there a way to make Mathematica solve such quadratic programmes?
  2. Is there some quadratic programming package that's easy to call from within Mathematica?

Here's an example of failing FindMaximum, followed by working FindMaximum initialized at the solution

setupQuadratic[g_Graph] := (
   Ag = AdjacencyMatrix[g];
   A = IdentityMatrix[Length@VertexList@g] - Ag;
   cons = And @@ Table[0 <= x[v] <= 1, {v, VertexList@g}];
   vars = x /@ VertexList[g];
   indSet = FindIndependentVertexSet@g;
   xOpt = Array[Boole[MemberQ[indSet, #]] &, {Length@VertexList@g}];
   );

g = GraphData[{"Cubic", {10, 11}}];
setupQuadratic[g];
FindMaximum[{vars.A.vars, cons}, vars]
FindMaximum[{vars.A.vars, cons}, Thread[{vars, xOpt}]]

Here are other graphs I tried

{"DodecahedralGraph", "FruchtGraph", "TruncatedPrismGraph", \
"TruncatedTetrahedralGraph", {"Cubic", {10, 2}}, {"Cubic", {10, 
   3}}, {"Cubic", {10, 4}}, {"Cubic", {10, 6}}, {"Cubic", {10, 
   7}}, {"Cubic", {10, 11}}, {"Cubic", {10, 12}}, {"Cubic", {12, 
   5}}, {"Cubic", {12, 6}}, {"Cubic", {12, 7}}, {"Cubic", {12, 
   9}}, {"Cubic", {12, 10}}}
like image 930
Yaroslav Bulatov Avatar asked Oct 20 '25 00:10

Yaroslav Bulatov


1 Answers

Might try method shown in package located here. See problem 8

Daniel Lichtblau Wolfram Research

like image 179
Daniel Lichtblau Avatar answered Oct 22 '25 05:10

Daniel Lichtblau



Donate For Us

If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!