求解器

https://github.com/Diego-Fabbri/Multiple-Knapsack-Problem

大纲

  • 背包问题及其引例：
    • 0-1背包问题(0-1 Knapsack Problem)
    • 多维背包问题（Multi-dimensional Knapsack Problem）：MKP（Multidimensional Knapsack Problem）被称为多维背包问题，也叫多约束背包问题。MKP较单约束背包问题不同在于每个物品消耗的资源并不是单一的。在单约束背包问题中，物品只消耗一个资源属性，即重量，物品的装入只受重量的约束，而在多约束背包问题中，物品有多个消耗属性，比如重量，体积等等，物品的装入就变得更加复杂。
  • 不可行解处理方法总结
  • 修复法及其实例介绍
  • 提速技巧及其总结
  • 求解结果及分析
    • 遗传算法参数
  • 解处理策略
    • 看文献，实现文献中的两种repair算子：在MKP问题中，修补算子的含义是解可行化的一种方式。
      • 第一阶段（drop操作）主要是保证解可行，其将值为1的变量元启发式算法求解0-1整数规划问题 - 图1首先按照元启发式算法求解0-1整数规划问题 - 图2从小到大排序，然后按照顺序将元启发式算法求解0-1整数规划问题 - 图3的值由1变为0，直到解可行。
      • 第二阶段（add操作)主要作用是提高解的质量。
  • RO1 计算影子价格：介绍，但是不计算

元启发式算法求解0-1整数规划问题 - 图4

转化为
元启发式算法求解0-1整数规划问题 - 图5

其中元启发式算法求解0-1整数规划问题 - 图6是原问题的线性松弛问题的子问题的对偶变量值。转换后每个变量的伪效用如公式（7）
元启发式算法求解0-1整数规划问题 - 图7

文献
[1] The 0/1 Multidimensional Knapsack Problem and Its Variants: A Survey of Practical Models and Heuristic Approaches
[2] 可以查到一些最新的相关文章：https://www.researchgate.net/publication/225487545_Greedy_algorithm_for_the_general_multidimensional_knapsack_problem
[3] https://piasekhgw.medium.com/multidimensional-knapsack-problem-distributed-218ecf64b0a 一个范例
[4] 策略算法工程师之路-背包问题及应用