## What is Operations Research about?

Operations Research deals with quantitative approaches in management science: process optimization and decision making using mathematical models. Therefore OR specialists use models from applied mathematics, statistics and computer science.

When OR Research started people had high expectations and in fact it has proven to be useful in many business cases like flight crew scheduling, production planning, supply chains and so on. So OR can help you to make your business smarter. But how important are methods from Operations Research in general? I think this is a very important question. Without optimization algorithms today’s super fast VLSI chips couldn’t be designed – and efficient management of container terminals needs those techniques. So let me summarize: In my opinion at the moment Operations Research has a only small number of applications but it has the potential to make the difference.

Linear optimization models are very simple models in which you optimize a linear function regards to linear constraints. Those linear optimization models can be used in resource allocation problems, production planning and to calculate network flows. Linearization is a very successful method in many cases. On the other hand many properties of linear models can be generalized to convex functions. And last but not least we have very effective algorithms to solve them.

## Linear Optimization

In the following I will present a small example of a problem that can be modeled using a linear functions. It is a hypothetical example that arises when you try to optimize SAP workflows by changing the priority of workitems according to cost/benefit ratio of a certain type of workflow. I will solve this problem using an LP solver in ABAP but I won’t present the details of changing workitem priorities.

Consider the case that we have a huge number of workflows of three different types but only a limited number of people who can work on them. Each workflow of a certain type needs a certain amount of resources/time to get completed and has a certain gain. So the task is to calculate a certain number of workflows so that that they completed according to the resources such that the total benefit is maximized.

Let’s consider the following mathematical model:

- We have three workflow types and 100 workflows of type 1, 50 of type 2 and 40 of type 3.
- Each workflow of type 1 needs an amount of 10, type 2 needs an amount of 50 resource units and type 3 needs 80 units.
- We have at most 2000 units of resources.
- Each completed workflow of type 1 has a benefit of 15, workflow type 2 has a benefit of 10 and workflow type 3 has 40

Please be aware that the numbers I’m using here are hypothtical. In the real world most probably a consultant would measure those values and calculate the numbers. But please be aware that those numbers can and will change because of following reasons: the cost/benefit ration changes or the number of people who do the work. Perhaps the values will even change day by day and if this happens the linear constraints and the linear function changes, too, but the solver will still find a new solution.

Now we have to find a more mathematical formulation of above introduced model. So we have to maximize the objective function 15 x1 + 10 x2 + 40 x3 with regards to following constraints:

- x1 <= 100, x2 <= 50 and x3 <= 40 and
- 10 x1 + 50 x2 + 80 x3 <= 2000.

The first inequalities defines the number of workflows of each type. The second inequality defines the ressources constraints we have to complete workitems. If we calculate non-negative numbers for x1, x2 und x3, we could select a set of workflows and raise their priority according to the computed result.

To solve a linear optimization problem you can use LP solvers you can use commercial and free tools on the java stack, but there is also an ABAP tool.

## GENIOS – an LP Solver in ABAP

SAP offers reuse tools as foundation of SAP Business Suite and I already blogged about it: Reuse Tools as Part of SAP Branding and Value Chain in SAP Ecosystem. Within software component SAP_BS_FND as part of in ERP Ehp 5 there is a tool called GENIOS called GEneric Integer Optimizer System. It has the SAP application component CA-EPT-GEN.

GENIOS has some unit tests that show how to use the tool. In the following I give an example how to solve the above mentioned problem instance.

DATA:

lr_model TYPE REF TO cl_genios_model,"problem instance

lr_objective TYPE REF TO cl_genios_objective,"objective function

lr_environment TYPE REF TO cl_genios_environment,

lr_x1 TYPE REF TO cl_genios_variable,"variables

lr_x2 TYPE REF TO cl_genios_variable,

lr_x3 TYPE REF TO cl_genios_variable,

lr_constraint TYPE REF TO cl_genios_linearconstraint,

lr_solver TYPE REF TO cl_genios_solver,

ls_result TYPE genioss_solver_result,

ls_variable TYPE genioss_variable,

lt_variables TYPE geniost_variable,

lv_value TYPE genios_float,

lv_name TYPE string."name of the variable

lr_environment = cl_genios_environment=>get_environment( ).

lr_model = lr_environment->create_model( 'PRIORIZATION' )."model name* Do maximazation

lr_objective = lr_model->create_objective(

if_genios_model_c=>gc_obj_maximization ).* We have three continous variables x1, x2 and x3

lr_x1 = lr_model->create_variable( iv_name = 'x1'

iv_type = if_genios_model_c=>gc_var_continuous ).

lr_x2 = lr_model->create_variable( iv_name = 'x2'

iv_type = if_genios_model_c=>gc_var_continuous ).

lr_x3 = lr_model->create_variable( iv_name = 'x3'

iv_type = if_genios_model_c=>gc_var_continuous ).* Define objective function as 15 x1 + 10 x2 + 40 x3

lr_objective->add_monom( io_variable = lr_x1 iv_coefficient = 15 ).

lr_objective->add_monom( io_variable = lr_x2 iv_coefficient = 10 ).

lr_objective->add_monom( io_variable = lr_x3 iv_coefficient = 40 ).* Definition of linear constraints: x1 <= 100

lr_constraint = lr_model->create_linearconstraint( iv_name = 'c1'

iv_type = if_genios_model_c=>gc_con_lessorequal iv_righthandside = 100 ).

lr_constraint->add_monom( io_variable = lr_x1 iv_coefficient = 1 ).* Definition of linear constraints: x2 <= 50

lr_constraint = lr_model->create_linearconstraint( iv_name = 'c2'

iv_type = if_genios_model_c=>gc_con_lessorequal iv_righthandside = 50 ).

lr_constraint->add_monom( io_variable = lr_x2 iv_coefficient = 1 ).* Definition of linear constraints: x3 <= 40

lr_constraint = lr_model->create_linearconstraint( iv_name = 'c3'

iv_type = if_genios_model_c=>gc_con_lessorequal iv_righthandside = 40 ).

lr_constraint->add_monom( io_variable = lr_x3 iv_coefficient = 1 ).* Definition of linear constraints: 10 x1 + 50 x2 + 80 x3 <= 2000

lr_constraint = lr_model->create_linearconstraint( iv_name = 'c4'

iv_type = if_genios_model_c=>gc_con_lessorequal iv_righthandside = 2000 ).

lr_constraint->add_monom( io_variable = lr_x1 iv_coefficient= 10 ).

lr_constraint->add_monom( io_variable = lr_x2 iv_coefficient = 50 ).

lr_constraint->add_monom( io_variable = lr_x3 iv_coefficient = 80 ).* Use the simplex solver

lr_solver = lr_environment->create_solver( 'SIMP' ).

lr_solver->load_model( lr_model )."load the model into the solver

ls_result = lr_solver->solve( )."solve the problem* Get the result

IF ls_result-solution_status = if_genios_solver_result_c=>gc_optimal OR

ls_result-solution_status = if_genios_solver_result_c=>gc_abortfeasible.

lt_variables = lr_model->get_variables( ).

LOOP AT lt_variables INTO ls_variable.

lv_name = ls_variable-variable_ref->gv_name.

lv_value = ls_variable-variable_ref->get_primalvalue( ).

WRITE: /,lv_name,' = ',lv_value.

ENDLOOP.

ENDIF.

lr_environment->destroy_solver( 'SIMP' ).

lr_environment->destroy_model( 'PRIORIZATION' ).

The program gives a solution to the workflow problem. In fact the solution is not integral so have to round it. Finding integer solutions is far more complex and requires more advanced mathematical methods like solving a series of linear programs perhaps using so called branch and cut algorithms but this is beyond the scope of this blog entry or you need a more powerful solver for mixed integer linear programs for example.

If you are interested I further features of GENIOS (resp. formulating linear models using a DSL) I recommend to check the unit tests of the framework.

## How can OR help to make the difference?

Operations Research deals with quantitative approaches in management science. Those methods can help in following areas:

- resource planning in highly adaptive, cloud based infrastructure,
- simulation to help making decisions and
- complex business rules.

So far most methods from Operations Research are used by mechanical or economical engineers or scientists and not by Business Process Experts. I think there is a reason for it. Some years ago many of us believed in projects organized by the waterfall approach but the speed of business increased and we had to learn agility. So project management changed and instead of huge project plans we are using iterative approaches. In my opinion this approach is characterized by following principles:

- divide and conquer,
- priorization,
- circle feedback.

So we try to find simple and pragmatic solutions and usually avoid every kind of complexity and especially mathematical models.

Please be aware SAP APO and SAP SCM use sophisticated methods for global optimization using aggregation and detailed scheduling using local optimization to tackle problems like the Multi-Level Capacitated Lotsizing Problem. Therefore we use techniques like heuristics, mixed integer linear programming and more. So OR can make a difference if we find the right use cases.

Graham RobinsonTobias TrappPost authorI have to apologize if the mathematical model caused the pain – perhaps I should have written some more lines about it.

But the main idea is really simple: in worflow environment -and in ERP in general- we often deal with ressource allocation: priorization or assigment of workitems to users and so on. And I put the question whether we could use standardized methods to do this in a smarter way.

Cheers,

Tobias

Graham RobinsonCheers

Graham Robbo

Trond Stroemme“we have to maximize the objective function 15 x1 + 10 x2 + 40 x3”

Where does this formula come from? why 15?

Cheers,

Trond

Tobias TrappPost authoronly a few lines above from where I introduced the formula I motivated the model: we have three types of workflows and each one has certain costs and benefits and we have only a limited group of people to complete the work.

I also meantioned the numbers 15, 10 and so on but I didn’t motivated how they were figured out: In the real world most prapobly a consultant would measure those values and calculate the numbers. But please be aware that those numbers can and will change because of following reasons: the cost/benefit ration changes or the number of people who do the work. Perhaps they will even change day by day and if this happens the linear constraints and the linear function changes, too, but the solver will still find a new solution.

I only used the numbers because I didn’t want to write about theory of linear programming and instead I wanted to show how to solve this in ABAP – and in fact those numbers occur in the source code.

Cheers,

Tobias

Jim SpathSince then, C has become the workhorse of code slinging (in my experience), with many other languages arguably taking its place as the ubiquitous Rosetta stone of scientific coding. Is ABAP the tool for operations research? I’d say hardly. Most university students would be coding in VB, PHP or maybe Perl (add a handful of others from Blag’s bag of tricks, like Ruby, or whatever) and may not know FORTRAN from an Edsel. The GNU g77 compiler, evolved in part from Bell Lab’s f2c, would be my engine of choice for high end numeric computing.

ABAP? As I said, it’s nice to demonstrate how one could use it, but I just don’t see a valid argument for converting FORTRAN models, or other algebraic notations, into ABAP.

Good blog, though.

Jim

Tobias TrappPost authorI don’t think the language is important. In fact most numerical algorithms are written in languages like Fortran, C and so on but there are computer scientists who claim that it is possible to compile better code in Java than C because Java has no pointers – others speak about inherent inefficiencies in Java. But this doesn’t bother me because an LP solver in ABAP can’t be as strong as super fast and sophisticated implementations like CPLEX. So if you want to do “hard” OR you should integrate a commercial solver or using Web Services. If you need to solve easier problems an free tool in C (wrapped into Java using JNDI and exposed as a web service) could be reasonable. The same is necessary if you use solvers for quadratic/convex optimization.

But are these reasons not you use an ABAP LP solver at all? I’m not sure. I know SAP customers who spent lots of effort to write sophisticated code for resource allocation that is hard to maintain and less powerful compared to the approach I sketched in this blog entry. I’m really convinced those people didn’t even think about a mathematical approach. At the moment I am asking why? Is mathematics completely useless for Business Process Experts except in SAP Solutions like SAP APO/SCM? Or are too many people used to define out mathematics?

Cheers,

Tobias

Jim SpathI thought about mentioning Java, and then didn’t, as I believe it is being orphaned within the SAP world view. It’s all “Mobile”, or “HANA” now. Fortunately I was drinking my black coffee when you came back with that, so I didn’t spill any. 🙂

As for the question “Is mathematics completely useless for Business Process Experts except in SAP Solutions like SAP APO/SCM”? I’d say BPXers aren’t going to be writing or implementing the models, they are going to be the power users who want it to (1) just work and (2) be there yesterday and (3) be bigger badder and faster than anything has been before. Does the idea of high-end analytics fit this bill? I really have no idea, but sense that the somewhat closed/proprietary HANA development environment (“it’s a package, not an app platform”, to paraphrase my friend Jon Reed’s findings) will impede leveraging it as the super-computer on your desktop that BPXers really want. And get IT out of the critical path, to boot.

Jim

Michelle CrapoI am a KISS type gal. Keep it simple. This to me is not simple.

But I learned some new things – so even though my brain fried while trying to understand the code – I liked the blog!

Michelle

Uwe FetzerJim SpathUwe Fetzer:

> We only have to document the code together with the BPXer.

Tobias Trapp:

> I thought that topics like linear optimization (or least squares and so on) are so trivial…

Operations Research works well for problems that can be modeled, or stated in a mathematically defined way. Something like the traveling salesperson, logistics or most supply chain transportation questions are answerable, but this solution has been so commoditized by now there is no point in anyone trying to build their own models, except as an academic exercise.

In the problems I see, most are simple enough that the computing power built into spreadsheets for the last couple decades can manage them (e.g., choose data set, “add trendline”, chose “linear”), with other questions too complex for the data constraints to be easily enumerated, and thus impossible to wield operations research as a tool. The number of exceptions, special cases, overrides and plain freedom of choice would prevent such topics from being calculated. I could see a truck driver following the guidance issued by the dispatcher on which deliveries to make, and which route to take, but asking a salesperson to do the same might be trickier. Yes, you’ll want to contact your prospects, your hot list, or whatever, but how do you build in the gut checks? And on the product development side, modelling expected consumer acceptance is certainly tried, but everyone can appreciate that past experiences are no predictor of future events. Just read your stock brokers fine print.

I would think there has to be an integrator or architect role between the developer and the BPXer. I don’t see most code slingers being able to work directly with the business users to fully scope which models work for which questions. Not trying to offend, but the developers job usually seems to be restricted to making the code “work” not making the code “useful.” I’ve needed to explain input sensitivity to various models more than once (i.e., Quicksizer).

I also don’t think a subject like least squares is trivial in most contexts. It is basic math, of course, but bringing algebra into a discussion of financial choices requires a receptive audience. That doesn’t always happen, I think.

Jim

Tobias TrappPost authorWithin the last days I found another interesting use case in the are of technical operations: jobs nets. The SAP LT tool creates job nets and using tests we know the runtime of every job and the dependencies. With scheduling methods we could optimize the model and so the overall runtime. I think the same can be true for comlex parallelization.

But now to business: As SAP For Insurance guy I would like to discuss OR methods in the are of financial and insurance products and expecially in the area of Provision Management and Reinsurance.

I agree with you: ABAP isn’t a platform for doing econometrics but I think ERP with Planning is like SOA without HTTP.

Cheers,

Tobias

Gregory Misiorekjust like they do today with statistical methods (e.g. least squares or standard deviation) which lie underneath all the investment advice they’ve been getting with regards to their 401(k) plans.

it only needs to be “dumbed down” (or KISSed) to the most basic elements and they will run with it in no time.

Michelle CrapoMichelle

Tobias TrappPost authorI was surprised that many people feel a little uncomfortable when reading mathematical models – I thought that topics like linear optimization (or least squares and so on) are so trivial that people could get bored when I spend too much time to motivate it. But @thorstenster convinced me that the blog is much more readable if I would motivated my approach with a few more lines. I already copied some things I explained in comments into the blog I hope I’ll find the time to make it even better.

Cheers,

Tobias

Michelle CrapoYes the comments help a lot! I’m still working my way through it. This intrigues me enough that I want to understand it.

If I understand it, I may use it. But even better, I’ll feel more comfortable using a mathematical model in my programming. I’m guessing there were / are times when it would make my programming easier.

Thank you! It’s a great blog. And I’m so glad you are keeping up with the questions.

Michelle

o oHi Tobias ,

Very good example. Thank you .

Please mind that there is a typing mistake in your problem . You’re stating :

1 – “Each completed workflow of type 1 has a benefit of 10, workflow type 2 has a benefit of 50 and workflow type 3 has 80 ”

2 – “So we have to maximize the objective function 15 x1 + 10 x2 + 40 x3 ” .

Therefore I assume that 1’s statement should be :

“Each completed workflow of type 1 has a benefit of 15, workflow type 2 has a benefit of 10 and workflow type 3 has 40 ”

For my LP models I used to declare :

lv_value TYPE P DECIMALS 2

Thank you ,

Octav

Tobias TrappPost authorHi Octav,

thank you for your correction, I just changes the blog entry.

Would you like to tell what kind of LP models do you use in the ABAP world?

Best Regards,

Tobias

Tobias TrappPost authorHi Yogendra,

did you delete that post?

I think this a typical knapsack problem: Please have a look at http://en.wikipedia.org/wiki/Knapsack_problem Can you check the Wikipedia entry to find out if this is indeed a knapsack problem?

This problem is hard to solve in terms of computational complexity – we call it NP-hard which means that there is probably no efficient algorithm that can solve the problem. Nevertheless computers got so fast that even unefficient algorithms have a chance to find solutions.

The problem is that the approach in this blog entry describes linear programming (LP) models and for knapsack the so called integer linear programming (ILP) is natural. I have no experience whether the ABAP LP solver supports ILP problems but If you are interested I can try it out end of this week. If you need a solution right now I think you should try a heuristic. Above mentioned Wikipedia article describes a Greedy algorithm proposed by George Dantzig that is quite good from my experience.

Best Regards,

Tobias

Yogendra AhujaHi Tobias….. thx a lot again for your time.

i am going through the wikipedia article , its very useful , although a bit complex to understand the equation. I also tried with ABAP LP Solver but dint succeed may be i am not creating right objective and constraints or may be it can not be solved using ABAP LP model .

Please if you can give it a try either using ABAP LP model or knapsack algorithm.

P.S I dint not delete my Post but was just editing and i think somehow it got deleted , as its not showing now.

Tobias TrappPost authorI tried the solver using NW 7.40 SP4 and got an error messages the the current bowser version doesn’t support non-continous models:

I tried it also with a mixed-integer linear solver:

lr_solver = lr_environment->create_solver( ‘MILP’ ).

But you can use the algorithm above as a heuristic for the knapsack problem by using a simplex solver (‘SIMP’) and continous models as above:

The linear constraints are necessary if your products are limited (f.e. in certain time period). But if there are no constraints you should set them to

x1 >= 0, x2 >= 0….There may be constraints about the freight weight if the goods have different weights. So this is about the capacity of the knapsack:

10 x1 + 50 x2 + 80 x3 <= 2000

Then you have to optimize the sum of x1, x2 and x3.

Since you use a continous model you have to round down the values which creates usually a non-optimal solution. You can try to “repair” by adding objects with small weight. This could create a good solution but not necessarily an optimum.

Best Regards,

Tobias

Shafiul FaisolNice Article!

Andrew BarnardI know it is rather late to comment – but there are a lot of potential applications for linear programming within SAP. I think about Enterprise Asset Management – and the development of a maintenance schedule that maximises the utility of maintenance activities whilst ensuring feasibility of material and labour resources. Funny that – sounds a little like what the SAP Multi Resource Scheduling could be…