诚心请教混合整数规划的问题～

问题如下：
We have a list of N items that each cost [0-50$] (integer) to purchase and M shoppers.
Each shopper has a maximum of 100$ available that they can spend.

Solve this with the following constraints –
1.        Minimize the number of shoppers used
2.        If we need to use more than 1 shopper, minimize the variance in $ spent by the shoppers

Examples
1.        5 items costing [10,20,20,5,10]
Solution = 1 shopper who buys all the items
We can use 1 shopper since total is $65 which is less than the maximum of $100 available to one shopper.

2.        5 items costing [50,15,30,30,10]
Solution = Shopper 1 buys [50,15] and shopper 2 buys [30,30,10]

We need to use 2 shoppers since total is > 100.

What should my objective function be for this problem?

如果没有第2个要求，方法应该是
Variables:
    M*N variables x_{i,j}, i=1,...,M, j=1,...,N where x_{i,j}=1 iff shopper i is used to buy item j，
    M variables y_i, i=1...M where y_i=1 iff shopper is used
Constraints:
    y_i >= sum_{j}^N x_{i,j}, for all i.   -- if shopper i buys at least one item, then he is used
    sum_{i}^M x_{i,j} >= 1, for all j.  -- every item must be bought by one shopper
    sum_{j}^N ( x_{i,j}*p_{j} ) <= 100, for all i. -- the total cost of items bought by shopper i can not exceeds the $100 budget
    x_{i,j}, y_{i,j} in {0,1},
Objective function:
    sum_{i}^M y_i  

如果加了第二个要求的话，min variance有平方我觉得线性整数规划不太可行，如果是deviation的话，大概方法把deviation里面的绝对值转换一下，然后在目标函数加上deviation的项，因为题目有价格的范围，所以给sum_{i}^M y_i  乘上一个足够大的权重，这样只有sum_{i}^M y_i 相等的时候第二项才会起作用。

帮忙解决的有赏，虽然还不知道怎么赏。

Create variables x_i, i=1,..., M
x_i=1 if we need to use shopper i, x_i=0 otherwise
The objective function is min sum_{i=1}^M x_i

luo_luyang3 发表于 2020-7-16 23:42
Create variables x_i, i=1,..., M
x_i=1 if we need to use shopper i, x_i=0 otherwise
The objective  ...

第二个minimize variance的目标怎么处理？

楼上正解。我之前忽略了第二个目标。补充一下，第一个constraint应该是N*y_i >= sum_{j}^N x_{i,j}, 因为式子右边是有可能大于1的。
如楼上所说第二个要求用线性不太可行，如果不要求用线性的话，objective function应该是 sum_{i}^N (sum_{j}^M x_{ij}*p_j - C)^2, where C= sum_{j}^M p_j / sum_{i}^M y_i.

variance objective是convex的么？ 是MIQP么？

reab 发表于 2020-7-17 07:53
如果没有第2个要求，方法应该是
Variables:
    M*N variables x_{i,j}, i=1,...,M, j=1,...,N where x_{ ...

variance objective是convex的么？ 是MIQP么？

reab 发表于 2020-7-17 07:53
如果没有第2个要求，方法应该是
Variables:
    M*N variables x_{i,j}, i=1,...,M, j=1,...,N where x_{ ...

是朋友的提问。我完全不懂哈哈。后来用bean packing解决的。

多谢大家的解答，最后bean packing解决的。