解决背包问题:组合优化的应用与建模方法

简介: 组合优化是数学优化的一支,专注于从有限集合中选取元素的最优化问题。它涉及将一组对象组合在一起,以满足特定条件并优化某个目标函数,即在所有可能的组合中找到最有利的一个。本文将以一个简化的背包问题为例,来讲解采用数学规划的方法来解决背包这个组合优化问题。

前言

在之前发布的智能解决装箱问题:使用优化算法实现高效包装一文中,我们已经介绍了什么是组合优化问题。这里仅简述:

组合优化是数学优化的一支,专注于从有限集合中选取元素的最优化问题。它涉及将一组对象组合在一起,以满足特定条件并优化某个目标函数,即在所有可能的组合中找到最有利的一个。

本文将以一个简化的背包问题为例,来讲解采用数学规划的方法来解决背包这个组合优化问题。

背包问题

背包问题(Knapsack Problem)和装箱问题(Packing Problem)是两类经典的组合优化问题。虽然在概念上有所相似,都涉及物品的选择和分配,它们的优化目标和具体应用场景却有所不同。


背包问题

目标是在不超过背包容量限制的条件下,选取总价值最大化的物品组合。应用场景广泛,如行李打包、物流、购物选择、广告投放、投资组合、资源分配。


装箱问题

目标是在尽量减少容器数量或最小化容器空余容量的前提下将物品装入箱子。常见的应用场景包括集装箱装载、仓库货物分配、内存分配等。


最明显的区别,是优化目标:

  • 背包问题:最大化所装物品的价值
  • 装箱问题:最小化容器数量


问题描述以及数学规划建模

image.png

假设小美要出远门长住几个月,她带了4个包,需要带更有价值的物品。有一堆物品可以带,如果忽略物品刚性形状,我们假设所有物品都可以变形,评估物品体积、重量和有用价值如表格data/items-1.csv,部分内容如下:


物品ID

物品重量(g)

物品体积(cm^3)

价值因子

1

161

1807

14

2

794

4109

55

3

255

4952

-4

4

841

5773

88

100

753

1231

49


物品和背包属性如下:


  • 物品集合 image.png
  • 它的描述信息参数是 重量 image.png 、尺寸 image.png 和 价值 image.png
  • 假设有背包集合 image.png
  • 它的描述信息参数是 承重上限 image.png 、 尺寸上限 image.png



变量:

  • 货物如何摆放,设置 0-1 变量 image.png ,其中 image.png 。 当变量取值为1的时候,则代表物品装进该背包,为0的时候则不放置。


建模目标和约束条件:

目标函数: image.png


约束条件:

  • 每个货物最多只能放一个位置: image.png
  • 每个货车上,装载的货物重量和体积限制:
  • image.png
  • image.png


MindOpt APL 编程和求解

MindOpt APL是达摩院研发的代数建模语言,国内首款!语法简单!点击了解>>

使用MindOpt APL进行建模和求解。导入背包和物品的数据,定义变量、目标函数和约束,调用求解器获取最优解。

clear model;
option modelname knapsackproblem_01; #定义存储文件名
# ----------建模--------Start----
# knapsackproblem_01.mapl
## 导入数据-------
print "导入数据-------";
param fileDir = "data/";
# 物品数据
param ItemsFilename = "items-1.csv"; # 有10份数据,名字分别是 items-1.csv,items-2.csv……
set Items = {read fileDir+ItemsFilename as "<1n>" skip 1}; #读取货物序号
param ItemWeight[Items] = read fileDir+ItemsFilename as "<1n> 2n" skip 1; #读取物品的重量,单位克g
param ItemSize[Items] = read fileDir+ItemsFilename as "<1n> 3n" skip 1; #读取物品的尺寸,单位立方厘米cm^3
param ItemValue[Items] = read fileDir+ItemsFilename as "<1n> 4n" skip 1; #读取物品的价值,有正有负
print "数据:{}"%ItemsFilename;
print "- 总共有{}个可选择物品,总重量{}g,总体积{}cm^3,总价值{},其中正价值总和{},负价值总和{}"
    % card(Items),
    sum{i in Items}ItemWeight[i],
    sum{i in Items}ItemSize[i],
    sum{i in Items}ItemValue[i],
    sum{i in Items with ItemValue[i] >0 } ItemValue[i],
    sum{i in Items with ItemValue[i] <=0 } ItemValue[i];
# 背包数据
param BagsFilename = "bags.csv";
set Bags = {read fileDir+BagsFilename as "<1n>" skip 1}; #读取货物序号
param BagWeightCapacity[Bags] = read fileDir+BagsFilename as "<1n> 2n" skip 1; #读取包的重量承重,单位克g
param BagSizeCapacity[Bags] = read fileDir+BagsFilename as "<1n> 3n" skip 1; #读取包的体积容量,单位立方厘米cm^3
print "- 总共有{}个可选择物品,承重上限{}g,容积上限{}cm^3"
    % card(Bags),
    sum{b in Bags} BagWeightCapacity[b],
    sum{b in Bags} BagSizeCapacity[b];
## 数学建模-------
print  "数学建模--------------";
# 变量----
var x_Item2Bag[Items*Bags]  >= 0 binary; #物品放哪个包
# 目标----
# 目标函数:最大化所带物品的价值
maximize TotalValue: sum { <i,b> in Items*Bags } x_Item2Bag[i,b] * ItemValue[i];
# 每个物品最多只能放一个位置,且至少是一个位置
subto constraint_0:
    forall {i in Items}
         sum {b in Bags} x_Item2Bag[i,b] <= 1;
# 每个包的容量限制
# 重量
subto constraint_1:
    forall {b in Bags}
            sum { i in Items} x_Item2Bag[i,b] * ItemWeight[i] <= BagWeightCapacity[b];
# 体积
subto constraint_2:
    forall {b in Bags}
            sum { i in Items} x_Item2Bag[i,b] * ItemSize[i] <= BagSizeCapacity[b];
#求解
print  "调用求解器求解--------------";
option solver mindopt;     # (可选)指定求解用的求解器,默认是MindOpt
#option mindopt_options 'max_time=600'; #设置求解器参数
#option mindopt_options 'print=0'; #设置求解器输出级别,减少过程打印
solve;         # 求解
# 结果打印和检查结果
print "结果打印和存文件--------------";
#display; 
print "- 带的物品数 = ",sum { <i,b> in Items*Bags } x_Item2Bag[i,b];
print "- 总价值是 = ",sum { <i,b> in Items*Bags } x_Item2Bag[i,b] * ItemValue[i];
print "- 包里面摆放物品清单:";
print "|背包ID|物品ID|体积|重量|价值|";
print "|--|--|--|--|--|";
# 由于打印太多,只打印小报包的,如需打印全部,可以删除`with b>2 `
forall { b in Bags with b>2 }
    forall { i in Items with  x_Item2Bag[i,b]>= 0.5}
        print "|{}|{}|{}|{}|{}|"%b,i,ItemWeight[i],ItemSize[i],ItemValue[i];
print "|……|……|……|……|……|";
# 存文件
print "背包ID,物品ID,体积,重量,价值": "每个背包的物品清单.csv";
close "每个背包的物品清单.csv";
forall { b in Bags }
    forall { i in Items with  x_Item2Bag[i,b] >= 0.5}
        print "{},{},{},{},{}"%b,i,ItemWeight[i],ItemSize[i],ItemValue[i] >> "每个背包的物品清单.csv";
close "每个背包的物品清单.csv";
print "- 结果文件存储在: [每个背包的物品清单.csv](每个背包的物品清单.csv)";

运行上述代码结果如下:

导入数据-------
数据:items-1.csv
- 总共有100个可选择物品,总重量44795g,总体积326428cm^3,总价值4342,其中正价值总和4411,负价值总和-69
- 总共有4个可选择物品,承重上限34000g,容积上限237000cm^3
数学建模--------------
调用求解器求解--------------
Running mindoptampl
wantsol=1
MindOpt Version 1.1.1 (Build date: 20240306)
Copyright (c) 2020-2024 Alibaba Cloud.
Start license validation (current time : 27-MAR-2024 16:13:18).
License validation terminated. Time : 0.008s
Model summary.
 - Num. variables     : 400
 - Num. constraints   : 108
 - Num. nonzeros      : 1200
 - Num. integer vars. : 400
 - Bound range        : [1.0e+00,1.2e+05]
 - Objective range    : [1.0e+00,9.9e+01]
Branch-and-cut method started.
Original model: nrow = 108 ncol = 400 nnz = 1200
Tolerance: primal = 1e-06 int = 1e-06 mipgap = 0.0001 mipgapAbs = 1e-06
Limit: time = 1.79769313486232e+308 node = -1 stalling = -1 solution = -1
presolver terminated; took 0 ms
presolver terminated; took 9 ms
Parallelism: root=2, tree=2
      accept new sol: obj 0 bnd vio 0 int vio 0 mipgap inf time 0
      accept new sol: obj -4201 bnd vio 0 int vio 0 mipgap 2.57295881932873 time 0
Model summary.
 - Num. variables     : 294
 - Num. constraints   : 94
 - Num. nonzeros      : 882
 - Bound range        : [1.0e+00,1.2e+05]
 - Objective range    : [1.0e+00,9.9e+01]
 - Matrix range       : [1.0e+00,6.0e+03]
Presolver started.
Presolver terminated. Time : 0.000s
Simplex method started.
Model fingerprint: mdXZv92dj5WZ3Nmb
    Iteration       Objective       Dual Inf.     Primal Inf.     Time
            0    -1.50100e+04      0.0000e+00      3.9240e+02     0.00s    
          137    -4.30372e+03      0.0000e+00      0.0000e+00     0.00s    
Postsolver started.
Simplex method terminated. Time : 0.001s
      accept new sol: obj -4211 bnd vio 0 int vio 0 mipgap 0.0220180858248353 time 0
      accept new sol: obj -4290 bnd vio 0 int vio 0 mipgap 0.00319770615579984 time 0
Root relaxation: -4303.71815940838 iteration = 137 time = 0.002
 #node(P:0 Q:0) #(dual:-4303.72 best:-4290 gap:0.32%) #time = 0
      accept new sol: obj -4299 bnd vio 0 int vio 2.81374923361e-15 mipgap 0.00109750160697402 time 0
      accept new sol: obj -4303 bnd vio 6.66133814775094e-16 int vio 0 mipgap 0.000166897375872955 time 1
- Solution pool    : 5
Branch-and-cut method terminated. Time : 1.913s
OPTIMAL; objective 4303.00
Completed.
结果打印和存文件--------------
- 带的物品数 = 75
- 总价值是 = 4303
- 包里面摆放物品清单:
|背包ID|物品ID|体积|重量|价值|
|--|--|--|--|--|
|3|13|650|4889|67|
|3|28|684|5395|36|
|3|38|236|1966|62|
|3|47|379|3467|24|
|3|48|317|3168|94|
|3|74|402|5083|58|
|4|73|250|35|54|
|4|86|50|2411|67|
|4|95|536|510|13|
|……|……|……|……|……|
- 结果文件存储在: [每个背包的物品清单.csv](每个背包的物品清单.csv)

高阶方案尝试

案例发布在云上建模平台中读者可尝试复制本项目,增加难度进行调试。比如:

  1. 在平台中的data文件夹中,我们提供了不同的item.csv数据,如 data/items-2.csv,观察不同数据的结果区别。
  2. 增加物品的其他信息,如类别,标记每个类别里面至少带的数量。
  3. 将此模型推广到其他场景,比如:
  • 在线广告:选择最优化的广告投放组合,以最大化点击率或转化率。
  • 股票投资:如何在有限的资金下,挑选出能带来最大收益的股票组合。
  • 资源分配:如何在有限的资源下,最大化利益。
  • 云计算:在有限的资源下,为各个任务分配最优的资源组合。
  • 学术研究:在有限的资源和时间下,选择最有价值的研究课题。
相关文章
|
6月前
|
存储 算法 程序员
【算法训练-回溯算法 二】【子集组合问题】子集、组合、子集II、组合总和
【算法训练-回溯算法 二】【子集组合问题】子集、组合、子集II、组合总和
58 0
|
6月前
|
机器学习/深度学习 数据采集 监控
机器学习-特征选择:如何使用递归特征消除算法自动筛选出最优特征?
机器学习-特征选择:如何使用递归特征消除算法自动筛选出最优特征?
913 0
|
1月前
|
决策智能
【LeetCode 50】77.组合(优化、剪枝操作)
【LeetCode 50】77.组合(优化、剪枝操作)
15 2
|
4月前
|
机器学习/深度学习 人工智能 分布式计算
算法金 | 最难的来了:超参数网格搜索、贝叶斯优化、遗传算法、模型特异化、Hyperopt、Optuna、多目标优化、异步并行优化
机器学习中的超参数调优是提升模型性能的关键步骤,包括网格搜索、随机搜索、贝叶斯优化和遗传算法等方法。网格搜索通过穷举所有可能的超参数组合找到最优,但计算成本高;随机搜索则在预设范围内随机采样,降低计算成本;贝叶斯优化使用代理模型智能选择超参数,效率高且适应性强;遗传算法模拟生物进化,全局搜索能力强。此外,还有多目标优化、异步并行优化等高级技术,以及Hyperopt、Optuna等优化库来提升调优效率。实践中,应结合模型类型、数据规模和计算资源选择合适的调优策略。
176 0
算法金 | 最难的来了:超参数网格搜索、贝叶斯优化、遗传算法、模型特异化、Hyperopt、Optuna、多目标优化、异步并行优化
|
5月前
|
机器学习/深度学习 算法 vr&ar
Theta方法:一种时间序列分解与预测的简化方法
Theta方法整合了两个基本概念:分解时间序列和利用基本预测技术来估计未来的价值。
142 0
|
6月前
|
数据可视化 Java 数据挖掘
R语言Fama-French三因子模型实际应用:优化投资组合
R语言Fama-French三因子模型实际应用:优化投资组合
|
6月前
|
数据可视化
R语言两层2^k析因试验设计(因子设计)分析工厂产量数据和Lenth方法检验显著性可视化|数据分享(一)
R语言两层2^k析因试验设计(因子设计)分析工厂产量数据和Lenth方法检验显著性可视化|数据分享(一)
|
算法 调度 决策智能
【两阶段鲁棒优化】利用列-约束生成方法求解两阶段鲁棒优化问题(Python代码实现)
【两阶段鲁棒优化】利用列-约束生成方法求解两阶段鲁棒优化问题(Python代码实现)
326 0
【两阶段鲁棒优化】利用列-约束生成方法求解两阶段鲁棒优化问题(Python代码实现)
|
自然语言处理 算法 C++
探索动态规划:优化问题求解的高效策略
探索动态规划:优化问题求解的高效策略
64 0
Matlab:如何利用层次分析法(升级版)计算具有多重指标的判断矩阵的一致性检验和权重
Matlab:如何利用层次分析法(升级版)计算具有多重指标的判断矩阵的一致性检验和权重
349 0