一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
Offer多多
Salarytics
交友
Learn
Who's Hiring?
Visa Tracker
疫情动态
指尖新闻
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
查看: 661|回复: 9
收起左侧

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

[复制链接] |只看干货 |机器学习
我的人缘0

升级   54%


分享帖子到朋友圈
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (52)
 
 
0% (0)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
问题如下:
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?
我的人缘0

升级   25.43%

reab 2020-7-17 07:53:37 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (80)
 
 
0% (0)    👎
如果没有第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 相等的时候第二项才会起作用。

评分

参与人数 1大米 +1 收起 理由
redSonja113 + 1 多谢啦 解决啦

查看全部评分

回复

使用道具 举报

我的人缘0

升级   54%

 楼主| redSonja113 2020-7-16 11:53:30 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (52)
 
 
0% (0)    👎
帮忙解决的有赏,虽然还不知道怎么赏。
回复

使用道具 举报

我的人缘0

升级   0.5%

luo_luyang3 2020-7-16 23:42:51 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (6)
 
 
0% (0)    👎
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

评分

参与人数 1大米 +1 收起 理由
redSonja113 + 1 非常感谢

查看全部评分

回复

使用道具 举报

我的人缘0

升级   25.43%

reab 2020-7-17 04:31:01 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (80)
 
 
0% (0)    👎
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的目标怎么处理?
回复

使用道具 举报

我的人缘0

升级   0.5%

luo_luyang3 2020-7-17 10:38:55 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (6)
 
 
0% (0)    👎
楼上正解。我之前忽略了第二个目标。补充一下,第一个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.
回复

使用道具 举报

我的人缘0

升级   60.71%

abby3 2020-7-17 15:44:12 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   84% (1542)
 
 
15% (289)    👎
variance objective是convex的么? 是MIQP么?
回复

使用道具 举报

我的人缘0

升级   60.71%

abby3 2020-7-17 15:46:09 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   84% (1542)
 
 
15% (289)    👎
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么?
回复

使用道具 举报

我的人缘0

升级   54%

 楼主| redSonja113 2020-7-19 01:53:06 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (52)
 
 
0% (0)    👎
reab 发表于 2020-7-17 07:53
如果没有第2个要求,方法应该是
Variables:
    M*N variables x_{i,j}, i=1,...,M, j=1,...,N where x_{ ...

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

使用道具 举报

我的人缘0

升级   54%

 楼主| redSonja113 2020-7-19 01:53:32 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (52)
 
 
0% (0)    👎
多谢大家的解答,最后bean packing解决的。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

Some icons made by Freepik from flaticon.com

快速回复 返回顶部 返回列表