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:

https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linprog.html

I implemented 3 different input structures for defining LP problems:

1. Model table with fixed number of columns (horizontal structure) – in situation when we have relatively small number of optimizing variables and this number is fixed
2. Model table with vertical structures – instead of defining input for Python RFA in matrix structure, matrix structure is transformed into vertical structure in order to keep number of columns fixed, but also keep possible to define very complex linear programming problems without restrictions on the number of unknown variables and constraints
3. Model table with equation in textual format – this approach has same advantages as previous one, but this approach requires very careful definition of equations in text format.

In order to explain as simply as possible the way of solving linear programming tasks and the way a Python script works, we will use the following optimization problem:

Approach with horizontal structure

For this approach we use 2 input model tables and one Python RFA:

In model table Variables, we define all unknown variables and their lower and upper boundary:

In model table Constraints, we define all constraints as well as objective function:

Name of fields that we use to store coefficients should match name of unknown variables defined in model table Variables. For constraint type we can choose following values “<=”, “<”, “>=”, “>”, “=” and also we can set our optimization problem to minimization (MIN) or maximization (MAX).

We use Python RFA to perform linear programming calculations. Below you can see code that we implemented in script.

Firstly, we need to import all necessary packages:

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

takes the following format

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'] == '<')]

Function linprog accepts following arguments:

• c – array of coefficients in objective function
• A_ub – matrix of all coefficients in constraints of type “<” and “<=”
• b_ub – array of bounds for constraints of type “<” and “<=”
• A_eq – matrix of all coefficients in constraints of type “=”
• b_eq – array of bounds for constraints of type “=”
• bounds – array of tuples that represent lower and upper boundary

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')

Python script produces correct optimal result:

Approach with vertical structure

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):

We can transform this matrix into 3-columns table and thus enable simple definition and modification of linear programming problems. First row will be transformed into following table:

By simply increasing the Constraint number variable, we can define other constraints in the same table Second row will be transformed into following table:

Similarly, third row will be transformed into following table:

For this approach we are also using two model tables although we can use just one.

Model table Bounds has same purpose as in previous example; to define upper and lower boundary for each variable.

In model table Linear Programming Vertical, we save our vertical structure.

This approach can be implemented with just Linear Programming Vertical model table (without MT Bounds), since we can define upper and lower boundaries for unknown variables as additional constraints. Here is an example:

Python Remote Function Adapter is implemented with following code. Code will not be additionally explained since it is similar to code previously explained.

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')

Approach with equations in textual format

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:

1. All unknown variables should be in format X1, X2, …, Xn
2. There should be no characters between coefficients and unknown variables
3. There should be no characters between +/- signs and coefficients
4. There should be only one “space” between unknown variables and +/- signs

For defining lower and upper boundaries for each variable we can also use model table Bounds, but we can define bounds as additional constraints in model table Text Formula MT.

Here is an implementation code for Python RFA for this approach:

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