lineare Zielfunktion mit nichtlinearen Randbedingungen und binären Variablen

Question

Ich habe ein Problem, wo ich eine Auswahl von Kandidaten optimieren muss. Jeder Kandidat hat eine Punktzahl (zwischen 0 und 1), einen Typ (10 Auswahlmöglichkeiten von 1 bis 10) und eine Menge.

Meine zu optimierenden Variablen sind binär. Sie repräsentieren die Wahl oder nicht des Kandidaten. Die Objektfunktion ist linear, sie ist das Skalarprodukt der Binärvariablen und ein Score-Vektor. Die Idee ist, die höchste Punktzahl zu wählen.

Jetzt habe ich eine lineare Einschränkung: die Anzahl der Kandidaten, die

höchstens 35 seine

ausgewählt werden kann, aber ich habe auch 10 nicht lineares Constraints: es gibt 10 Arten von Kandidaten. In der endgültigen Auswahl sollte die Gesamtmenge jedes Typs höchstens 10% der Gesamtmenge aller Typen betragen.

Ich habe daher einen Code mit intlinprog geschrieben, weil es binäre Variablen handhabt, aber ich kämpfe, um mit den nichtlinearen Einschränkungen umzugehen. Ich bin mir nicht sicher, ob es am besten wäre, sie zu linearisieren oder vielleicht einen anderen Löser zu benutzen.

hier ist der Code:

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); 

Das Problem ist, in meinem A, b, die erste Bedingung ist die lineare eine (höchstens 35 Kandidaten) und die letzten 10 nicht linear, so dass es offensichtlich gibt nicht das richtige Ergebnis.

Answer 1

Zur Klarstellung: jede Art von Kandidat kann nicht mehr als 10% der Gesamtzahl der Kandidaten vorgestellt werden? Das heißt, z.B. 33 Kandidaten insgesamt, die maximale Anzahl der Kandidaten pro Typ ist 3,3? In Logiken übersetzt, beträgt der Höchstbetrag 3 Selektionen, also insgesamt 30. Wenn ich Ihre Beschreibung richtig verstehe, führt Ihr Constraintsystem dazu, dass jeder Typ die gleiche Anzahl von Kandidaten und einen Bruchteil von genau 10% der gesamten Kandidaten hat. und die Gesamtzahl der Kandidaten muss ein ganzzahliges Vielfaches von 10 sein.

Answer 2

Hier ist eine Möglichkeit, einen Algorithmus für eine lineare Partition zu verwenden.

Wie es funktioniert:

1. sortieren Sie die Elemente in absteigender Reihenfolge
2. Nimm die ersten Elemente K und sie in verschiedene Sätze (wobei k = typeq)
3. Für die nächsten NK Elemente, Setzen Sie sie in das Set mit der niedrigsten Summe

Sie sind fertig.

Dieser Algorithmus soll Ihnen nicht die Lösung bieten, die die Varianz zwischen der Summe jeder Menge für jeden Typ minimiert. Aber das ist eine gute Annäherung, besonders wenn maxSize und n groß sind.

Sie können auch einfach alle möglichen Kombinationen von k Element in einer Menge von n Element (35 | 100) mit combnk (35,100) berechnen. Dann können Sie prüfen, welche Kombination die kleinste Abweichung ergibt, aber diese Methode ist natürlich zeitaufwendig.

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