정수 계획법

정수 계획법(integer programming)

Example 6-4

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

Table 6-1는 배낭에 넣어 갖고 갈 수 있는 3개의 상이한 품목에 대한 품목별 무게와 효용 및 배낭의 보관능력을 나타내고 있다. 배낭의 보관능력 제약을 만족하면서 배낭에 넣어 갖고 갈 수 있는 품목의 효용을 최대화하는 정수계획모형을 작성한 후 최적 정수해를 구하라. 단, 같은 품목을 중복으로 배낭에 넣을 수 없다.

Item	Weight	Value
1	3	6
2	4	8
3	2	3

단일품목 배낭문제를 0-1정수계획모형으로 정식화하기 위해서는 배낭에 넣을 수 있는 품목 \(j\)를 결정변수 \(X_{j}\)라고 정의하고 \(X_{j}\)가 0과 1 중에서 하나의 값만 갖도록 하여야 한다. 왜냐하면 배낭에 넣어 갖고 갈 수 있는 품목은 단일품목 배낭문제의 성격상 그 품목을 선택하거나 또는 선택하지 않기 때문이다. 따라서 \(X_{j}\)가 1의 값을 가질 때는 품목 \(j\)가 선택되고, 0의 값을 가질 때는 품목 \(j\)가 선택되지 않는다고 하자. 만일 각 품목에 대해 전체가 아닌 일부분의 선택이 가능하다면 이 문제는 분할성의 가정이 성립하므로 선형계획문제로 정식화할 수 있다.

\[\begin{split}X_{j} = \begin{cases} 1, \text{ 배낭에 품목 $j$를 넣는 경우 $(j=1,2,3)$}\\ 0, \text{ 배낭에 품목 $j$를 넣지 않는 경우 $(j=1,2,3)$}\\ \end{cases}\end{split}\]

from pulp import *

prob = LpProblem(name='0-1 Knapsack Problem', sense=LpMaximize)

x1 = LpVariable(name='X1', lowBound=0, cat='Binary')
x2 = LpVariable(name='X2', lowBound=0, cat='Binary')
x3 = LpVariable(name='X3', lowBound=0, cat='Binary')

prob += 7*x1 + 8*x2 + 3*x3

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

# Solving problem
prob.solve()
print('Status', LpStatus[prob.status])

print('Z = {}'.format(value(prob.objective)))
for i in prob.variables():
    print('{} = {}'.format(i.name, i.varValue))

---------------------------------------------------------------------------
ModuleNotFoundError                       Traceback (most recent call last)
Cell In[1], line 1
----> 1 from pulp import *
      3 prob = LpProblem(name='0-1 Knapsack Problem', sense=LpMaximize)
      5 x1 = LpVariable(name='X1', lowBound=0, cat='Binary')

ModuleNotFoundError: No module named 'pulp'

Multiple Knapsack Problem

Example 6-5

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

Table 6-3는 트럭에 적재할 수 있는 3개의 상이한 품목에 대하여 이들 품목별 단위당 무게, 적재가능 수량, 단위당 수익 및 트럭의 적재능력을 나타내고 있다. 트럭의 적재능력의 제약을 만족하면서 트럭에 품목들을 적재하여 최대의 수익을 얻을려고 한다. 트럭의 수익을 최대로 하는 적재 품목의 수량을 결정하기 위한 정수계획 모형을 작성하고 최적해를 구하라. 단, 트럭에 적재하는 품목의 수량은 정수단위로 결정해야 한다.

Table 6-1. 단일품목 배낭문제의 자료

품목	단위당 무게(kg)	적재가능수량(개)	단위당 수익(천원)	적재능력(kg)
1	30	100	70	6
2	40	200	80
3	20	300	30

from pulp import *

prob = LpProblem(name='Knapsack Problem', sense=LpMaximize)

x1 = LpVariable(name='x1', lowBound=0, cat='Integer')
x2 = LpVariable(name='x2', lowBound=0, cat='Integer')
x3 = LpVariable(name='x3', lowBound=0, cat='Integer')

prob += 70*x1 + 80*x2 + 30*x3

prob += 30*x1 + 40*x2 + 20*x3 <= 10000
prob += x1 <= 100
prob += x2 <= 200
prob += x3 <= 300

# Solving problem
prob.solve()
print('Status', LpStatus[prob.status])

print('Z = {}'.format(value(prob.objective)))
for i in prob.variables():
    print('{} = {}'.format(i.name, i.varValue))

Status Optimal
Z = 21000.0
x1 = 100.0
x2 = 175.0
x3 = 0.0

Example: Bin Packing Problem

\[\begin{split}\begin{split} & \text{minimize } &Z=&\sum_{i=1}^{n}y_{i} & &\\[1ex] & \text{subject to } & &\sum_{j=1}^{n}w_{j}x_{ij} \le cy_{i},\quad &i \in N = \{1,...,n\},&\\[1ex] & & &\sum_{i=1}^{n}x_{ij} = 1, &j \in N,&\\[1ex] & & &y_{i} = 0 or 1, &i \in N,&\\[1ex] & & &x_{ij} = 0 or 1 &i \in N, j \in N,&\\[1ex] \end{split}\end{split}\]

from pulp import *
import time

#
# A list of item tuples (name, weight) -- name is meaningless except to humans.
# Weight and Size are used interchangeably here and elsewhere.
#
items = [("a", 5),
         ("b", 6),
         ("c", 7),
         ("d", 32),
         ("e", 2),
         ("f", 32),
         ("g", 5),
         ("h", 7),
         ("i", 9),
         ("k", 12),
         ("l", 11),
         ("m", 1),
         ("n", 2)]

itemCount = len(items)

# Max number of bins allowed.
maxBins = 32

# Bin Size
binCapacity = 32



# Indicator variable assigned 1 when the bin is used.
y = pulp.LpVariable.dicts('BinUsed', range(maxBins),
                            lowBound = 0,
                            upBound = 1,
                            cat = pulp.LpInteger)

# An indicator variable that is assigned 1 when item is placed into binNum
possible_ItemInBin = [(itemTuple[0], binNum) for itemTuple in items
                                            for binNum in range(maxBins)]
x = pulp.LpVariable.dicts('itemInBin', possible_ItemInBin,
                            lowBound = 0,
                            upBound = 1,
                            cat = pulp.LpInteger)

# Initialize the problem
prob = LpProblem("Bin Packing Problem", LpMinimize)

# Add the objective function.
prob += lpSum([y[i] for i in range(maxBins)]), "Objective: Minimize Bins Used"

#
# This is the constraints section.
#

# First constraint: For every item, the sum of bins in which it appears must be 1
for j in items:
    prob += lpSum([x[(j[0], i)] for i in range(maxBins)]) == 1, ("An item can be in only 1 bin -- " + str(j[0]))

# Second constraint: For every bin, the number of items in the bin cannot exceed the bin capacity
for i in range(maxBins):
    prob += lpSum([items[j][1] * x[(items[j][0], i)] for j in range(itemCount)]) <= binCapacity*y[i], ("The sum of item sizes must be smaller than the bin -- " + str(i))

# Write the model to disk

# Solve the optimization.
start_time = time.time()
prob.solve()
print("Solved in %s seconds." % (time.time() - start_time))


# Bins used
print("Bins used: " + str(sum(([y[i].value() for i in range(maxBins)]))))

# The rest of this is some unpleasent massaging to get pretty results.
bins = {}
for itemBinPair in x.keys():
    if(x[itemBinPair].value() == 1):
        itemNum = itemBinPair[0]
        binNum = itemBinPair[1]
        if binNum in bins:
            bins[binNum].append(itemNum)
        else:
            bins[binNum] = [itemNum]

for b in bins.keys():
    print(str(b) + ": " + str(bins[b]))

Solved in 0.05406332015991211 seconds.
Bins used: 5.0
0: ['a', 'b', 'e', 'i', 'm', 'n']
1: ['c', 'g', 'h', 'l']
12: ['d']
13: ['f']
7: ['k']

Problem 3

from pulp import *

prob = LpProblem(name='Profit maximising problem', sense=LpMaximize)

x1 = LpVariable(name='x1', lowBound=0, cat='Integer')
x2 = LpVariable(name='x2', lowBound=0, cat='Integer')

prob += 30000*x1 + 45000*x2, 'Profit'

prob += 3*x1 + 4*x2 <= 30
prob += 5*x1 + 6*x2 <= 60
prob += 1.5*x1 + 3*x2 <= 21

prob.solve(solver=GUROBI())

print(LpStatus[prob.status])

# Print our decision variable values
print('Production of Car x1 = {}'.format(x1.varValue))
print('Production of Car x2 = {}'.format(x2.varValue))

# Print our objective function value
print(value(prob.objective))

Knapsack Problem

from pulp import *

model = LpProblem('knapsack problem', LpMaximize)

x1 = LpVariable('x1', lowBound=0, upBound=1, cat=LpInteger)
x2 = LpVariable('x2', lowBound=0, upBound=1, cat=LpInteger)
x3 = LpVariable('x3', lowBound=0, upBound=1, cat=LpInteger)

model += 7*x1 + 8*x2 + 3*x3
model += 3*x1 + 4*x2 + 2*x3 <= 6

model.solve(GUROBI())

print('Status', LpStatus[model.status])
print(value(model.objective))
for v in model.variables():
    print(v.name, '=', v.varValue)

Knapsack Problem II

from pulp import *

items = ['A', 'B', 'C']
weights = [3, 4, 2]
values = [7, 8, 3]

prob = LpProblem('knapsack problem', LpMaximize)

# Define decision variables
decision_variables = []
for num, i in enumerate(items):
    var_str = str('x' + str(num))
    variables = LpVariable(str(var_str), lowBound=0, upBound=1, cat='Integer')
    decision_variables.append(variables)
print(decision_variables)

# Define objective function
objective_function = ''
for u, uf in enumerate(values):
    for d, dv in enumerate(decision_variables):
        if u == d:
            objective_function += uf * dv
        
prob += objective_function
print(objective_function)

# Define constraint
capacity = 6
constraint = ''
for w, wt in enumerate(weights):
    for d, dv in enumerate(decision_variables):
        if w == d:
            constraint += wt * dv
            
prob += constraint <= capacity
print(constraint)

prob.solve(GUROBI())

print('Status', LpStatus[prob.status])
print(value(prob.objective))
for v in prob.variables():
    print(v.name, '=', v.varValue)

from pulp import *

data = {
    ("SMITH"): [6,8,30,6,20], ("JOHNSON"): [6,8,50,0,24], 
    ('WILLIAMS'): [6,8,30,0,24], ('JONES'): [6,8,30,0,24], 
    ('BROWN'): [6,8,40,0,24], ('DAVIS'): [6,8,50,0,24],
    ('MILLER'): [6,8,45,6,18], ('WILSON'): [6,8,30,0,24], 
    ('MOORE'): [6,8,35,0,24], ('TAYLOR'): [6,8,40,0,24], 
    ('ANDERSON'): [2,3,60,0,6], ('THOMAS'): [2,4,40,0,24],
    ('JACKSON') :[2,4,60,8,16], ('WHITE'): [2,6,55,0,24], 
    ('HARRIS'): [2,6,45,0,24], ('MARTIN'): [2,3,40,0,24], 
    ('THOMPSON'): [2,5,50,12,24], ('GARCIA'): [2,4,50,0,24],
    ('MARTINEZ'): [2,4,40,0,24], ('ROBINSON'): [2,5,50,0,24]
}

required = [1,1,2,3,6,6,7,8,9,8,8,8,7,6,6,5,5,4,4,3,2,2,2,2]

time = 24

employee = list(data.keys())
mins, maxs, costs, avs, ave = splitDict(data)

x = {}
for d in employee:
    for i in range(time):
        for j in range(i+1, time+1):
            x[d,i,j] = LpVariable(name='x_%s%d%d'%(d,i,j), cat='Binary')
            
staff_number = {}
for t in range(time):
    staff_number[t] = LpVariable(name='staffNumber_%d'%t, cat='Integer', lowBound=required[t])

prob = LpProblem('Work Schedule', LpMinimize)

prob += lpSum(lpSum(lpSum((j-i) * x[d,i,j] * costs[d] for j in range(i+1,time+1)) \
                    for i in range(time)) for d in employee)

for d in employee:
    prob += (lpSum(lpSum(x[d,i,j] for j in range(i+1,ave[d]+1)if min[d] <= \
                         (j-i) <= max[d]) for i in range(avs[d],ave[d])) <= 1)
    
    prob += (lpSum(lpSum(x[d,i,j] for j in range(i+1,time+1)) for i in range(time)) <= \
             lpSum(quicksum(x[d,i,j] for j in range(i+1,ave[d]+1) if min[d] <= (j-i) <= \
                            max[d]) for i in range(avs[d],ave[d])))

    
    
for d in employee:
    m.addConstr(quicksum(quicksum(x[d,i,j] for j in range(i+1,ave[d]+1)if min[d] <= (j-i) <= max[d])for i in range(avs[d],ave[d]))<=1)
    m.addConstr(quicksum(quicksum(x[d,i,j] for j in range(i+1,t+1))for i in range(t))<=quicksum(quicksum(x[d,i,j] for j in range(i+1,ave[d]+1)
    if min[d] <= (j-i) <= max[d])for i in range(avs[d],ave[d])))
    
    
for c in range(t):
    m.addConstr(quicksum(quicksum(quicksum(x[d,i,j] for j in range(i+1,t+1)if i <= c <j) for i in range(t))for d in employee)==staffNumber[c])
D101=quicksum(quicksum(x['ANDERSON',i,j] for j in range(i+1,7)if min["ANDERSON"]<=(j-i)<=max["ANDERSON"])for i in range(0,7))
D102=quicksum(quicksum(x['ANDERSON',i,j] for j in range(i+1,21))for i in range(18,21))
m.addConstr(D101+D102<=1,"F")
m.addConstr(quicksum(quicksum(x['ANDERSON',i,j] for j in range(i+1,t+1))for i in range(t))<=D101+D102)

from pulp import *

identifiers = ['A', 'B', 'C', 'D', 'E']
prices = dict(zip(identifiers, [100.0, 99.0, 100.5, 101.5, 200.0]))

prob = LpProblem(name='Minimalist example', sense=LpMaximize)

x = LpVariable.dicts(name='x', indexs=identifiers, lowBound=0, 
                     upBound=1, cat='Integer')

prob += lpSum([x[i]*prices[i] for i in identifiers])

prob += lpSum([x[i] for i in identifiers]) == 2

prob.solve(solver=GUROBI())

for i in prob.variables():
    print(i.name, '=', i.varValue)
print('Status:', LpStatus[prob.status])
print(value(prob.objective))