约束下的优化

我有一个关于优化的问题。约束下的优化

我有一个矩阵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

约束下的优化

回答

相关问题