INDR $220$: Introduction to Computing for Operations Research

Homework $5$: The Non$-$attacking Knights Problem

Deadline: May $27,2024,11$:$59$ PM

In this homework, you will implement a Python script that solves the non$-$attacking knights

problem using CPLEX. The task is to find the maximum number of knights that can be placed

on an $MN$ chessboard such that no knight attack some other knight. The decision variables

can be formulated as

$x_{ij}=\{\begin{array}{ccc}1& if\text{a}\text{k}\text{n}\text{i}\text{g}\text{h}\text{t}is\text{p}\text{l}\text{a}\text{c}\text{e}\text{d}at\text{l}\text{o}\text{c}\text{a}\text{t}\text{i}\text{o}\text{n}(i,& j),\\ 0& \text{o}\text{t}\text{h}\text{e}\text{r}\text{w}\text{i}\text{s}\text{e}\text{.}& \end{array}$

The integer linear programming formulation of this problem becomes

maximize $z={\displaystyle \underset{i=1}{\overset{N}{}}}{\displaystyle \underset{j=1}{\overset{M}{}}}{x}_{ij}$

subject $to$: $x_{ij}+x_{kl}1,AA(i,j,k,l)$ where $(i,j)$ and $(k,l)$ are attacking locations

$x_{ij}in\{0,1\},i=1,2,$dots,$M$;$j=1,2,$dots,$N.$

An example of the non$-$attacking knights problem with a $26$ chessboard can be given as

maximize $z=x_{11}+x_{12}+x_{13}+x_{14}+x_{15}+x_{16}+x_{21}+x_{22}+x_{23}+x_{24}+x_{25}+x_{26}$

subject $to$: $x_{11}+x_{23}1$

$x_{12}+x_{24}1$

$x_{13}+x_{25}1$

$x_{13}+x_{21}1$

$x_{14}+x_{26}1$

$x_{14}+x_{22}1$

$x_{15}+x_{23}1$

$x_{16}+x_{24}1$

$x_{11}in\{0,1\},x_{12}in\{0,1\},x_{13}in\{0,1\},x_{14}in\{0,1\},x_{15}in\{0,1\},x_{16}in\{0,1\}$

$x_{21}in\{0,1\},x_{22}in\{0,1\},x_{23}in\{0,1\},x_{24}in\{0,1\},x_{25}in\{0,1\},x_{26}in\{0,1\}.$

An optimum solution of the example problem with a $26$ chessboard is as follows:

$x_{11}^{***}=1,x_{12}^{***}=1,x_{13}^{***}=0,x_{14}^{***}=0,x_{15}^{***}=1,x_{16}^{***}=1$

$x_{21}^{***}=1,x_{22}^{***}=1,x_{23}^{***}=0,x_{24}^{***}=0,x_{25}^{***}=1,x_{26}^{***}=1$

An example of the non$-$attacking knights problem with a $33$ chessboard can be given as

$mamizez=x_{11}+x_{12}+x_{13}+x_{21}+x_{22}+x_{23}+x_{31}+x_{32}+x_{33}$

subject $to$: $x_{11}+x_{32}1x_{11}+x_{23}1$

$x_{12}+x_{33}1$

$x_{12}+x_{31}1$

$x_{13}+x_{32}1$

$x_{13}+x_{21}1$

$x_{21}+x_{33}1$

$x_{23}+x_{31}1$

$x_{11}in\{0,1\},x_{12}in\{0,1\},x_{13}in\{0,1\}$

$x_{21}in\{0,1\},x_{22}in\{0,1\},x_{23}in\{0,1\}$

$x_{31}in\{0,1\},x_{32}in\{0,1\},x_{33}in\{0,1\}.$

An optimum solution of the example problem with a $33$ chessboard is as follows:

$x_{11}^{***}=0,x_{12}^{***}=1,x_{13}^{***}=0$

$x_{21}^{***}=1,x_{22}^{***}=1,x_{23}^{***}=1$

$x_{31}^{***}=0,x_{32}^{***}=1,x_{33}^{***}=0$

Implement your algorithm to solve the non$-$attacking knights problem in a single interactive

Python notebook using Azure Lab Services. Your notebook should include at least the following

function definition that takes the number of rows and columns as parameters and returns the

solution found.

What to submit: You are provided with a template file named as $0099999$ hw$05.$ipynb,

where $99999$ should be replaced with your $5-$digit student number. You are allowed to change

the template file between the following lines.

# your implementation starts below

# your implementation ends above

You need to submit your source code in a single file $(0099999hw05.$py file that you will

download from Azure Lab Services by following "File" $/$ "Save and Export Notebook As$..."/$

"Executable Script" menu items$).$

How to submit: Submit the file you edited to Blackboard by following the exact style

mentioned. Submissions that do not follow these guidelines will not be graded.

Late submission policy: Late submissions will not be graded.

Cheating policy: Very similar submissions will not be graded.