(6)#\[\begin{split}& \mathrm{Maximize:}~ \sum_{g\in GOODS} VALUE[g]\cdot x[g] \\ & \mathrm{subject~to:}~ \\ & \sum_{g\in GOODS} SIZE[g]\cdot x[g] \leq U\end{split}\]

PySIMPLE Sample Code

def optimize(data):
    from pysimple import Problem, Set, Element, IntegerVariable, Sum, Parameter

    # Sets and Parameters
    GOODS = Set(dim=1, value=['缶コーヒー','水入りペットボトル','バナナ','りんご','おにぎり','パン'])
    g = Element(set=GOODS)
    U = Parameter(value=data['CAPACITY'])
    VALUE = Parameter(index=g, value=data['VALUE'])
    SIZE = Parameter(index=g, value=data['SIZE'])

    # Variables
    x = IntegerVariable(index=g, lb=0)

    # Constraint
    prob = Problem(name='knapsack-problem', type=max)
    prob += Sum(SIZE[g]*x[g]) <= U, 'CoCapacity'

    # Objective
    prob += Sum(VALUE[g]*x[g]), 'TotalValue'

    # Solve
    prob.solve()

    # Print
    print(prob.objective.val)
    print(x.val)

data = {
    'CAPACITY': 65,
    'VALUE': {
        '缶コーヒー':    120,
        '水入りペットボトル':    130,
        'バナナ': 80,
        'りんご': 100,
        'おにぎり': 250,
        'パン': 185
    },
    'SIZE': {
        '缶コーヒー': 10,
        '水入りペットボトル': 12,
        'バナナ': 7,
        'りんご': 9,
        'おにぎり': 21,
        'パン': 16,
    },
}
optimize(data)

上記を実行すると次の結果を得る．

Result

[About Nuorium Optimizer]
Nuorium Optimizer 24.1.1 build:ff97c72
	 <with META-HEURISTICS engine "wcsp"/"rcpsp">
	 <with Netlib BLAS>
, Copyright (C) 1991 NTT DATA Mathematical Systems Inc.

[Problem and Algorithm]
PROBLEM_NAME                                 knapsack-problem
NUMBER_OF_VARIABLES                                         6
(#INTEGER/DISCRETE)                                         6
NUMBER_OF_FUNCTIONS                                         2
PROBLEM_TYPE                                     MAXIMIZATION
METHOD                                                SIMPLEX

[Progress]
<preprocess begin>.........<preprocess end>
<iteration begin>
Coefficient Statistics (original problem)
  Coefficient range         [min,max] : [7.00e+00,2.10e+01]
  RHS and bounds            [min,max] : [6.50e+01,6.50e+01]
  Objective                 [min,max] : [8.00e+01,2.50e+02]
Coefficient Statistics (after scaling)
  Coefficient range         [min,max] : [5.99e-01,1.80e+00]
  RHS and bounds            [min,max] : [5.56e+00,5.56e+00]
  Objective                 [min,max] : [5.55e-01,1.73e+00]
  Row scaling range         [min,max] : [-6.94e-03,0.00e+00]
  Column scaling range      [min,max] : [1.00e+00,1.00e+00]
#sol         upper         lower   gap(%)  time(s)  list  mem(MiB)
#1            +inf            -0     +inf      0.0     0       413  sol: init 

<<wcsp tabu search begin>>
  number of column singleton : 0
  skip search . . .
<<wcsp tabu search end>>


        1.2

               770            -0  100.000      0.0     1       413  cut: 2 
               770            -0  100.000      0.0     1       413  cut: 2 
#2             770           760    1.299      0.0     4       413  sol: relax 
#3             770           765    0.649      0.0     3       413  sol: relax 
#4             770           770    0.000      0.0     1       413  sol: relax 
               770           770    0.000      0.0     0       413

<iteration end>

[Result]
STATUS                                                OPTIMAL
VALUE_OF_OBJECTIVE                                        770
SIMPLEX_PIVOT_COUNT                                        24
PARTIAL_PROBLEM_COUNT                                      10
ELAPSED_TIME(sec.)                                       0.00
TotalValue.val=770
x[缶コーヒー].val=3.0
x[水入りペットボトル].val=0.0
x[バナナ].val=2.0
x[りんご].val=0.0
x[おにぎり].val=1.0
x[パン].val=0.0

1.4.1. コメント #

設定された問題を定式化することは以下の点で容易になっている．

表形式にデータを整理 (整然データへと整理) するだけで，定式化に必要な集合であるとか，定数や変数が容易に見出せる点
表の各列について，列に並ぶ値の総和が上下限値の制約や目的関数と直接に関連している点

これらのことから，ナップサック問題は数理最適化の定式化を述べる上で，よく引用されるのだが，ここで暗黙に仮定したことは線形性であることには注意する．

注釈

例えば目的関数は価値の最大化であるが，ナップサックに詰め込む品物組み合わせが人によっては，単純に価値の総和とは限らない．「缶コーヒー」と「おにぎり」は口に合うだろうか．また制約条件についても，ナップサックや品物の形状によっては単純な容量の足し上げで正しいとは限らない．つまり，このような非線形性は考慮に入れていないのである．「この組み合わせが最もコスパがいい！」と無批判に結果を受け止めてはいけないのだ！

教科書的な問題の説明では，こういった線形性の仮定を疑うことは意図することではないが，実務ではこの仮定が理想的すぎて，上で述べた単純なナップサック問題としてそのまま適用できると目論むことは希望的観測となりやすい．

設定された問題ではナップサックの容量や品物のサイズは与えられているものの，その「形」については与えられていなかった．よってナップサック問題を実務に応用する際には，「形」という要素が関係してこないように努めなければならない．例えば，品物は流体のように容器に自在に形を変えることができたり，もしくはサイズは規格化されていて，仮に正方形だとしたとき，サイズ \(n\) とは単位正方形が \(n\) 個寄せ集まったものを意味して容器に個数分詰め合わせるだけで済むといったことである．他にも品物の個別の形はあるものの，ナップサックは柔軟に伸縮できて，容量の上限さえ満たされていれば済むというものである．

こういった事柄が定式化の特徴としてあることも理解しておくと，実際のオペレーションが「形」を考慮する必要があるかどうかが気になるようになり，一段抽象的に見れるようになってくる．

1.4.2. アレンジ #

ナップサックに詰め込める品物は種類ごとに一つまでだと改題した場合を考えよう．この制限を加えると \(0\)-\(1\) ナップサック問題という典型的な \(0\)-\(1\) 整数計画問題となる．つまり整数変数がバイナリ変数となるのだが，このために PySIMPLEでは BinaryVariable と書き換えればよい．

x = BinaryVariable(index=g)

以上の点についてモデルファイルを書き換えると次のとおり．

PySIMPLE Sample Code

def optimize(data):
    from pysimple import Problem, Set, Element, BinaryVariable, Sum, Parameter

    # Sets and Parameters
    GOODS = Set(dim=1, value=['缶コーヒー','水入りペットボトル','バナナ','りんご','おにぎり','パン'])
    g = Element(set=GOODS)
    U = Parameter(value=data['CAPACITY'])
    VALUE = Parameter(index=g, value=data['VALUE'])
    SIZE = Parameter(index=g, value=data['SIZE'])

    # Variables
    x = BinaryVariable(index=g)

    # Constraint
    prob = Problem(name='knapsack-problem', type=max)
    prob += Sum(SIZE[g]*x[g]) <= U, 'CoCapacity'

    # Objective
    prob += Sum(VALUE[g]*x[g]), 'TotalValue'

    # Solve
    prob.solve()

    # Print
    print(prob.objective.val)
    print(x.val)

data = {
    'CAPACITY': 65,
    'VALUE': {
        '缶コーヒー':    120,
        '水入りペットボトル':    130,
        'バナナ': 80,
        'りんご': 100,
        'おにぎり': 250,
        'パン': 185
    },
    'SIZE': {
        '缶コーヒー': 10,
        '水入りペットボトル': 12,
        'バナナ': 7,
        'りんご': 9,
        'おにぎり': 21,
        'パン': 16,
    },
}
optimize(data)

上記を実行すると次の結果を得る．

Result

[About Nuorium Optimizer]
Nuorium Optimizer 26.1.0 build:f2d78da8
	 <with META-HEURISTICS engine "wcsp"/"rcpsp">
	 <with Netlib BLAS>
, Copyright (C) 1991 NTT DATA Mathematical Systems Inc.

[Problem and Algorithm]
PROBLEM_NAME                                 knapsack-problem
NUMBER_OF_VARIABLES                                         6
(#INTEGER/DISCRETE)                                         6
NUMBER_OF_FUNCTIONS                                         2
PROBLEM_TYPE                                     MAXIMIZATION
METHOD                                                SIMPLEX

[Progress]
<preprocess begin>.........<preprocess end>
<iteration begin>
Coefficient Statistics (original problem)
  Coefficient range         [min,max] : [7.00e+00,2.10e+01]
  RHS and bounds            [min,max] : [1.00e+00,6.50e+01]
  Objective                 [min,max] : [8.00e+01,2.50e+02]
Coefficient Statistics (after scaling)
  Coefficient range         [min,max] : [5.99e-01,1.80e+00]
  RHS and bounds            [min,max] : [1.00e+00,5.56e+00]
  Objective                 [min,max] : [5.55e-01,1.73e+00]
  Row scaling range         [min,max] : [-6.94e-03,0.00e+00]
  Column scaling range      [min,max] : [1.00e+00,1.00e+00]
#sol         upper         lower   gap(%)  time(s)  list  mem(MiB)
#1            +inf            -0     +inf      0.0     0       749  sol: init 

<<wcsp tabu search begin>>
  number of column singleton : 0
  number of column selection : 0
  Modify coefficients 
  search target : -173
<preprocess begin>..<preprocess end>
preprocessing time: 0(s) 
<iteration begin>
--- TryCount = 1 ---
# random seed = 1
(hard/semihard/soft) penalty= 0/0/87, time= 0.00(s)
<greedyupdate begin>......<greedyupdate end>
greedyupdate time= 0(s)
(hard/semihard/soft) penalty= 0/0/24, time= 0.00(s), iteration= 0
--- End Phase-I iteration ---
# (hard/semihard/soft) penalty= 0/0/24
# time = 0.00/0.00(s)
# iteration = 0/1000
<iteration end>
# (hard/soft) = 0/24
# iteration = 1000
# time =  0.00 (s), succ = 1
<<wcsp tabu search end>>

#2            +inf           745     +inf      0.0     0       749  sol: wcsp 
               745           745    0.000      0.0     0       749

<iteration end>

[Result]
STATUS                                                OPTIMAL
VALUE_OF_OBJECTIVE                                        745
SIMPLEX_PIVOT_COUNT                                         0
PARTIAL_PROBLEM_COUNT                                       1
ELAPSED_TIME(sec.)                                       0.00
TotalValue.val=745
x[缶コーヒー].val=0.0
x[水入りペットボトル].val=1.0
x[バナナ].val=1.0
x[りんご].val=1.0
x[おにぎり].val=1.0
x[パン].val=1.0

引用書式

BibTeX

ナップサック問題

目次