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