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

Alain
112
accept rate: 0%

retagged 31 Jan '16, 13:51

Rob%20Pratt's gravatar image

Rob Pratt
1.2k26


Hi,

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

https://www.ibm.com/developerworks/community/forums/html/topic?id=84ac39db-dcaf-4661-aebd-eeeb89cb4b62&ps=25

and you will see

x[i-1+start["Vertical"][g][b]][g]==1;

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!

regards

link

answered 30 Jan '16, 11:23

AlexFleischer's gravatar image

AlexFleischer
863
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

http://www-01.ibm.com/software/websphere/products/optimization/cplex-studio-community-edition/

or free academic initiative if you are allowed to.

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

regards

(30 Jan '16, 12:34) AlexFleischer
1

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.

link

answered 31 Jan '16, 10:42

Rob%20Pratt's gravatar image

Rob Pratt
1.2k26
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

By RSS:

Answers

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

Tags:

×65
×56
×6

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.