Knapsack Problem

이강우 & 김정자. (2012). EXCEL 2010 경영과학. 한경사, 380.

Table 1. Example

Items	Weights (kg)	Values	Max weight (kg)
1	3	6	6
2	4	8
3	2	3

단일품목 배낭문제의 최적 정수해를 구하기 위한 정수계획모형을 정식화하기 위하여 품목 1, 품목2, 품목 3을 각각 결정변수 $X_{1}$, $X_{2}$, $X_{3}$이라고 정의하고 다음과 같이 $0-1$변수로 정의하자.

\[\begin{split}X_{j} = \begin{cases}1: \text{if item $j$ is selected } (j=1,2,3)\\ 0: \text{if item $j$ is not selected } (j=1,2,3) \end{cases}\end{split}\]

위에서 정의한 결정변수를 이용하여 배낭에 넣어 갖고 갈 수 있는 품목의 효용을 최대화하는 목적함수와 배낭의 보관능력에 대한 제약식을 정식화하면 다음과 같다.

\[\begin{split}\begin{align*} & \text{maximize } & Z=7&X_{1} + 8X_{2} + 3X_{3} \\ & \text{subject to } & \, 3&X_{1} + 4X_{2} + 2X_{3} \le 6 \\ & \text{and} & \, &X_{j} = 0 \text{ or } 1 (j=1,2,3) \end{align*}\end{split}\]

import os
import sys

# Add the parent directory for importing custom library
sys.path.insert(0, os.path.abspath(os.path.join(os.getcwd(), os.pardir)))

Optimization with PuLP

from pulp import *
from ortools.utils import output

# Define problem
prob = LpProblem('Knapsack Problem', LpMaximize)

# Create decision variables and non-negative constraint
x1 = LpVariable(name='X1', lowBound=0, cat='Binary')
x2 = LpVariable(name='X2', lowBound=0, cat='Binary')
x3 = LpVariable(name='X3', lowBound=0, cat='Binary')

# Set objective function
prob += 7*x1 + 8*x2 + 3*x3

# Set constraints
prob += 3*x1 + 4*x2 + 2*x3 <= 6

# Solving problem
prob.solve()
output(prob)

---------------------------------------------------------------------------
ModuleNotFoundError                       Traceback (most recent call last)
Cell In[2], line 1
----> 1 from pulp import *
      2 from ortools.utils import output
      4 # Define problem

ModuleNotFoundError: No module named 'pulp'

from pulp import *
from ortools.utils import output

n_items = 3
weights = [3, 4, 2]
values = [7, 8, 3]
max_weight = 6

# Define problem
prob = LpProblem('Knapsack Problem', LpMaximize)

# Create decision variables
x = LpVariable.dicts('x', [i for i in range(n_items)], lowBound=0, cat='Binary')

# Set objective function
prob += lpSum([values[i]*x[i] for i in range(n_items)])

# Set constraints
prob += lpSum([weights[i]*x[i] for i in range(n_items)]) <= max_weight

# Solving problem
prob.solve()
output(prob)

Status: Optimal
Objective value: 11.0

Variables      Values
-----------  --------
x_0                 0
x_1                 1
x_2                 1

Statistics:
- Number of variables: 3
- Number of constraints: 1
- Solve time: 0.006s

Optimization with GUROBI

from gurobipy import *
from ortools.utils import set_gurobi, custom_callback, output

n_items = 3
weights = [3, 4, 2]
values = [7, 8, 3]
max_weight = 6

# Define problem
m = Model('Knapsack Problem')

# Create decision variables
x = [m.addVar(vtype=GRB.BINARY, name='X{}'.format(i)) for i in range(n_items)]
m.update()

# Set objective function
m.setObjective(quicksum(values[i]*x[i] for i in range(n_items)), GRB.MAXIMIZE)

# Set constraints
m.addConstr(quicksum(weights[i]*x[i] for i in range(n_items)) <= max_weight)

set_gurobi(m, verbose=False)

# Optimize model
m.optimize(custom_callback)
output(m)

Status: Optimal
Objective value: 11.0

Variables      Values
-----------  --------
X0                  0
X1                  1
X2                  1

Statistics:
- Number of variables: 3
- Number of constraints: 1
- Solve time: 0.000s