Modelling P(x) when P is a unknown permutation and x an integer variable

 0 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 11●2 accept rate: 0% Rob Pratt 1.2k●2●6

 1 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 answered 30 Jan '16, 11:23 AlexFleischer 86●3 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 ♦♦
 0 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 Pratt 1.2k●2●6 accept rate: 28% @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
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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: