Here is an another example of code that generates an lpsolve-formatted IP.
Here we wish to solve the problem of finding a pair of dice (i.e., finding what their face values should be) such that when thrown, the sum of the two dice is always a prime number.
Here is the Python (2) code.
#
# Matthew M. Conroy 2018
#
# This code outputs an lpsolve-formatted LP which
# determines the faces of a pair of dice that yields
# only prime sums.
#
# The faces are all distinct (i.e., no face value is repeated).
#
# this function determines if arg1 is prime (this is not
# a cleverly written method, but arg1 is very small, so it is fine)
def isprime(arg1): # we assume arg1 is a positive integer
prime=1;
for i in range(2,arg1-1):
if ((arg1 % i)==0):
prime=0
return(prime);
sides = 3; # set the number of sides the dice will have
n = 12; # this is the upper bound for the face values;
# The large n is set, the slower the calculation, so it should
# be determined experimentally, starting small and increasing
# until solutions are found
# print the objective function
# Here the objective is to minimize the sum of all die faces
# so that the solution is in some sense "small".
outstring="min: ";
# a variables for the even faces
for i in range(2,n,2):
outstring = outstring+"+"+str(i)+"*a_"+str(i)
# b variables for the odd faces
for i in range(1,n,2):
outstring = outstring+"+"+str(i)+"*b_"+str(i)
print outstring+";"
# set the number of sides
# Here we use the fact that one die must have all even sides and the other must have all odd sides,
# since otherwise the sums would not (always) be prime.
outstring = "a_2"
for i in range(4,n,2):
outstring = outstring +"+a_"+str(i)
outstring = outstring+"="+str(sides)+";"
print outstring
outstring = "b_1"
for i in range(3,n,2):
outstring = outstring +"+b_"+str(i)
outstring = outstring+"="+str(sides)+";"
print outstring
# avoid composite sums
# We add a constraint for every pair of face values that would sum to a non-prime,
# forcing the avoidance of these pairs
outstring=""
for i in range(2,n,2):
for j in range(1,n,2):
if (not(isprime(i+j))):
outstring="a_"+str(i)+"+b_"+str(j)+"<=1;"
print outstring
# define variables to be bianary
outstring="bin "
for i in range(2,n,2):
if (i==2):
outstring = outstring +"a_"+str(i)
else:
outstring = outstring+",a_"+str(i)
for i in range(1,n,2):
outstring = outstring +",b_"+str(i)
outstring = outstring+";"
print outstring
Suppose our two dice as "A" and "B".
The idea here is to introduce two sets of binary variables, ai and bi,
with a
We suppose that the maximum face will be less than n.
If we say the dice will have m sides, then we require a1+a2+...+an=m and b1+b2+...+bn=m.
Since we want only prime sums, we need to exclude the possibility that a face from A and a face from B could add to a non-prime. This achieved with a set of constraints in the form ai+bj ≤ 1 for all pairs (i,j) such that i+j is not prime, with i<n and j<n.
For large n and m, this will be a large number of constraints.
Finally, we need an objective function, so we choose to minimize the sum of all face values, so that the values are in a certain sense "small".
Running the code above (to find dice with three sides, and maximum face less than 12), we get this output:
min: +2*a_2+4*a_4+6*a_6+8*a_8+10*a_10+1*b_1+3*b_3+5*b_5+7*b_7+9*b_9+11*b_11;
a_2+a_4+a_6+a_8+a_10=3;
b_1+b_3+b_5+b_7+b_9+b_11=3;
a_2+b_7<=1;
a_4+b_5<=1;
a_4+b_11<=1;
a_6+b_3<=1;
a_6+b_9<=1;
a_8+b_1<=1;
a_8+b_7<=1;
a_10+b_5<=1;
a_10+b_11<=1;
bin a_2,a_4,a_6,a_8,a_10,b_1,b_3,b_5,b_7,b_9,b_11;
Saving this to a file, say, dice.lps, we can run lp_solve with the command (the -ia flag suppressed output of zero variables, making things easier to read)
lp_solve -ia dice.lps
and get the output
Value of objective function: 29.00000000
Actual values of the variables:
a_2 1
a_4 1
a_10 1
b_1 1
b_3 1
b_9 1
which shows that our dice should have sides {2,4,10} and {1,3,9}. You can quickly check that any value in the first set added to any value in the second set yields a prime number.