sample.cutting_stock のソースコード

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

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

class CuttingStock(ColumnGenerator):
    """カッティングストック問題"""
    def __init__(self, L: int, lenvalue: dict[str, int], reqvalue: dict[str, int]) -> None:
        self.L = L                # 母材の長さ
        self.lenvalue = lenvalue  # 木材の長さ
        self.reqvalue = reqvalue  # 木材の必要本数

    def create_init_pattern(self) -> None:
        pattern = {(p, t): self.L // v for p, (t, v) in enumerate(self.lenvalue.items(), 1)}
        super().create_init_pattern(pattern=pattern, b=self.reqvalue)

    def create_new_pattern(self, lmbval: Table, *, silent: bool=True) -> tuple[Table, Table]:
        """母材に収まる木材の組合せを 1 つ生成する"""
        t = Element(value=self.lenvalue.keys())
        len_ = Parameter(index=t, value=self.lenvalue)
        lmb = Parameter(index=t, value=lmbval, name='λ')
        z = IntegerVariable(index=t, lb=0)  # タイプ t の木材を幾つ使用するか
        prb = Problem(type=max)
        prb += Sum(len_[t]*z[t], t) <= self.L  # 母材 L に収まるパターン
        prb += Sum(lmb[t]*z[t], t)  # なるべくたくさん使う(λ による重みつけ和)
        prb.solve(silent=silent)
        assert prb.status == NuoptStatus.OPTIMAL
        return z[z[t].val>0].val, prb.objective.val

    def select_pattern(self, *, vtype=int, silent: bool=True) -> tuple[Table, Table]:  # 主問題
        """生成されたパターンから需要を満たす組合せを選択する"""
        return super().select_pattern(vtype=vtype, silent=silent)

    def visualize(self, zval: Table) -> None:
        """結果表示"""
        for (p,), val in zval.items():
            lentimes = [(len_, self.pattern[p,t]) for t, len_ in self.lenvalue.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(*, L: int, N: int) -> tuple[int, dict[str, int], dict[str, int]]:
    """L: 母材の長さ, N: 切り出す木材の種類の数"""
    T = [f'type{t}' for t in range(1, N+1)]  # 切り出す木材の種類
    # 木材の長さ(L の 10%～40% 重複無し)
    lenvalue = dict(zip(T, sample(range(int(L*0.1), int(L*0.4)), N)))
    reqvalue = {t: randint(5, 30) for t in T}   # 木材の必要本数
    return L, lenvalue, reqvalue


if __name__ == '__main__':
    L, LENVALUE, REQVALUE = create_init_data(L=80, N=20)
    cs = CuttingStock(L, LENVALUE, REQVALUE)
    ZVAL = cs.solve(eps=1)
    cs.visualize(ZVAL)