I am trying to solve the partition problem, it is a problem that belongs to the category of optimization problems and is known as an NP-complete problem. It is posed as follows:
Given a set of positive (or negative) integers S = {a1, a2, ..., an}, we seek to determine if it is possible to divide S into two disjoint subsets (that is, without common elements) such that the sum of the elements in both subsets is the same.
My code: P.mod:
set S;
param v {S};
# binary decision variables indicating which subset each value is in
var x {S} binary;
minimize obj: abs(sum{i in S: x[i] = 1} v[i] - sum{i in S: x[i] = 0} v[i]);
# constraint that ensures that all the values of the set S are distributed among the subsets
subject to c1: sum{i in S} x[i] = card(S)/2;
# constraint that ensures that each value of the set S can only be in one subset at a time
subject to c2 {i in S}: sum{j in S: j != i} x[j] <= 1 - x[i];
# constraint that ensures that if there are repeated values, they are in the same subset
subject to c3 {i in S, j in S: i < j and v[i] = v[j]}: x[i] = x[j];
P.dat:
set S := 1 2 3 4 5 6 7 8 9 10;
param v :=
1 8
2 4
3 2
4 7
5 5
6 1
7 9
8 3
9 6
10 2;
P.run:
reset;
model P.mod;
data P.dat;
option solver gurobi;
solve;
The error message:
P.mod, line 7 (offset 241):
variable in such-that part of set specification
context: minimize obj: abs(sum{i in S: x[i] = 1} v[i] - sum{i in S: x[i] = >>> 0} <<< v[i]);
ampl:
It should be noted that I am a student, and I am starting in AMPL, however, I have tried to understand why this error occurred and I cannot find out, in addition to trying other ways without success.
For example, consider S = {10, 20, 15, 5, 25}.
We can partition S into two partitions where the minimum absolute difference between the sum of the elements is 5.
S1 = {10, 20, 5} S2 = {15, 25}
Please note that this solution is not unique. The following is another solution
S1 = {10, 25} S2 = {20, 15, 5}