1 files changed, 152 insertions, 0 deletions
diff --git a/casa/annealing/Anneal.C b/casa/annealing/Anneal.C
new file mode 100644
index 0000000..b77e344
--- /dev/null
+++ b/casa/annealing/Anneal.C
@@ -0,0 +1,152 @@
+// Copyright 2008, 2009 Brady J. Garvin
+
+// This file is part of Covering Arrays by Simulated Annealing (CASA).
+
+// CASA is free software: you can redistribute it and/or modify it
+// under the terms of the GNU General Public License as published by
+// the Free Software Foundation, either version 3 of the License, or
+// (at your option) any later version.
+
+// CASA is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License
+// along with CASA.  If not, see <http://www.gnu.org/licenses/>.
+
+
+#include "io/Usage.H"
+
+#include "annealing/Anneal.H"
+#include "annealing/Bounds.H"
+#include "annealing/AnnealingSuccess.H"
+#include "annealing/AnnealingPartitioner.H"
+
+#include "search/Search.H"
+#include "search/StateGuide.H"
+
+#include "covering/space/SingleChangeSpace.H"
+#include "covering/space/GraftSpace.H"
+#include "covering/heuristic/CoveringArrayHeuristic.H"
+#include "covering/goal/CoverageGoal.H"
+#include "covering/filter/CoveringArrayAnnealingFilter.H"
+#include "covering/report/IterationReport.H"
+
+#include "algorithms/BinarySearch.H"
+
+CoveringArray anneal
+  (const SpecificationFile&specification,
+   const ConstraintFile&constraints,
+   unsigned iterations,
+   double startingTemperature,
+   double decrement) {
+  std::cout << "Setting up annealing framework" << std::endl;
+  // Build and connect all of the pieces of the search.
+  // For simulated annealing:
+  SearchConfiguration configuration(false,true,1U,0U);
+#ifdef WITHOUT_INNER
+  SingleChangeSpace space
+#else
+  GraftSpace space
+#endif
+    (specification.getStrength(), specification.getOptions());
+  // Add the constraints.
+  {
+    SATSolver&solver = space.getSolver();
+    const Array<InputClause>&clauses = constraints.getClauses();
+    for (unsigned i = clauses.getSize(); i--;) {
+      solver.addClause(const_cast<InputClause&>(clauses[i]));
+    }
+  }
+  CoveringArrayHeuristic heuristic;
+  StateGuide<CoveringArray, CoverageCost>guide;
+  CoverageGoal goal(space.computeTargetCoverage());
+  CoveringArrayAnnealingFilter filter(startingTemperature,decrement);
+  IterationReport iterationReport;
+  Search<CoveringArray, CoverageCost>search
+    (configuration, &space, &heuristic, &guide, &goal, &filter, true);
+  AnnealingPartitioner partitioner;
+  // Add the listeners.
+  {
+    // For cooling:
+    ((EventSource<SearchIteration>&)search).addListener(filter);
+    typedef EventSource<SearchFinish<CoveringArray, CoverageCost> >
+      FinishEventSourceT;
+    // Structure start states:
+    ((FinishEventSourceT&)search).addListener(space);
+    // Use search feedback to guide the outer search:
+    ((FinishEventSourceT&)search).addListener(partitioner);
+    // Give reports on iterations taken:
+    ((FinishEventSourceT&)search).addListener(iterationReport);
+  }
+  CoveringArray initialSolution
+    (0,
+     specification.getStrength(),
+     specification.getOptions(),
+     space.getSolver());
+
+  // Here we go...
+  std::cout << "Annealing"
+#ifdef WITHOUT_INNER
+       << " (without t-set replacement)"
+#endif
+#ifdef WITHOUT_OUTER
+       << " (without extra outer search)"
+#endif
+       << std::endl;
+  unsigned lower =
+    computeLowerBound(specification.getStrength(), specification.getOptions());
+  unsigned upper =
+    computeUpperBound(specification.getStrength(), specification.getOptions());
+  AnnealingSuccess annealingSuccess(search, iterations, initialSolution);
+
+  std::cout << "Suspect that the optimum number of rows is in [" << lower <<
+    ".." << upper << ']' << std::endl;
+  std::cout << "Starting binary search" << std::endl;
+  BinarySearch binarySearch(annealingSuccess, partitioner);
+  unsigned result = binarySearch(lower, upper + 1 - lower);
+  while (result > upper) {
+    upper <<= 1;
+    std::cout << "Trying more conservative upper bound " << upper << std::endl;
+    result = binarySearch(lower, upper + 1 - lower);
+  }
+#ifndef WITHOUT_OUTER
+  do {
+    if (result == lower) {
+      if (lower > 5) {
+	lower -= 5;
+      } else {
+	--lower;
+	if (!lower) {
+	  break;
+	}
+      }
+      std::cout << "Trying less conservative lower bound " << lower <<
+	std::endl;
+    }
+    unsigned lastResult = result;
+    unsigned upped = 0;
+    do {
+      if (lastResult == result) {
+	iterations *= 2;
+	annealingSuccess.setIterations(iterations);
+	std::cout << "Upping iterations to " << iterations << std::endl;
+	++upped;
+      } else {
+	upped = 0;
+      }
+      lastResult = result;
+      std::cout << "Restarting binary search with best result at " <<
+	lastResult << " rows" << std::endl;
+      filter.setTemperature(startingTemperature);
+      result = binarySearch(lower, lastResult - lower);
+    } while ((result < lastResult || upped < retries) && result > lower);
+  } while (result == lower);
+#endif
+  std::cout << "Giving up with best result at " << result << " rows" <<
+    std::endl;
+  std::cout << "Total cost of computation: " << iterationReport.getTotal() <<
+    " iteration(s)" << std::endl;
+  return annealingSuccess.getSolution();
+}