Iain Dunning

Contact: iaindunning at gmail, @iaindunning, github/IainNZ

› JuMP + Julia - Combination Lock Puzzle

First posted: Sep 21, 2013

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 optimization embedded 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:

$$ P = \begin{bmatrix} 39 & 06 & 75 & 88 & 15 & 57 \\ 9 & 2 & 58 & 68 & 48 & 64 \\ \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\ 44 & 63 & 10 & 83 & 46 & 03 \end{bmatrix} $$

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:

$$ \begin{alignat*}{1} \max \quad & 0\\ \text{subject to} \quad & \sum_{ij}D_{ij}x_{ij}=419\\ & \sum_{j=1}^6 x_{ij} = 1 \qquad \forall i \in \{1,\dots,6\}\\ & x_{ij}\in\left\{ 0,1\right\} \end{alignat*} $$

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?


© Iain Dunning, 2015. Base theme/CSS by Skeleton.