Unconstrained minimisation problem with a complicated range
87 Ansichten (letzte 30 Tage)
Ältere Kommentare anzeigen
I have 3N objects with properties p1,p2,p3. I need to organise these objects into groups of N objects such that the sum of property p1 is the same. I think I can do with the functional:
f(p1)=(sum(p1,1)-sum(p1,2)).^2+(sum(p1,1)-sum(p1,3)).^2+(sum(p1,3)-sum(p1,2)).^2
|Where sum(p1,i) denotes the sum over the subset of p1's for N objects. The same for other properties, so the objective functionals will simply add(I think). Is there a way of doing this? I guess, if I can do it for one property, I can do it for three?
7 Kommentare
Antworten (1)
Torsten
am 10 Sep. 2024 um 19:28
Bearbeitet: Torsten
am 10 Sep. 2024 um 20:03
I'll formulate the problem for one property - a generalization to three properties is obvious.
I'll assume that each of the 3*N objects is assigned a number p1j which stands for the amount of property 1 in object j ( 1<= j <= 3*N).
This can be formulated as a mixed-integer linear optimization problem:
min: d1 + d2 + d3
s.t.
-d1 <= sum_{i=1}^{i=N} sum_{j=1}^{3*N} x_ij * p1j - sum_{i=N+1}^{i=2*N} sum_{j=1}^{3*N} x_ij * p1j
d1 >= sum_{i=1}^{i=N} sum_{j=1}^{3*N} x_ij * p1j - sum_{i=N+1}^{i=2*N} sum_{j=1}^{3*N} x_ij * p1j
-d2 <= sum_{i=1}^{i=N} sum_{j=1}^{3*N} x_ij * p1j - sum_{i=2*N+1}^{i=3*N} sum_{j=1}^{3*N} x_ij * p1j
d2 >= sum_{i=1}^{i=N} sum_{j=1}^{3*N} x_ij * p1j - sum_{i=2*N+1}^{i=3*N} sum_{j=1}^{3*N} x_ij * p1j
d3 <= sum_{i=N+1}^{i=2*N} sum_{j=1}^{3*N} x_ij * p1j - sum_{i=2*N+1}^{i=3*N} sum_{j=1}^{3*N} x_ij * p1j
-d3 >= sum_{i=N+1}^{i=2*N} sum_{j=1}^{3*N} x_ij * p1j - sum_{i=2*N+1}^{i=3*N} sum_{j=1}^{3*N} x_ij * p1j
sum_{i=1}^{3*N} x_ij = 1 for 1 <= j <= 3*N
sum_{j=1}^{3*N} x_ij = 1 for 1 <= i <= 3*N
0 <= x_ij <= 1 integer for 1 <= i,j <= 3*N
d1, d2, d3 >= 0
You can use MATLAB's "intlinprog" to solve.
8 Kommentare
Torsten
am 11 Sep. 2024 um 17:03
Bearbeitet: Torsten
am 11 Sep. 2024 um 18:19
I think N = 72 will be too large for the way I suggested.
N = 6 cannot finish with MATLAB Online (i.e. within 235 seconds).
You should search for approximate (heuristic) algorithms. And you should search for the name of this problem so that you can find information on how it can be efficiently tackled (I don't think it can be classified as "bin packing problem" as @Steven Lord suggests).
But test it first on your PC:
rng("default")
N = 5;
p1 = rand(3*N,1);
prob = optimproblem;
X = optimvar('X',3*N,3*N,'Type','integer','LowerBound',0,'UpperBound',1);
d = optimvar('d',3,1,'LowerBound',0);
prob.Objective = sum(d);
y = X*p1;
prob.Constraints.c11 = sum(y(1:N))-sum(y(N+1:2*N)) <= d(1);
prob.Constraints.c12 = sum(y(1:N))-sum(y(N+1:2*N)) >= -d(1);
prob.Constraints.c21 = sum(y(1:N))-sum(y(2*N+1:3*N)) <= d(2);
prob.Constraints.c22 = sum(y(1:N))-sum(y(2*N+1:3*N)) >= -d(2);
prob.Constraints.c31 = sum(y(N+1:2*N))-sum(y(2*N+1:3*N)) <= d(3);
prob.Constraints.c32 = sum(y(N+1:2*N))-sum(y(2*N+1:3*N)) >= -d(3);
prob.Constraints.scr = sum(X,1) == ones(1,3*N);
prob.Constraints.scc = sum(X,2) == ones(3*N,1);
sol = solve(prob)
Xsol = sol.X
dsol = sol.d
ysol = Xsol*p1;
sum(ysol(1:N))
sum(ysol(N+1:2*N))
sum(ysol(2*N+1:3*N))
[row,~] = find(abs(Xsol.'-1)<1e-3);
sort(row(1:N))
p1(sort(row(1:N)))
sort(row(N+1:2*N))
p1(sort(row(N+1:2*N)))
sort(row(2*N+1:3*N))
p1(sort(row(2*N+1:3*N)))
Torsten
am 14 Sep. 2024 um 14:45
Bearbeitet: Torsten
am 14 Sep. 2024 um 15:03
The name of the problem is "Balanced number partitioning".
If you choose n = 3*N, m = 3 and k = N, you can check heuristic methods to solve your problem here:
Especially have a look at this publication:
Babel, Luitpold; Kellerer, Hans; Kotov, Vladimir (1998-02-01). "The k-partitioning problem". Mathematical Methods of Operations Research. 47 (1): 59–82. doi:10.1007/BF01193837. ISSN 1432-5217. S2CID 5594197.
Siehe auch
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!