[mlpack-svn] r11420 - mlpack/trunk/src/mlpack/tests

fastlab-svn at coffeetalk-1.cc.gatech.edu fastlab-svn at coffeetalk-1.cc.gatech.edu
Tue Feb 7 00:57:03 EST 2012


Author: rcurtin
Date: 2012-02-07 00:57:02 -0500 (Tue, 07 Feb 2012)
New Revision: 11420

Modified:
   mlpack/trunk/src/mlpack/tests/lrsdp_test.cpp
Log:
Add tests for two other Lovasz-Theta problems.  hamming6-4 isn't converging
right, and keller4 is working, but takes 5 minutes.  Perhaps johnson8-4-4 will
be the only test case we use in the long run.


Modified: mlpack/trunk/src/mlpack/tests/lrsdp_test.cpp
===================================================================
--- mlpack/trunk/src/mlpack/tests/lrsdp_test.cpp	2012-02-07 05:56:20 UTC (rev 11419)
+++ mlpack/trunk/src/mlpack/tests/lrsdp_test.cpp	2012-02-07 05:57:02 UTC (rev 11420)
@@ -59,15 +59,16 @@
 }*/
 
 /**
- * johnson8-4-4.co test case for Lovasz-Theta LRSDP.
- * See Monteiro and Burer 2004.
+ * Prepare an LRSDP object to solve the Lovasz-Theta SDP in the manner detailed
+ * in Monteiro + Burer 2004.  The list of edges in the graph must be given; that
+ * is all that is necessary to set up the problem.  A matrix which will contain
+ * initial point coordinates should be given also.
  */
-BOOST_AUTO_TEST_CASE(Johnson844LovaszThetaSDP)
+void setupLovaszTheta(const arma::mat& edges,
+                      LRSDP& lovasz,
+                      arma::mat& coordinates)
 {
-  // Load the edges.
-  arma::mat edges;
-  data::Load("johnson8-4-4.csv", edges, true);
-
+  // Get the number of vertices in the problem.
   const size_t vertices = max(max(edges)) + 1;
 
   const size_t m = edges.n_cols + 1;
@@ -75,7 +76,7 @@
   if (ceil(r) > vertices)
     r = vertices; // An upper bound on the dimension.
 
-  arma::mat coordinates(vertices, ceil(r));
+  coordinates.set_size(vertices, ceil(r));
 
   // Now we set the entries of the initial matrix according to the formula given
   // in Section 4 of Monteiro and Burer.
@@ -90,7 +91,7 @@
     }
   }
 
-  LRSDP lovasz;
+  lovasz = LRSDP(coordinates);
 
   // C = -(e e^T) = -ones().
   lovasz.C().ones(vertices, vertices);
@@ -100,24 +101,126 @@
   lovasz.B().zeros(edges.n_cols);
   lovasz.B()[0] = 1;
 
+  // All of the matrices will just contain coordinates because they are
+  // super-sparse (two entries each).  Except for A_0, which is I_n.
+  lovasz.AModes().ones(edges.n_cols);
+  lovasz.AModes()[0] = 0;
+
   // A_0 = I_n.
   lovasz.A().push_back(arma::eye<arma::mat>(vertices, vertices));
 
   // A_ij only has ones at (i, j) and (j, i) and 1 elsewhere.
   for (size_t i = 0; i < edges.n_cols; ++i)
   {
-    arma::mat a;
-    a.zeros(vertices, vertices);
+    arma::mat a(2, 2);
 
-    a(edges(0, i), edges(1, i)) = 1;
-    a(edges(1, i), edges(0, i)) = 1;
+    a(0, 0) = edges(0, i);
+    a(1, 0) = edges(1, i);
+    a(0, 1) = edges(1, i);
+    a(1, 1) = edges(0, i);
 
     lovasz.A().push_back(a);
   }
+}
 
+/**
+ * johnson8-4-4.co test case for Lovasz-Theta LRSDP.
+ * See Monteiro and Burer 2004.
+ */
+BOOST_AUTO_TEST_CASE(Johnson844LovaszThetaSDP)
+{
+  // Load the edges.
+  arma::mat edges;
+  data::Load("johnson8-4-4.csv", edges, true);
+
+  // The LRSDP itself and the initial point.
+  arma::mat coordinates;
+  LRSDP lovasz;
+
+  setupLovaszTheta(edges, lovasz, coordinates);
+
   double finalValue = lovasz.Optimize(coordinates);
 
+  // Final value taken from Monteiro + Burer 2004.
   BOOST_REQUIRE_CLOSE(finalValue, -14.0, 1e-5);
+
+  // Now ensure that all the constraints are satisfied.
+  arma::mat rrt = coordinates * trans(coordinates);
+  BOOST_REQUIRE_CLOSE(trace(rrt), 1.0, 1e-5);
+
+  // All those edge constraints...
+  for (size_t i = 0; i < edges.n_cols; ++i)
+  {
+    BOOST_REQUIRE_SMALL(rrt(edges(0, i), edges(1, i)), 1e-5);
+    BOOST_REQUIRE_SMALL(rrt(edges(1, i), edges(0, i)), 1e-5);
+  }
 }
 
+/**
+ * hamming6-4.co test case for Lovasz-Theta LRSDP.
+ * See Monteiro and Burer 2004.
+ *
+BOOST_AUTO_TEST_CASE(Hamming64LovaszThetaSDP)
+{
+  // Load the edges.
+  arma::mat edges;
+  data::Load("hamming6-4.csv", edges, true);
+
+  // The LRSDP itself and the initial point.
+  arma::mat coordinates;
+  LRSDP lovasz;
+
+  setupLovaszTheta(edges, lovasz, coordinates);
+
+  double finalValue = lovasz.Optimize(coordinates);
+
+  // Final value taken from Monteiro + Burer 2004.
+  BOOST_REQUIRE_CLOSE(finalValue, -5.333333, 1e-5);
+
+  // Now ensure that all the constraints are satisfied.
+  arma::mat rrt = coordinates * trans(coordinates);
+  BOOST_REQUIRE_CLOSE(trace(rrt), 1.0, 1e-5);
+
+  // All those edge constraints...
+  for (size_t i = 0; i < edges.n_cols; ++i)
+  {
+    BOOST_REQUIRE_SMALL(rrt(edges(0, i), edges(1, i)), 1e-5);
+    BOOST_REQUIRE_SMALL(rrt(edges(1, i), edges(0, i)), 1e-5);
+  }
+}*/
+
+/**
+ * keller4.co test case for Lovasz-Theta LRSDP.
+ * See Monteiro and Burer 2004.
+ *
+BOOST_AUTO_TEST_CASE(Keller4LovaszThetaSDP)
+{
+  // Load the edges.
+  arma::mat edges;
+  data::Load("keller4.csv", edges, true);
+
+  // The LRSDP itself and the initial point.
+  arma::mat coordinates;
+  LRSDP lovasz;
+
+  setupLovaszTheta(edges, lovasz, coordinates);
+
+  double finalValue = lovasz.Optimize(coordinates);
+
+  // Final value taken from Monteiro + Burer 2004.
+  BOOST_REQUIRE_CLOSE(finalValue, -14.013, 1e-2); // Not as much precision...
+  // The SB method came to -14.013, but M&B's method only came to -14.005.
+
+  // Now ensure that all the constraints are satisfied.
+  arma::mat rrt = coordinates * trans(coordinates);
+  BOOST_REQUIRE_CLOSE(trace(rrt), 1.0, 1e-5);
+
+  // All those edge constraints...
+  for (size_t i = 0; i < edges.n_cols; ++i)
+  {
+    BOOST_REQUIRE_SMALL(rrt(edges(0, i), edges(1, i)), 1e-3);
+    BOOST_REQUIRE_SMALL(rrt(edges(1, i), edges(0, i)), 1e-3);
+  }
+}*/
+
 BOOST_AUTO_TEST_SUITE_END();




More information about the mlpack-svn mailing list