5
$\begingroup$

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
$\endgroup$
  • $\begingroup$ You are multiplying variables vars and r in your objective function, which is not linear. PuLP only deals with linear expressions. $\endgroup$ – Kuifje May 13 at 8:02
5
$\begingroup$

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))
| improve this answer | |
$\endgroup$
  • $\begingroup$ I tried that but I'm having the same error. It seems like the objective function does not accept a conditional decision variable. $\endgroup$ – fsimoyama May 14 at 22:13
  • $\begingroup$ I tried, it works. $\endgroup$ – Siong Thye Goh May 15 at 1:48
  • $\begingroup$ That's great! It worked. Tks $\endgroup$ – fsimoyama May 15 at 3:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.