Constraint Alldifferent for linear solvers

[dmitry.e...@gmail.com]

Possibly?

subject to st {i in N, j in N : i < j} : X[i] != X[j];

or

subject to st : min {i in N, j in N : i < j} (abs(X[i] - X[j])) = 1;

not work in linear solvers, because !=/abs/min/max is logical/nonlinear constraints.

Expression "min {i in N, j in N : i < j} (abs(X[i] - X[j])) = 1" is possible to convert in piecewise-linear notation?

[AMPL Google Group]

You can linearize your minimum and absolute function. You can find some resource about it at https://www.leandro-coelho.com/how-to-linearize-max-min-and-abs-functions/ .

--
Dr. Paras Tiwari
am...@googlegroups.com

{#HS:606776724-11620#}

--
You received this message because you are subscribed to the Google Groups "AMPL Modeling Language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to ampl+uns...@googlegroups.com.
To post to this group, send email to am...@googlegroups.com.
Visit this group at https://groups.google.com/group/ampl.
For more options, visit https://groups.google.com/d/optout.

[dmitry.e...@gmail.com]

Thanks, very interesting!

This for abs(A,B)/min(A,B)/max(A,B). How it method to convert for min {i in N} X[i] and abs(X[i]-X[j])? Hard...

суббота, 23 июня 2018 г., 7:10:16 UTC+5 пользователь AMPL Google Group написал:

[AMPL Google Group]

Just to be clear, are you actually trying to linearize this constraint which you quoted in your original question?

subject to st {i in N, j in N : i < j} : X[i] != X[j];

And is X a variable? Then you have a so-called "all-different" constraint. There are a few approaches to linearizing it, but I want to be sure this is the constraint of interest before I suggest anything. Transforming this constraint to something like

subject to st : min {i in N, j in N : i < j} (abs(X[i] - X[j])) = 1;

is likely to lead to one of the same linearizations as for the all-different formulation.

--
Robert Fourer
am...@googlegroups.com

{#HS:606776724-11620#}

On Sat, Jun 23, 2018 at 6:09 AM UTC, Ampl Modeling Language <am...@googlegroups.com> wrote:

Thanks, very interesting!

This for *abs(A,B)*/*min(A,B)*/*max(A,B)*. How it method to convert for *min
{i in N} X* and *abs(X-X[j])*? Hard...

суббота, 23 июня 2018 г., 7:10:16 UTC+5 пользователь AMPL Google Group
написал:

On Sat, Jun 23, 2018 at 2:09 AM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

You can linearize your minimum and absolute function. You can find some resource about it at https://www.leandro-coelho.com/how-to-linearize-max-min-and-abs-functions/ .

--
Dr. Paras Tiwari
am...@googlegroups.com

[dmitry.e...@gmail.com]

Yes, X is variable

[AMPL Google Group]

From what we can tell, your variables X[i] are integer-valued, so that X[i] < X[j] is equivalent to X[i] <= X[j] - 1, and X[i] > X[j] is equivalent to X[i] >= X[j] + 1. The setup might be like this:

param N > 0;
param K >= N;
var X {1..N} >= 1, <= K;

Linearization approach #1: Define binary (zero-one) variables Y[i,j] equal to 1 if and only if X[i] < X[j]. Using the AMPL "implies" operator (==>) these can be written as:

var Y {i in 1..N, j in i+1..N} binary;

subject to st {i in 1..N, j in i+1..N}:
Y[i,j] = 1 ==> X[i] <= X[j] - 1 else X[i] >= X[j] + 1;

Any of the popular MIP solvers (CPLEX, Gurobi, Xpress) will accept these "indicator constraints" and do any needed conversions internally. Alternatively if you want to do some more work yourself, you can make your own linearization of these constraints.

Linearization approach #2: Define binary variables Z[i,k] equal to 1 if and only if X[i] takes the value K. Then you have basically an assignment problem:

var Z {i in 1..N, k in 1..K} binary;

subject to Exactly_1_k_for_each_i {i in 1..N}:
sum {k in 1..K} Z[i,k] = 1;

subject to At_most_1_i_for_each_k {k in 1..K}:
sum {i in 1..N} Z[i,k] <= 1;

subject to Definition_of_X {i in 1..N}: X[i] = sum {k in 1..K} k * Z[i,k];

This approach is most attractive when you can do the whole formulation in terms of the Z-variables and do not need the X-variables in the model at all. (Linear formulations of the Sudoku puzzle are an example of this.)

Hopefully these ideas will get you started, but you should expect to do some work adapting them to your particular optimization model.

--
Robert Fourer
am...@googlegroups.com

{#HS:606776724-11620#}

On Tue, Jun 26, 2018 at 5:09 AM UTC, Ampl Modeling Language <am...@googlegroups.com> wrote:

Yes, X is variable

[dmitry.e...@gmail.com]

Thanks!!!

With model below Gurobi worked, but Cplex and Xpress crashed

set Primes := {3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101};

param n := 3; set N := 1..n; set N4 := 1..n*4; set NN := 1..n*n; set K := 1..49;

set P ordered := {p in Primes : p >= 13 && p <= 79};

param A {i in N, j in N} := if ((i+j-1) mod n)==0 then n else (i+j-1) mod n;

param I {i in NN} := i div n + if i mod n = 0 then 0 else 1;

param J {i in NN} := if i mod n = 0 then n else i mod n;


var X {N, N} integer in K;

var S {N4} integer in P;


s.t. st1 {i in N} : S[    i] = sum {j in N} (X[i,j]);
s.t. st2 {i in N} : S[  n+i] = sum {j in N} (X[j,i]);
s.t. st3 {i in N} : S[2*n+i] = sum {j in N} (X[j,A[i,j]]);
s.t. st4 {i in N} : S[3*n+i] = sum {j in N} (X[A[i,j],n-j+1]);


#s.t. stX : alldiff {i in N, j in N} (X[i,j]);

var Y {i in NN} = X[I[i],J[i]];

var Xb {i in NN, j in NN : i < j} binary;

s.t. stX {i in NN, j in NN : i < j} : Xb[i,j] = 1 ==> Y[i] <= Y[j] - 1 else Y[i] >= Y[j] + 1;


#s.t. stS : alldiff {i in N4} (S[i]);

var Sb {i in N4, j in N4 : i < j} binary;

s.t. stS {i in N4, j in N4 : i < j} : Sb[i,j] = 1 ==> S[i] <= S[j] - 1 else S[i] >= S[j] + 1;


minimize s : sum {i in N, j in N} (X[i,j]);


option solver gurobi;
option gurobi_options 'logfreq=10 outlev=1 timing=1 threads=3';

#option solver cplex;
#option cplex_options 'timing=1 threads=3 display=1 mipdisplay=4 mipinterval=10000';

#option solver xpress;
#option xpress_options 'timing threads=3 outlev=1 miplog=-10000 lplog=10000';


solve;


printf ("\nSum = " & s & "\n{{");
printf {i in N, j in N} (X[i,j] & (if j < n then "," else (if i<n then "},{" else "}}\n")));

[AMPL Google Group]

Running on one of our computers, the Gurobi log shows that it took about 10 minutes to find a feasible solution, and the rest of the long run time was spent proving that no better solution was possible.

We have reproduced the crashes in CPLEX and Xpress, and will report back when a fix is available.

--
Robert Fourer
am...@googlegroups.com

{#HS:606776724-11620#}

On Thu, Jun 28, 2018 at 5:20 AM UTC, Ampl Modeling Language <am...@googlegroups.com> wrote:

Thanks!!!

With model below Gurobi worked, but Cplex and Xpress crashed

set Primes := {3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101};

param n := 3; set N := 1..n; set N4 := 1..n*4; set NN := 1..n*n; set K := 1..49;
set P ordered := {p in Primes : p >= 13 && p <= 79};

param A {i in N, j in N} := if ((i+j-1) mod n)==0 then n else (i+j-1) mod n;

param I {i in NN} := i div n + if i mod n = 0 then 0 else 1;

param J {i in NN} := if i mod n = 0 then n else i mod n;

var X {N, N} integer in K;
var S {N4} integer in P;


s.t. st1 {i in N} : S[ i] = sum {j in N} (X[i,j]);
s.t. st2 {i in N} : S[ n+i] = sum {j in N} (X[j,i]);
s.t. st3 {i in N} : S[2*n+i] = sum {j in N} (X[j,A[i,j]]);
s.t. st4 {i in N} : S[3*n+i] = sum {j in N} (X[A[i,j],n-j+1]);

#s.t. stX : alldiff {i in N, j in N} (X[i,j]);

var Y {i in NN} = X[I,J];

var Xb {i in NN, j in NN : i < j} binary;

s.t. stX {i in NN, j in NN : i < j} : Xb[i,j] = 1 ==> Y <= Y[j] - 1 else Y >= Y[j] + 1;

#s.t. stS : alldiff {i in N4} (S);

var Sb {i in N4, j in N4 : i < j} binary;

s.t. stS {i in N4, j in N4 : i < j} : Sb[i,j] = 1 ==> S <= S[j] - 1 else S >= S[j] + 1;

minimize s : sum {i in N, j in N} (X[i,j]);


option solver gurobi;
option gurobi_options 'logfreq=10 outlev=1 timing=1 threads=3';
#option solver cplex;#option cplex_options 'timing=1 threads=3 display=1 mipdisplay=4 mipinterval=10000';
#option solver xpress;#option xpress_options 'timing threads=3 outlev=1 miplog=-10000 lplog=10000';


solve;

printf ("\nSum = " & s & "\n{{");
printf {i in N, j in N} (X[i,j] & (if j < n then "," else (if i<n then "},{" else "}}\n")));