Hi there,
My name is Novak and in this blog I will share with you the progress that I have made in the field of Linear Programming in SAP Profitability and Performance Management Cloud. Optimization problems can be easily solved on SAP Profitability and Performance Management Cloud using Python Remote Function Adapter which offers huge possibilities to end users for different purposes. In this blog I will describe three approaches for defining and solving Linear Programming problems and hope that you will find this blog useful for solving your own optimization problems.
Python has a very powerful library called Scipy that allows users to perform very complex calculations and solve optimization problems. For linear programming problems we can use function linprog from scipy.optimize subpackage. You can find more information about linprog function on the following link:
I implemented 3 different input structures for defining LP problems:
import pandas as pd
from scipy import optimize
import numpy as np
Next step is to import all data from our two input model tables. We will access to model table Variables using “Input” feature and to model table Constraints using “Lookup” feature. After that we can extract our unknown variables and bounds. We need to structure bounds as array of tuples.
variables = pd.DataFrame(scope.get('data'))
constraints = pd.DataFrame(scope.get('lookups')['F_2'])
unknown = variables['VAR']
bounds = []
for a, b in zip(variables['LOWBOUND'], variables['UPPBOUND']):
bounds.append((a, b))
Function linprog works by only minimizing objective function. However, this does not mean that linear programming problems with an objective function to be maximized cannot be solved. Maximization problem can be easily converted into minimizing problem by multiplying all coefficients by -1 (changing their sign). This way our objective function
There is one more conversion that needs to be done. Since function linprog accepts only constraints of type “<=”, “<” or “=” we need to convert constraints of type “>” and “<=” to constraints of type “<” and “<=” on the same way, by multiplying coefficients by -1.
change_sign = unknown.append(pd.Series('CONSTVALUE'))
constraints.loc[constraints.CONSTTYPE == '>=', change_sign] = constraints[constraints.CONSTTYPE == '>='][change_sign] * (-1)
constraints.loc[constraints.CONSTTYPE == '>', change_sign] = constraints[constraints.CONSTTYPE == '>'][change_sign] * (-1)
constraints.loc[constraints.CONSTTYPE == 'MAX', change_sign] = constraints[constraints.CONSTTYPE == 'MAX'][change_sign].astype('float') * (-1)
constraints.loc[constraints.CONSTTYPE == '>=', 'CONSTTYPE'] = ['<=']
constraints.loc[constraints.CONSTTYPE == '>', 'CONSTTYPE'] = ['<']
constraints.loc[constraints.CONSTTYPE == 'MAX', 'CONSTTYPE'] = ['MIN']
Now we can separate objective function and constraints:
c = constraints[(constraints['CONSTTYPE'] == 'MIN')][unknown]
constraints = constraints[(constraints['CONSTTYPE'] == '<=') | (constraints['CONSTTYPE'] == '<')]
lower = constraints[np.array(constraints['CONSTTYPE'] == '<=')]
equal = constraints[np.array(constraints['CONSTTYPE'] == '=')]
A_ub = lower[unknown]
b_ub = lower['CONSTVALUE']
A_eq = equal[unknown]
b_eq = equal['CONSTVALUE']
solution = optimize.linprog(c, A_ub, b_ub, A_eq,b_eq, bounds)
At the end we need to extract optimal solution for each unknown variable and save it as output of Python RFA function by assigning it to variable scope[‘data’] in form of dictionary:
result = pd.DataFrame([], columns = ['VAR', 'OPTIMAL'])
result['VAR'] = variables['VAR']
result['OPTIMAL'] = round(pd.Series(solution.x), 2)
scope['data'] = result.to_dict('records')
Sometimes it might be problem if we have large number of unknown variables or number of these variables changes over time. If we choose previous approach, each time we need to change optimization problem (adding new variables), we need to create new environment field and change definition of model table Coefficient. This requires additional work and effort. Fortunately, we can transform horizontal into vertical structure and thus make system much more flexible. Below is shown illustration how we can transform matrix structure into vertical (array) structure:
First row represents objective function and following rows represent all constraints (not including individual lower and upper boundary for each variable). If n is number of unknown variables, first n columns contain coefficient. Column n+1 represents constraint type (<=, >=, <, >, 😃 or if problem is maximization or minimization (for first row). Last column represent constraint boundary (in the first row this value has no effect):
X1 | X2 | X3 | Type | Boundary |
24000 | 19000 | 50000 | MAX | 0 |
32 | 27 | 38 | <= | 11520 |
15 | 12 | 45 | <= | 11520 |
30 | 25 | 40 | <= | 23040 |
15 | 8 | 50 | <= | 6000 |
Constraint number | Variable | Coefficient |
0 | X1 | 24000 |
0 | X2 | 19000 |
0 | X3 | 50000 |
0 | TYPE | MAX |
Constraint number | Variable | Coefficient |
1 | X1 | 32 |
1 | X2 | 27 |
1 | X3 | 38 |
1 | TYPE | <= |
1 | BOUND | 11520 |
Constraint number | Variable | Coefficient |
2 | X1 | 15 |
2 | X2 | 12 |
2 | X3 | 45 |
2 | TYPE | <= |
2 | BOUND | 11520 |
Constraint number | Variable | Coefficient |
5 | X1 | 1 |
5 | TYPE | >= |
5 | BOUND | 100 |
Constraint number | Variable | Coefficient |
6 | X1 | 1 |
6 | TYPE | <= |
6 | BOUND | 180 |
import pandas as pd
import numpy as np
from scipy.optimize import linprog
data = pd.DataFrame(scope.get('data'))
bounds = pd.DataFrame(scope.get('lookups')['F_5'])
unknown = data[data['CONNUM'] == 0]['VAR']
unknown = unknown[unknown != 'TYPE']
matrix = data.set_index(['CONNUM','VAR'])['COEFF'].unstack().rename_axis(None, axis=1).rename_axis(None).fillna(0)
matrix[unknown.append(pd.Series('BOUND'))] = matrix[unknown.append(pd.Series('BOUND'))].apply(pd.to_numeric)
change_sign = unknown.append(pd.Series('BOUND'))
matrix.loc[matrix.TYPE == '>=', change_sign] = matrix[matrix.TYPE == '>='][change_sign] * (-1)
matrix.loc[matrix.TYPE == '>', change_sign] = matrix[matrix.TYPE == '>'][change_sign] * (-1)
matrix.loc[matrix.TYPE == 'MAX', change_sign] = matrix[matrix.TYPE == 'MAX'][change_sign] * (-1)
matrix.loc[matrix.TYPE == '>=', 'TYPE'] = ['<=']
matrix.loc[matrix.TYPE == '>', 'TYPE'] = ['<']
matrix.loc[matrix.TYPE == 'MAX', 'TYPE'] = ['MIN']
matrix = matrix[unknown.to_list() + ['TYPE', 'BOUND']]
c = matrix[matrix.TYPE == 'MIN'][unknown]
lower = matrix[np.array(matrix.TYPE == '<=')]
equal = matrix[np.array(matrix.TYPE == '=')]
A_ub = lower[unknown]
b_ub = lower['BOUND']
A_eq = equal[unknown]
b_eq = equal['BOUND']
all_bounds = []
for i in unknown:
el = bounds[bounds.VAR == i]
if(el.size == 0):
all_bounds.append((0, None))
else:
all_bounds.append((el.LOWBOUND.iloc[0], el.UPPBOUND.iloc[0]))
all_bounds
solution = linprog(c, A_ub, b_ub, A_eq,b_eq, all_bounds)
result = pd.DataFrame()
result['VAR'] = unknown
result['OPTIMAL'] = solution.x
result['OPTIMAL'] = result['OPTIMAL'].round()
scope['data'] = result.to_dict('records')
There is one more option we can use in order to avoid creation of additional environment fields and modification of input model table; we can define equations in textual format. For this purpose we use model table Text Formula MT where we define constraints and objective function and model table Bounds (like in previous example). Model table Text Formula MT consists of 3 columns: Formula, Constraint Type and Constraint Value.
There are a few things to keep in mind when writing equations:
import pandas as pd
import numpy as np
from scipy.optimize import linprog
import re
data = pd.DataFrame(scope.get('data'))
bounds = pd.DataFrame(scope.get('lookups')['F_5'])
formula = data.FORMULA
matrix = pd.DataFrame()
for i in range(formula.size):
row = formula[i].split(' ')
for j in row:
coef_x = j.split('X')
matrix.loc[i, 'X' + str(coef_x[1])] = float(coef_x[0])
unknown = pd.Series(matrix.columns)
matrix[['TYPE', 'BOUND']] = data[['CONSTTYPE', 'CONSTVALUE']]
matrix[unknown.append(pd.Series('BOUND'))] = matrix[unknown.append(pd.Series('BOUND'))].apply(pd.to_numeric)
change_sign = unknown.append(pd.Series('BOUND'))
matrix.loc[matrix.TYPE == '>=', change_sign] = matrix[matrix.TYPE == '>='][change_sign] * (-1)
matrix.loc[matrix.TYPE == '>', change_sign] = matrix[matrix.TYPE == '>'][change_sign] * (-1)
matrix.loc[matrix.TYPE == 'MAX', change_sign] = matrix[matrix.TYPE == 'MAX'][change_sign] * (-1)
matrix.loc[matrix.TYPE == '>=', 'TYPE'] = ['<=']
matrix.loc[matrix.TYPE == '>', 'TYPE'] = ['<']
matrix.loc[matrix.TYPE == 'MAX', 'TYPE'] = ['MIN']
matrix = matrix[unknown.to_list() + ['TYPE', 'BOUND']]
c = matrix.loc[matrix.TYPE == 'MIN', unknown]
lower = matrix[np.array(matrix.TYPE == '<=')]
equal = matrix[np.array(matrix.TYPE == '=')]
A_ub = lower[unknown]
b_ub = lower['BOUND']
A_eq = equal[unknown]
b_eq = equal['BOUND']
all_bounds = []
for i in unknown:
el = bounds[bounds.VAR == i]
if(el.size == 0):
all_bounds.append((0, None))
else:
all_bounds.append((el.LOWBOUND.iloc[0], el.UPPBOUND.iloc[0]))
all_bounds
solution = linprog(c, A_ub, b_ub, A_eq,b_eq, all_bounds)
result = pd.DataFrame()
result['VAR'] = unknown
result['OPTIMAL'] = solution.x
result['OPTIMAL'] = result['OPTIMAL'].round()
scope['data'] = result.to_dict('records')
Linear programming has great possibilities of application in practice, and SAP Profitability and Performance Management has once again shown its potential and power to solve the most demanding practical problems. I hope you find this blog useful and it will help you solve far more advanced and complex optimization problems. If you have any question, feel free to ask it in the comments, and we will do our best to answer and help you. For the end I would like to suggest you to follow SAP Profitability and Performance Management topic page as well as blog feed so you can be up-to-date with all topics and innovations and ask and answer questions you are interested in here
You must be a registered user to add a comment. If you've already registered, sign in. Otherwise, register and sign in.