Non-constant expressions cannot be multiplied

I am trying to solve a valued n-queens problem, in which queens in black squares worth double of those in white squares. I solved it in AMPL just fine, but I would like to try that in Python using a different approach. I tried to simplify that by using a variable $$k$$ in an if statement, such that if $$k$$ is odd then 1 (white square) and if $$k$$ is even then $$2$$ (black square) (Obs: $$k = N - i - j$$, where $$N$$ is the size of the chessboard, $$i$$ represents rows and $$j$$ represents columns). However I am getting this error: Non-constant expressions cannot be multiplied". I understand where the problem is but do not know how to overcome it.

Objective function $$\max z = \sum x_{ij} w_{ij}$$

Subject to:

1 queen per row $$\sum x_{ij} = 1 \; \forall j \; \{j \in \mathbb{N}, j \leq 8 \}$$ 1 queen per column $$\sum x_{ij} = 1 \; \forall i \; \{i \in \mathbb{N}, i \leq 8 \}$$ 1 queen per diagonal type 1 $$\sum x_{ij} \leq 1 \; \forall k \; \{ k=i+j | k \in \mathbb{N}, k < 16 \}$$ 1 queen per diagonal type 2 $$\sum x_{ij} \leq 1 \; \forall k \; \{ k=i-j | k \in \mathbb{Z}, -7 < k < 7 \}$$

$$x_{ij} \in \{0,1\}$$

from pulp import *
N = 8
nums = list(range(1, N+1)) #list from 1 to N",
numsC = list(range(1, N+1)) #list from 1 to N",
numsL = list(range(1, N+1)) #list from 1 to N",

vars = {}
r = {}

model = LpProblem('Damas', LpMaximize)

# Decison Variables
for i in nums:
for j in nums: # create a binary variable
vars[i, j] = LpVariable('x{},{}'.format(i, j), cat='Binary')

for i in numsC:
for j in numsL:
k = N - i - j
if k % 2 == 0:
r[i,j] = 2
r[i, j] = LpVariable('r', 'LowBound=0', cat='Integer')
else:
r[i,j] = 1
r[i,j] = LpVariable('r','LowBound=0', cat='Integer')

# Objective function
model += sum(vars[i, j] for i in nums for j in nums) * sum(r[i,j] for i in numsC for j in numsL)

# Restrições
# 1 queen per row
for i in nums:
model += sum(vars[i, j] for j in nums) <= 1
# 1 queen per column
for j in nums:
model += sum(vars[i, j] for i in nums) <= 1
# 1 queen per diagonal 1
for k in range(2, 2*N+1):
model += sum(vars[i, j] for i in nums for j in nums if i+j == k) <= 1
# 1 queen per diagonal 2
for k in range(-(N-2),(N-2)+1):
model += sum(vars[i, j] for i in nums for j in nums if i-j == k) <= 1
• You are multiplying variables vars and r in your objective function, which is not linear. PuLP only deals with linear expressions. May 13 '20 at 8:02

Here are some problems in your code:

1. I don't think you need

r[i, j] = LpVariable('r', 'LowBound=0', cat='Integer')

in your code. $$r$$ has been defined to be either $$1$$ or $$2$$ in the line above.

1. Also,

model += sum(vars[i, j] for i in nums for j in nums) * sum(r[i,j] for i in numsC for j in numsL

is not correct, you are performing the sum separately and then multiplied them together. Try the following list comprehension.

sum(vars[i, j] * r[i,j] for i in nums for j in nums)

Edit:

I have fixed your code, I will leave the final formatting to you:

from pulp import *
N = 8
nums = list(range(1, N+1)) #list from 1 to N",
numsC = list(range(1, N+1)) #list from 1 to N",
numsL = list(range(1, N+1)) #list from 1 to N",

vars = {}
r = {}

model = LpProblem('Damas', LpMaximize)

# Decison Variables
for i in nums:
for j in nums: # create a binary variable
vars[i, j] = LpVariable('x{},{}'.format(i, j), cat='Binary')

for i in numsC:
for j in numsL:
k = N - i - j
if k % 2 == 0:
r[i,j] = 2
else:
r[i,j] = 1

# Objective function
model += sum(vars[i, j] * r[i,j] for i in nums for j in nums)

# Restrições
# 1 queen per row
for i in nums:
model += sum(vars[i, j] for j in nums) <= 1
# 1 queen per column
for j in nums:
model += sum(vars[i, j] for i in nums) <= 1
# 1 queen per diagonal 1
for k in range(2, 2*N+1):
model += sum(vars[i, j] for i in nums for j in nums if i+j == k) <= 1
# 1 queen per diagonal 2
for k in range(-(N-2),(N-2)+1):
model += sum(vars[i, j] for i in nums for j in nums if i-j == k) <= 1

model.solve()
for variable in model.variables():
print("{} = {}".format(variable.name, variable.varValue))
• I tried that but I'm having the same error. It seems like the objective function does not accept a conditional decision variable. May 14 '20 at 22:13
• I tried, it works. May 15 '20 at 1:48
• That's great! It worked. Tks May 15 '20 at 3:11