How to use sum of absolute difference condition in python pulp?

Question

I have been looking up similar posts regarding absolute value condition in linear programming, and trying the proposed solutions. However, I am still struggling to make my pulp setup work in python.

I post the simplified code here. Specifically, in "nearer constraint" below, I want to impose the sum of absolute difference to be smaller than some threshold, "sum(df['diff_orig'])". The posted code works but this is with just a sum difference not with absolute difference.

Any help will be greatly appreciated!

J

import pandas as pd
import pulp

# initialize data
nav = 1000
data = [['A', 0.2], ['B', 0.4], ['C', 0.1], ['D', 0.3], ['cash', 0.0]]

# create the pandas DataFrame
df = pd.DataFrame(data, columns=['asset', 'w_star'])
df['prccd'] = [17, 21, 119, 49, None]
df['q_tilde'] = [11, 19, 0, 6, None]
df['val'] = df.prccd * df.q_tilde
df.loc[df.asset == 'cash', 'val'] = nav - sum(df.loc[~df.val.isna(), 'val'])
df['w_act'] = df.val / sum(df.val)
df['diff_orig'] = abs(df.w_star - df.w_act)
df = df.set_index('asset')

# manipulate cash
dfnc = df[df.index != 'cash']

# create variables and model
dq = pulp.LpVariable.dicts("dq", dfnc.index, cat='Integer', lowBound=0)
mod = pulp.LpProblem("CashReduction", pulp.LpMinimize)

# objective function
mod += nav - sum([dq[i] * dfnc.loc[i, 'prccd'] + dfnc.loc[i, 'q_tilde'] * dfnc.loc[i, 'prccd'] for i in dfnc.index])

# lower bounds:
for i in dfnc.index:
    mod += dq[i] >= 0

# budget constraint
mod += sum([dq[i] * dfnc.loc[i, 'prccd'] for i in dfnc.index]) <= df.loc['cash', 'val']

# nearer constraint
mod += sum(
    [dfnc.loc[i, 'w_star'] - (dq[i] * dfnc.loc[i, 'prccd'] + dfnc.loc[i, 'q_tilde'] * dfnc.loc[i, 'prccd']) / nav
     for i in dfnc.index]) <= sum(df['diff_orig'])

# individual diff cannot be bigger than 3%
for i in dfnc.index:
    mod += (dfnc.loc[i, 'w_star'] -
            (dq[i] * dfnc.loc[i, 'prccd'] + dfnc.loc[i, 'q_tilde'] * dfnc.loc[i, 'prccd']) / nav) <= 0.03
for i in dfnc.index:
    mod += (dfnc.loc[i, 'w_star'] -
            (dq[i] * dfnc.loc[i, 'prccd'] + dfnc.loc[i, 'q_tilde'] * dfnc.loc[i, 'prccd']) / nav) >= -0.03

# solve model
mod.solve()

# output solution
for i in dfnc.index:
    print(i, dq[i].value())```

Answer 1

You will need to introduce an additional indexed variable to do this. ABS is non-linear, so the typical way to handle one ABS function is to introduce one variable and make that variable greater than the pos value and greater than the negation of the target of ABS like so:

if we are working with |x - y|...
g > x - y
g > -(x - y)

in your case you have an ABS function for each element to be summed, so you can just extend the above by creating a new variable, indexed by the same things you want to sum, and working with that...

import pandas as pd
import pulp

# initialize data
nav = 1000
data = [['A', 0.2], ['B', 0.4], ['C', 0.1], ['D', 0.3], ['cash', 0.0]]

# create the pandas DataFrame
df = pd.DataFrame(data, columns=['asset', 'w_star'])
df['prccd'] = [17, 21, 119, 49, None]
df['q_tilde'] = [11, 19, 0, 6, None]
df['val'] = df.prccd * df.q_tilde
df.loc[df.asset == 'cash', 'val'] = nav - sum(df.loc[~df.val.isna(), 'val'])
df['w_act'] = df.val / sum(df.val)
df['diff_orig'] = abs(df.w_star - df.w_act)
df = df.set_index('asset')
print(df)

# manipulate cash
dfnc = df[df.index != 'cash']

# create variables and model
dq = pulp.LpVariable.dicts("dq", dfnc.index, cat='Integer', lowBound=0)
ab_dif_element = pulp.LpVariable.dicts("ab_dif", df.index)
mod = pulp.LpProblem("CashReduction", pulp.LpMinimize)

# objective function
mod += nav - sum([dq[i] * dfnc.loc[i, 'prccd'] + dfnc.loc[i, 'q_tilde'] * dfnc.loc[i, 'prccd'] for i in dfnc.index])

# this is redundant...you've already set lowBound
# # lower bounds:
# for i in dfnc.index:
#     mod += dq[i] >= 0

# budget constraint
mod += sum([dq[i] * dfnc.loc[i, 'prccd'] for i in dfnc.index]) <= df.loc['cash', 'val']


for i in dfnc.index:
    # pos ab_dif
    mod += ab_dif_element[i] >= dfnc.loc[i, 'w_star'] - (dq[i] * dfnc.loc[i, 'prccd'] + dfnc.loc[i, 'q_tilde'] * dfnc.loc[i, 'prccd']) / nav
    # neg ab_dif
    mod += ab_dif_element[i] >= -(dfnc.loc[i, 'w_star'] - (dq[i] * dfnc.loc[i, 'prccd'] + dfnc.loc[i, 'q_tilde'] * dfnc.loc[i, 'prccd']) / nav)

# nearer constraint
mod += sum(ab_dif_element[i] for i in dfnc.index) <= sum(df['diff_orig'])

# individual diff cannot be bigger than 3%
for i in dfnc.index:
    mod += (dfnc.loc[i, 'w_star'] -
            (dq[i] * dfnc.loc[i, 'prccd'] + dfnc.loc[i, 'q_tilde'] * dfnc.loc[i, 'prccd']) / nav) <= 0.03
for i in dfnc.index:
    mod += (dfnc.loc[i, 'w_star'] -
            (dq[i] * dfnc.loc[i, 'prccd'] + dfnc.loc[i, 'q_tilde'] * dfnc.loc[i, 'prccd']) / nav) >= -0.03

# solve model
mod.solve()

# output solution
for i in dfnc.index:
    print(i, dq[i].value(), ab_dif_element[i].value())