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 }

Documentation generated for frePPLe by  doxygen