The PuzzlOR is a website connected to INFORMS that publishes operations research-related problems bimonthly. In a series of posts I'm going to solve some of the problems to demonstrate JuMP, an algebraic modeling language for/in Julia.

## Combination Locks (August 2012)

(Link to full problem statement)

Our goal is to determine 6 numbers, where each of the 6 numbers has 6 possibilities and the sum of the numbers is 419. Lets first describe the possibilities (pulled from the image) as a matrix P:

We will model the problem as a integer program with variables \( x_{ij} \) that equal 1 if and only if for lock (row) *i* we select the number (column) *j*. Our model is thus the following feasibility problem:

where the first constraint enforces the sum of the numbers equals 419, and the second constraint ensures we pick a number for each lock. We can solve this problem with the following code:

```
# Assuming a solver has been previously installed, e.g. Cbc
using JuMP
function SolveCombination(P)
m = Model()
# Variable x: 1 iff select number j for lock i
@defVar(m, 0 <= x[i=1:6, j=1:6] <= 1, Int)
# Constraint 1: Sum of numbers is equal to 419
@addConstraint(m, sum{P[i,j]*x[i,j], i=1:6, j=1:6} == 419)
# Constraint 2: Must pick a number from each lock
for i in 1:6
@addConstraint(m, sum{x[i,j], j=1:6} == 1)
end
# Solve with default solver (CBC)
status = solve(m)
if status == :Infeasible
println("Couldn't find the numbers!")
else
println("Found the numbers:")
for i in 1:6
for j in 1:6
if getValue(x[i,j]) >= 0.99
println("Lock $i is $(P[i,j])")
break
end
end
end
end
end
P = [39 06 75 88 15 57;
9 2 58 68 48 64;
29 55 16 67 8 91;
40 54 66 22 32 25;
49 1 17 41 14 30;
44 63 10 83 46 3]
SolveCombination(P)
```

An extension question: what happens if relax constraint 2? How many locks would we need to make the sum 419 if we didn't need to set all 6 locks?