約束下的優化

我有一個關於優化的問題。約束下的優化

我有一個矩陣x有3列和一定數量的行（最大200）。每一行代表一個候選人。第一列包含一個分數（在0和1之間），第二列包含候選人的種類（總共有10種標記從1到10），列3包含每個候選人的數量。有一件事情需要考慮：金額可以是負數

我想要做的是在這些候選人中選擇最多35個元素，以最大限度地發揮他們各自的得分（第1列）約束條件是每種類型最多可以有10％以下列方式計算：種類1種類：總數種類1除以總額全部數量。

最後，我想有一個最大35個候選人滿足約束和優化他們的分數總和的集合。

這裏是一個代碼我想出了這麼遠，但我10％的約束上掙扎，因爲它似乎並沒有被考慮在內：

rng('default'); 

clc; 
clear; 
n = 100; 
maxSize = 35; 

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

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

fTop = -score; 
intconTop = [1:1:n]; 

%Write the linear INEQUALITY constraints: 
A = [ones(1,n);bsxfun(@times,typeMask,quantity)'/sum(type.*quantity)]; 
b = [maxSize;0.1*ones(10,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 = intlinprog(fTop,intconTop,A,b,Aeq,beq,lb,ub);

我將不勝感激一些建議，其中我做錯了！

來源

2016-10-03 Tulkkas

你是什麼意思的10％規則？ ** A **：'''sum_amount_kind_x/sum_all_amounts''或** B **：'''sum_amound_kind_x_selected/sum_all_amounts_selected''''。 ** A **是一個簡單的混合整數程序。 ** B **將非常困難（在我看來可能是非凸的）。 – sascha

這裏應該理解10％規則如下：選擇完成後的sum_amount_kind_x，這意味着尊重其他約束，如最大35個元素不應該大於sum_all_amounts_selected的10％。所以我相信這不幸落入你的B類別。因爲基本上A部分沒有什麼意義。我希望在選擇後的每個類別中選擇最多10％。希望澄清一點。 – Tulkkas

爲模型的線性程序可能是這個樣子：

n是候選人的人數。
S[x]是候選人x的得分。
A[i][x]是候選人的數量x種類i（A [i] [x]可以是正數或負數，就像你說的那樣）。
T[i]是所有應聘者的總數i。
I[x]如果要包括要素x則爲1，如果要排除要素x則爲0。

要優化功能f是S[x]和I[x]功能。你可以將S和I視爲n維矢量，所以你想優化的功能是它們的點積。

f() = DotProduct(I, S)

這相當於線性函數I1 * S1 + I2 * S2 + ... + In * Sn。

我們可以通過這種方式制定所有的約束條件，以得到一系列線性函數，其係數因子是尺寸向量中的分量，我們可以用點I（要優化的參數）。

對於約束，我們只能採取35個元素至多，讓C1()是其計算元素的總數的函數。然後，第一約束可以形式化爲C1() <= 35和C1()是線性函數可正是如此計算：

j令是一個n維向量與每個分量等於1：j = <1,1,...,1>。

C1() = DotProduct(I, j)

所以C1() <= 35是一個線性不等式等價於：

I1 * 1 + I2 * 1 + ... + In * 1 <= 35 I1 + I2 + ... + In <= 35

我們需要添加鬆弛變量x1這裏把它變成和等價關係：

I1 + I2 + ... + In + x1 = 35

對於約束我們只能使用每種類型的10％，我們將有一個函數C2[i]()爲每種i（你說有10個）。 C2[i]()計算我們選擇給了學生們採取一種i學生數量：

C21() <= .1 * T1
C22() <= .1 * T2
...
C210() <= .1 * T10

我們計算C2[i]()這樣的：設k是n等於<A[i]1, A[i]2, ..., A[i]n>的三維向量，每個分量是每個候選人的種類數量i。然後DotProduct(I, k) = I1 * A[i]1 + I2 * A[i]2 + ... + In * A[i]n，是我們正在採取的種類i給出的總量I，這是捕獲我們包括的元素的向量。

所以C2[i]() = DotProduct(I, k)

現在我們知道如何計算C2[i]()，我們需要添加鬆弛變量把它變成一個平等的關係：

C2[i]() + x[i + 1] = .1 * T[i]

這裏x的下標是[i + 1]因爲x1已被用作先前約束的鬆弛變量。

總之，線性規劃是這樣的（增加11個鬆弛變量x1, x2, ..., x11因爲這是一個不平等每個約束）：

Let: 
V = <I1, I2, ..., In, x1, x2, ..., x11> (variables) 

    |S1| 
    |S2| 
    |. | 
    |. | 
    |. | 
P = |Sn| (parameters of objective function) 
    |0 | 
    |0 | 
    |. | 
    |. | 
    |. | 
    |0 | 

    |35 |    
    |.1*T1 |    
C = |.1*T2 | (right-hand sides of constraining equality relations)  
    |... |    
    |.1*T10| 


    |1 |1 |...|1 |1|0|...|0| 
    |A1,1 |A1,2 |...|A1,n |0|1|...|0| 
CP = |A2,1 |A2,2 |...|A2,n |0|0|...|0| (parameters of constraint functions) 
    |... |... |...|... |0|0|...|0| 
    |A10,1|A10,2|...|A10,n|0|0|...|1| 

Maximize: 
V x P 

Subject to: 
CP x Transpose(V) = C

但願這是明確的，對不起，可怕的格式。

來源

2016-10-03 17:32:23

這不是一個線性程序。這是一個混合整數程序。我也認爲你誤解了10％的規則（但也許不是;我在評論中提到）。 – sascha

啊，你說得對。應該是，一種給定的種類最多可以包含所選元素的10％，而不是隻能佔總種類的10％。我會修復我的回答 –

也許就是這樣。在更改答案之前，我會先等待答覆。我也很好奇你將如何解決它。我不認爲這會很容易。 – sascha

我相信MIP模型可以看起來像：

這裏i是數據點和j表示該類型。爲了簡單起見，我在這裏假定每種類型都有相同數量的數據點（即Amount(i,j),Score(i,j)是矩陣）。通過限制總和很容易處理更不規則的情況。

10％的規則只適用於金額的總和。我希望這是正確的解釋。如果我們有負面的情況，不確定這是否屬實。

來源

2016-10-04 03:50:46

我想我明白了，但我很難寫下類型上的約束，你稱之爲vlimit。事實上，totalv和vj取決於相同的變量。你會如何在Matlab中編寫這個代碼？我已經試過了：寫出線性不等式約束： A = [ones（1，n）; bsxfun（@times，sectorTopMask，quantityTop）']; b = [maxSize; 0.1 * ones（10,1）。* sum（sum（bsxfun（@ times，sectorTopMask，quantityTop）'，2））]; – Tulkkas

這不是很容易寫在Matlab中，因爲您必須創建兩個大矩陣（一個用於等式約束，另一個用於不等式約束）。每個變量都是這些矩陣中的一列。這是一種痛苦，我擔心它需要一些相當的代碼。 [Here]（http://yetanothermathprogrammingconsultant.blogspot.com/2016/10/matlab-vs-gams-integer-programming.html）是一個可以與其他建模系統相比有多困難的例子。 –

我可以與你分享我目前的代碼嗎？只是爲了看看它是什麼樣子，因爲在我看來，你提供給我的例子似乎簡單得多，但即使找到了解決方案，不知何故10％約束也不受尊重。那麼我相信我會以某種方式給他們寫信。 – Tulkkas

約束下的優化

回答

相關問題