Unconstrained minimisation problem with a complicated range
6 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
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 comentarios
Respuestas (1)
Torsten
el 10 de Sept. de 2024
Editada: Torsten
el 10 de Sept. de 2024
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 comentarios
Torsten
el 11 de Sept. de 2024
Editada: Torsten
el 11 de Sept. de 2024
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
el 14 de Sept. de 2024
Editada: Torsten
el 14 de Sept. de 2024
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.
Ver también
Categorías
Más información sobre Solver Outputs and Iterative Display en Help Center y File Exchange.
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!