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