Hi OR Experts,

I am trying to solve this problem with MILP after having tried heuristic methods with no success. (It is a cryptography challenge)
Let E = {1,2,...25,26} be the set of positive integers <= 26. (the set of the 26 letters of the standard alphabet)
Let P and P' be two unknown permutations of E.
The (simplified) problem I have to solve is:

Find P , P' and variables Mk ϵ E subject to:

Ck = P(Ak) + P'(Mk) (mod 26) where Ck ϵ E and Ak ϵ E are known constants, for k = 1 to 49

The Mk are subject to 36 extra linear constraints.
I have represented P and P' the usual way, with 26x26=676 binary variables for each permutation, summing to 1 for each row and each column: x(i,j) and x'(i,j)
Each Mk is also represented by 26 binary variables m(k,i) summing to 1 over i for all k.
The difficulty I face is to represent P'(Mk).
Obviously P'(i) = sum( j * x'(i,j) ) over j.
Hence P'(Mk) = sum( m(k,i)*P'(i) ) over i, but this turns the model into a quadratic one.
Adding extra variables and constraints for linearizing the products m(k,i)*x'(i,j) makes the model gigantic...
I'm using lp-solve for the moment. There is no objective function, as any feasible solution will be *the* solution.

More generally, the question is: Is there a simple way/trick to index an array of variables by a variable, in a linear way ?

Any advice is greatly appreciated.

Note: the (mod 26) is not an issue, as Ck = P(Ak) + P'(Mk) (mod 26) can be transformed into
Ck = P(Ak) + P'(Mk) -26*Ek with Ek = binary

asked 30 Jan '16, 10:11

Alain's gravatar image

accept rate: 0%

retagged 31 Jan '16, 13:51

Rob%20Pratt's gravatar image

Rob Pratt


My suggestion is to have a look at Constraint Programming which is available within CPLEX. I posted an example of a GCHQ puzzle at


and you will see


where x and start are decision variables.

So a yes there is a trivial way to your question:

Is there a simple way/trick to index an array of variables by a variable, in a linear way ?

but not in a linear way!



answered 30 Jan '16, 11:23

AlexFleischer's gravatar image

accept rate: 10%

thank you . However, CPLEX is not affordable for a simple enthusiast ... lp-solve and CBC do not have this feature. I don't know of any free CP software

(30 Jan '16, 12:00) Alain

If your problem is not too big you may use the free community edition


or free academic initiative if you are allowed to.

You may also try pay as you go in the cloud.


(30 Jan '16, 12:34) AlexFleischer

I concur with Alex about using CP (and with using CPOptimizer if possible). If CPOptimizer is not an option, there are a number of free constraint solvers. You might want to have a look a MiniZinc, which combines an IDE, modeling language and a few free solvers (plus links to others, I think).

(31 Jan '16, 16:35) Paul Rubin ♦♦

Instead of linearizing m(k,i) * x'(i,j), you might try linearizing m(k,i) * P'(i), which is a product of binary and bounded integer variables. Explicitly, introduce bounded integer variable z(k,i) for that product, use linear constraints -26 (1 - m(k,i)) <= z(k,i) - P'(i) <= 26 (1 - m(k,i)) to enforce the rule that m(k,i) = 1 implies z(k,i) = P'(i), and use linear constraints 0 <= z(k,i) <= 26 m(k,i) to enforce the rule that m(k,i) = 0 implies z(k,i) = 0.


answered 31 Jan '16, 10:42

Rob%20Pratt's gravatar image

Rob Pratt
accept rate: 28%

edited 31 Jan '16, 13:29

@Rob Pratt: thank you for your time.
I have indeed added 26 variables P'(i), unbounded and continuous, s.t. P'(i) = sum( j * x'(i,j) ) over j.
The upper bound of P'(i) being 26, I replace the products m(k,i)*P'(i) by z(k,i) (continuous and unbounded) but with 3 additional constraints:
26*m(k,i) - z(k,i) >= 0
P'(i) - z(k,i) >= 0
26*m(k,i) + P'(i) - z(k,i) <= 26
They enforce: m(k,i) = 0 => z(k,i) = 0 and m(k,i) = 1 => z(k,i) = P'(i)
I don't clearly see how the 2 constraints you mention imply z(k,i) = 0 when m(k,i) = 0

(31 Jan '16, 11:23) Alain

Sorry, I had omitted some constraints, and I have now edited my answer to include them.

Your second constraint is indeed a valid tightening of my z(k,i) - P'(i) <= 26 (1 - m(k,i)).

But it seems that you also need z(k,i) >= 0.

By the way, you might see better performance by declaring the P, P', and z variables to be (doubly-bounded) integers. Although they will automatically be integer-valued when x, x', and M are, explicitly declaring them to be integer variables allows the solver more latitude in branching.

(31 Jan '16, 13:37) Rob Pratt
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported



Asked: 30 Jan '16, 10:11

Seen: 625 times

Last updated: 31 Jan '16, 16:35

OR-Exchange! Your site for questions, answers, and announcements about operations research.