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 }

Documentation generated for frePPLe by  doxygen