How can I determine the amount of times a certain value can be achieved by summing values in a matrix?

1 次查看(过去 30 天)
I have a vector of up to 50 whole numbers, all of which are length values for wall panels. The wall panels come in sections of 144 inches, so my goal is to apply the lengths from the matrix and determine the number of full wall panels I would need. For example:
LengthVal = [50 50 60 70]; %User Input
With the values above, I know I would ned two 144 in panels: the 70 and 60 on one with the 50 and 50 on the other. I want to do this programetrically with a much larger number of length values. I assume the solution will require several for loops, but I am unsure about how to implement that. Are there any short cuts that you may know to perform a similar function?
Edit: Essentially, I want to get something with similar functionality to this website.
Thanks for any help!
  4 个评论
Walter Roberson
Walter Roberson 2020-7-31
Is the requirement the minimum number of pieces used and any solution that achieves that is acceptable? Is the requirement the minimum total waste? Is the requirement that assuming that you are using the minimum number of pieces, that you want to maximize the waste width -- because the larger the waste pieces the more likely that you could use one of them for a later job?

请先登录,再进行评论。

回答(3 个)

Matt J
Matt J 2020-7-31
编辑:Matt J 2020-7-31
This solution (EDITED) requires the Optimization Toolbox:
LengthVal = [50,50 ,60,70]; %User Input
N=numel(LengthVal);
X=optimvar('X',[N,N],'LowerBound',0,'UpperBound',1,'type','integer');
y=optimvar('y',[1,N],'LowerBound',0,'UpperBound',1,'type','integer');
prob=optimproblem('Objective',sum(y));
prob.Constraints.row=sum(X,2)==1; %assign exactly 1 panel to each wall
prob.Constraints.capacity=LengthVal*X<=144; %respect panel capacity
prob.Constraints.ylb=sum(X,1)/N<=1.1*y;
prob.Constraints.yub=sum(X,1)>=y;
sol=solve(prob);
[~,~,groups]=unique((1:N)*round(sol.X.'),'stable') %the result, as a grouping vector
groups =
1
2
1
2
  15 个评论
Matt J
Matt J 2020-7-31
编辑:Bruno Luong 2020-7-31
Very well, but I wonder if it is good to have as an explicit constraint anyway to help the algorithm narrow the search...
Bruno Luong
Bruno Luong 2020-7-31
In my experience no.
By removing the redundancy of the constraints, we'll help the minimizer for not doing extra calculation for when it needs to update the active set.

请先登录,再进行评论。


Bruno Luong
Bruno Luong 2020-7-31
编辑:Bruno Luong 2020-7-31
I put here the code with limiting CPU time so one can run up to 50 samples. Matt should get credit for his original idea.
fulllength = 144;
% Random LengthVal
LengthVal = randi(fulllength,1,50)
N=numel(LengthVal);
X=optimvar('X',[N,N],'LowerBound',0,'UpperBound',1,'type','integer');
y=optimvar('y',[1,N],'LowerBound',0,'UpperBound',1,'type','integer');
prob=optimproblem('Objective',sum(y));
prob.Constraints.row=sum(X,2)==1; %assign exactly 1 panel to each wall
prob.Constraints.capacity=LengthVal*X<=fulllength; %respect panel capacity
for j=1:N
for i=1:N
prob.Constraints.(sprintf('Bnd_i%dj%d',i,j))=X(i,j)<=y(1,j);
end
end
problem = prob2struct(prob);
problem.options = optimoptions('intlinprog','MaxTime',60); % limits the computation to 60s
x = intlinprog(problem);
% Post process data
X = reshape(x(1:N^2),[N,N]);
X = round(X);
X(:,all(X==0,1)) = [];
ng = size(X,2);
FillLengths=LengthVal*X;
L = X.*LengthVal(:);
N = cumsum(X,1).*X;
[~,g,n] = find(N);
data = accumarray([g,n],L(X>0),[],[],NaN);
% Graphic output
figure(1);
clf
subplot(1,2,1);
imagesc(X);
xlabel(sprintf('group (1-%d)', ng));
ylabel('Wall paper number');
subplot(1,2,2);
bar(1:ng,data,'stacked');
xlim([0.5 ng+0.5]);
ylim([0 fulllength]);
xlabel(sprintf('group (1-%d)', ng));
ylabel('stack lengths');
Examples of results:

Matt J
Matt J 2020-8-2
Below is a more advanced version of my original answer, which is showing greater empirical succes. It incorporates initialization and restart strategies to iterative reduce problem dimension, and hence the run time. On 3 consecutive sets of randomized inputs with N=50,
LengthVal = (randi(10,1,50)*10);
it was able to complete the optimization within a few minutes. However, for some cases, it does still fall into a protracted branch and bound phase, so I have chosen an empirical cap for the MaxNodes option parameter:
N=numel(LengthVal);
e=ones(N,1);
sol=init(LengthVal);
M=sum(sol.y);
tic;
while 1
X=optimvar('X',[N,M],'LowerBound',0,'UpperBound',1,'type','integer');
y=optimvar('y',[1,M],'LowerBound',0,'UpperBound',1,'type','integer');
prob=optimproblem('Objective',sum(y));
prob.Constraints.rowLB=sum(X,2)>=0.5; %assign exactly 1 panel to each wall
prob.Constraints.rowUB=sum(X,2)<=1.5;
prob.Constraints.capacity=LengthVal*X<=144; %respect panel capacity
% prob.Constraints.ylb=sum(X,1)/N<=1.1*y;
prob.Constraints.ylb=X/2<=e*y;
%prob.Constraints.yub=sum(X,1)+0.5>=y;
prob.Constraints.mono=sum(X(:,1:M-1),1)>=sum(X(:,2:M),1);
of=@(x,o,s) customFcn(x,o,s,M);
cut=logical(sol.y);
sol.X=sol.X(:,cut);
[~,is]=sort(sum(sol.X,1),'descend');
sol.X=sol.X(:,is);
sol.y=sol.y(cut);
[sol,fval]=solve(prob,sol,...
'options',optimoptions(@intlinprog,'OutputFcn',of,...
'MaxNodes',M*20000));
fval=round(fval),
if fval==M, break; end
M=fval;
end
toc;
[~,~,groups]=unique((1:M)*round(sol.X.'),'stable'); %the result, as a grouping vector
grous=groups(:).',
function stop = customFcn(x,optimValues,state,M)
stop=false;
if ~isempty(optimValues.fval) && ~isempty(x)
stop=optimValues.fval<M;
end
end
function sol=init(LengthVal)
N=numel(LengthVal);
sol.X=zeros(N);
j=1; accum=0;
for i=1:N
accum=accum+LengthVal(i);
if accum<=144
sol.X(i,j)=1;
else
accum=LengthVal(i); j=j+1;
sol.X(i,j)=1;
end
end
sol.y=double(any(sol.X,1));
end

类别

Help CenterFile Exchange 中查找有关 Linear Algebra 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by