swh:1:snp:7a4cd2a5ec73a061be17605597c4b1660b799026
Tip revision: 121131be58bc1b6f91a4863bd01fe7cbd0439ab9 authored by Max Göttlicher on 16 August 2023, 15:14:58 UTC
readme
readme
Tip revision: 121131b
pdssolve.hpp
//
// Created by max on 19.08.22.
//
#ifndef PDS_PDSSOLVE_HPP
#define PDS_PDSSOLVE_HPP
#include "pds.hpp"
#include <queue>
#include <concepts>
namespace pds {
using BoundCallback = std::function<void(size_t lower, size_t upper, size_t extra)>;
template<std::invocable<const PdsState&, const std::string&> F = void(const PdsState&, const std::string&)>
bool exhaustiveSimpleReductions(PdsState& state, F callback = pds::unused) {
bool anyChanged = false;
bool changed;
do {
changed = false;
if (state.disableLowDegree()) { callback(state, "low_degree"); changed = true; }
while (state.collapseLeaves()) { callback(state, "leaves"); changed = true; }
while (state.collapseDegreeTwo()) { callback(state, "path"); changed = true; }
if (state.reduceObservedNonZi()) { callback(state, "non_zi"); changed = true; }
if (state.collapseObservedEdges()) { callback(state, "observed_edges"); changed = true; }
anyChanged |= changed;
} while (changed);
return anyChanged;
}
template<std::invocable<const PdsState&, const std::string&> F = void(const PdsState&, const std::string&)>
bool dominationReductions(PdsState &state, bool firstRun = true, F callback = unused) {
bool changed = false;
if (state.disableObservationNeighborhood()) { callback(state, "observation_neighborhood"); changed = true; }
if ((firstRun || changed) && state.activateNecessaryNodes()) { callback(state, "necessary_nodes"); changed = true; }
return changed;
}
template<std::invocable<const PdsState&, const std::string&> F = void(const PdsState&, const std::string&)>
bool exhaustiveReductions(PdsState &state, bool firstRun = true, F callback = unused) {
bool anyChanged = false;
bool changed;
do {
changed = exhaustiveSimpleReductions(state, callback);
if (firstRun || changed) changed |= dominationReductions(state, firstRun, callback);
firstRun = false;
anyChanged |= changed;
} while (changed);
return anyChanged;
}
template<std::invocable<const PdsState&, const std::string&> F = void(const PdsState&, const std::string&)>
bool noNecessaryReductions(PdsState &state, bool firstRun = true, F callback = unused) {
bool anyChanged = false;
bool changed;
do {
changed = exhaustiveSimpleReductions(state, callback);
if (firstRun || changed) if(state.disableObservationNeighborhood()) {
callback(state, "observation_neighborhood");
changed = true;
}
firstRun = false;
anyChanged |= changed;
} while (changed);
return anyChanged;
}
namespace greedy_strategies {
std::optional<PdsState::Vertex> largestObservationNeighborhood(const PdsState &state);
std::optional<PdsState::Vertex> largestDegree(const PdsState &state);
std::optional<PdsState::Vertex> medianDegree(const PdsState &state);
}
template<
std::invocable<const PdsState&> Strategy = std::optional<PdsState::Vertex>(const PdsState&),
std::invocable<const PdsState&, const std::string&> F = void(const PdsState&, const std::string&)
>
SolveResult solveGreedy(PdsState& state, bool applyReductions = true, Strategy strategy = greedy_strategies::largestObservationNeighborhood, F callback = unused) {
size_t lower = state.numActive();
while (!state.allObserved()) {
if (applyReductions) {
exhaustiveReductions(state, true, callback);
}
if (state.allObserved()) break;
auto best = strategy(state);
if (!best) break;
state.setActive(*best);
}
return {lower, state.numActive(), SolveState::Heuristic};
}
SolveResult fastGreedy(PdsState &state, int useReductions = true);
SolveResult topDownGreedy(PdsState &state, bool activateAll = true, std::span<PdsState::Vertex> vertices = {});
using Bounds = std::pair<size_t, size_t>;
Bounds sensorBounds(const PdsState& state);
template< std::invocable<const PdsState&> Strategy = std::optional<PdsState::Vertex>(const PdsState&) >
SolveResult solveBranching(PdsState &state,
bool useReductions,
Strategy strategy = greedy_strategies::largestDegree) {
if (useReductions) {
exhaustiveReductions(state, true);
}
auto heuristic = state;
fastGreedy(heuristic, true);
auto upper = sensorBounds(heuristic).second;
fmt::print("heuristic result: {}\n", upper);
size_t lower = state.numActive();
auto compare = [](const auto& first, const auto& second) { return first.first.first > second.first.first; };
using Element = std::pair<Bounds, PowerGrid>;
std::priority_queue<Element, std::vector<Element>, decltype(compare)> queue(compare);
queue.push({sensorBounds(state), state.graph()});
size_t explored = 0;
using namespace std::chrono_literals;
auto now = []() { return std::chrono::high_resolution_clock::now(); };
auto sec = [](auto time) { return std::chrono::duration_cast<std::chrono::seconds>(time).count(); };
auto printPeriod = 1s;
auto previousPrint = now();
auto start = previousPrint;
while (!queue.empty()) {
++explored;
PdsState top(std::move(queue.top().second));
auto bounds = queue.top().first;
queue.pop();
if (bounds.first > upper) continue;
lower = bounds.first;
auto t = now();
if (t - previousPrint > printPeriod) {
fmt::print("explored {} nodes\t{}\t{}\t{}\t{}\t{}\t{}s\n", explored, lower, upper, bounds.first, bounds.second, top.allObserved(), sec(t - start));
previousPrint = t;
}
upper = std::min(upper, bounds.second);
if (bounds.first == bounds.second && top.allObserved()) {
heuristic = top;
fmt::print("incumbent solution: {}\t{}\n", bounds.first, top.allObserved());
}
auto best = strategy(top);
if (!best) continue;
auto activated = top;
activated.setActive(*best);
top.setInactive(*best);
if (useReductions) {
exhaustiveReductions(activated);
exhaustiveReductions(top);
}
auto activatedBounds = sensorBounds(activated);
auto disabledBounds = sensorBounds(top);
if (activatedBounds.first < upper) {// && isFeasible(activated)) {// && activatedBounds.first <= activatedBounds.second
upper = std::min(upper, activatedBounds.second);
queue.template emplace(activatedBounds, std::move(activated.moveGraph()));
}
if (disabledBounds.first < upper) {// && isFeasible(top)) { // && disabledBounds.first <= disabledBounds.second
upper = std::min(upper, disabledBounds.second);
queue.emplace(disabledBounds, std::move(top.moveGraph()));
}
}
fmt::print("finished after exploring {} nodes\t{}\t{}\n", explored, lower, upper);
state = std::move(heuristic);
fmt::print("solved by branching. result: {}\n", upper);
return {lower, upper, SolveState::Optimal};
}
} //namespace pds
#endif //PDS_PDSSOLVE_HPP