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_i_j for each square on the board which indicates whether or not a knight is placed 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 Perl.
#!/usr/local/bin/perl
#
# Matthew Conroy 2015
# conroy (at) math.washington.edu
#
# A perl script to generate
# an lpsolve-format IP (integer program) to determine
# the minimum number of knights needed to attack
# every square on a chess board.
#
# Note: this is to attack every square! not "attack or occupy every square" !
#
# $start = (times)[0]; ### get start time
$boardSizeX=4;
$boardSizeY=4;
## print out objective function
print "min:";
for ($j=0; $j<$boardSizeY; $j++) {
for($i=0; $i<$boardSizeX; $i++) {
print "+x_",$j,"_",$i;
}
}
print ";\n";
## generate a constraint for each square on the board that
## ensures that the square is attacked
for($j=0; $j<$boardSizeY; $j++) {
for($i=0; $i<$boardSizeX; $i++) {
## find all the locations from which (i,j) could be attacked;
## add each one to the constraint for (i,j): (i,j) must be attacked!
for($k=0; $k<8; ++$k) { # eight possible square could attack (i,j)
$xChangeAbs=2-(int($k/2) % 2);
if ($k<4) { $xDelta=$xChangeAbs; }
else {$xDelta = -$xChangeAbs; }
$yChangeAbs=3-$xChangeAbs;
if (($k % 2)==0) { $yDelta = $yChangeAbs; }
else { $yDelta = -$yChangeAbs; }
$targetX=$i+$xDelta;
$targetY=$j+$yDelta;
if (($targetX>=0) && ($targetX<$boardSizeX) && ($targetY>=0) && ($targetY<$boardSizeY)) {
## target is an actual square on the board, so add this location to the constraint
print "+x_",$targetX,"_",$targetY;
}
}
## finish the constraint
print ">=1;\n";
}
}
## specify that all variables are binary
print "bin ";
for($j=0; $j<$boardSizeY; $j++) {
for($i=0; $i<$boardSizeX; $i++) {
if ($i+$j>0) { print ","; } ## prepend a comma after the first variable
print "x_",$j,"_",$i;
}
}
print ";\n";
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 $boardSizeX=4 and $boardSizeY=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 gub.txt
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_0_2 0
x_0_3 0
x_1_0 0
x_1_1 1
x_1_2 1
x_1_3 0
x_2_0 0
x_2_1 0
x_2_2 1
x_2_3 1
x_3_0 0
x_3_1 0
x_3_2 0
x_3_3 0
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.