[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