Help : change permutations

Rafa1 · January 11, 2024, 12:21pm

I ask for help with the next issue that I am unable to salvage by my own means.

I want to solve a problem that is completely linear in its constraints (I can’t use anything other than CPLEX/MILP)

The problem is as follows:

I start with a random permutation of the first n natural numbers.

At each stage t, of a perfectly defined horizon t=1,2…T, I execute a single move out of among k possible k.
This movement causes a change in some of the positions of the numbers that form the permutation of the previous stage. For each movement I know the positions that are exchanged (the movement is linked to the positions that are exchanged, regardless of the values they contain).
Both the permutation and the movement of each stage are variables in the decision of the problem.

I can’t find a formulation that doesn’t have motion variables as subscripts of decision variables.

THANKS

4er · January 12, 2024, 8:25pm

I suggest posting the simplest formulation that you do have, even if it involves subscripting some variables by other variables. Then it will be clear exactly what problem you want to solve, and it will be easier to suggest a linear reformulation.

Rafa1 · January 14, 2024, 9:29am

Thank you very much Mr Fourer for your interest
The code is:

Rafa1 · January 15, 2024, 8:42am

##
## TWIDDLE
##

## The Origin is:
##	https://puzzling.stackexchange.com/questions/47124/what-is-the-strategy-to-solve-simon-tathams-twiddle
##
## Parameters defining board, horizont,...

param n	:= 4;  # Tablero
set N	:= 1..n;
set Fic	:= 1..n^2;  # Fichas
set Mov := 1..18;  # Movimientos
set Cam:= 1..8;
set V := {1..n} cross {1..n};
param M := (n+5)^2;  # M suficientemente grande
	
param Epoc;  # Movimientos a considerar
let Epoc := 16;		
set H := 1..Epoc;  # HORIZONTE
set H1 := 1..(Epoc-1);


# Params BB and TR (calculated offside)
# BB[peg,movement] =1 iff peg is affected by mov
# TR[peg,movement] = position to change	
	
param BB{Fic,Mov} binary default 0;
	let BB[1,1] := 1;	let BB[11,6] :=1;	let BB[14,7] :=1;	let BB[2,2] :=1;	let BB[6,1] :=1;	let BB[7,5] :=1;
	let BB[10,4] :=1;	let BB[11,8] :=1;	let BB[14,8] :=1;	let BB[3,2] :=1;	let BB[6,2] :=1;	let BB[7,6] :=1;
	let BB[10,5] :=1;	let BB[11,9] :=1;	let BB[15,8] :=1;	let BB[3,3] :=1;		let BB[6,4] :=1;		let BB[8,3] :=1;
	let BB[10,7] :=1;	let BB[12,6] :=1;	let BB[15,9] :=1;	let BB[4,3] :=1;		let BB[6,5] :=1;		let BB[8,6] :=1;
	let BB[10,8] :=1;	let BB[12,9] :=1;	let BB[16,9] :=1;	let BB[5,1] :=1;	let BB[7,2] :=1;		let BB[9,4] :=1;
	let BB[11,5] :=1;	let BB[13,7] :=1;	let BB[2,1] :=1;	let BB[5,4] :=1;	let BB[7,3] :=1;		let BB[9,7] :=1;	
	let BB[1,10] :=1;	let BB[11,15] :=1;	let BB[14,16] :=1;	let BB[2,11] :=1;	let BB[6,10] :=1;	let BB[7,14] :=1;
	let BB[10,13] :=1;	let BB[11,17] :=1;	let BB[14,17] :=1;	let BB[3,11] :=1;	let BB[6,11] :=1;	let BB[7,15] :=1;
	let BB[10,14] :=1;	let BB[11,18] :=1;	let BB[15,17] :=1;	let BB[3,12] :=1;	let BB[6,13] :=1;	let BB[8,12] :=1;
	let BB[10,16] :=1;	let BB[12,15] :=1;	let BB[15,18] :=1;	let BB[4,12] :=1;	let BB[6,14] :=1;	let BB[8,15] :=1;
	let BB[10,17] :=1;	let BB[12,18] :=1;	let BB[16,18] :=1;	let BB[5,10] :=1;	let BB[7,11] :=1;	let BB[9,13] :=1;
	let BB[11,14] :=1;	let BB[13,16] :=1;	let BB[2,10] :=1;	let BB[5,13] :=1;	let BB[7,12] :=1;	let BB[9,16] :=1;

param TR{Fic,Mov} integer default 0;
	let TR[1,1] :=5;		let TR[11,6] :=12;	let TR[14,7] :=10;	let TR[2,2] :=6;		let TR[6,1] :=2;		let TR[7,5] :=6;
	let TR[10,4] :=6;	let TR[11,8] :=10;	let TR[14,8] :=15;	let TR[3,2] :=2;		let TR[6,2] :=7;		let TR[7,6] :=11;
	let TR[10,5] :=11;	let TR[11,9] :=15;	let TR[15,8] :=11;	let TR[3,3] :=7;		let TR[6,4] :=5;		let TR[8,3] :=4;
	let TR[10,7] :=9;	let TR[12,6] :=8;	let TR[15,9] :=16;	let TR[4,3] :=3;		let TR[6,5] :=10;	let TR[8,6] :=7;
	let TR[10,8] :=14;	let TR[12,9] :=11;	let TR[16,9] :=12;	let TR[5,1] :=6;		let TR[7,2] :=3;		let TR[9,4] :=10;
	let TR[11,5] :=7;	let TR[13,7] :=14;	let TR[2,1] :=1;		let TR[5,4] :=9;		let TR[7,3] :=8;		let TR[9,7] :=13;
	let TR[1,10] :=2;	let TR[11,15] :=7;	let TR[14,16] :=13;	let TR[2,11] :=3;	let TR[6,10] :=5;	let TR[7,14] :=11;
	let TR[10,13] :=9;	let TR[11,17] :=15;	let TR[14,17] :=10;	let TR[3,11] :=7;	let TR[6,11] :=2;	let TR[7,15] :=8;
	let TR[10,14] :=6;	let TR[11,18] :=12;	let TR[15,17] :=14;	let TR[3,12] :=4;	let TR[6,13] :=10;	let TR[8,12] :=7;
	let TR[10,16] :=14;	let TR[12,15] :=11;	let TR[15,18] :=11;	let TR[4,12] :=8;	let TR[6,14] :=7;	let TR[8,15] :=12;
	let TR[10,17] :=11;	let TR[12,18] :=16;	let TR[16,18] :=15;	let TR[5,10] :=1;	let TR[7,11] :=6;	let TR[9,13] :=5;
	let TR[11,14] :=10;	let TR[13,16] :=9;	let TR[2,10] :=6;	let TR[5,13] :=6;	let TR[7,12] :=3;	let TR[9,16] :=10;

# P = position of number Fic in Board
# Z = movement (1..18) = 2 ways x 9 centers of rotation

	var P{Fic,H} >=1,<=n^2 integer;  # Posicion en tablero de ficha i en t (0..15)
	var Z{Mov,H} binary default 0;  # Movimiento elegido

# Desvs to goals
 	var DesvPos{Fic} >=0, <=n^2			; # Desviaciones a meta
 	var DesvNeg{Fic} >=0, <=n^2			; # Desviaciones a meta

# Some dummys during trials
		# OBJETIVO	
		#	minimize SX: 
		#		sum{i in Fic} (DesvPos[i] + DesvNeg[i]);

# Initial board just rewired		
		# Configuración Inicial del Tablero
			subject to TabIni {i in Fic}:				
				P[i,1] == 17-i;
				
# In use is goal positions to achieve			
		# Desviaciones a objetivo
		#	subject to Desvs {i in Fic}:
		#		(P[i,Epoc] + DesvPos[i] - DesvNeg[i]) == i;

# One movement per turn	
		# Sólo un Movimiento
			subject to UnMov {t in H}:
				sum{i in Mov} Z[i,t] == 1;
# Cut added				
		# Se cumplen valores de P	
			subject to CaCo {t in H} :
				sum {i in Fic} P[i,t] == sum {j in Fic} j;

# Here where the problem is
# The Position P[j] change iff j is affected by move, j = TR[i,movement]....			
#
		#	subject to S {i in Fic,t in H1}: 
		#		P[i,t+1] == 	sum {m1 in Mov} (TR[i,m1]*Z[m1,t]) + sum {m1 in Mov} P[i,t]*Z[m1,t]*(1-BB[i,m1]);
				
# Linealizing the product of binary (Z) by integer (P) 
# CONTAINS A VARIABLE 	
			
# Actualiza valores	(S1,S2 = Cambian;  S3,S4 = Permanecen)
	subject to S1 {i in Fic,t in 2..Epoc}: 
		P[i,t] >= sum {m1 in Mov} TR[i,m1]*Z[m1,t-1] - M*sum {m1 in Mov} Z[m1,t-1]*(1-BB[i,m1]);
				
	subject to S2 {i in Fic,t in 2..Epoc}: 
		P[i,t] <= sum {m1 in Mov} TR[i,m1]*Z[m1,t-1] + M*sum {m1 in Mov} Z[m1,t-1]*(1-BB[i,m1]);
				
	subject to S3 {i in Fic,t in 2..Epoc}: 
		P[i,t] >= P[i,t-1]-sum {m1 in Mov} Z[m1,t-1]*M*BB[i,m1];
				
	subject to S4 {i in Fic,t in 2..Epoc}: 
		P[i,t] <= P[i,t-1]+sum {m1 in Mov} Z[m1,t-1]*M*BB[i,m1];

4er · January 15, 2024, 5:56pm

I copied your model and data to a file twiddle.txt, and was able to run it using AMPL and a solver, without any error messages:

ampl: include twiddle.txt;
ampl: option solver gurobi;

ampl: solve;
Gurobi 11.0.0: optimal solution
1207 simplex iterations
1 branching nodes
Objective = find a feasible point.

I noticed that your model mentions a possible problem here:

# Here where the problem is
# The Position P[j] change iff j is affected by move, j = TR[i,movement]....			

# subject to S {i in Fic,t in H1}: 
#	P[i,t+1] == sum {m1 in Mov} (TR[i,m1]*Z[m1,t]) 
#             + sum {m1 in Mov} P[i,t]*Z[m1,t]*(1-BB[i,m1]);

I tried adding the constraint S to the model, but still there were no error messages. So, I am not sure what the problem is. Can you give an explanation?

Rafa1 · January 16, 2024, 11:50am

First of all, thank you for your interest,

The S constraint is not valid in CPLEX/MILP since it includes the product of two variables (P and Z) so 4 constraints (S1,…S4) are needed to linearize that product.

But S1,S2 should be (it is not like that in the text I sent)

P[i,t] >=(<=) P[sum {m1 in Mov} TR[i,m1]Z[m1,t-1] - M * sum {m1 in Mov} Z[m1,t-1]( 1-BB[i,m1]);t-1]

that again contains a product.

This is where I cannot formulate the change of positions in each epoc without using variables as subindexes of other variables.

Thank you very much!!!
R

4er · January 17, 2024, 2:22pm

I am not sure why you need such complicated constraints to linearize the product of variables in constraint S. Instead you could consider replacing P[i,t]*Z[m1,t] by new variables PZ[i,m1,t], which makes S linear:

subject to S {i in Fic,t in H1}: 
   P[i,t+1] == sum {m1 in Mov} (TR[i,m1]*Z[m1,t]) 
             + sum {m1 in Mov} PZ[i,m1,t]*(1-BB[i,m1]);

Then you can add four simpler linear constraints to force PZ[i,m1,t] to equal P[i,t]*Z[m1,t], as explained for example in Binary Variables and Quadratic Terms.

Topic		Replies	Views
How I can model this Support	2	45	February 21, 2024
[AMPL 24856] Fixing this code Google Group Mirror	5	283	November 1, 2023
Something about smoothing parameters with ipopt Support solvers	3	296	August 7, 2023
CPLEX error message: CPLEX 20.1.0.0: logical constraint _slogcon[1] is not an indicator constraint Support solvers , errors-and-messages	5	234	July 21, 2023
Strange error (exit code) after repeat structure Support errors-and-messages	4	357	April 19, 2023

Help : change permutations

Related Topics