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.
