非線形制約と2進変数による線形目的関数

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には、第1の制約は（ほとんどの35件の候補で）線形一つである、最後の10はそう明らかに非直線的であるが、正しい結果が得られません。

Answer 1

説明のために：すべてのタイプの候補者は、合計候補者の数の10％を超えて提示できませんか？すなわち、例えば33人の合計候補、タイプあたりの候補者の最大数は3.3ですか？あなたの説明を正しく理解すれば、あなたの制約システムは、同じ数の候補と、合計候補の正確に10％の割合を特徴とするすべてのタイプをもたらします。これは、及び候補の総数はここ線形パーティション・アルゴリズムを使用する方法である10

Answer 2

の整数倍でなければなりません。

それは動作しませんどのように

：

1. ソート
2. 降順の要素は次のNK要素について
3. （ここで、kは= typeq）最初のKの要素を取り、異なるセットに入れ、あなたが行っている

最低の合計とセットでそれらを置きます。

このアルゴリズムは、あなたのタイプごとに各量の合計との差異を最小化するソリューションを提供することになっていません。しかし、これは良い近似であり、特にmaxSizeとnが大きい場合には当てはまります。 combnk（35100）と|（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