solverload.cpp
Go to the documentation of this file.
00001 /*************************************************************************** 00002 file : $URL: https://frepple.svn.sourceforge.net/svnroot/frepple/tags/0.9.1/src/solver/solverload.cpp $ 00003 version : $LastChangedRevision: 1656 $ $LastChangedBy: jdetaeye $ 00004 date : $LastChangedDate: 2012-03-27 19:05:34 +0200 (Tue, 27 Mar 2012) $ 00005 ***************************************************************************/ 00006 00007 /*************************************************************************** 00008 * * 00009 * Copyright (C) 2007-2012 by Johan De Taeye, frePPLe bvba * 00010 * * 00011 * This library is free software; you can redistribute it and/or modify it * 00012 * under the terms of the GNU Lesser General Public License as published * 00013 * by the Free Software Foundation; either version 2.1 of the License, or * 00014 * (at your option) any later version. * 00015 * * 00016 * This library is distributed in the hope that it will be useful, * 00017 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 00018 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser * 00019 * General Public License for more details. * 00020 * * 00021 * You should have received a copy of the GNU Lesser General Public * 00022 * License along with this library; if not, write to the Free Software * 00023 * Foundation Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 * 00024 * USA * 00025 * * 00026 ***************************************************************************/ 00027 00028 #define FREPPLE_CORE 00029 #include "frepple/solver.h" 00030 00031 namespace frepple 00032 { 00033 00034 00035 bool sortLoad(const Load* lhs, const Load* rhs) 00036 { 00037 return lhs->getPriority() < rhs->getPriority(); 00038 } 00039 00040 00041 void SolverMRP::solve(const Load* l, void* v) 00042 { 00043 // Note: This method is only called for decrease loadplans and for the leading 00044 // load of an alternate group. See SolverMRP::checkOperation 00045 SolverMRPdata* data = static_cast<SolverMRPdata*>(v); 00046 unsigned int loglevel = data->getSolver()->getLogLevel(); 00047 00048 if (data->state->q_qty >= 0.0) 00049 { 00050 // The loadplan is an increase in size, and the resource solver only needs 00051 // the decreases. 00052 data->state->a_qty = data->state->q_qty; 00053 data->state->a_date = data->state->q_date; 00054 return; 00055 } 00056 00057 if (!l->hasAlternates() && !l->getAlternate()) 00058 { 00059 // CASE I: It is not an alternate load. 00060 // Delegate the answer to the resource 00061 l->getResource()->solve(*this,v); 00062 return; 00063 } 00064 00065 // CASE II: It is an alternate load. 00066 // We ask each alternate load in order of priority till we find a flow 00067 // that has a non-zero reply. 00068 00069 // 1) collect a list of alternates 00070 list<const Load*> thealternates; 00071 const Load *x = l->hasAlternates() ? l : l->getAlternate(); 00072 SearchMode search = l->getSearch(); 00073 for (Operation::loadlist::const_iterator i = l->getOperation()->getLoads().begin(); 00074 i != l->getOperation()->getLoads().end(); ++i) 00075 if ((i->getAlternate() == x || &*i == x) 00076 && i->getEffective().within(data->state->q_loadplan->getDate())) 00077 thealternates.push_back(&*i); 00078 00079 // 2) Sort the list 00080 thealternates.sort(sortLoad); // @todo cpu-intensive - better is to maintain the list in the correct order 00081 00082 // 3) Control the planning mode 00083 bool originalPlanningMode = data->constrainedPlanning; 00084 data->constrainedPlanning = true; 00085 00086 // Don't keep track of the constraints right now 00087 bool originalLogConstraints = data->logConstraints; 00088 data->logConstraints = false; 00089 00090 // 4) Loop through all alternates or till we find a non-zero 00091 // reply (priority search) 00092 Date min_next_date(Date::infiniteFuture); 00093 LoadPlan *lplan = data->state->q_loadplan; 00094 double bestAlternateValue = DBL_MAX; 00095 double bestAlternateQuantity = DBL_MIN; 00096 const Load* bestAlternateSelection = NULL; 00097 double beforeCost = data->state->a_cost; 00098 double beforePenalty = data->state->a_penalty; 00099 OperationPlanState originalOpplan(lplan->getOperationPlan()); 00100 double originalLoadplanQuantity = data->state->q_loadplan->getQuantity(); 00101 for (list<const Load*>::const_iterator i = thealternates.begin(); 00102 i != thealternates.end();) 00103 { 00104 const Load *curload = *i; 00105 data->state->q_loadplan = lplan; // because q_loadplan can change! 00106 00107 // 4a) Switch to this load 00108 if (lplan->getLoad() != curload) lplan->setLoad(curload); 00109 lplan->getOperationPlan()->restore(originalOpplan); 00110 data->state->q_qty = lplan->getQuantity(); 00111 data->state->q_date = lplan->getDate(); 00112 00113 // 4b) Ask the resource 00114 CommandManager::Bookmark* topcommand = data->setBookmark(); 00115 if (search == PRIORITY) 00116 curload->getResource()->solve(*this,data); 00117 else 00118 { 00119 data->getSolver()->setLogLevel(0); 00120 try {curload->getResource()->solve(*this,data);} 00121 catch (...) 00122 { 00123 data->getSolver()->setLogLevel(loglevel); 00124 // Restore the planning mode 00125 data->constrainedPlanning = originalPlanningMode; 00126 data->logConstraints = originalLogConstraints; 00127 throw; 00128 } 00129 data->getSolver()->setLogLevel(loglevel); 00130 } 00131 00132 // 4c) Evaluate the result 00133 if (data->state->a_qty > ROUNDING_ERROR 00134 && lplan->getOperationPlan()->getQuantity() > 0) 00135 { 00136 if (search == PRIORITY) 00137 { 00138 // Priority search: accept any non-zero reply 00139 // Restore the planning mode 00140 data->constrainedPlanning = originalPlanningMode; 00141 data->logConstraints = originalLogConstraints; 00142 return; 00143 } 00144 else 00145 { 00146 // Other search modes: evaluate all 00147 double deltaCost = data->state->a_cost - beforeCost; 00148 double deltaPenalty = data->state->a_penalty - beforePenalty; 00149 // Message 00150 if (loglevel>1 && search != PRIORITY) 00151 logger << indent(l->getOperation()->getLevel()) << " Operation '" 00152 << l->getOperation()->getName() << "' evaluates alternate '" 00153 << curload->getResource() << "': cost " << deltaCost 00154 << ", penalty " << deltaPenalty << endl; 00155 if (deltaCost < ROUNDING_ERROR && deltaPenalty < ROUNDING_ERROR) 00156 { 00157 // Zero cost and zero penalty on this alternate. It won't get any better 00158 // than this, so we accept this alternate. 00159 if (loglevel) 00160 logger << indent(l->getOperation()->getLevel()) << " Operation '" 00161 << l->getOperation()->getName() << "' chooses alternate '" 00162 << curload->getResource() << "' " << search << endl; 00163 // Restore the planning mode 00164 data->constrainedPlanning = originalPlanningMode; 00165 data->logConstraints = originalLogConstraints; 00166 return; 00167 } 00168 data->state->a_cost = beforeCost; 00169 data->state->a_penalty = beforePenalty; 00170 double val = 0.0; 00171 switch (search) 00172 { 00173 case MINCOST: 00174 val = deltaCost / lplan->getOperationPlan()->getQuantity(); 00175 break; 00176 case MINPENALTY: 00177 val = deltaPenalty / lplan->getOperationPlan()->getQuantity(); 00178 break; 00179 case MINCOSTPENALTY: 00180 val = (deltaCost + deltaPenalty) / lplan->getOperationPlan()->getQuantity(); 00181 break; 00182 default: 00183 LogicException("Unsupported search mode for alternate load"); 00184 } 00185 if (val + ROUNDING_ERROR < bestAlternateValue 00186 || (fabs(val - bestAlternateValue) < ROUNDING_ERROR 00187 && lplan->getOperationPlan()->getQuantity() > bestAlternateQuantity)) 00188 { 00189 // Found a better alternate 00190 bestAlternateValue = val; 00191 bestAlternateSelection = curload; 00192 bestAlternateQuantity = lplan->getOperationPlan()->getQuantity(); 00193 } 00194 } 00195 } 00196 else if (loglevel>1 && search != PRIORITY) 00197 logger << indent(l->getOperation()->getLevel()) << " Operation '" 00198 << l->getOperation()->getName() << "' evaluates alternate '" 00199 << curload->getResource() << "': not available before " 00200 << data->state->a_date << endl; 00201 00202 // 4d) Undo the plan on the alternate 00203 data->rollback(topcommand); 00204 00205 // 4e) Prepare for the next alternate 00206 if (data->state->a_date < min_next_date) 00207 min_next_date = data->state->a_date; 00208 if (++i != thealternates.end() && loglevel>1 && search == PRIORITY) 00209 logger << indent(curload->getOperation()->getLevel()) << " Alternate load switches from '" 00210 << curload->getResource()->getName() << "' to '" 00211 << (*i)->getResource()->getName() << "'" << endl; 00212 } 00213 00214 // 5) Unconstrained plan: plan on the first alternate 00215 if (!originalPlanningMode && !(search != PRIORITY && bestAlternateSelection)) 00216 { 00217 // Switch to unconstrained planning 00218 data->constrainedPlanning = false; 00219 bestAlternateSelection = *(thealternates.begin()); 00220 } 00221 00222 // 6) Finally replan on the best alternate 00223 if (!originalPlanningMode || (search != PRIORITY && bestAlternateSelection)) 00224 { 00225 // Message 00226 if (loglevel) 00227 logger << indent(l->getOperation()->getLevel()) << " Operation '" 00228 << l->getOperation()->getName() << "' chooses alternate '" 00229 << bestAlternateSelection->getResource() << "' " << search << endl; 00230 00231 // Switch back 00232 data->state->q_loadplan = lplan; // because q_loadplan can change! 00233 data->state->a_cost = beforeCost; 00234 data->state->a_penalty = beforePenalty; 00235 if (lplan->getLoad() != bestAlternateSelection) 00236 lplan->setLoad(bestAlternateSelection); 00237 lplan->getOperationPlan()->restore(originalOpplan); 00238 data->state->q_qty = lplan->getQuantity(); 00239 data->state->q_date = lplan->getDate(); 00240 bestAlternateSelection->getResource()->solve(*this,data); 00241 00242 // Restore the planning mode 00243 data->constrainedPlanning = originalPlanningMode; 00244 data->logConstraints = originalLogConstraints; 00245 return; 00246 } 00247 00248 // 7) No alternate gave a good result 00249 data->state->a_date = min_next_date; 00250 data->state->a_qty = 0; 00251 00252 // Restore the planning mode 00253 data->constrainedPlanning = originalPlanningMode; 00254 00255 // Maintain the constraint list 00256 if (originalLogConstraints) 00257 { 00258 const Load *primary = *(thealternates.begin()); 00259 data->planningDemand->getConstraints().push( 00260 ProblemCapacityOverload::metadata, 00261 primary->getResource(), originalOpplan.start, originalOpplan.end, 00262 -originalLoadplanQuantity); 00263 } 00264 data->logConstraints = originalLogConstraints; 00265 00266 if (loglevel>1) 00267 logger << indent(lplan->getOperationPlan()->getOperation()->getLevel()) << 00268 " Alternate load doesn't find supply on any alternate : " 00269 << data->state->a_qty << " " << data->state->a_date << endl; 00270 } 00271 00272 00273 }