• 90、一维装箱

    数据集

    Bin packing - one-dimensional

    整数规划建模

    1.  
    2. import pyscipopt
    3. import re
    4. import time
    5. import math
    6. #记录每个函数执行的时间
    7. loop = 1
    8. def timeLog(f):
    9.     def wrapper(*args, **kw):
    10.         global loop
    11.         now = time.perf_counter()
    12.         res = f(*args, **kw)
    13.         print("%s-%s:"%(loop, f.__name__), time.perf_counter()-now)
    14.         loop += 1
    15.         return res
    16.     return wrapper
    17.  
    18. class Case:
    19.  
    20.     def __init__(self, name, box, goods, boxUsedMin):
    21.         self.name = name
    22.         self.box = box
    23.         self.goods = goods
    24.         self.boxUsedMin = boxUsedMin
    25.  
    26.     def __repr__(self):
    27.         return str([self.name, self.box, self.goods, self.boxUsedMin])
    28.  
    29. def dataRead():
    30.     data_paths = [r"/Users/zhangchaoyu/PycharmProjects/pythonProject/OR_Library/BPP1D/data/binpack1.txt",
    31.                   r"/Users/zhangchaoyu/PycharmProjects/pythonProject/OR_Library/BPP1D/data/binpack2.txt",
    32.                   r"/Users/zhangchaoyu/PycharmProjects/pythonProject/OR_Library/BPP1D/data/binpack3.txt",
    33.                   r"/Users/zhangchaoyu/PycharmProjects/pythonProject/OR_Library/BPP1D/data/binpack4.txt",
    34.                   r"/Users/zhangchaoyu/PycharmProjects/pythonProject/OR_Library/BPP1D/data/binpack5.txt",
    35.                   r"/Users/zhangchaoyu/PycharmProjects/pythonProject/OR_Library/BPP1D/data/binpack6.txt",
    36.                   r"/Users/zhangchaoyu/PycharmProjects/pythonProject/OR_Library/BPP1D/data/binpack7.txt",
    37.                   r"/Users/zhangchaoyu/PycharmProjects/pythonProject/OR_Library/BPP1D/data/binpack8.txt"]
    38.  
    39.     cases = []
    40.     for path in data_paths:
    41.         f = open(path)
    42.         #一个文件中的case个数
    43.         num = int(f.readline())
    44.         for _ in range(num):
    45.             name = f.readline().replace('\n', '').strip()
    46.             row = f.readline().replace('\n', '').strip()
    47.             row = [float(w) for w in re.split(" ", row)]
    48.             box, numGoods, boxUsedMin = row[0], int(row[1]), int(row[2])
    49.             goods = []
    50.             for _ in range(numGoods):
    51.                 goods.append(float(f.readline()))
    52.             cases.append(Case(name, box, goods, boxUsedMin))
    53.  
    54.     return cases
    55.  
    56. def caseStandardization(cases):
    57.     for case in cases:
    58.         #确认需要乘多少
    59.         n = 1
    60.         while case.box * n != int(case.box * n):
    61.             n *= 10
    62.         for good in case.goods:
    63.             while good * n != int(good * n):
    64.                 n *= 10
    65.         #都乘以这个数，化为整数
    66.         case.box = int(case.box * n)
    67.         for i in range(len(case.goods)):
    68.             case.goods[i] = int(case.goods[i] * n)
    69.  
    70. #启发式方法得到箱子数上界
    71. def NF(case):
    72.     L_goods = [[]]
    73.     box = case.box
    74.     boxLeft = box
    75.     for good in case.goods:
    76.         if good <= boxLeft:
    77.             boxLeft -= good
    78.             L_goods[-1].append(good)
    79.         else:
    80.             boxLeft = box - good
    81.             L_goods.append([good])
    82.     return len(L_goods)
    83.  
    84. def IPBPP1D(case, time_limit = 1000, printLog = False):
    85.  
    86.     m = NF(case)
    87.     n = len(case.goods)
    88.     W = case.goods
    89.     V = case.box
    90.     mMin = math.ceil(sum(case.goods)/case.box)
    91.     model = pyscipopt.Model("IPBPP1D")
    92.  
    93.     Y = [model.addVar(vtype="B", name="Y[%s]" % i) for i in range(m)]
    94.     X = [[model.addVar(vtype="B", name="X[%s,%s]" % (i, j)) for j in range(n)] for i in range(m)]
    95.     model.setObjective(pyscipopt.quicksum(Y[i] for i in range(m)), "minimize")
    96.  
    97.     #每个箱子启用后才能进行装载
    98.     for i in range(m):
    99.         model.addCons(pyscipopt.quicksum(W[j]*X[i][j] for j in range(n)) <= V*Y[i])
    100.  
    101.     #每个good都被装下
    102.     for j in range(n):
    103.         model.addCons(pyscipopt.quicksum(X[i][j] for i in range(m)) == 1)
    104.  
    105.     #体积约束
    106.     model.addCons(pyscipopt.quicksum(Y[i] for i in range(m)) >= mMin)
    107.  
    108.     # 设置求解时间
    109.     model.setRealParam("limits/time", time_limit)
    110.     if not printLog:
    111.         model.hideOutput()
    112.     model.optimize()
    113.     print("\ngap:", model.getGap())
    114.  
    115.     # 拿结果
    116.     Y1 = [round(model.getVal(Y[i])) for i in range(m)]
    117.     X1 = [[round(model.getVal(X[i][j])) for j in range(n)] for i in range(m)]
    118.  
    119.     return Y1, X1
    120.  
    121. if __name__ == '__main__':
    122.     cases = dataRead()
    123.     caseStandardization(cases)
    124.     case = cases[0]
    125.     Y, X = IPBPP1D(case, printLog=True)
    126.

    启发式算法

    1.  
    2. import re
    3. import time
    4. from BPP.meta_heuristic.Two_opt import two_opt
    5.  
    6. #记录每个函数执行的时间
    7. loop = 1
    8. def timeLog(f):
    9.     def wrapper(*args, **kw):
    10.         global loop
    11.         now = time.perf_counter()
    12.         res = f(*args, **kw)
    13.         print("%s-%s:"%(loop, f.__name__), time.perf_counter()-now)
    14.         loop += 1
    15.         return res
    16.     return wrapper
    17.  
    18. class Case:
    19.  
    20.     def __init__(self, name, box, goods, boxUsedMin):
    21.         self.name = name
    22.         self.box = box
    23.         self.goods = goods
    24.         self.boxUsedMin = boxUsedMin
    25.  
    26.     def __repr__(self):
    27.         return str([self.name, self.box, self.goods, self.boxUsedMin])
    28.  
    29. def dataRead():
    30.     data_paths = [r"/Users/zhangchaoyu/PycharmProjects/pythonProject/OR_Library/BPP1D/data/binpack1.txt",
    31.                   r"/Users/zhangchaoyu/PycharmProjects/pythonProject/OR_Library/BPP1D/data/binpack2.txt",
    32.                   r"/Users/zhangchaoyu/PycharmProjects/pythonProject/OR_Library/BPP1D/data/binpack3.txt",
    33.                   r"/Users/zhangchaoyu/PycharmProjects/pythonProject/OR_Library/BPP1D/data/binpack4.txt",
    34.                   r"/Users/zhangchaoyu/PycharmProjects/pythonProject/OR_Library/BPP1D/data/binpack5.txt",
    35.                   r"/Users/zhangchaoyu/PycharmProjects/pythonProject/OR_Library/BPP1D/data/binpack6.txt",
    36.                   r"/Users/zhangchaoyu/PycharmProjects/pythonProject/OR_Library/BPP1D/data/binpack7.txt",
    37.                   r"/Users/zhangchaoyu/PycharmProjects/pythonProject/OR_Library/BPP1D/data/binpack8.txt"]
    38.  
    39.     cases = []
    40.     for path in data_paths:
    41.         f = open(path)
    42.         #一个文件中的case个数
    43.         num = int(f.readline())
    44.         for _ in range(num):
    45.             name = f.readline().replace('\n', '').strip()
    46.             row = f.readline().replace('\n', '').strip()
    47.             row = [float(w) for w in re.split(" ", row)]
    48.             box, numGoods, boxUsedMin = row[0], int(row[1]), int(row[2])
    49.             goods = []
    50.             for _ in range(numGoods):
    51.                 goods.append(float(f.readline()))
    52.             cases.append(Case(name, box, goods, boxUsedMin))
    53.  
    54.     return cases
    55.  
    56. def caseStandardization(cases):
    57.     for case in cases:
    58.         #确认需要乘多少
    59.         n = 1
    60.         while case.box * n != int(case.box * n):
    61.             n *= 10
    62.         for good in case.goods:
    63.             while good * n != int(good * n):
    64.                 n *= 10
    65.         #都乘以这个数，化为整数
    66.         case.box = int(case.box * n)
    67.         for i in range(len(case.goods)):
    68.             case.goods[i] = int(case.goods[i] * n)
    69.  
    70. #next fit，一个个的打开箱子，将物品装进去，如果装不下就开一个新的箱子
    71. def NF(box, goods):
    72.     L_goods = [[]]
    73.     boxLeft = box
    74.     for good in goods:
    75.         if good <= boxLeft:
    76.             boxLeft -= good
    77.             L_goods[-1].append(good)
    78.         else:
    79.             boxLeft = box - good
    80.             L_goods.append([good])
    81.     return len(L_goods)
    82.  
    83. #first fit，检查所有非空箱子，找第一个非空箱子放进去
    84. def FF(box, goods):
    85.     L_goods = [[]]
    86.     L_boxLeft = [box]
    87.     for good in goods:
    88.         flag = False
    89.         for i in range(len(L_boxLeft)):
    90.             if good <= L_boxLeft[i]:
    91.                 L_boxLeft[i] -= good
    92.                 L_goods[i].append(good)
    93.                 flag = True
    94.                 break
    95.         if not flag:
    96.             L_boxLeft.append(box - good)
    97.             L_goods.append([good])
    98.     return len(L_goods)
    99.  
    100. #first fit Decreasing，先降序排序，再FF
    101. def FFD(box, goods):
    102.     goods1 = sorted(goods, reverse=True)
    103.     return FF(box, goods1)
    104.  
    105. #best fit，检查所有非空箱子，找剩余空间最小的放进去
    106. def BF(box, goods):
    107.     L_goods = [[]]
    108.     L_boxLeft = [box]
    109.     for good in goods:
    110.         idx, leftMin = None, None
    111.         for i in range(len(L_boxLeft)):
    112.             if good <= L_boxLeft[i]:
    113.                 if leftMin is None or leftMin > L_boxLeft[i]:
    114.                     idx = i
    115.                     leftMin = L_boxLeft[i]
    116.         if idx is not None:
    117.             L_boxLeft[idx] -= good
    118.             L_goods[idx].append(good)
    119.         else:
    120.             L_boxLeft.append(box - good)
    121.             L_goods.append([good])
    122.     return len(L_goods)
    123.  
    124. #best fit Decreasing，先降序排序，再BF
    125. def BFD(box, goods):
    126.     goods1 = sorted(goods, reverse=True)
    127.     return BF(box, goods1)
    128.  
    129. #打散顺序，然后采用FF和BF尝试
    130. def twoOpt(box, goods):
    131.     goods1 = sorted(goods, reverse=True)
    132.     X = goods1
    133.     def f(X, **kwargs):
    134.         return FF(kwargs['box'], X)
    135.     def f2(X, **kwargs):
    136.         return BF(kwargs['box'], X)
    137.     def c(X):
    138.         return True
    139.     def e(x,y):
    140.         if x == y:
    141.             return True
    142.         return False
    143.  
    144.     X1 = two_opt(X, f, c, e, False, 100, box=box)
    145.     X2 = two_opt(X, f2, c, e, False, 100, box=box)
    146.  
    147.     return min(FF(box, X1),BF(box, X2))
    148.  
    149. def runOne(case):
    150.     box, goods = case.box, case.goods
    151.  
    152.     #NF
    153.     boxUsedNF = NF(box, goods)
    154.  
    155.     #FF
    156.     boxUsedFF = FF(box, goods)
    157.     boxUsedFFD = FFD(box, goods)
    158.  
    159.     #BF
    160.     boxUsedBF = BF(box, goods)
    161.     boxUsedBFD = BFD(box, goods)
    162.  
    163.     #twoOpt
    164.     boxUsedTwoOpt = twoOpt(box, goods)
    165.  
    166.     print("\nname: ", case.name)
    167.     print("opt: ", case.boxUsedMin)
    168.     print("boxUsedNF: ", boxUsedNF)
    169.     print("boxUsedFF: ", boxUsedFF)
    170.     print("boxUsedFFD: ", boxUsedFFD)
    171.     print("boxUsedBF: ", boxUsedBF)
    172.     print("boxUsedBFD: ", boxUsedBFD)
    173.     print("boxUsedTwoOpt: ", boxUsedTwoOpt)
    174.     return case.boxUsedMin, boxUsedNF, boxUsedFF, boxUsedFFD, boxUsedBF, boxUsedBFD, boxUsedTwoOpt
    175.  
    176. def gapCount(L_opt, L):
    177.     L_gap = [(L[i]-L_opt[i])/L_opt[i] for i in range(len(L_opt))]
    178.     return sum(L_gap)/len(L_gap)
    179.  
    180. def runAll(cases):
    181.     L_opt = []
    182.     L_NF = []
    183.     L_FF = []
    184.     L_FFD = []
    185.     L_BF = []
    186.     L_BFD = []
    187.     L_twoOpt = []
    188.     for case in cases:
    189.         boxUsedMin, boxUsedNF, boxUsedFF, boxUsedFFD, boxUsedBF, boxUsedBFD, boxUsedTwoOpt = runOne(case)
    190.         L_opt.append(boxUsedMin)
    191.         L_NF.append(boxUsedNF)
    192.         L_FF.append(boxUsedFF)
    193.         L_FFD.append(boxUsedFFD)
    194.         L_BF.append(boxUsedBF)
    195.         L_BFD.append(boxUsedBFD)
    196.         L_twoOpt.append(boxUsedTwoOpt)
    197.  
    198.     #统计gap
    199.     gapNF = gapCount(L_opt, L_NF)
    200.     gapFF = gapCount(L_opt, L_FF)
    201.     gapFFD = gapCount(L_opt, L_FFD)
    202.     gapBF = gapCount(L_opt, L_BF)
    203.     gapBFD = gapCount(L_opt, L_BFD)
    204.     gaptwoOpt = gapCount(L_opt, L_twoOpt)
    205.     print("\ngapNF: ", gapNF)
    206.     print("gapFF: ", gapFF)
    207.     print("gapFFD: ", gapFFD)
    208.     print("gapBF: ", gapBF)
    209.     print("gapBFD: ", gapBFD)
    210.     print("gaptwoOpt: ", gaptwoOpt)
    211.  
    212.  
    213. if __name__ == '__main__':
    214.     cases = dataRead()
    215.     caseStandardization(cases)
    216.     runAll(cases)
    217.  
    218.

  • 相关阅读:
    【优化算法】最小均值 (LMF) 和最小均方 (LMS) 算法【含Matlab源码 2134期】
    vue3使用router.push()页面跳转后，该页面不刷新问题
    什么是智能视频美颜SDK？
    2023年【电工（中级）】考试题库及电工（中级）模拟考试
    【论文|复现]Vertebra-Focused Landmark Detection For Scoliosis Assessment
    【Linux从0到1】第十七篇：高级IO
    隐写术----LSB隐写
    java 连接SSH工具操作服务器 (构建者模式+Util类) 分享
    深度学习——动物数据集大合集（附下载地址）
    C语言刷题（一）
  • 原文地址：https://blog.csdn.net/chaoyuzhang/article/details/133269602