Here is an example of code that generates an lpsolve-formatted IP.
This is code for the Knights' Domination Problem: what is the minimum number of knights that need to be placed on an nxn chessboard such that every square is attacked?
This is the code used to generate this sequence at the OEIS.
(A more popular version of this problem has every square occupied or attacked, so this is a different problem.)
The idea is to define a binary variable x_a_b for each square on the board which indicates whether or not a knight is placed there: x_a_b=1 if there is a knight there, and x_a_b=0 if no knight is there.
Then, we wish to minimize the sum x_0_0+x_0_1+...+x_n_n subject to constraints that enforce the requirement that each square is attacked.
There is exactly one constraint for each square.
For example, for the upper left square, we have the constraint x_1_2+x_2_1 >= 1 since the (0,0) square can only be attacked from the (1,2) and (2,1) squares. Since the variables are binary, the constraint is satisfied if and only if x_1_2 or x_2_1 is equal to 1 (i.e., a knight occupied square (1,2) or (2,1)).
The code below is written in Python 3.
#
# Matthew M. Conroy, 2021
# University of Washington
# conroy@math.washington.edu
#
# Knight's domination problem lpsolve IP input file generator
#
# see http://oeis.org/A261752 for more info
#
import math
# define a function to check is a position is actually on the board
def isonboard(x,y,n):
if (x>=0 and y>=0 and x<n and y<n):
return(1)
else:
return(0)
## define the moves a knight can make
knightMoves=[[1,2],[1,-2],[-1,2],[-1,-2],[2,1],[2,-1],[-2,1],[-2,-1]]
# board size is nxn
n=4
##### generate lpsolve input file
# objective function
fullString = ""
for a in range(n):
for b in range(n):
fullString += "+x_"+str(a)+"_"+str(b)
print("min: "+fullString+";")
## constraint: each location must be attacked
# for each location (a,b) on the board, find all
# possible attacking posittions and add their
# corresponding x variable to the sum
for a in range(n):
for b in range(n):
constraintString=""
for move in knightMoves:
x = a+move[0]
y = b+move[1]
if (isonboard(x,y,n)):
constraintString+= "+x_"+str(x)+"_"+str(y)
print(constraintString +">=1;")
# declare all variables as binary
binString = "bin "
for a in range(n):
for b in range(n):
if (a>0 or b>0):
binString += ","
binString += "x_"+str(a)+"_"+str(b)
print(binString+";")
Output can then be directed to a file, and then lpsolve can be run on it to find the solution.
Here is the output with boardsize n=4:
min:+x_0_0+x_0_1+x_0_2+x_0_3+x_1_0+x_1_1+x_1_2+x_1_3+x_2_0+x_2_1+x_2_2+x_2_3+x_3_0+x_3_1+x_3_2+x_3_3;
+x_2_1+x_1_2>=1;
+x_3_1+x_2_2+x_0_2>=1;
+x_3_2+x_0_1+x_1_2>=1;
+x_1_1+x_2_2>=1;
+x_2_2+x_2_0+x_1_3>=1;
+x_3_2+x_3_0+x_2_3+x_0_3>=1;
+x_3_3+x_0_2+x_0_0+x_1_3>=1;
+x_1_2+x_1_0+x_2_3>=1;
+x_2_3+x_2_1+x_1_0>=1;
+x_3_3+x_3_1+x_2_0+x_0_0>=1;
+x_3_0+x_0_3+x_0_1+x_1_0>=1;
+x_1_3+x_1_1+x_2_0>=1;
+x_2_2+x_1_1>=1;
+x_3_2+x_2_1+x_0_1>=1;
+x_3_1+x_0_2+x_1_1>=1;
+x_1_2+x_2_1>=1;
bin x_0_0,x_0_1,x_0_2,x_0_3,x_1_0,x_1_1,x_1_2,x_1_3,x_2_0,x_2_1,x_2_2,x_2_3,x_3_0,x_3_1,x_3_2,x_3_3;
We could save this output to a file, say, gub.txt.
Then lpsolve can be run on it at the command line:
>lpsolve -ia gub.txt
The -ia flag suppresses zero variables, and tells lpsolve to print out intermediate, possibly suboptimal solutions. This is useful when the computation take a long time.
If you are using the IDE, you can read in gub.txt and run it. Set the Print Sol option to Automatic to have the same effect as the -ia flag.
The resulting output is this:
Value of objective function: 6.00000000
Actual values of the variables:
x_0_0 1
x_0_1 1
x_1_1 1
x_2_1 1
x_2_2 1
x_2_3 1
All other variables are zero.
This indicates that a minimum of 6 knights are needed for the 4x4 board, and the output shows where those knights should be located on the board.