75 int getOptimalSolution(
const T &initialSol,T &finalSol,
double upperLevel=HUGE_VAL,
double maxComputationTime=HUGE_VAL) {
80 std::multimap<double,T> partialSols;
81 partialSols.insert(std::pair<double,T>(
getTotalCost(initialSol),initialSol));
83 double currentOptimal=upperLevel;
85 std::vector<T> children;
87 while (!partialSols.empty()) {
89 if (time.
Tac()>=maxComputationTime)
return found?2:0;
90 typename std::multimap<double,T>::iterator it=partialSols.begin();
91 double tempCost=it->first;
93 if (tempCost>=currentOptimal)
return found?1:0;
95 partialSols.erase(it);
98 currentOptimal=tempCost;
105 for (
typename std::vector<T>::const_iterator it2=children.begin();it2!=children.end();++it2)
if (
isSolutionValid(*it2)) {
106 bool alreadyPresent=
false;
108 typename std::pair<typename std::multimap<double,T>::const_iterator,
typename std::multimap<double,T>::const_iterator> range = partialSols.equal_range(cost);
109 for (
typename std::multimap<double,T>::const_iterator it3=range.first;it3!=range.second;++it3)
if (it3->second==*it2) {
113 if (!alreadyPresent) partialSols.insert(std::pair<double,T>(
getTotalCost(*it2),*it2));