Cited from the PuLP documentation as in previous link. This problem is to produce a cat food composed of two proteins chicken or beef with certain constraints.
I will jump to Sudoku problem as the framework is same and it’s more fun to solve. First, what is Sudoku problem, according to wiki, there is an incomplete 9×9 table of numbers which must be filled according to several rules:
• Within any of the 9 individual 3×3 boxes, each of the numbers 1 to 9 must be found
• Within any column of the 9×9 grid, each of the numbers 1 to 9 must be found
• Within any row of the 9×9 grid, each of the numbers 1 to 9 must be found
For LP problem the steps to Identify the Decision Variables, Formulate the Objective Function and Formulate the Constraints are most critical, after which, the solution is straightforward.
What variable to create for each of the 81 squares? there is no “not equal to” operator, so we can only apply values in a row/box/column equal 45. So it’s clever the author of this Sudoku solution figured 729 variables, so if Choice_4_2_9 was 1, it would mean the number 4 was present in the square situated in row 2, column 9. (If it was 0, it would mean there was not a 4 there. And as to the objective function, whilst either LpMinimize or LpMaximize must be entered, it is not important which. Similarly, the objective function can be anything, so in this example it is simply zero.
choices = LpVariable.dicts(“Choice”,(Vals,Rows,Cols),0,1,LpInteger)
We see the structure of 729 variables:
choices[‘1’][‘1’]
{‘1’: Choice_1_1_1, ‘2’: Choice_1_1_2, ‘3’: Choice_1_1_3, ‘4’: Choice_1_1_4, ‘5’: Choice_1_1_5, ‘6’: Choice_1_1_6, ‘7’: Choice_1_1_7, ‘8’: Choice_1_1_8, ‘9’: Choice_1_1_9}
The codes are
# A list of strings from '1' to '9' is created
Sequence = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
# The Vals, Rows and Cols sequences all follow this form
Vals = Sequence
Rows = Sequence
Cols = Sequence
# The boxes list is created, with the row and column index of each square in each box
Boxes = []
for i in range(3):
for j in range(3):
Boxes += [[(Rows[3*i+k],Cols[3*j+l]) for k in range(3) for l in range(3)]]
# The prob variable is created to contain the problem data
prob = LpProblem('Sudoku Problem',LpMinimize)
# The problem variables are created
choices = LpVariable.dicts('Choice',(Vals,Rows,Cols),0,1,LpInteger)
# As explained above, the objective function (what we try to change using the problem variables) is simply zero (constant) since we are only concerned with any variable combination that can satisfy the constraints.
# The arbitrary objective function is added
prob += 0, 'Arbitrary Objective Function'
# A constraint ensuring that only one value can be in each square is created
for r in Rows:
for c in Cols:
prob += lpSum([choices[v][r][c] for v in Vals]) == 1, ''
# These constraints ensure that each number (value) can only occur once in each row, column and box.
# The row, column and box constraints are added for each value
for v in Vals:
for r in Rows:
prob += lpSum([choices[v][r][c] for c in Cols]) == 1,''
for c in Cols:
prob += lpSum([choices[v][r][c] for r in Rows]) == 1,''
for b in Boxes:
prob += lpSum([choices[v][r][c] for (r,c) in b]) == 1,''
# The starting numbers are entered as constraints i.e a “5” in row “1” column “1” is true.
# The starting numbers are entered as constraints
prob += choices['5']['1']['1'] == 1,''
prob += choices['6']['2']['1'] == 1,''
prob += choices['8']['4']['1'] == 1,''
prob += choices['4']['5']['1'] == 1,''
prob += choices['7']['6']['1'] == 1,''
prob += choices['3']['1']['2'] == 1,''
prob += choices['9']['3']['2'] == 1,''
prob += choices['6']['7']['2'] == 1,''
prob += choices['8']['3']['3'] == 1,''
prob += choices['1']['2']['4'] == 1,''
prob += choices['8']['5']['4'] == 1,''
prob += choices['4']['8']['4'] == 1,''
prob += choices['7']['1']['5'] == 1,''
prob += choices['9']['2']['5'] == 1,''
prob += choices['6']['4']['5'] == 1,''
prob += choices['2']['6']['5'] == 1,''
prob += choices['1']['8']['5'] == 1,''
prob += choices['8']['9']['5'] == 1,''
prob += choices['5']['2']['6'] == 1,''
prob += choices['3']['5']['6'] == 1,''
prob += choices['9']['8']['6'] == 1,''
prob += choices['2']['7']['7'] == 1,''
prob += choices['6']['3']['8'] == 1,''
prob += choices['8']['7']['8'] == 1,''
prob += choices['7']['9']['8'] == 1,''
prob += choices['3']['4']['9'] == 1,''
prob += choices['1']['5']['9'] == 1,''
prob += choices['6']['6']['9'] == 1,''
prob += choices['5']['8']['9'] == 1,''
# The problem is written to an LP file, solved using CPLEX (due to CPLEX’s simple output) and the solution status is printed to the screen
# The problem data is written to an .lp file
prob.writeLP('Sudoku.lp')
# The problem is solved using PuLP’s choice of Solver
prob.solve()
# The status of the solution is printed to the screen
print('Status:', LpStatus[prob.status])
The key here is the cleverness in constructing 729 variables.
Naixian Zhang 