- Problem decomposition is how the problem is divided up for processing.
- There are major problems in decomposition for the supply chain optimization in SNP.
- There are important benefits to decomposition.
- One test that can be used is running the optimizer for a single location in the supply network.
In finding a way to segregate the problem, cost optimizers are typically programmed to process material supply network by material supply network. This is called “decomposition,” which means to “decompose” the problem as described below:
SNP Optimizer Problem Division Decomposition
“Decomposition in computer science, also known as factoring, refers to the process by which a complex problem or system is broken down into parts that are easier to conceive, understand, program, and maintain.” – Wikipedia
SAP has the following comment on decomposition in its help:
“Decomposition is a flexible tool for balancing the tradeoff between optimization quality and required runtime. When runtime is unrestricted, the SNP optimizer usually provides a better (optimal) solution without decomposition; however, when a fixed runtime has been specified, using decomposition could assist the optimizer to find a better or, in fact, feasible solution.” – SAP Help
Decomposition can take place along several dimensions. For instance, in SAP SNP, decomposition can take place upon the following dimensions:
This can be found on the Solutions Methods tab of the SNP Optimizer Profile.
Time, product, and resource are all stated differently from one another.
Time asks for a window size. SAP recommends using time decomposition and says that it improves solution quality (which is not surprising as problem division tends to improve solution quality). Time is relatively easy to dimension on which to decompose due to the lack of problems with interdependence. The number of windows breaks down the planning horizon into buckets.
The product decomposition is entered as a percentage. This divides the problem into product groups. Product decomposition is the most commonly used form of problem division.
This is the only decomposition method in SNP that requires more master data to implement. Of course, whenever the need of master data is, the likelihood of success declines as companies have a problem keeping master data up to date. The master data of resource priority profiles are then assigned when this is engaged. Of the different decomposition methods, resource decomposition is the least frequently used and the most difficult to understand.
“Resource decomposition speeds up the solution process by analyzing the material flow and basic optimizer decisions about production, procurement, and transportation to determine a resource sequence. The optimizer can then create sub-problems for the individual resources, which are solved in sequence. The optimizer makes decisions in every sub-problem that cause the resource to be loaded.” – SAP Help
However, one important issue here is how SAP has designed SNP concerning resources versus how the resources, specifically the categories of used resources. SAP’s resource setup allows a wide variety of resources to be used, as can be seen from the screenshot below:
While many resource categories are possible, the vast majority of SNP implementations only actually constrain production constraints. Optimization only focuses on or uses constraints that are set to finite. (If not finite, the resource can be used for information purposes to allow planners to see what weeks are over capacity.)
Because of this fact, the complexity involved in, as SAP says, “analyzing the material flow and basic optimizer decisions about production, procurement, and transportation to determine a resource sequence” is a lot more simple than it sounds. The material flow means looking at the overall supply network.
If the only resource to be analyzed are production resources, then it really just comes down to combining products that share the same resource as a sub-problem. Without this, a sequential run of each product (each product that shares the resources as a separate sub-problem, as in the case with product decomposition) would result in one product receiving the resource allocated to its production before another based upon the “luck” of the sequence of the product sub-problem being run through the optimizer.
Using Both Product and Resource Decomposition
There are a few interesting things about this comment from SAP concerning using both product and resource decomposition at the same time.
“It is particularly advisable to use resource decomposition if the production processes always load the resources in a similar sequence. Resource decomposition does not reduce memory requirements. If you want to use product and resource decomposition together, the system carries out the resource decomposition first. The product decomposition then tries to improve upon the results of the resource decomposition.” – SAP Help
The portion from the quotation above in orange is, of course, fascinating. It is also surprising, at least to me. If I had been designing the decomposition method with developers at SAP, I would have requested that when both resource and product decomposition are selected, it would mean that the system would look at both at the same time. This is closer to the material flow requirements at most companies I have worked with.
In effect, this would increase the sub-problem size, as products with shared resources would be included as part of the same sub-problem in the supply network. This conceptually would be described below:
Sharing Resources Across Products
This type of decomposition solves the issue of resources that are shared across products. It does have the disadvantage of creating a larger sub-problem; however, shared entities with inter-relationships should be in the same sub-problem. However, SNP does not work that way. Instead, it processes the decomposition sequentially. This cannot possibly be as good a solution as the design laid out above. Although this would seem to be an issue with CPLEX rather than SAP, as CPLEX is the solver doing the work behind the scenes, this is SAP’s setup, and I have to say, the fact that one optimization does not respect a previous optimization, makes this design looks quite strange to me.
Getting back to the technical aspects of the discussion, I am unsure if I would use it. This would lead one to perform the decomposition by manually breaking up the problem into different runs, which is less desirable and requires extra maintenance effort. Furthermore, the more resources there are, the less feasible this solution would be. Interestingly, I have never read any post or book which criticized SAP’s resource decomposition method before.
The following quote is instructive concerning the benefits of decomposition:
“Since the existence of many restrictions or – to a higher extent – discrete variables can lead to high computational efforts, SAP APO offers various possibilities to reduce the storage and runtime requirements by dividing the problem into parts. Particularly in the case the supply chain model results in a MILP (mixed integer linear program) problem solver runtimes can get very high; integer models are a consequence of discrete decisions such as modeling lot size intervals. As the implementor does not have direct access to SAP’s mathematical model formulations these methods of handling the solution times are the approximate way of influencing the behavior of the SAP APO optimizer (apart from changing master data that define the coefficients in the model equations). Especially when dealing with large MILP problems the runtime of the algorithm might be cut by decomposing the problem into smaller subproblems.” – Real Optimization with SAP APO
Optimization with Integers and Integer Relaxation
While integer relaxation may appear to be a minor issue, in fact, setting a number of the variables to integers greatly lengthens out the run-time, and APO does not have an option for relaxing integer constraint as most other optimizers that I have worked with do.
Here is an example of integer relaxation within the Frontline Solver for Excel. It is set as a default to 5% of integer optimality. This allows the solver to find a perfect solution still but to spend much less time calculating it. Because Frontline Solver is much more frequently used for calculating strategic objective functions with far fewer outputs, relaxing the integer requirement is a much more simple matter than doing so in a supply chain planning enterprise optimizer which calculates a tremendous number of value as output, all that would have to be adjusted post-optimizer to be actionable in the real world.
The concept of integer relaxation is design to solve the problem more quickly for testing. Integer relaxation determines that all of the output (such as purchase orders) could be relaxed within the optimizer, bringing much faster solution times, but with internal rounding.
Therefore, 45.3 units would become 50 units to meet the lot size quantity and the integer requirement. (sending .3 of a unit makes great sense from a mathematical perspective but does not make much sense in the real world. APO could accomplish this with a post-optimization rounding routine, but evidently, the developers preferred not to go down this track, which means much more hardware is required to run SNP than would have been required if this approach was taken.
Josef Kallrath, Thomas I. Maindl, describes how the problem decompositions change depending upon the decomposition selected.
“Resource decomposition is based on the analysis of the material flow and the basic decisions about production. After the analysis, sub-problems are developed for the individual resources according to which the resource assignment is generated. With product and resource decomposition priority profiles can be established to determine the sequence in which the optimizer aggregates and plans product groups and resources.” – Real Optimization with SAP APO
Time decomposition, on the other hand, divides the optimization problem by the time horizon.
“Finally, there is an option for vertical and horizontal aggregation of planning data where the optimization is dealing with aggregated data.. Vertical aggregation is concerned with product demand and horizontal aggregation deals with subgroups of the supply chain network.” – Real Optimization with SAP APO
More on Problem Division
While decomposition sounds comprehensive, in fact, this is only one method and the most automated method of dividing the optimization problem. Another way is to divide the problem into different optimization runs manually. For instance, some companies may use product decomposition but then divide the problem by product attribute so that product with similar attributes is run together.
This can overlay with how many production facilities there are that produce each type of product. In general, the topic of both decomposition and run division is one of the most all-encompassing and complex of all the optimization decisions.
Single Location Optimization in the SNP Optimizer
One fascinating question is whether the SNP optimizer should be run interactively and for one “sub-problem.” (you can read about sub-problems and decomposition in this article.) Companies that migrate to cost optimization do so most frequently from MRP or supply planning heuristics. However, both of these methods can be run interactively. This can be accomplished without negatively affecting the rest of the product locations in the supply network. I explain this in my Supply Planning with MRP, DRP, and APS Software.
However, cost optimization works differently. The CPLEX optimizer, which resides within SAP SNP (and does the heaviest lifting – SAP has essentially created a “wrapper” around the optimizer, which allows for input fields and output interfaces) divides the overall supply network problem into a series of sub-problems, in a process called decomposition.
SNP allows the optimizer’s interactive running from within the product location combination instead of the overall supply network. This can be activated by selecting the Optimizer button within the planning book, as shown below.
An optimizer should never be run for a single product location combination but should follow the exact decomposition set up in the SNP Optimization Profile. Instead, the way SAP has designed the interactive optimizer transaction. The optimizer runs for any set of products that are selected in the planning book. However, the planner must know what locations are part of the product location sub-problem to produce a plan which is optimal or even “correct.”
This is not a production facility, and there are, therefore, no production costs. In fact, the costs are quite limited, with the vast majority of costs only being storage. This is simply a re-calculation of the storage costs that were calculated during the past optimization planning run.
The SNP Optimizer Analysis
The optimizer cannot in effect do anything because no transportation lanes are included in the optimization run. This means that it is not interacting with the other locations. However, for a supply plan to make any sense, a location must interact with different locations. This is accomplished by selecting the planning book — choosing APO Location in the Selection Profile and then selecting all of the line items and opening them in spreadsheet view to the right.
Different optimizers have different ways of decomposing the problem. The selection is actively made during the design stage based upon either time, resource, or product. The three products are the most common, which breaks each sub-problem into a sub-network per product within the overall supply network.
“Real Optimization with SAP APO,” Josef Kallrath, Thomas I. Maindl, Springer Press, 2006 https://help.sap.com/saphelp_ewm70/helpdata/en/01/bc044017355c0ce10000000a1550b0/content.htm SAP Help
History of CPLEX
(CPLEX is now owned by IBM, which is a mitigating factor against its use. The fact that so many enterprise optimizers are built around CPLEX says excellent things about the CPLEX product.