линейная целевая функция с нелинейными ограничениями и двоичными переменными

Question

У меня проблема, когда мне нужно оптимизировать выбор кандидатов. Каждый кандидат имеет оценку (от 0 до 1), тип (10 вариантов от 1 до 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 и поместить их в различные наборы по убыванию (где к = типа ц)
3. Для следующих элементов NK, положите их в набор с самой низкой суммой

Все готово.

Этот алгоритм не должен давать вам решение, которое минимизирует дисперсию между суммой каждой величины для каждого типа. Но это хорошее приближение, особенно когда maxSize и n являются большими.

Вы также можете рассчитать всю возможную комбинацию элемента k в наборе n элемента (35 | 100) с гребенкой (35,100). Затем вы можете проверить, какая комбинация дает вам наименьшую дисперсию, но, конечно, этот метод занимает много времени.

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