Scipy Linear Programming with Slack Variable

Question

I would like to minimize an objective function which I calculate based on variables A, B1, B2, B3, B4 coming from 4 Centers.

My (simplified) dataset looks like follows:

    Center1  Center2  Center3  Center4
A   10.0000  10.0000  10.0000  10.0000
B1   0.8415   0.9547   0.9460   0.9512
B2   0.9895   0.9443   0.9042   0.9634
B3   0.9460   0.9443   0.8101   0.9199
B4   0.9878   0.8362   0.9233   0.7909

I know how to find the vector of weights x that minimizes this objective function simply using scipy.optimize.linprog

import numpy as np
from scipy.optimize import linprog
from numpy.linalg import multi_dot as dot
import pandas as pd

# minimise the costs across A and B variables in the 4 centres.
df = pd.DataFrame(np.array([[10, 10, 10, 10],
                           [0.8415, 0.9547, 0.9460, 0.9512],
                           [0.9895, 0.9443, 0.9042, 0.9634],
                           [0.9460, 0.9443, 0.8101, 0.9199],
                           [0.9878, 0.8362, 0.9233, 0.7909]]),
                  columns=['Center1', 'Center2', 'Center3', 'Center4'],
                  index=['A', 'B1', 'B2', 'B3', 'B4'])
# to reduce df (2-D array) to a 1-D array
lamb = np.array([0.1, 1, 1, 1, 1])
bounds = list(zip([-3, -3, -3, -3], [3, 3, 3, 3]))
A= None
b=None
c = dot([lamb,df.values]).squeeze()
res3 = linprog(c=c, A_ub=A, b_ub=b, bounds=bounds,
              options={"disp": True})
# Solution vector of weights x
x = res3.x

My question is, I want to penalize the max difference between B1.x, B2.x, B3.x, B4.x. In other words, at the end of the optimization, I want the solution set x that results in the least absolute deviations in set B1.x, B2.x, B3.x, B4.x.

>>df.loc[['B1', 'B2', 'B3', 'B4'],:].dot(x)
Out[24]: 
B1   -11.0802
B2   -11.4042
B3   -10.8609
B4   -10.6146
dtype: float64

I can calculate the pairwise differences between all pairs of Bi,Bj as follows, since I want the maximum differences for each pair I look at both Bi-Bj and Bj-Bi.

# pairwise differences
constraints = {'b1_b2' : df.loc['B1']-df.loc['B2'],
               'b1_b3' : df.loc['B1']-df.loc['B3'],
               'b1_b4' : df.loc['B1']-df.loc['B4'],
               'b2_b3' : df.loc['B2']-df.loc['B3'],
               'b2_b4' : df.loc['B2']-df.loc['B4'],
               'b3_b4' : df.loc['B3']-df.loc['B4']}
const_df = pd.DataFrame(constraints)
A = pd.concat([const_df, -1*const_df], axis=1).T
b = np.array([1]*12) # the 1's here are arbitrary place holders.
res4 = linprog(c=c, A_ub=A, b_ub=b, bounds=bounds,
          options={"disp": True})

The code above runs but I do not quite get how to include slack variables that penalise the max() of these pairwise differences in A, which are currently just in Ax<=b constraint form. I am aware Linear Programming can be used to solve the absolute deviation problem. I would appreciate greatly if anyone can provide some direction / simple code.

Maybe add a formal description of your optimization-problem as it's not your typical LP-problem (no constraints?) and it's questionable if that's the approach to take here. Penalizing the differences to each other in LP is possible, but only with l1-norm (which has some downsides). L2-norm like penalization would render it a QP (not available in scipy). If your problem is really constraint-less, there is not need to use linprog. scipy's minimize then would be much easier to use and can work with nonlinear objectives (e.g. l2-norm). — sascha
– sascha, Commented Jan 15, 2018 at 13:48
@sascha, thank you for your comment. I have been told it is possible to penalize all C (4,2) pairs using pairwise differences (B1-B2), (B1-B3),... and including slack variables and a maximum deviation variable. So solving this while remaining within LP. I just do not know how to formulate it exactly. — Zhubarb
– Zhubarb, Commented Jan 15, 2018 at 13:49
Yes it's possible and can be done easier with auxiliary-variables. But i'm not sold yet about it being a good approach. — sascha
– sascha, Commented Jan 15, 2018 at 13:50
@sascha, there are indeed other inequality constraints but I have excluded them to simplify the problem to capture the core of my question: use of slack variables and minimizing the "variance" in the B1.x, B2.x, B3.x, B4.x. — Zhubarb
– Zhubarb, Commented Jan 15, 2018 at 13:53
Completely ignoring things like that does not help much (as people will question your approach). Research / decide on the penalization first: l1, l2, ... It's not yet formal in a mathematical sense. — sascha
– sascha, Commented Jan 15, 2018 at 13:55

Erwin Kalvelagen · Accepted Answer · 2018-01-15 17:53:13Z

1

Minimizing the range of a set of variables is not too difficult:

minimize sum(j, c(j)*x(j)) + P*(maxx - minx)
B(i) = sum(j, b(i,j)*x(j))
minx ≤ B(i)
maxx ≥ B(i)

where minx and maxx are additional variables and p is some penalty. This is linear and continuous so can be used in an LP model in a straightforward way.

edited Jan 15, 2018 at 17:53

answered Jan 15, 2018 at 14:00

Erwin Kalvelagen

16.9k3 gold badges17 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

Zhubarb Over a year ago

Thank you for your answer, I am not clear on how to implement what you provide above in the context of linear programming. Some more context would be helpful.

Erwin Kalvelagen Over a year ago

You don't know how to add a linear constraint to an LP?

Zhubarb Over a year ago

I know how to a dd a linear constraint. I do not know which columns you propose to add to C in C'x, which is df in my example.

Erwin Kalvelagen Over a year ago

You need to add variables (or columns) B1,B2,B3.B4 and minx,maxx to your LP problem.

Zhubarb Over a year ago

Apologies, I have edited my question to try to make it clearer.

|

Collectives™ on Stack Overflow

Scipy Linear Programming with Slack Variable

1 Answer 1

8 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

8 Comments

Your Answer

Sign up or log in

Post as a guest

Related