비선형 제약 조건 및 이진 변수를 사용하는 선형 목적 함수

Question

후보의 선택을 최적화해야하는 문제가 있습니다. 각 후보자는 점수 (0과 1 사이), 유형 (1에서 10까지의 10 가지 선택 사항) 및 수량을가집니다.

최적화 할 변수는 바이너리입니다. 그들은 후보자의 선택을 대표하거나 아닙니다. 객체 함수는 선형이며, 이진 변수와 스코어 벡터의 스칼라 곱입니다. 아이디어는 가장 높은 점수 합을 선택하는 것입니다.

는 지금은 선형 제약이 있습니다 최대 35

될 수 있습니다 선택할 수있는 후보의 수를하지만 나 또한 10 비선형 제약이 있습니다 후보자의 10 종류가 있습니다. 마지막 선택에서, 각 유형의 총 수량은 모든 유형의 총 수량의 많아야 10 %이어야합니다.

나는 따라서 이진 변수를 처리하지만 비선형 제약에 대처하기 위해 고군분투하고 있기 때문에 intlinprog를 사용하여 코드를 작성했다. 선형화를 시도하거나 다른 솔버를 사용하는 것이 가장 좋은지 확실하지 않습니다.

rng('default'); 

clc; 
clear; 
n = 100; 
maxSize = 35; 
nbType = 10; 
NAV = 6000000; 
thresholdType = 0.1 * NAV; 

%%%TOP BASKET 
score = rand(n,1)/10+0.9; 
quantity = rand(n,1)*300000; 
type = ceil(rand(n,1)*nbType); 
typeMask = zeros(n,nbType); 

for i=1:nbType 
    typeMask(:,i) = type(:,1) == i; 
end 

f = -score; 
intcon = [1:1:n]; 

%Write the linear INEQUALITY constraints: 
A = [ones(1,n);bsxfun(@times,typeMask,quantity)'/thresholdType]; 
b = [maxSize;ones(nbType,1)]; 

%Write the linear EQUALITY constraints: 
Aeq = []; 
beq = []; 

%Write the BOUND constraints: 
lb = zeros(n,1); 
ub = ones(n,1); % Enforces i1,i2,...in binary 

%x = fmincon(fun,x0,A,b,Aeq,beq,lb,ub); 
x = intlinprog(f,intcon,A,b,Aeq,beq,lb,ub); 

문제는, 내 A, B의 첫 번째 제약은 선형 일 (최대 35 후보)와 지난 10가 너무 분명 비선형가 있습니다 : 여기

코드입니다 올바른 결과를주지 못한다.

Answer 1

설명을 위해 : 모든 유형의 후보자는 총 후보자 수의 10 %를 초과하지 않을 수 있습니까? 즉, 예를 들어. 33 명의 총 후보자, 유형 당 후보자의 최대 수는 3.3입니까? 논리적으로 번역 된 최대 값은 3 가지로 세 가지가 선택되므로 합계가 30입니다. 설명을 올바르게 이해하면 제약 시스템이 모든 유형의 후보가 같고 전체 후보의 정확히 10 %에 불과합니다. 후보의 총 수는 여기 선형 분할 알고리즘을 사용하는 방법 10.

Answer 2

의 정수배이어야한다.

가 작동합니까 방법 :

1. 정렬 요소를 순서
2. 최초의 K 요소를 가지고 다른 세트에 넣어 내림차순으로 (여기서 K = typeq) 다음 NK 요소에 대한
3. , 당신이 완료

가장 낮은 금액으로 세트에 넣어.

이 알고리즘

는 당신에게 각 유형에 대한 각 수량의 합 사이의 차이를 최소화하는 솔루션을 제공하기로되어 있지 않습니다. 그러나 이것은 좋은 근사치입니다. 특히 maxSize 및 n이 큰 경우가 좋습니다. combnk (35,100)와 | (100 35)

는 또한 단지 N 개의 엘리먼트들의 세트의 K 소자의 모든 가능한 조합을 산출 할 수있다. 그런 다음 어느 조합이 가장 작은 분산을 제공하는지 확인할 수 있습니다. 물론이 방법은 시간이 많이 걸립니다.

clc; 
clear; 
n = 1000; 
maxSize = 400; 
typeq = 10; 

%creation of the dataset 
id = 1:n; 
quantity = rand(n,1)*1000; 
type = ceil(rand(n,1)*typeq); 

%sort the vectors 
[quantity,rank] = sort(quantity,'descend'); 
type = type(rank); 
id = id(rank); 

% Get the id of the 10 biggest quantities for the 10 different types 
[~,b] = unique(flipud(type)); 
b = (n-b)+1; 


if length(b) < typeq 
    error('Not enough type') %mean that all the type are not represented. 
end 

ids = id(b); 
types = type(b); 
quantitys = quantity(b); 

%Now we add the biggest remaining quantity to the type that have the smallest sum(quantity per type) 
for i = typeq+1:maxSize 
[~,minq] = sort(accumarray(types,quantitys,[],@sum)); 
quantity(b) = []; 
type(b) = []; 
id(b) = []; 

b = find(type==minq(1),1); 

%if there is no more value for the type that have the smallest sum(quantity) we take the second smallest type, the third.... until that the type still exist. 
ii = 2; 
while isempty(b) 
    b = find(type == minq(ii),1); 
    ii = ii+1; 
    disp('Variance is going to increase') 
end 

ids = [ids(:);id(b)]; 
types = [types(:);type(b)]; 
quantitys = [quantitys(:);quantity(b)]; 
end 

% the selected ID 
id_selected = sort(ids); 
% The sum for each type. 
res = accumarray(types,quantitys,[],@sum); 
cnt = accumarray(types,ones(maxSize,1),[],@sum); 
for i = 1:typeq 
    fprintf('The total quantity for type %d = %f and we have %d elements of this type\n',i,res(i),cnt(i)) 
end