4

I was trying to resolve a LP problem with a constraint that is calculated by dividing variable A by variable B.

The simple version of the problem is as below:

  1. The product is made by two materials (A and B)

  2. % of A should be greater than 50%

  3. % of B should be less than 40%

  4. Total amount of A and B are 100

Objective: What's the minimum amount of A?

The code is like:

from pulp import *

prob = LpProblem('Simple problem', LpMinimize)
x = LpVariable('x', 0, None, 'Integer')
y = LpVariable('y', 0, None, 'Integer')
prob += x
prob += x / (x + y) > 0.5  # <== Where the error happens
prob += y / (x + y) < 0.4
prob += x + y == 100
prob.solve()

print 'Result: %s' % LpStatus[prob.status]
print 'Amount of A: %s' % value(prob.objective)

However I'm getting an error message saying:

TypeError: Expressions cannot be divided by a non-constant expression

It looks like PuLP does not support variable as divisor. https://github.com/coin-or/pulp/blob/master/src/pulp/pulp.py#L800

Any idea? If PuLP is not the right library to use, I'm happy to switch to any library that fits in.

UPDATE 27 Nov 2015

For some reason, the sample above does not make sense (not working as expected). I am very newbie to this library. Maybe it's not the right one to solve my problem at all. So if any one has suggestions of other libraries, it'd be appreciated.

BTW, Koen Peters's advice below is great. The error is gone after taking his advice. Thank you.

Community
  • 1
  • 1
killua8p
  • 304
  • 5
  • 10

2 Answers2

5

Linear Programming doesn't understand divisions, hence the error :) You have to reformulate it so that the division is formulated linearly. In this case:

prob += x / (x + y) > 0.5  
prob += y / (x + y) < 0.4

is equivalent to:

prob += x > 0.5 * (x + y)
prob += y < 0.4 * (x + y)

Which are linear constraints. Good luck!

Koen Peters
  • 326
  • 1
  • 2
  • 9
  • Thanks for the solution. It's working. What if the Objective is a division? Is there any way to work around? – killua8p Nov 26 '15 at 23:40
  • Optimising non-linear objectives is more challenging. If you can, try to avoid it or work around it! Look into Charles-Cooper's method (https://en.wikipedia.org/wiki/Linear-fractional_programming) if you can't avoid it – Koen Peters Nov 27 '15 at 09:55
0

I felt like zero shouldn't be allowed in my solution — and I included a variable that was the sum of x and y (think you're referring to it as A).

from pulp import LpProblem, LpStatus, LpVariable
from pulp import LpMinimize, LpMaximize, lpSum, value

# I feel like zero shouldn't be allowed for lower bound...
x = LpVariable("x", lowBound=1, cat="Integer")
y = LpVariable("y", lowBound=1, cat="Integer")
z = LpVariable("z", lowBound=1, cat="Integer")

model = LpProblem("Divison problem", LpMinimize)

model += x
model += z == x + y
model += z == 100

# Rather than division, we can use multiplication
model += x >= z * 0.5
model += y <= z * 0.4

model.solve()

print(LpStatus[model.status])

print(f"""
x = {int(x.varValue):>3}  #  60
y = {int(y.varValue):>3}  #  40
z = {int(z.varValue):>3}  # 100
""")
zachwill
  • 4,395
  • 3
  • 19
  • 17