Unconstrained minimisation problem with a complicated range
27 views (last 30 days)
Show older comments
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 Comments
Answers (1)
Torsten
on 10 Sep 2024
Edited: Torsten
on 10 Sep 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 Comments
Torsten
on 11 Sep 2024 at 17:03
Edited: Torsten
on 11 Sep 2024 at 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
on 14 Sep 2024 at 14:45
Edited: Torsten
on 14 Sep 2024 at 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.
See Also
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!