sample.bin_packing のソースコード

# -*- coding: utf-8 -*-
from itertools import combinations
from random import sample, seed; seed(0)

from pysimple import Element, Parameter, BinaryVariable, Problem, NuoptStatus, Sum
from pysimple.typing import Table
from .column_generator import ColumnGenerator

class BinPacking(ColumnGenerator):
    """ビンパッキング問題"""
    def __init__(self, binsize: int, sizevalue: dict[str, int]) -> None:
        self.binsize = binsize      # ビンのサイズ
        self.sizevalue = sizevalue  # アイテムのサイズ

    def create_init_pattern(self) -> None:
        pattern = dict.fromkeys(enumerate(self.sizevalue, 1), 1)
        super().create_init_pattern(pattern=pattern)

    def create_new_pattern(self, lmbval: Table, *, silent: bool=True) -> tuple[Table, Table]:
        """ビンに収まるアイテムの組合せを 1 つ生成する"""
        i = Element(value=self.sizevalue.keys())   # アイテム
        size = Parameter(index=i, value=self.sizevalue)  # アイテム i のサイズ
        lmb = Parameter(index=i, value=lmbval, name='λ')
        z = BinaryVariable(index=i)  # アイテム i を使用するか
        prb = Problem(type=max)
        prb += Sum(size[i]*z[i]) <= self.binsize, 'アイテムをビンに収める'
        prb += Sum(lmb[i]*z[i])
        prb.solve(silent=silent)
        assert prb.status == NuoptStatus.OPTIMAL
        return z[z[i].val>0].val, prb.objective.val

    def visualize(self, zval: Table) -> None:
        """結果表示"""
        for (p,), val in zval.items():
            lentimes = [(len_, self.pattern[p,t]) for t, len_ in self.sizevalue.items() if (p, t) in self.pattern]
            pstr = '+'.join(f'{l}{(f"*{times}","")[times==1]}' for l, times in lentimes)
            line = '+'+''.join(('-'*(l-1)+'+')*times for l, times in lentimes)
            print(f'pattern{p:2}({pstr:^15}){val:2}枚: {line}')

def create_init_data(*, binsize: int, N: int) -> tuple[int, dict[str, int]]:
    """binsize: ビンサイズ, N: アイテム種類数"""
    I = [f'item{t}' for t in range(1, N+1)]                      # アイテムの種類
    sizevalue = dict(zip(I, sample(range(1, binsize//2+1), N)))  # アイテムの長さ(重複無し)
    return binsize, sizevalue

def at_once(binsize: int, sizevalue: dict[str, int], *, silent: bool=True) -> None:
    """一度に全部解く"""
    i = Element(value=sizevalue.keys())   # アイテム
    j = Element(value=range(len(i.set)))  # ビン(数は上限のアイテム数とする)
    size = Parameter(index=i, value=sizevalue)  # アイテム i のサイズ
    z = BinaryVariable(index=(i,j))  # アイテム i をビン j に収納するか
    w = BinaryVariable(index=j)      # ビン j を使用するか
    p = Problem()
    p += Sum(z[i,j], j) == 1 , 'いずれかのビンに入れる'
    p += Sum(size[i]*z[i,j], i) <= binsize*w[j],  'アイテムをビンに収める'
    p += Sum(w[j])  # ビンの本数
    p.solve(silent=silent)
    assert p.status == NuoptStatus.OPTIMAL
    print(w[w[j].val>0].val)    # 使ったビン
    print(z[z[i,j].val>0].val)  # 選ばれたアイテムとビンの組合せ

def enumerate_all_patterns(binsize: int, sizevalue: dict[str, int]) -> None:
    """全列挙で解く"""
    # 長さが binsize 以下になる size の組合せを全列挙する
    s2i = {s: i for i, s in sizevalue.items()}  # size -> item
    patterns: list[tuple[int, str]] = []
    p = 1
    for i in range(len(s2i)):
        for comb in combinations(s2i, i+1):
            if sum(comb) <= binsize:
                patterns.extend((p, s2i[s]) for s in comb)
                p += 1

    bp = BinPacking(binsize, sizevalue)
    ColumnGenerator.create_init_pattern(bp, pattern=dict.fromkeys(patterns, 1))
    zval, _ = bp.select_pattern()
    bp.visualize(zval)  # 結果表示

def column_generation(binsize: int, sizevalue: dict[str, int]) -> None:
    """列生成で解く"""
    bp = BinPacking(binsize, sizevalue)
    zval = bp.solve(eps=1)
    bp.visualize(zval)  # 結果表示


if __name__ == '__main__':
    BINSIZE, SIZEVALUE = create_init_data(binsize=70, N=30)

    # 素直な定式化で解く
    #at_once(BINSIZE, SIZEVALUE)

    # 全列挙で解く
    #enumerate_all_patterns(BINSIZE, SIZEVALUE)

    # 列生成で解く
    column_generation(BINSIZE, SIZEVALUE)