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