// 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 .
#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&clauses = constraints.getClauses();
for (unsigned i = clauses.getSize(); i--;) {
solver.addClause(const_cast(clauses[i]));
}
}
CoveringArrayHeuristic heuristic;
StateGuideguide;
CoverageGoal goal(space.computeTargetCoverage());
CoveringArrayAnnealingFilter filter(startingTemperature,decrement);
IterationReport iterationReport;
Searchsearch
(configuration, &space, &heuristic, &guide, &goal, &filter, true);
AnnealingPartitioner partitioner;
// Add the listeners.
{
// For cooling:
((EventSource&)search).addListener(filter);
typedef EventSource >
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();
}