Python non-linear optimization problem (minimize) in SciPy

Question

I am trying to solve a shift scheduling optimisation problem in Python that is slightly different from the one outlined in this article. The only issue is I can't use the pulp package as it is not a linear problem.

From what I understand, the best way to solve my problem is to use the scipy.optimize package, however I am having difficulties translating the following problem formulation into actual code. The inputs are straightforward (two arrays) and the goal is to minimize a function with a constraint.

Problem formulation

• Dimensions: i=1...T (hours of the day), j=1...n (total number of multi-hour shifts for the day)
• Inputs: a[i,j] (two-dimensional array storing the shift configuration) and d[i] (expected demand for the hour i)
• Output: the script must return the optimal number of workers required for each shift w[j]
• Minimization: we want to minimize the total cost of workers for the day. What makes the problem slightly more complicated is the cost per hour c[i] is a function of w[j] (we don't pay the same hourly wage if there are too many workers): min(sum c[i]) (i=1...T) where c[i] = d[i]^2 / sum(a[i,j]*w[j]) (j=1...n).
• Constraint: for all i, sum a[i,j] w[j] >= d[i] (to ensure workers can meet the level of demand for each hour)

Code

w = pulp.LpVariable.dicts("num_workers", list(range(n)), lowBound=0, cat="Integer")
pulp.lpSum([(d[i]^2 / pulp.lpSum([a[i,j] * w[j] for j in range(n)])) for i in range(T)])

TypeError: unsupported operand type(s) for /: 'int' and 'LpAffineExpression'

Could anyone give me some hints on how to turn the following problem into an actual code understandable by SciPi? Thanks!

Answer 1

I think there's an issue w/ your formulation....

First, a typo: in python exponentiation is double asterisk, so this is proper (you just popped a different error before this one hit):

d[i]**2

Second, I think you have a problem with your cost function c[i]. As it is written above, your costs go down the more workers you hire, which is nonsensical. If you hired a million workers in time period i, then the cost would be infinitesimally small.

I would suggest you take a hard look at the relationships of cost and wage. And in the process relabel some things to make this read easier:

x:  Number of workers to hire
w:  Wage (indexed by either shift or hour, doesn't matter)
c:  Cost (indexed by wage or hour)

hand-jam a couple of example numbers into these formula to ensure you get something believable out of them.

Comment back if I've mis-interpreted this...

Answer 2

Yes, as it was suggested in the comments, one can approximate most of non-linear constraints and objectives by using piecewise linearization. It significantly reduces computational complexity of your problem.

However, for non-linear optimization in Python you may consider using pyomo optimization package, which fully supports open-source non-linear solvers (ipopt for continuous problems, couenne for non-convex mixed-integer non-linear programming or bonmin for convex mixed-integer nonlinear programming