solverdemand.cpp
Go to the documentation of this file.
00001 /***************************************************************************
00002   file : $URL: https://frepple.svn.sourceforge.net/svnroot/frepple/trunk/src/solver/solverdemand.cpp $
00003   version : $LastChangedRevision: 1489 $  $LastChangedBy: jdetaeye $
00004   date : $LastChangedDate: 2011-07-19 16:57:33 +0200 (Tue, 19 Jul 2011) $
00005  ***************************************************************************/
00006 
00007 /***************************************************************************
00008  *                                                                         *
00009  * Copyright (C) 2007-2011 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     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 }

Documentation generated for frePPLe by  doxygen