Questions Tagged With permutationhttp://www.or-exchange.com/tags/permutation/?type=rssquestions tagged <span class="tag">permutation</span>enSat, 30 Jan 2016 10:11:58 -0500Modelling P(x) when P is a unknown permutation and x an integer variablehttp://www.or-exchange.com/questions/13292/modelling-px-when-p-is-a-unknown-permutation-and-x-an-integer-variable<p>Hi OR Experts,</p>
<p>I am trying to solve this problem with MILP after having tried heuristic methods with no success.
(It is a cryptography challenge)<br>
Let E = {1,2,...25,26} be the set of positive integers <= 26. (the set of the 26 letters of the standard alphabet) <br>
Let P and P' be two unknown permutations of E.<br>
The (simplified) problem I have to solve is:<br>
</p>
<p>Find P , P' and variables Mk ϵ E subject to:<br>
</p>
<p>Ck = P(Ak) + P'(Mk) (mod 26) where Ck ϵ E and Ak ϵ E are known constants, for k = 1 to 49<br>
</p>
<p>The Mk are subject to 36 extra linear constraints.<br>
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) <br>
Each Mk is also represented by 26 binary variables m(k,i) summing to 1 over i for all k.<br>
The difficulty I face is to <strong>represent P'(Mk</strong>).<br>
Obviously P'(i) = sum( j * x'(i,j) ) over j.<br>
Hence P'(Mk) = sum( m(k,i)*P'(i) ) over i, but this turns the model into a quadratic one.<br>
Adding extra variables and constraints for linearizing the products m(k,i)*x'(i,j) makes the model gigantic...<br>
I'm using lp-solve for the moment.
There is no objective function, as any feasible solution will be *the* solution.</p>
<p>More generally, the question is: <strong>Is there a simple way/trick to index an array of variables by a variable, in a linear way ?</strong><br>
</p>
<p>Any advice is greatly appreciated.</p>
<p>Note: the (mod 26) is not an issue, as Ck = P(Ak) + P'(Mk) (mod 26) can be transformed into <br>
Ck = P(Ak) + P'(Mk) -26*Ek with Ek = binary</p>AlainSat, 30 Jan 2016 10:11:58 -0500http://www.or-exchange.com/questions/13292/modelling-px-when-p-is-a-unknown-permutation-and-x-an-integer-variablelinearizationmixed-integer-programmingpermutationHow to model permutations in an integer program?http://www.or-exchange.com/questions/10850/how-to-model-permutations-in-an-integer-program<p>The problem that I am trying to solve is to find a permutation of <code>{1..n}</code> which minimizes a certain cost function.</p>
<p><strong>How can I tell an MILP solver that I want to optimize over all possible permutations?</strong></p>
<p><strong>IMPORTANT:</strong> This question is meant to be a generic question; I do not want to assume anything about the rest of the MILP (the cost function and / or the other constraints).</p>
<hr>
<p>I have already found the <code>alldifferent</code> constraint (which only seems to work with constraint programming solvers unfortunately), and it's formulation with binary variables as: (AMPL code snippet)</p>
<pre><code>param n;
var y{1..n, 1..n} binary;
var P{i in 1..n} = sum {k in 1..n} y[i,k]*k; # <-- Permutation vector P
row{i in 1..n}:
sum{j in 1..n} y[i,j] = 1;
col{j in 1..n}:
sum{i in 1..n} y[i,j] = 1;
</code></pre>
<p>Some tweaks of this formulation were suggested at my previous question (posted 2 years ago):</p>
<p><a href="https://www.or-exchange.org/questions/6262">integer programming formulation of the alldifferent constraint</a></p>
<p><strong>Did I miss anything major or are these my best options?</strong></p>AliFri, 12 Dec 2014 10:02:44 -0500http://www.or-exchange.com/questions/10850/how-to-model-permutations-in-an-integer-programinteger-programmingmathematical-modelingpermutationHow can I avoid indexing into an array with a discrete variable?http://www.or-exchange.com/questions/10842/how-can-i-avoid-indexing-into-an-array-with-a-discrete-variable<p>The problem that I am trying to solve is to find a permutation of <code>1..n</code> which minimizes a certain cost. The cost function involves indexing into a parameter array with the permutated numbers as indices. Here is a <em>similar</em> example in IBM ILOG OPL:</p>
<pre><code>using CP;
int n = 10;
int A[i in 1..n] = n-i+1; // just for the sake of this example
dvar int P[1..n] in 1..n; // permutation vector
minimize sum (i in 1..n) i*A[P[i]]; // <-- indexing into an array with a variable
subject to {
allDifferent( P );
}
</code></pre>
<p>The actual problem at hand is more complicated; <strong>the above code snippet is just for illustration</strong> as it admits an analytic solution. Nevertheless, it shows what I mean by indexing into an array with a variable.</p>
<p><strong>How can I rewrite the problem so that I do not have to index into an array with a discrete variable?</strong> What are the best practices?</p>
<hr>
<p><strong>UPDATE:</strong> The above example was too simple apparently. That's the problem with the examples: If they are too simple, they are misleading; if they are too complicated, they are not helpful anymore. In the above example, it is fairly easy to get rid of the indices that are variables. However, if the <code>A</code> array is a 2D array and we do <code>A[P[i]][P[j]]</code>, the objective becomes quadratic after the straightforward way of rewriting the problem. Is it really the best we can do?</p>AliFri, 12 Dec 2014 08:25:09 -0500http://www.or-exchange.com/questions/10842/how-can-i-avoid-indexing-into-an-array-with-a-discrete-variableinteger-programmingcombinatorial-optimizationmathematical-modelingpermutationCalculate number of combinations/permutations for job assignment to machineshttp://www.or-exchange.com/questions/9278/calculate-number-of-combinationspermutations-for-job-assignment-to-machines<p>This might looks like a job-shop scheduling problem, but not 100% is. I'm just trying to map my problem to job-shop problem, and am starting with calculating the number of permutations required for each job being assigned to each machine.</p>
<p>There are 12 machines (M). Each machine can execute for 20 slot (S) of time per session.
We have 8 jobs (J) to be done. Each job requires 2 continuous slots (T). There is a fixed timeframe between the start-time slot (ST) to a deadline that the job must be completed. In this case, each job must be scheduled to start and finish between a 10 slots (D) timeframe. It is assumed that the given timeframe is (i) always larger that the duration of each job (i.e D >= T), (ii) always smaller than maximum time per session per machine (i.e. S). In this case, ST + D <= S.</p>
<p>Lets M = 12, S=20, J=8, T=2, D=10.
What is the number of combinations for the job assignment?</p>
<p>My idea is, since D is fixed, S is not important. So, we would select machine, then select slot from the machine, then select job to be assigned</p>
<pre><code>(12 x 10C2 x 8) + (12 x 10C2 x 7) + (12 x 10C2 x 6) + ... + (11 x 10C2 x 1)
</code></pre>
<p>But I feel it is incorrect.
In (12 x 10C2 x 8): select 1 from the 12 machines, select 2 slots from the 10 slots timeframe, select 1 out of 8 jobs.</p>
<p>In (12 x 10C2 x 7): this formulation seems to be wrong, as there are 11 machines which have 10 free slots + 1 machines which has 8 free slots, how can I incorporate this into the formulations?</p>
<p>Another question is, how can I calculate the number of permutations for this job assignment?</p>twfxWed, 19 Feb 2014 11:26:29 -0500http://www.or-exchange.com/questions/9278/calculate-number-of-combinationspermutations-for-job-assignment-to-machinesjob-shop-problemcombinatorial-optimizationpermutationinteger programming formulation of the alldifferent constrainthttp://www.or-exchange.com/questions/6262/integer-programming-formulation-of-the-alldifferent-constraint<p>In my ILP problem I need permutations of \(\{1, 2, ..., n\}\). Below is what I have come up with, the issue is: it uses \(O(n^2)\) binary variables. Is it possible to express the alldifferent constraint with \(O(n)\) variables (integer allowed) <em>and</em> constraints, neglecting poor relaxation? If yes, how? (The goal is to use the students version of AMPL :) )</p>
<p>If not, what reasonable formulations are there?</p>
<p>I am particularly interested in formulations using \(O(n)\) variables: many of the constraints might be eliminated by the presolve, based on other constraints in my ILP problem.</p>
<hr>
<p>Finally, a fragment of my attempt in AMPL:</p>
<pre><code>param n_row;
param n_col;
set ROWS := {1 .. n_row};
set COLS := {1 .. n_col};
var row{ROWS,COLS} binary;
var P{i in ROWS} =
sum {k in COLS} row[i,k]*k;
s.t.
row_r{i in ROWS}:
sum{j in COLS} row[i,j] = 1;
row_c{j in COLS}:
sum{i in ROWS} row[i,j] = 1;
</code></pre>
<hr>
<p><strong>Solution:</strong> I turned the ILP into a CSP and now I am using IBM ILOG CP Optimizer which is free for academic users.</p>AliWed, 22 Aug 2012 07:25:05 -0400http://www.or-exchange.com/questions/6262/integer-programming-formulation-of-the-alldifferent-constraintinteger-programminglinear-programmingpermutationSymmetry in Integer Programminghttp://www.or-exchange.com/questions/5672/symmetry-in-integer-programming<p>Hello everybody</p>
<p>I have a question regarding the symmetry group defined in the paper written by Francois Margot in the book of “50 years of integer programming 1958-2008”.</p>
<p>In fact the definition of a symmetric group is clear.
The definition of symmetry group in this paper is as following:</p>
<p>Assume that Q is the set of all feasible solution of an integer linear programming (ILP). Then the symmetry group G of ILP is the set of all permutations of the variables mapping Q on itself and mapping each feasible solution on a feasible solution having the same value. </p>
<p>The problem is here! In my ILP, the set of different feasible solutions with the same value does not define a group since it is not close under the operations defined on permutation groups! More precisely, there exists a permutation which maps a feasible solution on another one with the same value while it maps another feasible solution with the same value to a feasible solution with a different value. </p>
<p>Any comment is highly appreciated.</p>MonemiTue, 12 Jun 2012 11:48:58 -0400http://www.or-exchange.com/questions/5672/symmetry-in-integer-programmingintegerpermutationprogramminggroupsymmetry-breaking