[mlpack-git] master: lovasz theta SDP test (24dd0a8)
gitdub at big.cc.gt.atl.ga.us
gitdub at big.cc.gt.atl.ga.us
Thu Mar 5 22:12:54 EST 2015
Repository : https://github.com/mlpack/mlpack
On branch : master
Link : https://github.com/mlpack/mlpack/compare/904762495c039e345beba14c1142fd719b3bd50e...f94823c800ad6f7266995c700b1b630d5ffdcf40
>---------------------------------------------------------------
commit 24dd0a8b2d4c92cba5f72908bcf07dd3ee159db4
Author: Stephen Tu <tu.stephenl at gmail.com>
Date: Thu Jan 15 18:57:19 2015 -0800
lovasz theta SDP test
>---------------------------------------------------------------
24dd0a8b2d4c92cba5f72908bcf07dd3ee159db4
src/mlpack/tests/sdp_primal_dual_test.cpp | 48 +++++++++++++++++++++++++------
1 file changed, 40 insertions(+), 8 deletions(-)
diff --git a/src/mlpack/tests/sdp_primal_dual_test.cpp b/src/mlpack/tests/sdp_primal_dual_test.cpp
index 283f288..55053de 100644
--- a/src/mlpack/tests/sdp_primal_dual_test.cpp
+++ b/src/mlpack/tests/sdp_primal_dual_test.cpp
@@ -42,9 +42,10 @@ class UndirectedGraph
}
static void LoadFromEdges(UndirectedGraph& g,
- const std::string& edgesFilename)
+ const std::string& edgesFilename,
+ bool transposeEdges)
{
- data::Load(edgesFilename, g.edges, true, false);
+ data::Load(edgesFilename, g.edges, true, transposeEdges);
if (g.edges.n_rows != 2)
Log::Fatal << "Invalid datafile" << std::endl;
g.weights.ones(g.edges.n_cols);
@@ -53,12 +54,14 @@ class UndirectedGraph
static void LoadFromEdgesAndWeights(UndirectedGraph& g,
const std::string& edgesFilename,
- const std::string& weightsFilename)
+ bool transposeEdges,
+ const std::string& weightsFilename,
+ bool transposeWeights)
{
- data::Load(edgesFilename, g.edges, true, false);
+ data::Load(edgesFilename, g.edges, true, transposeEdges);
if (g.edges.n_rows != 2)
Log::Fatal << "Invalid datafile" << std::endl;
- data::Load(weightsFilename, g.weights, true, false);
+ data::Load(weightsFilename, g.weights, true, transposeWeights);
if (g.weights.n_elem != g.edges.n_cols)
Log::Fatal << "Size mismatch" << std::endl;
g.ComputeVertices();
@@ -125,6 +128,24 @@ ConstructMaxCutSDPFromGraph(const UndirectedGraph& g)
return sdp;
}
+static inline SDP
+ConstructLovaszThetaSDPFromGraph(const UndirectedGraph& g)
+{
+ SDP sdp(g.NumVertices(), g.NumEdges() + 1, 0);
+ sdp.DenseC().ones();
+ sdp.DenseC() *= -1.;
+ sdp.SparseA()[0].eye(g.NumVertices(), g.NumVertices());
+ for (size_t i = 0; i < g.NumEdges(); i++)
+ {
+ sdp.SparseA()[i + 1].zeros(g.NumVertices(), g.NumVertices());
+ sdp.SparseA()[i + 1](g.Edges()(0, i), g.Edges()(1, i)) = 1.;
+ sdp.SparseA()[i + 1](g.Edges()(1, i), g.Edges()(0, i)) = 1.;
+ }
+ sdp.SparseB().zeros();
+ sdp.SparseB()[0] = 1.;
+ return sdp;
+}
+
// TODO: does arma have a builtin way to do this?
static inline arma::mat
Diag(const arma::vec& diag)
@@ -200,9 +221,6 @@ static void SolveMaxCutPositiveSDP(const SDP& sdp)
BOOST_REQUIRE(p.first);
}
-/**
- * Start from a strictly feasible point
- */
BOOST_AUTO_TEST_CASE(SmallMaxCutSdp)
{
SDP sdp = ConstructMaxCutSDPFromLaplacian("r10.txt");
@@ -216,4 +234,18 @@ BOOST_AUTO_TEST_CASE(SmallMaxCutSdp)
SolveMaxCutPositiveSDP(sdp);
}
+BOOST_AUTO_TEST_CASE(SmallLovaszThetaSdp)
+{
+ UndirectedGraph g;
+ UndirectedGraph::LoadFromEdges(g, "johnson8-4-4.csv", true);
+ SDP sdp = ConstructLovaszThetaSDPFromGraph(g);
+
+ PrimalDualSolver solver(sdp);
+
+ arma::mat X, Z;
+ arma::vec ysparse, ydense;
+ const auto p = solver.Optimize(X, ysparse, ydense, Z);
+ BOOST_REQUIRE(p.first);
+}
+
BOOST_AUTO_TEST_SUITE_END();
More information about the mlpack-git
mailing list