solver.h
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 #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)
323  throw DataException("Invalid lazy delay");
324  lazydelay = l;
325  }
326 
327  /** Get the threshold to stop iterating when the delta between iterations
328  * is less than this absolute threshold.
329  */
330  double getIterationThreshold() const {return iteration_threshold;}
331 
332  /** Set the threshold to stop iterating when the delta between iterations
333  * is less than this absolute threshold.<br>
334  * The value must be greater than or equal to zero and the default is 1.
335  */
336  void setIterationThreshold(double d)
337  {
338  if (d<0.0)
339  throw DataException("Invalid iteration threshold: must be >= 0");
340  iteration_threshold = d;
341  }
342 
343  /** Get the threshold to stop iterating when the delta between iterations
344  * is less than this percentage threshold.
345  */
346  double getIterationAccuracy() const {return iteration_accuracy;}
347 
348  /** Set the threshold to stop iterating when the delta between iterations
349  * is less than this percentage threshold.<br>
350  * The value must be between 0 and 100 and the default is 1%.
351  */
352  void setIterationAccuracy(double d)
353  {
354  if (d<0.0 || d>100.0)
355  throw DataException("Invalid iteration accuracy: must be >=0 and <= 100");
356  iteration_accuracy = d;
357  }
358 
359  /** Return whether or not we automatically commit the changes after
360  * planning a demand. */
361  bool getAutocommit() const {return autocommit;}
362 
363  /** Update whether or not we automatically commit the changes after
364  * planning a demand. */
365  void setAutocommit(const bool b) {autocommit = b;}
366 
367  /** Specify a Python function that is called before solving a flow. */
368  DECLARE_EXPORT void setUserExitFlow(const string& n) {userexit_flow = n;}
369 
370  /** Specify a Python function that is called before solving a flow. */
371  DECLARE_EXPORT void setUserExitFlow(PyObject* p) {userexit_flow = p;}
372 
373  /** Return the Python function that is called before solving a flow. */
374  PythonFunction getUserExitFlow() const {return userexit_flow;}
375 
376  /** Specify a Python function that is called before solving a demand. */
377  DECLARE_EXPORT void setUserExitDemand(const string& n) {userexit_demand = n;}
378 
379  /** Specify a Python function that is called before solving a demand. */
380  DECLARE_EXPORT void setUserExitDemand(PyObject* p) {userexit_demand = p;}
381 
382  /** Return the Python function that is called before solving a demand. */
383  PythonFunction getUserExitDemand() const {return userexit_demand;}
384 
385  /** Specify a Python function that is called before solving a buffer. */
386  DECLARE_EXPORT void setUserExitBuffer(const string& n) {userexit_buffer = n;}
387 
388  /** Specify a Python function that is called before solving a buffer. */
389  DECLARE_EXPORT void setUserExitBuffer(PyObject* p) {userexit_buffer = p;}
390 
391  /** Return the Python function that is called before solving a buffer. */
392  PythonFunction getUserExitBuffer() const {return userexit_buffer;}
393 
394  /** Specify a Python function that is called before solving a resource. */
395  DECLARE_EXPORT void setUserExitResource(const string& n) {userexit_resource = n;}
396 
397  /** Specify a Python function that is called before solving a resource. */
398  DECLARE_EXPORT void setUserExitResource(PyObject* p) {userexit_resource = p;}
399 
400  /** Return the Python function that is called before solving a resource. */
401  PythonFunction getUserExitResource() const {return userexit_resource;}
402 
403  /** Specify a Python function that is called before solving a operation. */
404  DECLARE_EXPORT void setUserExitOperation(const string& n) {userexit_operation = n;}
405 
406  /** Specify a Python function that is called before solving a operation. */
407  DECLARE_EXPORT void setUserExitOperation(PyObject* p) {userexit_operation = p;}
408 
409  /** Return the Python function that is called before solving a operation. */
410  PythonFunction getUserExitOperation() const {return userexit_operation;}
411 
412  /** Python method for running the solver. */
413  static DECLARE_EXPORT PyObject* solve(PyObject*, PyObject*);
414 
415  /** Python method for commiting the plan changes. */
416  static DECLARE_EXPORT PyObject* commit(PyObject*, PyObject*);
417 
418  /** Python method for undoing the plan changes. */
419  static DECLARE_EXPORT PyObject* rollback(PyObject*, PyObject*);
420 
421  private:
422  typedef map < int, deque<Demand*>, less<int> > classified_demand;
423  typedef classified_demand::iterator cluster_iterator;
424  classified_demand demands_per_cluster;
425 
426  /** Type of plan to be created. */
427  short plantype;
428 
429  /** Time increments for a lazy replan.<br>
430  * The solver is expected to return always a next-feasible date when the
431  * request can't be met. The solver can then retry the request with an
432  * updated request date. In some corner cases and in case of a bug it is
433  * possible that no valid date is returned. The solver will then try the
434  * request with a request date incremented by this value.<br>
435  * The default value is 1 day.
436  */
437  TimePeriod lazydelay;
438 
439  /** Threshold to stop iterating when the delta between iterations is
440  * less than this absolute limit.
441  */
442  double iteration_threshold;
443 
444  /** Threshold to stop iterating when the delta between iterations is
445  * less than this percentage limit.
446  */
447  double iteration_accuracy;
448 
449  /** Enable or disable automatically committing the changes in the plan
450  * after planning each demand.<br>
451  * The flag is only respected when planning incremental changes, and
452  * is ignored when doing a complete replan.
453  */
454  bool autocommit;
455 
456  /** A Python callback function that is called for each alternate
457  * flow. If the callback function returns false, that alternate
458  * flow is an invalid choice.
459  */
460  PythonFunction userexit_flow;
461 
462  /** A Python callback function that is called for each demand. The return
463  * value is not used.
464  */
465  PythonFunction userexit_demand;
466 
467  /** A Python callback function that is called for each buffer. The return
468  * value is not used.
469  */
470  PythonFunction userexit_buffer;
471 
472  /** A Python callback function that is called for each resource. The return
473  * value is not used.
474  */
475  PythonFunction userexit_resource;
476 
477  /** A Python callback function that is called for each operation. The return
478  * value is not used.
479  */
480  PythonFunction userexit_operation;
481 
482  protected:
483  /** @brief This class is used to store the solver status during the
484  * ask-reply calls of the solver.
485  */
486  struct State
487  {
488  /** Points to the demand being planned.<br>
489  * This field is only non-null when planning the delivery operation.
490  */
492 
493  /** Points to the current owner operationplan. This is used when
494  * operations are nested. */
496 
497  /** Points to the current buffer. */
499 
500  /** A flag to force the resource solver to move the operationplan to
501  * a later date where it is feasible.
502  */
503  bool forceLate;
504 
505  /** This is the quantity we are asking for. */
506  double q_qty;
507 
508  /** This is the date we are asking for. */
510 
511  /** This is the maximum date we are asking for.<br>
512  * In case of a post-operation time there is a difference between
513  * q_date and q_date_max.
514  */
516 
517  /** This is the quantity we can get by the requested Date. */
518  double a_qty;
519 
520  /** This is the Date when we can get extra availability. */
522 
523  /** This is a pointer to a LoadPlan. It is used for communication
524  * between the Operation-Solver and the Resource-Solver. */
526 
527  /** This is a pointer to a FlowPlan. It is used for communication
528  * between the Operation-Solver and the Buffer-Solver. */
530 
531  /** A pointer to an operationplan currently being solved. */
533 
534  /** Cost of the reply.<br>
535  * Only the direct cost should be returned in this field.
536  */
537  double a_cost;
538 
539  /** Penalty associated with the reply.<br>
540  * This field contains indirect costs and other penalties that are
541  * not strictly related to the request. Examples are setup costs,
542  * inventory carrying costs, ...
543  */
544  double a_penalty;
545 
546  /** Motive of the current solver. */
548  };
549 
550  /** @brief This class is a helper class of the SolverMRP class.
551  *
552  * It stores the solver state maintained by each solver thread.
553  * @see SolverMRP
554  */
556  {
557  friend class SolverMRP;
558  public:
559  static void runme(void *args)
560  {
561  SolverMRP::SolverMRPdata* x = static_cast<SolverMRP::SolverMRPdata*>(args);
562  x->commit();
563  delete x;
564  }
565 
566  /** Return the solver. */
567  SolverMRP* getSolver() const {return sol;}
568 
569  /** Constructor. */
570  SolverMRPdata(SolverMRP* s = NULL, int c = 0, deque<Demand*>* d = NULL)
571  : sol(s), cluster(c), demands(d), constrainedPlanning(true),
572  state(statestack), prevstate(statestack-1) {}
573 
574  /** Destructor. */
575  virtual ~SolverMRPdata() {};
576 
577  /** Verbose mode is inherited from the solver. */
578  unsigned short getLogLevel() const {return sol ? sol->getLogLevel() : 0;}
579 
580  /** This function runs a single planning thread. Such a thread will loop
581  * through the following steps:
582  * - Use the method next_cluster() to find another unplanned cluster.
583  * - Exit the thread if no more cluster is found.
584  * - Sort all demands in the cluster, using the demand_comparison()
585  * method.
586  * - Loop through the sorted list of demands and plan each of them.
587  * During planning the demands exceptions are caught, and the
588  * planning loop will simply move on to the next demand.
589  * In this way, an error in a part of the model doesn't ruin the
590  * complete plan.
591  * @see demand_comparison
592  * @see next_cluster
593  */
594  virtual DECLARE_EXPORT void commit();
595 
596  virtual const MetaClass& getType() const {return *SolverMRP::metadata;}
597  virtual size_t getSize() const {return sizeof(SolverMRPdata);}
598 
599  bool getVerbose() const
600  {
601  throw LogicException("Use the method SolverMRPdata::getLogLevel() instead of SolverMRPdata::getVerbose()");
602  }
603 
604  /** Add a new state to the status stack. */
605  inline void push(double q = 0.0, Date d = Date::infiniteFuture)
606  {
607  if (state >= statestack + MAXSTATES)
608  throw RuntimeException("Maximum recursion depth exceeded");
609  ++state;
610  ++prevstate;
611  state->q_qty = q;
612  state->q_date = 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