solverdemand.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/solverdemand.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 00032 namespace frepple 00033 { 00034 00035 00036 DECLARE_EXPORT void SolverMRP::solve(const Demand* l, void* v) 00037 { 00038 // Call the user exit 00039 SolverMRPdata* data = static_cast<SolverMRPdata*>(v); 00040 if (userexit_demand) userexit_demand.call(l, PythonObject(data->constrainedPlanning)); 00041 unsigned int loglevel = data->getSolver()->getLogLevel(); 00042 00043 // Note: This solver method does not push/pop states on the stack. 00044 // We continue to work on the top element of the stack. 00045 00046 // Message 00047 if (loglevel>0) 00048 { 00049 logger << "Planning demand '" << l->getName() << "' (" << l->getPriority() 00050 << ", " << l->getDue() << ", " << l->getQuantity() << ")"; 00051 if (!data->constrainedPlanning || !data->getSolver()->isConstrained()) 00052 logger << " in unconstrained mode"; 00053 logger << endl; 00054 } 00055 00056 // Unattach previous delivery operationplans. 00057 // Locked operationplans will NOT be deleted, and a part of the demand can 00058 // still remain planned. 00059 const_cast<Demand*>(l)->deleteOperationPlans(false, data); 00060 00061 // Empty constraint list 00062 const_cast<Demand*>(l)->getConstraints().clear(); 00063 00064 // Determine the quantity to be planned and the date for the planning loop 00065 double plan_qty = l->getQuantity() - l->getPlannedQuantity(); 00066 Date plan_date = l->getDue(); 00067 00068 // Nothing to be planned any more (e.g. all deliveries are locked...) 00069 if (plan_qty < ROUNDING_ERROR) 00070 { 00071 if (loglevel>0) logger << " Nothing to be planned." << endl; 00072 return; 00073 } 00074 00075 // Temporary values to store the 'best-reply' so far 00076 double best_q_qty = 0.0, best_a_qty = 0.0; 00077 Date best_q_date; 00078 00079 // Which operation to use? 00080 Operation* deliveryoper = l->getDeliveryOperation(); 00081 string problemtext = string("Demand '") + l->getName() + "' has no delivery operation"; 00082 if (!deliveryoper) 00083 { 00084 // Create a problem 00085 new ProblemInvalidData(const_cast<Demand*>(l), problemtext, "demand", 00086 l->getDue(), l->getDue(), l->getQuantity()); 00087 // Abort planning of this demand 00088 throw DataException("Demand '" + l->getName() + "' can't be planned"); 00089 } 00090 else 00091 { 00092 // Remove problem that may already exist 00093 for (Problem::const_iterator j = Problem::begin(const_cast<Demand*>(l), false); 00094 j!=Problem::end(); ++j) 00095 if (&(j->getType()) == ProblemInvalidData::metadata 00096 && j->getDescription() == problemtext) 00097 { 00098 delete &*j; 00099 break; 00100 } 00101 } 00102 00103 // Planning loop 00104 do 00105 { 00106 // Message 00107 if (loglevel>0) 00108 logger << "Demand '" << l << "' asks: " 00109 << plan_qty << " " << plan_date << endl; 00110 00111 // Store the last command in the list, in order to undo the following 00112 // commands if required. 00113 CommandManager::Bookmark* topcommand = data->setBookmark(); 00114 00115 // Plan the demand by asking the delivery operation to plan 00116 double q_qty = plan_qty; 00117 data->state->curBuffer = NULL; 00118 data->state->q_qty = plan_qty; 00119 data->state->q_date = plan_date; 00120 data->state->curDemand = const_cast<Demand*>(l); 00121 data->state->motive = const_cast<Demand*>(l); 00122 deliveryoper->solve(*this,v); 00123 Date next_date = data->state->a_date; 00124 00125 if (data->state->a_qty < ROUNDING_ERROR 00126 && plan_qty > l->getMinShipment() && l->getMinShipment() > 0) 00127 { 00128 bool originalLogConstraints = data->logConstraints; 00129 data->logConstraints = false; 00130 try 00131 { 00132 // The full asked quantity is not possible. 00133 // Try with the minimum shipment quantity. 00134 if (loglevel>0) 00135 logger << "Demand '" << l << "' tries planning minimum quantity " << l->getMinShipment() << endl; 00136 data->rollback(topcommand); 00137 data->state->curBuffer = NULL; 00138 data->state->q_qty = l->getMinShipment(); 00139 data->state->q_date = plan_date; 00140 data->state->curDemand = const_cast<Demand*>(l); 00141 deliveryoper->solve(*this,v); 00142 if (data->state->a_date < next_date) 00143 next_date = data->state->a_date; 00144 if (data->state->a_qty > ROUNDING_ERROR) 00145 { 00146 // The minimum shipment quantity is feasible. 00147 // Now try iteratively different quantities to find the best we can do. 00148 double min_qty = l->getMinShipment(); 00149 double max_qty = plan_qty; 00150 double delta = fabs(max_qty - min_qty); 00151 while (delta > data->getSolver()->getIterationAccuracy() * l->getQuantity() 00152 && delta > data->getSolver()->getIterationThreshold()) 00153 { 00154 double new_qty = floor((min_qty + max_qty) / 2); // @TODO not generic to round down to an integer here 00155 if (loglevel>0) 00156 logger << "Demand '" << l << "' tries planning a different quantity " << new_qty << endl; 00157 data->rollback(topcommand); 00158 data->state->curBuffer = NULL; 00159 data->state->q_qty = new_qty; 00160 data->state->q_date = plan_date; 00161 data->state->curDemand = const_cast<Demand*>(l); 00162 deliveryoper->solve(*this,v); 00163 if (data->state->a_date < next_date) 00164 next_date = data->state->a_date; 00165 if (data->state->a_qty > ROUNDING_ERROR) 00166 // Too small: new min 00167 min_qty = new_qty; 00168 else 00169 // Too big: new max 00170 max_qty = new_qty; 00171 delta = fabs(max_qty - min_qty); 00172 } 00173 q_qty = min_qty; // q_qty is the biggest Q quantity giving a positive reply 00174 if (data->state->a_qty <= ROUNDING_ERROR) 00175 { 00176 if (loglevel>0) 00177 logger << "Demand '" << l << "' restores plan for quantity " << min_qty << endl; 00178 // Restore the last feasible plan 00179 data->rollback(topcommand); 00180 data->state->curBuffer = NULL; 00181 data->state->q_qty = min_qty; 00182 data->state->q_date = plan_date; 00183 data->state->curDemand = const_cast<Demand*>(l); 00184 deliveryoper->solve(*this,v); 00185 } 00186 } 00187 } 00188 catch (...) 00189 { 00190 data->logConstraints = originalLogConstraints; 00191 throw; 00192 } 00193 data->logConstraints = originalLogConstraints; 00194 } 00195 00196 // Message 00197 if (loglevel>0) 00198 logger << "Demand '" << l << "' gets answer: " 00199 << data->state->a_qty << " " << next_date << " " 00200 << data->state->a_cost << " " << data->state->a_penalty << endl; 00201 00202 // Update the date to plan in the next loop 00203 Date copy_plan_date = plan_date; 00204 00205 // Compare the planned quantity with the minimum allowed shipment quantity 00206 // We don't accept the answer in case: 00207 // 1) Nothing is planned 00208 // 2) The planned quantity is less than the minimum shipment quantity 00209 // 3) The remaining quantity after accepting this answer is less than 00210 // the minimum quantity. 00211 if (data->state->a_qty < ROUNDING_ERROR 00212 || data->state->a_qty + ROUNDING_ERROR < l->getMinShipment() 00213 || (q_qty - data->state->a_qty < l->getMinShipment() 00214 && q_qty - data->state->a_qty > ROUNDING_ERROR)) 00215 { 00216 if (q_qty - data->state->a_qty < l->getMinShipment() 00217 && data->state->a_qty + ROUNDING_ERROR >= l->getMinShipment() 00218 && data->state->a_qty > best_a_qty ) 00219 { 00220 // The remaining quantity after accepting this answer is less than 00221 // the minimum quantity. Therefore, we delay accepting it now, but 00222 // still keep track of this best offer. 00223 best_a_qty = data->state->a_qty; 00224 best_q_qty = q_qty; 00225 best_q_date = plan_date; 00226 } 00227 00228 // Delete operationplans - Undo all changes 00229 data->rollback(topcommand); 00230 00231 // Set the ask date for the next pass through the loop 00232 if (next_date <= copy_plan_date) 00233 { 00234 // Oops, we didn't get a proper answer we can use for the next loop. 00235 // Print a warning and simply try one day later. 00236 if (loglevel>0) 00237 logger << "Warning: Demand '" << l << "': Lazy retry" << endl; 00238 plan_date = copy_plan_date + data->getSolver()->getLazyDelay(); 00239 } 00240 else 00241 // Use the next-date answer from the solver 00242 plan_date = next_date; 00243 } 00244 else 00245 { 00246 // Accepting this answer 00247 if (data->state->a_qty + ROUNDING_ERROR < q_qty) 00248 { 00249 // The demand was only partially planned. We need to do a new 00250 // 'coordinated' planning run. 00251 00252 // Delete operationplans created in the 'testing round' 00253 data->rollback(topcommand); 00254 00255 // Create the correct operationplans 00256 if (loglevel>=2) 00257 logger << "Demand '" << l << "' plans coordination." << endl; 00258 data->getSolver()->setLogLevel(0); 00259 double tmpresult = data->state->a_qty; 00260 try 00261 { 00262 for(double remainder = data->state->a_qty; 00263 remainder > ROUNDING_ERROR; remainder -= data->state->a_qty) 00264 { 00265 data->state->q_qty = remainder; 00266 data->state->q_date = copy_plan_date; 00267 data->state->curDemand = const_cast<Demand*>(l); 00268 data->state->curBuffer = NULL; 00269 deliveryoper->solve(*this,v); 00270 if (data->state->a_qty < ROUNDING_ERROR) 00271 { 00272 logger << "Warning: Demand '" << l << "': Failing coordination" << endl; 00273 break; 00274 } 00275 } 00276 } 00277 catch (...) 00278 { 00279 data->getSolver()->setLogLevel(loglevel); 00280 throw; 00281 } 00282 data->getSolver()->setLogLevel(loglevel); 00283 data->state->a_qty = tmpresult; 00284 } 00285 00286 // Register the new operationplans. We need to make sure that the 00287 // correct execute method is called! 00288 if (data->getSolver()->getAutocommit()) 00289 { 00290 data->getSolver()->scanExcess(data); 00291 data->CommandManager::commit(); 00292 } 00293 00294 // Update the quantity to plan in the next loop 00295 plan_qty -= data->state->a_qty; 00296 best_a_qty = 0.0; // Reset 'best-answer' remember 00297 } 00298 00299 } 00300 // Repeat while there is still a quantity left to plan and we aren't 00301 // exceeding the maximum delivery delay. 00302 while (plan_qty > ROUNDING_ERROR 00303 && ((data->getSolver()->getPlanType() != 2 && plan_date < l->getDue() + l->getMaxLateness()) 00304 || (data->getSolver()->getPlanType() == 2 && !data->constrainedPlanning && plan_date < l->getDue() + l->getMaxLateness()) 00305 || (data->getSolver()->getPlanType() == 2 && data->constrainedPlanning && plan_date == l->getDue()) 00306 )); 00307 00308 // Accept the best possible answer. 00309 // We may have skipped it in the previous loop, awaiting a still better answer 00310 if (best_a_qty > 0.0 && data->constrainedPlanning) 00311 { 00312 if (loglevel>=2) logger << "Demand '" << l << "' accepts a best answer." << endl; 00313 data->getSolver()->setLogLevel(0); 00314 try 00315 { 00316 for(double remainder = best_q_qty; 00317 remainder > ROUNDING_ERROR; remainder -= data->state->a_qty) 00318 { 00319 data->state->q_qty = remainder; 00320 data->state->q_date = best_q_date; 00321 data->state->curDemand = const_cast<Demand*>(l); 00322 data->state->curBuffer = NULL; 00323 deliveryoper->solve(*this,v); 00324 if (data->state->a_qty < ROUNDING_ERROR) 00325 { 00326 logger << "Warning: Demand '" << l << "': Failing accepting best answer" << endl; 00327 break; 00328 } 00329 } 00330 if (data->getSolver()->getAutocommit()) 00331 { 00332 data->getSolver()->scanExcess(data); 00333 data->CommandManager::commit(); 00334 } 00335 } 00336 catch (...) 00337 { 00338 data->getSolver()->setLogLevel(loglevel); 00339 throw; 00340 } 00341 data->getSolver()->setLogLevel(loglevel); 00342 } 00343 } 00344 00345 00346 DECLARE_EXPORT void SolverMRP::scanExcess(CommandManager* mgr) 00347 { 00348 for(CommandManager::iterator i = mgr->begin(); i != mgr->end(); ++i) 00349 if (i->isActive()) scanExcess(&*i); 00350 } 00351 00352 00353 DECLARE_EXPORT void SolverMRP::scanExcess(CommandList* l) 00354 { 00355 // Loop over all newly created operationplans found in the command stack 00356 for(CommandList::iterator cmd = l->begin(); cmd != l->end(); ++cmd) 00357 { 00358 CommandCreateOperationPlan* createcmd = dynamic_cast<CommandCreateOperationPlan*>(&*cmd); 00359 if (!createcmd) 00360 { 00361 // If the command is a list: recursively call this function 00362 if (dynamic_cast<CommandList*>(&*cmd)) 00363 scanExcess(dynamic_cast<CommandList*>(&*cmd)); 00364 //else: Not a command creating an operationplan: move on 00365 } 00366 else 00367 { 00368 // Detect excess operationplans and undo them 00369 if (createcmd->getOperationPlan() && createcmd->getOperationPlan()->isExcess()) 00370 { 00371 if (getLogLevel()) 00372 logger << "Denying creation of redundant operationplan " 00373 << createcmd->getOperationPlan()->getOperation() << " " 00374 << createcmd->getOperationPlan()->getDates() << " " 00375 << createcmd->getOperationPlan()->getQuantity() << endl; 00376 createcmd->rollback(); 00377 } 00378 } 00379 } 00380 } 00381 00382 }