Unconstrained minimisation problem with a complicated range
古いコメントを表示
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 件のコメント
Mat
2024 年 9 月 10 日
David Goodmanson
2024 年 9 月 10 日
Hi Mat, does p1 take on integer values whose sum must be identical for all three groups, or does the problem concern something else?
Matt J
2024 年 9 月 10 日
Where sum(p1,i) denotes...
It already denotes something in Matlab, so please don't use it to denote something else. What are the independent variables here? Are p1,p2 and p3 each vectors of length N? Are they the design variables or are they functions of something else?
Mat
2024 年 9 月 11 日
Steven Lord
2024 年 9 月 11 日
Mat
2024 年 9 月 11 日
回答 (1 件)
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 件のコメント
Mat
2024 年 9 月 10 日
The 3Nx3N - matrix x_ij defines a permutation of the 3N objects.
The columns of row 1 to row N where the 1s are placed by the optimizer in the solution denote the first group of assembled objects, the columns of row N+1 to row 2N where the 1s are placed by the optimizer in the solution denote the second group of assembled objects and the column numbers of row 2N+1 to row 3N where the 1s are placed by the optimizer in the solution denote the third group of assembled objects.
The first 6 inequalities measure the difference of p1 between the three groups.
The objective function as the sum of absolute values of the differences of p1 between the three groups (not squared differences as in your functional to keep the problem linear) is to be minimized.
There is no need for p1j to be integers.
Maybe there is an easier way to achieve optimum homogenity of the three groups - I don't know.
If you use the problem-based approach as @Matt J suggests, I needed 16 lines of code to setup and solve the problem as formulated by the equalities and inequalities above. So it's worth to start reading the documentation.
Matt J
2024 年 9 月 11 日
You can use MATLAB's "intlinprog" to solve.
But I wouldn't use intlinprog directly. You should just use the Problem-Based set-up tools to define the problem and let solve pick the optimizer for you.
Mat
2024 年 9 月 11 日
Mat
2024 年 9 月 11 日
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)))
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.
カテゴリ
ヘルプ センター および File Exchange で Solver Outputs and Iterative Display についてさらに検索
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
Translated by 
