CODEWITHSUNDEEP
mathematical-optimizationlinear-programmingsolvercplexampl
user3787524
user3787524

Reputation: 155

AMPL difficulty writing an objective from a constraint using "count"

I'm trying to solve a small problem in AMPL but I faced a difficulty which I couldn't translate it into a constraint. The problem is: Assume that I have 3 sets A,B, and C. I want to link elements from A to elements in B such that no more than 2 elements from A are linked to a single element in B if they exist in 1 subset of C (maximum of 2 out of 3 elements in any subset of C are linked to 1 elements in B). I already did this part

Assume I wrote this constraint:

subject to constr {(i,j,k) in C, b in B}: x[i,b] + x[j,b] + x[k,b] <= 2;

I want the objective of the code to maximize the case where {(i,j,k) in C, b in B}: x[i,b] + x[j,b] + x[k,b] <= 1;

or in other words, to minimize the case where:

{(i,j,k) in C, b in B}: x[i,b] + x[j,b] + x[k,b] = 2;.

How can I write this objective? And in case I wanted to have the number of times where ( constraint is = 2 ) <= to a constant (for example MAX), how can I do that as well? Below is the code I wrote so far. I'm using a student edition of AMPL and a student edition of cplex. Your help is appreciated and thanks in advance.

set A;
set B;
set C within A cross A cross A;
param constant:= 5;
var x{A,B} binary;
subject to constr1 {(i,j,k) in C, b in B}: x[i,b]  + x[j,b] + x[k,b] <= 2;
subject to onlyOneLinkForEachElementInA {a in A}: sum{b in B} x[a,b] = 1;
data;
set A:= 0 a b c d e f;  #note that 0 is used only to pad the subsets and force them to have dimension of 3
set B:= 1 2 3;
set C: 0 a b c d e f:=
(a,b,c) (a,c,0) (c,d,0) (e,f,b) (a,b,0) (f,b,0);
solve;
for {i in A :i!=0} { printf "%s\t",i;for{c in B} {if x[i,c]=1 then printf "%s\n",c;}};

I tried this but it didn't work (neither did the numberof worked):

subject to constr2 {b in B}: count {(i,j,k) in C} ( (x[i,b] + x[j,b] + x[k,b]) = 2 ) <= MAX; where MAX is declared as:

param MAX:= 5;

Upvotes: 2

Views: 684

Answers (1)

David Nehme
David Nehme

Reputation: 21597

You can only optimize linear and (some) quadratic expressions. Since you are trying to minimize the number of times x[i,b] + x[j,b] + x[k,b] == 2, you need an additional indicator variable.

var has_2{C} binary;
minimize has_2 sum((i,j,k) in C) not_2[i,j,k]
subject to constr1 {(i,j,k) in C, b in B}: x[i,b] + x[j,b] + x[k,b] - has_2[i,j,k] <= 1

constr1 forces has_2 to be 1 if two of the x variables are 1. If 0 or 1 of the x variables are 1, then the objective will force has_2 to 0. If your x variables are already binary, then you might be better off making has_2 continuous with an upper bound of 1, especially considering that there are more has_2 variables than x variables.

Upvotes: 2

Related Questions