solver.h
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 #ifndef SOLVER_H
22 #define SOLVER_H
23 
24 #include "frepple/model.h"
25 #ifndef DOXYGEN
26 #include <deque>
27 #include <cmath>
28 #endif
29 
30 namespace frepple
31 {
32 
33 /** @brief This solver implements a heuristic algorithm for planning demands.
34  *
35  * One by one the demands are processed. The demand will consume step by step
36  * any upstream materials, respecting all constraints on its path.<br>
37  * The solver supports all planning constraints as defined in Solver
38  * class.<br>
39  * See the documentation of the different solve methods to understand the
40  * functionality in more detail.
41  *
42  * The logging levels have the following meaning:
43  * - 0: Silent operation. Default logging level.
44  * - 1: Show solver progress for each demand.
45  * - 2: Show the complete ask&reply communication of the solver.
46  * - 3: Trace the status of all entities.
47  */
48 class SolverMRP : public Solver
49 {
50  protected:
51  /** This variable stores the constraint which the solver should respect.
52  * By default no constraints are enabled. */
53  short constrts;
54 
55  /** Behavior of this solver method is:
56  * - It will ask the consuming flows for the required quantity.
57  * - The quantity asked for takes into account the quantity_per of the
58  * producing flow.
59  * - The date asked for takes into account the post-operation time
60  * of the operation.
61  */
62  DECLARE_EXPORT void solve(const Operation*, void* = NULL);
63 
64  /** Behavior of this solver method is:
65  * - Asks each of the routing steps for the requested quantity, starting
66  * with the last routing step.<br>
67  * The time requested for the operation is based on the start date of
68  * the next routing step.
69  */
70  DECLARE_EXPORT void solve(const OperationRouting*, void* = NULL);
71 
72  /** Behavior of this solver method is:
73  * - The solver loops through each alternate operation in order of
74  * priority. On each alternate operation, the solver will try to plan
75  * the quantity that hasn't been planned on higher priority alternates.
76  * - As a special case, operations with zero priority are skipped in the
77  * loop. These operations are considered to be temporarily unavailable.
78  * - The requested operation can be planned over multiple alternates.
79  * We don't garantuee that a request is planned using a single alternate
80  * operation.
81  * - The solver properly considers the quantity_per of all flows producing
82  * into the requested buffer, if such a buffer is specified.
83  */
84  DECLARE_EXPORT void solve(const OperationAlternate*,void* = NULL);
85 
86  /** Behavior of this solver method:
87  * - No propagation to upstream buffers at all, even if a producing
88  * operation has been specified.
89  * - Always give an answer for the full quantity on the requested date.
90  */
91  DECLARE_EXPORT void solve(const BufferInfinite*,void* = NULL);
92 
93  /** Behavior of this solver method:
94  * - Consider 0 as the hard minimum limit. It is not possible
95  * to plan with a 'hard' safety stock reservation.
96  * - Minimum inventory is treated as a 'wish' inventory. When replenishing
97  * a buffer we try to satisfy the minimum target. If that turns out
98  * not to be possible we use whatever available supply for satisfying
99  * the demand first.
100  * - Planning for the minimum target is part of planning a demand. There
101  * is no planning run independent of demand to satisfy the minimum
102  * target.<br>
103  * E.g. If a buffer has no demand on it, the solver won't try to
104  * replenish to the minimum target.<br>
105  * E.g. If the minimum target increases after the latest date required
106  * for satisfying a certain demand that change will not be considered.
107  * - The solver completely ignores the maximum target.
108  */
109  DECLARE_EXPORT void solve(const Buffer*, void* = NULL);
110 
111  /** Behavior of this solver method:
112  * - When the inventory drops below the minimum inventory level, a new
113  * replenishment is triggered.
114  * The replenishment brings the inventory to the maximum level again.
115  * - The minimum and maximum inventory are soft-constraints. The actual
116  * inventory can go lower than the minimum or exceed the maximum.
117  * - The minimum, maximum and multiple size of the replenishment are
118  * hard constraints, and will always be respected.
119  * - A minimum and maximum interval between replenishment is also
120  * respected as a hard constraint.
121  * - No propagation to upstream buffers at all, even if a producing
122  * operation has been specified.
123  * - The minimum calendar isn't used by the solver.
124  *
125  * @todo Optimize the solver method as follows for the common case of infinite
126  * buying capability (ie no max quantity + min time):
127  * - beyond lead time: always reply OK, without rearranging the operation plans
128  * - at the end of the solver loop, we revisit the procurement buffers to establish
129  * the final purchasing profile
130  */
131  DECLARE_EXPORT void solve(const BufferProcure*, void* = NULL);
132 
133  /** Behavior of this solver method:
134  * - This method simply passes on the request to the referenced buffer.
135  * It is called from a solve(Operation*) method and passes on the
136  * control to a solve(Buffer*) method.
137  * @see checkOperationMaterial
138  */
139  DECLARE_EXPORT void solve(const Flow*, void* = NULL);
140 
141  /** Behavior of this solver method:
142  * - The operationplan is checked for a capacity overload. When detected
143  * it is moved to an earlier date.
144  * - This move can be repeated until no capacity is found till a suitable
145  * time slot is found. If the fence and/or leadtime constraints are
146  * enabled they can restrict the feasible moving time.<br>
147  * If a feasible timeslot is found, the method exits here.
148  * - If no suitable time slot can be found at all, the operation plan is
149  * put on its original date and we now try to move it to a feasible
150  * later date. Again, successive moves are possible till a suitable
151  * slot is found or till we reach the end of the horizon.
152  * The result of the search is returned as the answer-date to the
153  * solver.
154  */
155  DECLARE_EXPORT void solve(const Resource*, void* = NULL);
156 
157  /** Behavior of this solver method:
158  * - Always return OK.
159  */
160  DECLARE_EXPORT void solve(const ResourceInfinite*,void* = NULL);
161 
162  /** Behavior of this solver method:
163  * - This method simply passes on the request to the referenced resource.
164  * With the current model structure it could easily be avoided (and
165  * thus gain a bit in performance), but we wanted to include it anyway
166  * to make the solver as generic and future-proof as possible.
167  * @see checkOperationCapacity
168  */
169  DECLARE_EXPORT void solve(const Load*, void* = NULL);
170 
171  /** Behavior of this solver method:
172  * - Respects the following demand planning policies:<br>
173  * 1) Maximum allowed lateness
174  * 2) Minimum shipment quantity
175  * This method is normally called from within the main solve method, but
176  * it can also be called independently to plan a certain demand.
177  * @see solve
178  */
179  DECLARE_EXPORT void solve(const Demand*, void* = NULL);
180 
181  /** Choose a resource.<br>
182  * Normally the chosen resource is simply the resource specified on the
183  * load.<br>
184  * When the load specifies a certain skill and an aggregate resource, then
185  * we search for appropriate child resources.
186  */
187  DECLARE_EXPORT void chooseResource(const Load*, void*);
188 
189  public:
190  /** This is the main solver method that will appropriately call the other
191  * solve methods.<br>
192  * The demands in the model will all be sorted with the criteria defined in
193  * the demand_comparison() method. For each of demand the solve(Demand*)
194  * method is called to plan it.
195  */
196  DECLARE_EXPORT void solve(void *v = NULL);
197 
198  /** Constructor. */
199  SolverMRP(const string& n) : Solver(n), constrts(15), plantype(1),
200  lazydelay(86400L), iteration_threshold(1), iteration_accuracy(0.01),
201  autocommit(true)
202  { initType(metadata); }
203 
204  /** Destructor. */
205  virtual ~SolverMRP() {}
206 
208  DECLARE_EXPORT void endElement(XMLInput& pIn, const Attribute& pAttr, const DataElement& pElement);
209  virtual DECLARE_EXPORT PyObject* getattro(const Attribute&);
210  virtual DECLARE_EXPORT int setattro(const Attribute&, const PythonObject&);
211  static int initialize();
212 
213  virtual const MetaClass& getType() const {return *metadata;}
215  virtual size_t getSize() const {return sizeof(SolverMRP);}
216 
217  /** Static constant for the LEADTIME constraint type.<br>
218  * The numeric value is 1.
219  * @see MATERIAL
220  * @see CAPACITY
221  * @see FENCE
222  */
223  static const short LEADTIME = 1;
224 
225  /** Static constant for the MATERIAL constraint type.<br>
226  * The numeric value is 2.
227  * @see LEADTIME
228  * @see CAPACITY
229  * @see FENCE
230  */
231  static const short MATERIAL = 2;
232 
233  /** Static constant for the CAPACITY constraint type.<br>
234  * The numeric value is 4.
235  * @see MATERIAL
236  * @see LEADTIME
237  * @see FENCE
238  */
239  static const short CAPACITY = 4;
240 
241  /** Static constant for the FENCE constraint type.<br>
242  * The numeric value is 8.
243  * @see MATERIAL
244  * @see CAPACITY
245  * @see LEADTIME
246  */
247  static const short FENCE = 8;
248 
249  /** Update the constraints to be considered by this solver. This field may
250  * not be applicable for all solvers. */
251  void setConstraints(short i) {constrts = i;}
252 
253  /** Returns the constraints considered by the solve. */
254  short getConstraints() const {return constrts;}
255 
256  /** Returns true if this solver respects the operation release fences.
257  * The solver isn't allowed to create any operation plans within the
258  * release fence.
259  */
260  bool isFenceConstrained() const {return (constrts & FENCE)>0;}
261 
262  /** Returns true if the solver respects the current time of the plan.
263  * The solver isn't allowed to create any operation plans in the past.
264  */
265  bool isLeadtimeConstrained() const {return (constrts & LEADTIME)>0;}
266 
267  /** Returns true if the solver respects the material procurement
268  * constraints on procurement buffers.
269  */
270  bool isMaterialConstrained() const {return (constrts & MATERIAL)>0;}
271 
272  /** Returns true if the solver respects capacity constraints. */
273  bool isCapacityConstrained() const {return (constrts & CAPACITY)>0;}
274 
275  /** Returns true if any constraint is relevant for the solver. */
276  bool isConstrained() const {return constrts>0;}
277 
278  /** Returns the plan type:
279  * - 1: Constrained plan.<br>
280  * This plan doesn't not violate any constraints.<br>
281  * In case of material or capacity shortages the demand is delayed
282  * or planned short.
283  * - 2: Unconstrained plan with alternate search.<br>
284  * This unconstrained plan leaves material, capacity and operation
285  * problems when shortages are found. Availability is searched across
286  * alternates and the remaining shortage is shown on the primary
287  * alternate.<br>
288  * The demand is always fully met on time.
289  * - 3: Unconstrained plan without alternate search.<br>
290  * This unconstrained plan leaves material, capacity and operation
291  * problems when shortages are found. It doesn't evaluate availability
292  * on alternates.<br>
293  * The demand is always fully met on time.
294  * The default is 1.
295  */
296  short getPlanType() const {return plantype;}
297 
298  void setPlanType(short b)
299  {
300  if (b < 1 || b > 3)
301  throw DataException("Invalid plan type");
302  plantype = b;
303  }
304 
305  /** This function defines the order in which the demands are being
306  * planned.<br>
307  * The following sorting criteria are appplied in order:
308  * - demand priority: smaller priorities first
309  * - demand due date: earlier due dates first
310  * - demand quantity: smaller quantities first
311  */
312  static DECLARE_EXPORT bool demand_comparison(const Demand*, const Demand*);
313 
314  /** Return the time increment between requests when the answered reply
315  * date isn't usable. */
316  TimePeriod getLazyDelay() const {return lazydelay;}
317 
318  /** Update the time increment between requests when the answered reply
319  * date isn't usable. */
321  {
322  if (l <= 0L) throw DataException("Invalid lazy delay");
323  lazydelay = l;
324  }
325 
326  /** Get the threshold to stop iterating when the delta between iterations
327  * is less than this absolute threshold.
328  */
329  double getIterationThreshold() const {return iteration_threshold;}
330 
331  /** Set the threshold to stop iterating when the delta between iterations
332  * is less than this absolute threshold.<br>
333  * The value must be greater than or equal to zero and the default is 1.
334  */
335  void setIterationThreshold(double d)
336  {
337  if (d<0.0)
338  throw DataException("Invalid iteration threshold: must be >= 0");
339  iteration_threshold = d;
340  }
341 
342  /** Get the threshold to stop iterating when the delta between iterations
343  * is less than this percentage threshold.
344  */
345  double getIterationAccuracy() const {return iteration_accuracy;}
346 
347  /** Set the threshold to stop iterating when the delta between iterations
348  * is less than this percentage threshold.<br>
349  * The value must be between 0 and 100 and the default is 1%.
350  */
351  void setIterationAccuracy(double d)
352  {
353  if (d<0.0 || d>100.0)
354  throw DataException("Invalid iteration accuracy: must be >=0 and <= 100");
355  iteration_accuracy = d;
356  }
357 
358  /** Return whether or not we automatically commit the changes after
359  * planning a demand. */
360  bool getAutocommit() const {return autocommit;}
361 
362  /** Update whether or not we automatically commit the changes after
363  * planning a demand. */
364  void setAutocommit(const bool b) {autocommit = b;}
365 
366  /** Specify a Python function that is called before solving a flow. */
367  DECLARE_EXPORT void setUserExitFlow(const string& n) {userexit_flow = n;}
368 
369  /** Specify a Python function that is called before solving a flow. */
370  DECLARE_EXPORT void setUserExitFlow(PyObject* p) {userexit_flow = p;}
371 
372  /** Return the Python function that is called before solving a flow. */
373  PythonFunction getUserExitFlow() const {return userexit_flow;}
374 
375  /** Specify a Python function that is called before solving a demand. */
376  DECLARE_EXPORT void setUserExitDemand(const string& n) {userexit_demand = n;}
377 
378  /** Specify a Python function that is called before solving a demand. */
379  DECLARE_EXPORT void setUserExitDemand(PyObject* p) {userexit_demand = p;}
380 
381  /** Return the Python function that is called before solving a demand. */
382  PythonFunction getUserExitDemand() const {return userexit_demand;}
383 
384  /** Specify a Python function that is called before solving a buffer. */
385  DECLARE_EXPORT void setUserExitBuffer(const string& n) {userexit_buffer = n;}
386 
387  /** Specify a Python function that is called before solving a buffer. */
388  DECLARE_EXPORT void setUserExitBuffer(PyObject* p) {userexit_buffer = p;}
389 
390  /** Return the Python function that is called before solving a buffer. */
391  PythonFunction getUserExitBuffer() const {return userexit_buffer;}
392 
393  /** Specify a Python function that is called before solving a resource. */
394  DECLARE_EXPORT void setUserExitResource(const string& n) {userexit_resource = n;}
395 
396  /** Specify a Python function that is called before solving a resource. */
397  DECLARE_EXPORT void setUserExitResource(PyObject* p) {userexit_resource = p;}
398 
399  /** Return the Python function that is called before solving a resource. */
400  PythonFunction getUserExitResource() const {return userexit_resource;}
401 
402  /** Specify a Python function that is called before solving a operation. */
403  DECLARE_EXPORT void setUserExitOperation(const string& n) {userexit_operation = n;}
404 
405  /** Specify a Python function that is called before solving a operation. */
406  DECLARE_EXPORT void setUserExitOperation(PyObject* p) {userexit_operation = p;}
407 
408  /** Return the Python function that is called before solving a operation. */
409  PythonFunction getUserExitOperation() const {return userexit_operation;}
410 
411  /** Python method for running the solver. */
412  static DECLARE_EXPORT PyObject* solve(PyObject*, PyObject*);
413 
414  /** Python method for commiting the plan changes. */
415  static DECLARE_EXPORT PyObject* commit(PyObject*, PyObject*);
416 
417  /** Python method for undoing the plan changes. */
418  static DECLARE_EXPORT PyObject* rollback(PyObject*, PyObject*);
419 
420  private:
421  typedef map < int, deque<Demand*>, less<int> > classified_demand;
422  typedef classified_demand::iterator cluster_iterator;
423  classified_demand demands_per_cluster;
424 
425  /** Type of plan to be created. */
426  short plantype;
427 
428  /** Time increments for a lazy replan.<br>
429  * The solver is expected to return always a next-feasible date when the
430  * request can't be met. The solver can then retry the request with an
431  * updated request date. In some corner cases and in case of a bug it is
432  * possible that no valid date is returned. The solver will then try the
433  * request with a request date incremented by this value.<br>
434  * The default value is 1 day.
435  */
436  TimePeriod lazydelay;
437 
438  /** Threshold to stop iterating when the delta between iterations is
439  * less than this absolute limit.
440  */
441  double iteration_threshold;
442 
443  /** Threshold to stop iterating when the delta between iterations is
444  * less than this percentage limit.
445  */
446  double iteration_accuracy;
447 
448  /** Enable or disable automatically committing the changes in the plan
449  * after planning each demand.<br>
450  * The flag is only respected when planning incremental changes, and
451  * is ignored when doing a complete replan.
452  */
453  bool autocommit;
454 
455  /** A Python callback function that is called for each alternate
456  * flow. If the callback function returns false, that alternate
457  * flow is an invalid choice.
458  */
459  PythonFunction userexit_flow;
460 
461  /** A Python callback function that is called for each demand. The return
462  * value is not used.
463  */
464  PythonFunction userexit_demand;
465 
466  /** A Python callback function that is called for each buffer. The return
467  * value is not used.
468  */
469  PythonFunction userexit_buffer;
470 
471  /** A Python callback function that is called for each resource. The return
472  * value is not used.
473  */
474  PythonFunction userexit_resource;
475 
476  /** A Python callback function that is called for each operation. The return
477  * value is not used.
478  */
479  PythonFunction userexit_operation;
480 
481  protected:
482  /** @brief This class is used to store the solver status during the
483  * ask-reply calls of the solver.
484  */
485  struct State
486  {
487  /** Points to the demand being planned.<br>
488  * This field is only non-null when planning the delivery operation.
489  */
491 
492  /** Points to the current owner operationplan. This is used when
493  * operations are nested. */
495 
496  /** Points to the current buffer. */
498 
499  /** A flag to force the resource solver to move the operationplan to
500  * a later date where it is feasible.
501  */
502  bool forceLate;
503 
504  /** This is the quantity we are asking for. */
505  double q_qty;
506 
507  /** This is the date we are asking for. */
509 
510  /** This is the maximum date we are asking for.<br>
511  * In case of a post-operation time there is a difference between
512  * q_date and q_date_max.
513  */
515 
516  /** This is the quantity we can get by the requested Date. */
517  double a_qty;
518 
519  /** This is the Date when we can get extra availability. */
521 
522  /** This is a pointer to a LoadPlan. It is used for communication
523  * between the Operation-Solver and the Resource-Solver. */
525 
526  /** This is a pointer to a FlowPlan. It is used for communication
527  * between the Operation-Solver and the Buffer-Solver. */
529 
530  /** A pointer to an operationplan currently being solved. */
532 
533  /** Cost of the reply.<br>
534  * Only the direct cost should be returned in this field.
535  */
536  double a_cost;
537 
538  /** Penalty associated with the reply.<br>
539  * This field contains indirect costs and other penalties that are
540  * not strictly related to the request. Examples are setup costs,
541  * inventory carrying costs, ...
542  */
543  double a_penalty;
544 
545  /** Motive of the current solver. */
547  };
548 
549  /** @brief This class is a helper class of the SolverMRP class.
550  *
551  * It stores the solver state maintained by each solver thread.
552  * @see SolverMRP
553  */
555  {
556  friend class SolverMRP;
557  public:
558  static void runme(void *args)
559  {
560  SolverMRP::SolverMRPdata* x = static_cast<SolverMRP::SolverMRPdata*>(args);
561  x->commit();
562  delete x;
563  }
564 
565  /** Return the solver. */
566  SolverMRP* getSolver() const {return sol;}
567 
568  /** Constructor. */
569  SolverMRPdata(SolverMRP* s = NULL, int c = 0, deque<Demand*>* d = NULL)
570  : sol(s), cluster(c), demands(d), constrainedPlanning(true),
571  state(statestack), prevstate(statestack-1) {}
572 
573  /** Destructor. */
574  virtual ~SolverMRPdata() {};
575 
576  /** Verbose mode is inherited from the solver. */
577  unsigned short getLogLevel() const {return sol ? sol->getLogLevel() : 0;}
578 
579  /** This function runs a single planning thread. Such a thread will loop
580  * through the following steps:
581  * - Use the method next_cluster() to find another unplanned cluster.
582  * - Exit the thread if no more cluster is found.
583  * - Sort all demands in the cluster, using the demand_comparison()
584  * method.
585  * - Loop through the sorted list of demands and plan each of them.
586  * During planning the demands exceptions are caught, and the
587  * planning loop will simply move on to the next demand.
588  * In this way, an error in a part of the model doesn't ruin the
589  * complete plan.
590  * @see demand_comparison
591  * @see next_cluster
592  */
593  virtual DECLARE_EXPORT void commit();
594 
595  virtual const MetaClass& getType() const {return *SolverMRP::metadata;}
596  virtual size_t getSize() const {return sizeof(SolverMRPdata);}
597 
598  bool getVerbose() const
599  {
600  throw LogicException("Use the method SolverMRPdata::getLogLevel() instead of SolverMRPdata::getVerbose()");
601  }
602 
603  /** Add a new state to the status stack. */
604  inline void push(double q = 0.0, Date d = Date::infiniteFuture)
605  {
606  if (state >= statestack + MAXSTATES)
607  throw RuntimeException("Maximum recursion depth exceeded");
608  ++state;
609  ++prevstate;
610  state->q_qty = q;
611  state->q_date = d;
612  state->q_date_max = d;
613  state->curOwnerOpplan = NULL;
614  state->q_loadplan = NULL;
615  state->q_flowplan = NULL;
616  state->q_operationplan = NULL;
617  state->curDemand = NULL;
618  state->a_cost = 0.0;
619  state->a_penalty = 0.0;
620  }
621 
622  /** Removes a state from the status stack. */
623  inline void pop()
624  {
625  if (--state < statestack)
626  throw LogicException("State stack empty");
627  --prevstate;
628  }
629 
630  private:
631  static const int MAXSTATES = 256;
632 
633  /** Points to the solver. */
634  SolverMRP* sol;
635 
636  /** An identifier of the cluster being replanned. Note that it isn't
637  * always the complete cluster that is being planned.
638  */
639  int cluster;
640 
641  /** A deque containing all demands to be (re-)planned. */
642  deque<Demand*>* demands;
643 
644  /** Stack of solver status information. */
645  State statestack[MAXSTATES];
646 
647  /** True when planning in constrained mode. */
648  bool constrainedPlanning;
649 
650  /** Flags whether or not constraints are being tracked. */
651  bool logConstraints;
652 
653  /** Points to the demand being planned. */
654  Demand* planningDemand;
655 
656  public:
657  /** Pointer to the current solver status. */
659 
660  /** Pointer to the solver status one level higher on the stack. */
662  };
663 
664  /** When autocommit is switched off, this command structure will contain
665  * all plan changes.
666  */
668 
669  /** This function will check all constraints for an operationplan
670  * and propagate it upstream. The check does NOT check eventual
671  * sub operationplans.<br>
672  * The return value is a flag whether the operationplan is
673  * acceptable (sometimes in reduced quantity) or not.
674  */
676 
677  /** Verifies whether this operationplan violates the leadtime
678  * constraints. */
680 
681  /** Verifies whether this operationplan violates the capacity constraint.<br>
682  * In case it does the operationplan is moved to an earlier or later
683  * feasible date.
684  */
686 
687  /** Scan the operationplans that are about to be committed to verify that
688  * they are not creating any excess.
689  */
691 
692  /** Scan the operationplans that are about to be committed to verify that
693  * they are not creating any excess.
694  */
696 };
697 
698 
699 /** @brief This class holds functions that used for maintenance of the solver
700  * code.
701  */
703 {
704  public:
705  static void initialize();
706 };
707 
708 
709 } // end namespace
710 
711 
712 #endif