solverload.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  * *
3  * Copyright (C) 2007-2012 by Johan De Taeye, frePPLe bvba *
4  * *
5  * This library is free software; you can redistribute it and/or modify it *
6  * under the terms of the GNU Affero General Public License as published *
7  * by the Free Software Foundation; either version 3 of the License, or *
8  * (at your option) any later version. *
9  * *
10  * This library is distributed in the hope that it will be useful, *
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of *
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the *
13  * GNU Affero General Public License for more details. *
14  * *
15  * You should have received a copy of the GNU Affero General Public *
16  * License along with this program. *
17  * If not, see <http://www.gnu.org/licenses/>. *
18  * *
19  ***************************************************************************/
20 
21 #define FREPPLE_CORE
22 #include "frepple/solver.h"
23 
24 namespace frepple
25 {
26 
27 
28 bool sortLoad(const Load* lhs, const Load* rhs)
29 {
30  return lhs->getPriority() < rhs->getPriority();
31 }
32 
33 
34 DECLARE_EXPORT void SolverMRP::chooseResource(const Load* l, void* v) // @todo handle unconstrained plan!!!!
35 {
36  if (!l->getSkill() && !l->getResource()->isGroup())
37  {
38  // CASE 1: No skill involved, and no aggregate resource either
39  l->getResource()->solve(*this, v);
40  return;
41  }
42 
43  // CASE 2: Skill involved, or aggregate resource
44  SolverMRPdata* data = static_cast<SolverMRPdata*>(v);
45  unsigned int loglevel = data->getSolver()->getLogLevel();
46 
47  // Control the planning mode
48  bool originalPlanningMode = data->constrainedPlanning;
49  data->constrainedPlanning = true;
50 
51  // Don't keep track of the constraints right now
52  bool originalLogConstraints = data->logConstraints;
53  data->logConstraints = false;
54 
55  // Initialize
56  Date min_next_date(Date::infiniteFuture);
57  LoadPlan *lplan = data->state->q_loadplan;
58  Resource *bestAlternateSelection = NULL;
59  double bestCost = DBL_MAX;
60  bool qualified_resource_exists = false;
61  double bestAlternateValue = DBL_MAX;
62  double bestAlternateQuantity = DBL_MIN;
63  double beforeCost = data->state->a_cost;
64  double beforePenalty = data->state->a_penalty;
65  OperationPlanState originalOpplan(lplan->getOperationPlan());
66  double originalLoadplanQuantity = lplan->getQuantity();
67  data->getSolver()->setLogLevel(0); // Silence during this loop
68 
69  // Loop over all candidate resources
70  stack<Resource*> res_stack;
71  res_stack.push(l->getResource());
72  while (!res_stack.empty())
73  {
74  // Pick next resource
75  Resource* res = res_stack.top();
76  res_stack.pop();
77 
78  // If it's an aggregate, push it's members on the stack
79  if (res->isGroup())
80  {
81  for (Resource::memberIterator x = res->beginMember(); x != Resource::end(); ++x)
82  res_stack.push(&*x);
83  continue;
84  }
85 
86  // Check if the resource has the right skill
87  if (l->getSkill())
88  {
89  bool isqualified = false;
90  for (Resource::skilllist::const_iterator i = res->getSkills().begin();
91  i != res->getSkills().end() && !isqualified; ++i)
92  {
93  if (i->getSkill() == l->getSkill()
94  && originalOpplan.start >= i->getEffective().getStart()
95  && originalOpplan.end <= i->getEffective().getEnd())
96  isqualified = true;
97  }
98  // Next resource in the loop if not qualified
99  if (!isqualified) continue; // TODO if there is a date effective skill, we need to consider it in the reply
100  }
101  qualified_resource_exists = true;
102 
103  // Switch to this resource
104  data->state->q_loadplan = lplan; // because q_loadplan can change!
105  lplan->setResource(res);
106  lplan->getOperationPlan()->restore(originalOpplan);
107  data->state->q_qty = lplan->getQuantity();
108  data->state->q_date = lplan->getDate();
109 
110  // Plan the resource
111  CommandManager::Bookmark* topcommand = data->setBookmark();
112  try { res->solve(*this,data); }
113  catch (...)
114  {
115  data->getSolver()->setLogLevel(loglevel);
116  data->constrainedPlanning = originalPlanningMode;
117  data->logConstraints = originalLogConstraints;
118  data->rollback(topcommand);
119  throw;
120  }
121  data->rollback(topcommand);
122 
123  // Evaluate the result
124  if (data->state->a_qty > ROUNDING_ERROR
125  && lplan->getOperationPlan()->getQuantity() > 0)
126  {
127  double deltaCost = data->state->a_cost - beforeCost;
128  double deltaPenalty = data->state->a_penalty - beforePenalty;
129  // Message
130  if (loglevel>1)
131  logger << indent(l->getOperation()->getLevel()) << " Operation '"
132  << l->getOperation()->getName() << "' evaluates alternate '"
133  << res << "': cost " << deltaCost
134  << ", penalty " << deltaPenalty << endl;
135  data->state->a_cost = beforeCost;
136  data->state->a_penalty = beforePenalty;
137  double val = 0.0;
138  switch (l->getSearch())
139  {
140  case PRIORITY:
141  val = 1; // @todo skill-resource model doesn't have a priority field yet
142  break;
143  case MINCOST:
144  val = deltaCost / lplan->getOperationPlan()->getQuantity();
145  break;
146  case MINPENALTY:
147  val = deltaPenalty / lplan->getOperationPlan()->getQuantity();
148  break;
149  case MINCOSTPENALTY:
150  val = (deltaCost + deltaPenalty) / lplan->getOperationPlan()->getQuantity();
151  break;
152  default:
153  LogicException("Unsupported search mode for alternate load");
154  }
155  if (val + ROUNDING_ERROR < bestAlternateValue
156  || (fabs(val - bestAlternateValue) < ROUNDING_ERROR
157  && lplan->getOperationPlan()->getQuantity() > bestAlternateQuantity))
158  {
159  // Found a better alternate
160  bestAlternateValue = val;
161  bestAlternateSelection = res;
162  bestAlternateQuantity = lplan->getOperationPlan()->getQuantity();
163  }
164  }
165  else if (loglevel>1)
166  logger << indent(l->getOperation()->getLevel()) << " Operation '"
167  << l->getOperation()->getName() << "' evaluates alternate '"
168  << lplan->getResource() << "': not available before "
169  << data->state->a_date << endl;
170 
171  // Keep track of best next date
172  if (data->state->a_date < min_next_date)
173  min_next_date = data->state->a_date;
174  }
175  data->getSolver()->setLogLevel(loglevel);
176 
177  // Not a single resource has the appropriate skills. You're joking?
178  if (!qualified_resource_exists)
179  throw DataException("No qualified resource exists for load");
180 
181  // Restore the best candidate we found in the loop above
182  if (bestAlternateSelection)
183  {
184  // Message
185  if (loglevel)
186  logger << indent(l->getOperation()->getLevel()) << " Operation '"
187  << l->getOperation()->getName() << "' chooses alternate '"
188  << bestAlternateSelection << "' " << l->getSearch() << endl;
189 
190  // Switch back
191  data->state->q_loadplan = lplan; // because q_loadplan can change!
192  data->state->a_cost = beforeCost;
193  data->state->a_penalty = beforePenalty;
194  if (lplan->getResource() != bestAlternateSelection)
195  lplan->setResource(bestAlternateSelection);
196  lplan->getOperationPlan()->restore(originalOpplan);
197  data->state->q_qty = lplan->getQuantity();
198  data->state->q_date = lplan->getDate();
199  bestAlternateSelection->solve(*this,data);
200 
201  // Restore the planning mode
202  data->constrainedPlanning = originalPlanningMode;
203  data->logConstraints = originalLogConstraints;
204  return;
205  }
206 
207  // 7) No alternate gave a good result
208  data->state->a_date = min_next_date;
209  data->state->a_qty = 0;
210 
211  // Restore the planning mode
212  data->constrainedPlanning = originalPlanningMode;
213 
214  // Maintain the constraint list
215  if (originalLogConstraints)
216  {
217  data->planningDemand->getConstraints().push(
219  l->getResource(), originalOpplan.start, originalOpplan.end,
220  -originalLoadplanQuantity);
221  }
222  data->logConstraints = originalLogConstraints;
223 
224  if (loglevel>1)
225  logger << indent(lplan->getOperationPlan()->getOperation()->getLevel()) <<
226  " Alternate load doesn't find supply on any alternate : "
227  << data->state->a_qty << " " << data->state->a_date << endl;
228 }
229 
230 
231 void SolverMRP::solve(const Load* l, void* v)
232 {
233  // Note: This method is only called for decrease loadplans and for the leading
234  // load of an alternate group. See SolverMRP::checkOperation
235  SolverMRPdata* data = static_cast<SolverMRPdata*>(v);
236  unsigned int loglevel = data->getSolver()->getLogLevel();
237 
238  if (data->state->q_qty >= 0.0)
239  {
240  // The loadplan is an increase in size, and the resource solver only needs
241  // the decreases.
242  data->state->a_qty = data->state->q_qty;
243  data->state->a_date = data->state->q_date;
244  return;
245  }
246 
247  if (!l->hasAlternates() && !l->getAlternate())
248  {
249  // CASE I: It is not an alternate load.
250  // Delegate the answer immediately to the resource
251  chooseResource(l, data);
252  return;
253  }
254 
255  // CASE II: It is an alternate load.
256  // We ask each alternate load in order of priority till we find a load
257  // that has a non-zero reply.
258 
259  // 1) collect a list of alternates
260  list<const Load*> thealternates;
261  const Load *x = l->hasAlternates() ? l : l->getAlternate();
262  SearchMode search = l->getSearch();
263  for (Operation::loadlist::const_iterator i = l->getOperation()->getLoads().begin();
264  i != l->getOperation()->getLoads().end(); ++i)
265  if ((i->getAlternate() == x || &*i == x)
266  && i->getEffective().within(data->state->q_loadplan->getDate()))
267  thealternates.push_back(&*i);
268 
269  // 2) Sort the list
270  thealternates.sort(sortLoad); // @todo cpu-intensive - better is to maintain the list in the correct order
271 
272  // 3) Control the planning mode
273  bool originalPlanningMode = data->constrainedPlanning;
274  data->constrainedPlanning = true;
275 
276  // Don't keep track of the constraints right now
277  bool originalLogConstraints = data->logConstraints;
278  data->logConstraints = false;
279 
280  // 4) Loop through all alternates or till we find a non-zero
281  // reply (priority search)
282  Date min_next_date(Date::infiniteFuture);
283  LoadPlan *lplan = data->state->q_loadplan;
284  double bestAlternateValue = DBL_MAX;
285  double bestAlternateQuantity = DBL_MIN;
286  const Load* bestAlternateSelection = NULL;
287  double beforeCost = data->state->a_cost;
288  double beforePenalty = data->state->a_penalty;
289  OperationPlanState originalOpplan(lplan->getOperationPlan());
290  double originalLoadplanQuantity = data->state->q_loadplan->getQuantity();
291  for (list<const Load*>::const_iterator i = thealternates.begin();
292  i != thealternates.end();)
293  {
294  const Load *curload = *i;
295  data->state->q_loadplan = lplan; // because q_loadplan can change!
296 
297  // 4a) Switch to this load
298  if (lplan->getLoad() != curload) lplan->setLoad(curload);
299  lplan->getOperationPlan()->restore(originalOpplan);
300  data->state->q_qty = lplan->getQuantity();
301  data->state->q_date = lplan->getDate();
302 
303  // 4b) Ask the resource
304  // TODO XXX Need to insert another loop here! It goes over all resources qualified for the required skill.
305  // The qualified resources need to be sorted based on their cost. If the cost is the same we should use a decent tie breaker, eg number of skills or number of loads.
306  // The first resource with the qualified skill that is available will be used.
307  CommandManager::Bookmark* topcommand = data->setBookmark();
308  if (search == PRIORITY)
309  curload->getResource()->solve(*this,data);
310  else
311  {
312  data->getSolver()->setLogLevel(0);
313  try {curload->getResource()->solve(*this,data);}
314  catch (...)
315  {
316  data->getSolver()->setLogLevel(loglevel);
317  // Restore the planning mode
318  data->constrainedPlanning = originalPlanningMode;
319  data->logConstraints = originalLogConstraints;
320  throw;
321  }
322  data->getSolver()->setLogLevel(loglevel);
323  }
324 
325  // 4c) Evaluate the result
326  if (data->state->a_qty > ROUNDING_ERROR
327  && lplan->getOperationPlan()->getQuantity() > 0)
328  {
329  if (search == PRIORITY)
330  {
331  // Priority search: accept any non-zero reply
332  // Restore the planning mode
333  data->constrainedPlanning = originalPlanningMode;
334  data->logConstraints = originalLogConstraints;
335  return;
336  }
337  else
338  {
339  // Other search modes: evaluate all
340  double deltaCost = data->state->a_cost - beforeCost;
341  double deltaPenalty = data->state->a_penalty - beforePenalty;
342  // Message
343  if (loglevel>1 && search != PRIORITY)
344  logger << indent(l->getOperation()->getLevel()) << " Operation '"
345  << l->getOperation()->getName() << "' evaluates alternate '"
346  << curload->getResource() << "': cost " << deltaCost
347  << ", penalty " << deltaPenalty << endl;
348  if (deltaCost < ROUNDING_ERROR && deltaPenalty < ROUNDING_ERROR)
349  {
350  // Zero cost and zero penalty on this alternate. It won't get any better
351  // than this, so we accept this alternate.
352  if (loglevel)
353  logger << indent(l->getOperation()->getLevel()) << " Operation '"
354  << l->getOperation()->getName() << "' chooses alternate '"
355  << curload->getResource() << "' " << search << endl;
356  // Restore the planning mode
357  data->constrainedPlanning = originalPlanningMode;
358  data->logConstraints = originalLogConstraints;
359  return;
360  }
361  data->state->a_cost = beforeCost;
362  data->state->a_penalty = beforePenalty;
363  double val = 0.0;
364  switch (search)
365  {
366  case MINCOST:
367  val = deltaCost / lplan->getOperationPlan()->getQuantity();
368  break;
369  case MINPENALTY:
370  val = deltaPenalty / lplan->getOperationPlan()->getQuantity();
371  break;
372  case MINCOSTPENALTY:
373  val = (deltaCost + deltaPenalty) / lplan->getOperationPlan()->getQuantity();
374  break;
375  default:
376  LogicException("Unsupported search mode for alternate load");
377  }
378  if (val + ROUNDING_ERROR < bestAlternateValue
379  || (fabs(val - bestAlternateValue) < ROUNDING_ERROR
380  && lplan->getOperationPlan()->getQuantity() > bestAlternateQuantity))
381  {
382  // Found a better alternate
383  bestAlternateValue = val;
384  bestAlternateSelection = curload;
385  bestAlternateQuantity = lplan->getOperationPlan()->getQuantity();
386  }
387  }
388  }
389  else if (loglevel>1 && search != PRIORITY)
390  logger << indent(l->getOperation()->getLevel()) << " Operation '"
391  << l->getOperation()->getName() << "' evaluates alternate '"
392  << curload->getResource() << "': not available before "
393  << data->state->a_date << endl;
394 
395  // 4d) Undo the plan on the alternate
396  data->rollback(topcommand);
397 
398  // 4e) Prepare for the next alternate
399  if (data->state->a_date < min_next_date)
400  min_next_date = data->state->a_date;
401  if (++i != thealternates.end() && loglevel>1 && search == PRIORITY)
402  logger << indent(curload->getOperation()->getLevel()) << " Alternate load switches from '"
403  << curload->getResource()->getName() << "' to '"
404  << (*i)->getResource()->getName() << "'" << endl;
405  }
406 
407  // 5) Unconstrained plan: plan on the first alternate
408  if (!originalPlanningMode && !(search != PRIORITY && bestAlternateSelection))
409  {
410  // Switch to unconstrained planning
411  data->constrainedPlanning = false;
412  bestAlternateSelection = *(thealternates.begin());
413  }
414 
415  // 6) Finally replan on the best alternate
416  if (!originalPlanningMode || (search != PRIORITY && bestAlternateSelection))
417  {
418  // Message
419  if (loglevel)
420  logger << indent(l->getOperation()->getLevel()) << " Operation '"
421  << l->getOperation()->getName() << "' chooses alternate '"
422  << bestAlternateSelection->getResource() << "' " << search << endl;
423 
424  // Switch back
425  data->state->q_loadplan = lplan; // because q_loadplan can change!
426  data->state->a_cost = beforeCost;
427  data->state->a_penalty = beforePenalty;
428  if (lplan->getLoad() != bestAlternateSelection)
429  lplan->setLoad(bestAlternateSelection);
430  lplan->getOperationPlan()->restore(originalOpplan);
431  // TODO XXX need to restore also the selected resource with the right skill!
432  data->state->q_qty = lplan->getQuantity();
433  data->state->q_date = lplan->getDate();
434  bestAlternateSelection->getResource()->solve(*this,data);
435 
436  // Restore the planning mode
437  data->constrainedPlanning = originalPlanningMode;
438  data->logConstraints = originalLogConstraints;
439  return;
440  }
441 
442  // 7) No alternate gave a good result
443  data->state->a_date = min_next_date;
444  data->state->a_qty = 0;
445 
446  // Restore the planning mode
447  data->constrainedPlanning = originalPlanningMode;
448 
449  // Maintain the constraint list
450  if (originalLogConstraints)
451  {
452  const Load *primary = *(thealternates.begin());
453  data->planningDemand->getConstraints().push(
455  primary->getResource(), originalOpplan.start, originalOpplan.end,
456  -originalLoadplanQuantity);
457  }
458  data->logConstraints = originalLogConstraints;
459 
460  if (loglevel>1)
461  logger << indent(lplan->getOperationPlan()->getOperation()->getLevel()) <<
462  " Alternate load doesn't find supply on any alternate : "
463  << data->state->a_qty << " " << data->state->a_date << endl;
464 }
465 
466 
467 }