solverdemand.cpp
Go to the documentation of this file.
1 /***************************************************************************
2  * *
3  * Copyright (C) 2007-2013 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 
25 namespace frepple
26 {
27 
28 
29 DECLARE_EXPORT void SolverMRP::solve(const Demand* l, void* v)
30 {
31  // Set a bookmark at the current command
32  SolverMRPdata* data = static_cast<SolverMRPdata*>(v);
33  CommandManager::Bookmark* topcommand = data->setBookmark();
34 
35  // Create a state stack
36  State* mystate = data->state;
37  data->push();
38 
39  try
40  {
41  // Call the user exit
42  if (userexit_demand) userexit_demand.call(l, PythonObject(data->constrainedPlanning));
43  unsigned int loglevel = data->getSolver()->getLogLevel();
44 
45  // Note: This solver method does not push/pop states on the stack.
46  // We continue to work on the top element of the stack.
47 
48  // Message
49  if (loglevel>0)
50  {
51  logger << "Planning demand '" << l->getName() << "' (" << l->getPriority()
52  << ", " << l->getDue() << ", " << l->getQuantity() << ")";
53  if (!data->constrainedPlanning || !data->getSolver()->isConstrained())
54  logger << " in unconstrained mode";
55  logger << endl;
56  }
57 
58  // Unattach previous delivery operationplans.
59  // Locked operationplans will NOT be deleted, and a part of the demand can
60  // still remain planned.
61  const_cast<Demand*>(l)->deleteOperationPlans(false, data);
62 
63  // Empty constraint list
64  const_cast<Demand*>(l)->getConstraints().clear();
65 
66  // Track constraints or not
67  data->logConstraints = (getPlanType() == 1);
68 
69  // Determine the quantity to be planned and the date for the planning loop
70  double plan_qty = l->getQuantity() - l->getPlannedQuantity();
71  if (plan_qty < l->getMinShipment()) plan_qty = l->getMinShipment();
72  Date plan_date = l->getDue();
73 
74  // Nothing to be planned any more (e.g. all deliveries are locked...)
75  if (plan_qty < ROUNDING_ERROR)
76  {
77  if (loglevel>0) logger << " Nothing to be planned." << endl;
78  return;
79  }
80 
81  // Temporary values to store the 'best-reply' so far
82  double best_q_qty = 0.0, best_a_qty = 0.0;
83  Date best_q_date;
84 
85  // Select delivery operation
86  Operation* deliveryoper = l->getDeliveryOperation();
87 
88  // Handle invalid or missing delivery operations
89  string problemtext = string("Demand '") + l->getName() + "' has no delivery operation";
90  Problem::const_iterator j = Problem::begin(const_cast<Demand*>(l), false);
91  while (j!=Problem::end())
92  {
94  && j->getDescription() == problemtext)
95  break;
96  ++j;
97  }
98  if (!deliveryoper)
99  {
100  // Create a problem
101  if (j == Problem::end())
102  new ProblemInvalidData(const_cast<Demand*>(l), problemtext, "demand",
103  l->getDue(), l->getDue(), l->getQuantity());
104  // Abort planning of this demand
105  throw DataException("Demand '" + l->getName() + "' can't be planned");
106  }
107  else
108  // Remove problem that may already exist
109  delete &*j;
110 
111  // Planning loop
112  do
113  {
114  // Message
115  if (loglevel>0)
116  logger << "Demand '" << l << "' asks: "
117  << plan_qty << " " << plan_date << endl;
118 
119  // Store the last command in the list, in order to undo the following
120  // commands if required.
121  CommandManager::Bookmark* topcommand = data->setBookmark();
122 
123  // Plan the demand by asking the delivery operation to plan
124  double q_qty = plan_qty;
125  data->state->curBuffer = NULL;
126  data->state->q_qty = plan_qty;
127  data->state->q_date = plan_date;
128  data->planningDemand = const_cast<Demand*>(l);
129  data->state->curDemand = const_cast<Demand*>(l);
130  data->state->motive = const_cast<Demand*>(l);
131  data->state->curOwnerOpplan = NULL;
132  deliveryoper->solve(*this,v);
133  Date next_date = data->state->a_date;
134 
135  if (data->state->a_qty < ROUNDING_ERROR
136  && plan_qty > l->getMinShipment() && l->getMinShipment() > 0)
137  {
138  bool originalLogConstraints = data->logConstraints;
139  data->logConstraints = false;
140  try
141  {
142  // The full asked quantity is not possible.
143  // Try with the minimum shipment quantity.
144  if (loglevel>0)
145  logger << "Demand '" << l << "' tries planning minimum quantity " << l->getMinShipment() << endl;
146  data->rollback(topcommand);
147  data->state->curBuffer = NULL;
148  data->state->q_qty = l->getMinShipment();
149  data->state->q_date = plan_date;
150  data->state->curDemand = const_cast<Demand*>(l);
151  deliveryoper->solve(*this,v);
152  if (data->state->a_date < next_date)
153  next_date = data->state->a_date;
154  if (data->state->a_qty > ROUNDING_ERROR)
155  {
156  // The minimum shipment quantity is feasible.
157  // Now try iteratively different quantities to find the best we can do.
158  double min_qty = l->getMinShipment();
159  double max_qty = plan_qty;
160  double delta = fabs(max_qty - min_qty);
161  while (delta > data->getSolver()->getIterationAccuracy() * l->getQuantity()
162  && delta > data->getSolver()->getIterationThreshold())
163  {
164  double new_qty = floor((min_qty + max_qty) / 2); // @TODO not generic to round down to an integer here
165  if (loglevel>0)
166  logger << "Demand '" << l << "' tries planning a different quantity " << new_qty << endl;
167  data->rollback(topcommand);
168  data->state->curBuffer = NULL;
169  data->state->q_qty = new_qty;
170  data->state->q_date = plan_date;
171  data->state->curDemand = const_cast<Demand*>(l);
172  deliveryoper->solve(*this,v);
173  if (data->state->a_date < next_date)
174  next_date = data->state->a_date;
175  if (data->state->a_qty > ROUNDING_ERROR)
176  // Too small: new min
177  min_qty = new_qty;
178  else
179  // Too big: new max
180  max_qty = new_qty;
181  delta = fabs(max_qty - min_qty);
182  }
183  q_qty = min_qty; // q_qty is the biggest Q quantity giving a positive reply
184  if (data->state->a_qty <= ROUNDING_ERROR)
185  {
186  if (loglevel>0)
187  logger << "Demand '" << l << "' restores plan for quantity " << min_qty << endl;
188  // Restore the last feasible plan
189  data->rollback(topcommand);
190  data->state->curBuffer = NULL;
191  data->state->q_qty = min_qty;
192  data->state->q_date = plan_date;
193  data->state->curDemand = const_cast<Demand*>(l);
194  deliveryoper->solve(*this,v);
195  }
196  }
197  }
198  catch (...)
199  {
200  data->logConstraints = originalLogConstraints;
201  throw;
202  }
203  data->logConstraints = originalLogConstraints;
204  }
205 
206  // Message
207  if (loglevel>0)
208  logger << "Demand '" << l << "' gets answer: "
209  << data->state->a_qty << " " << next_date << " "
210  << data->state->a_cost << " " << data->state->a_penalty << endl;
211 
212  // Update the date to plan in the next loop
213  Date copy_plan_date = plan_date;
214 
215  // Compare the planned quantity with the minimum allowed shipment quantity
216  // We don't accept the answer in case:
217  // 1) Nothing is planned
218  // 2) The planned quantity is less than the minimum shipment quantity
219  // 3) The remaining quantity after accepting this answer is less than
220  // the minimum quantity.
221  if (data->state->a_qty < ROUNDING_ERROR
222  || data->state->a_qty + ROUNDING_ERROR < l->getMinShipment()
223  || (q_qty - data->state->a_qty < l->getMinShipment()
224  && q_qty - data->state->a_qty > ROUNDING_ERROR))
225  {
226  if (q_qty - data->state->a_qty < l->getMinShipment()
227  && data->state->a_qty + ROUNDING_ERROR >= l->getMinShipment()
228  && data->state->a_qty > best_a_qty )
229  {
230  // The remaining quantity after accepting this answer is less than
231  // the minimum quantity. Therefore, we delay accepting it now, but
232  // still keep track of this best offer.
233  best_a_qty = data->state->a_qty;
234  best_q_qty = q_qty;
235  best_q_date = plan_date;
236  }
237 
238  // Delete operationplans - Undo all changes
239  data->rollback(topcommand);
240 
241  // Set the ask date for the next pass through the loop
242  if (next_date <= copy_plan_date)
243  {
244  // Oops, we didn't get a proper answer we can use for the next loop.
245  // Print a warning and simply try one day later.
246  if (loglevel>0)
247  logger << "Warning: Demand '" << l << "': Lazy retry" << endl;
248  plan_date = copy_plan_date + data->getSolver()->getLazyDelay();
249  }
250  else
251  // Use the next-date answer from the solver
252  plan_date = next_date;
253  }
254  else
255  {
256  // Accepting this answer
257  if (data->state->a_qty + ROUNDING_ERROR < q_qty)
258  {
259  // The demand was only partially planned. We need to do a new
260  // 'coordinated' planning run.
261 
262  // Delete operationplans created in the 'testing round'
263  data->rollback(topcommand);
264 
265  // Create the correct operationplans
266  if (loglevel>=2)
267  logger << "Demand '" << l << "' plans coordination." << endl;
268  data->getSolver()->setLogLevel(0);
269  double tmpresult = data->state->a_qty;
270  try
271  {
272  for(double remainder = data->state->a_qty;
273  remainder > ROUNDING_ERROR; remainder -= data->state->a_qty)
274  {
275  data->state->q_qty = remainder;
276  data->state->q_date = copy_plan_date;
277  data->state->curDemand = const_cast<Demand*>(l);
278  data->state->curBuffer = NULL;
279  deliveryoper->solve(*this,v);
280  if (data->state->a_qty < ROUNDING_ERROR)
281  {
282  logger << "Warning: Demand '" << l << "': Failing coordination" << endl;
283  break;
284  }
285  }
286  }
287  catch (...)
288  {
289  data->getSolver()->setLogLevel(loglevel);
290  throw;
291  }
292  data->getSolver()->setLogLevel(loglevel);
293  data->state->a_qty = tmpresult;
294  }
295 
296  // Register the new operationplans. We need to make sure that the
297  // correct execute method is called!
298  if (data->getSolver()->getAutocommit())
299  {
300  data->getSolver()->scanExcess(data);
301  data->CommandManager::commit();
302  }
303 
304  // Update the quantity to plan in the next loop
305  plan_qty -= data->state->a_qty;
306  best_a_qty = 0.0; // Reset 'best-answer' remember
307  }
308 
309  }
310  // Repeat while there is still a quantity left to plan and we aren't
311  // exceeding the maximum delivery delay.
312  while (plan_qty > ROUNDING_ERROR
313  && ((data->getSolver()->getPlanType() != 2 && plan_date < l->getDue() + l->getMaxLateness())
314  || (data->getSolver()->getPlanType() == 2 && !data->constrainedPlanning && plan_date < l->getDue() + l->getMaxLateness())
315  || (data->getSolver()->getPlanType() == 2 && data->constrainedPlanning && plan_date == l->getDue())
316  ));
317 
318  // Accept the best possible answer.
319  // We may have skipped it in the previous loop, awaiting a still better answer
320  if (best_a_qty > 0.0 && data->constrainedPlanning)
321  {
322  if (loglevel>=2) logger << "Demand '" << l << "' accepts a best answer." << endl;
323  data->getSolver()->setLogLevel(0);
324  try
325  {
326  for(double remainder = best_q_qty;
327  remainder > ROUNDING_ERROR; remainder -= data->state->a_qty)
328  {
329  data->state->q_qty = remainder;
330  data->state->q_date = best_q_date;
331  data->state->curDemand = const_cast<Demand*>(l);
332  data->state->curBuffer = NULL;
333  deliveryoper->solve(*this,v);
334  if (data->state->a_qty < ROUNDING_ERROR)
335  {
336  logger << "Warning: Demand '" << l << "': Failing accepting best answer" << endl;
337  break;
338  }
339  }
340  if (data->getSolver()->getAutocommit())
341  {
342  data->getSolver()->scanExcess(data);
343  data->CommandManager::commit();
344  }
345  }
346  catch (...)
347  {
348  data->getSolver()->setLogLevel(loglevel);
349  throw;
350  }
351  data->getSolver()->setLogLevel(loglevel);
352  }
353 
354  // Reset the state stack to the position we found it at.
355  while (data->state > mystate) data->pop();
356 
357  }
358  catch (...)
359  {
360  // Clean up if any exception happened during the planning of the demand
361  while (data->state > mystate) data->pop();
362  data->rollback(topcommand);
363  throw;
364  }
365 }
366 
367 
369 {
370  for(CommandManager::iterator i = mgr->begin(); i != mgr->end(); ++i)
371  if (i->isActive()) scanExcess(&*i);
372 }
373 
374 
376 {
377  // Loop over all newly created operationplans found in the command stack
378  for(CommandList::iterator cmd = l->begin(); cmd != l->end(); ++cmd)
379  {
380  CommandCreateOperationPlan* createcmd = dynamic_cast<CommandCreateOperationPlan*>(&*cmd);
381  if (!createcmd)
382  {
383  // If the command is a list: recursively call this function
384  if (dynamic_cast<CommandList*>(&*cmd))
385  scanExcess(dynamic_cast<CommandList*>(&*cmd));
386  //else: Not a command creating an operationplan: move on
387  }
388  else
389  {
390  // Detect excess operationplans and undo them
391  if (createcmd->getOperationPlan() && createcmd->getOperationPlan()->isExcess())
392  {
393  if (getLogLevel()>1)
394  logger << "Denying creation of redundant operationplan "
395  << createcmd->getOperationPlan()->getOperation() << " "
396  << createcmd->getOperationPlan()->getDates() << " "
397  << createcmd->getOperationPlan()->getQuantity() << endl;
398  createcmd->rollback();
399  }
400  }
401  }
402 }
403 
404 }