Capital Budgeting#
This problem is taken from Chapter 9 of Applied Mathematical Programming.
The following code shows how OptFlow solves the problem with mathematical programming, metaheuristics and search
# Author: Anonymized for paper review
# Case Study: Capital Budgeting
# https://web.mit.edu/15.053/www/AMP-Chapter-09.pdf
# item 1 2 3
# contribution 2 3 4
# cash 1 2 4
# manpower 2 1 4
# Total cash: 4; total manpower: 4 --> optimal solution: 1 / 1 / 0
# Total cash: 5; total manpower: 6 --> optimal solution: 1 / 0 / 1
import optflow as flow
import numpy as np
N, M = 3, 2
x = flow.Variable(cat=flow.binary, shape=(N, ))
c = flow.Constant(dtype=flow.float64, shape=(N, ), value=np.array([2., 3., 4.]))
a = flow.Constant(dtype=flow.float64, shape=(N, M), value=np.array([[1., 2.], [2., 1.], [4., 4.]]))
b = flow.Input(dtype=flow.float64, shape=(M, ))
obj = sum(c[i] * x[i] for i in range(N))
constraints = [sum(a[i, j] * x[i] for i in range(N)) <= b[j] for j in range(M)]
prob = flow.Problem(objective=obj, constraints=constraints, sense=flow.maximize)
# metaheuristics
opt_obj = prob.solve(solver=flow.metaheuristics, inputs={b: np.array([4., 4.])})
for i in range(N):
print("x[%d]: %f" % (i, x[i].optimized_value))
opt_obj = prob.solve(solver=flow.metaheuristics, inputs={b: np.array([5., 6.])})
for i in range(N):
print("x[%d]: %f" % (i, x[i].optimized_value))
# search
opt_obj = prob.solve(solver=flow.search, inputs={b: np.array([4., 4.])})
for i in range(N):
print("x[%d]: %f" % (i, x[i].optimized_value))
opt_obj = prob.solve(solver=flow.search, inputs={b: np.array([5., 6.])})
for i in range(N):
print("x[%d]: %f" % (i, x[i].optimized_value))
# programming
opt_obj = prob.solve(solver=flow.programming, inputs={b: np.array([4., 4.])})
for i in range(N):
print("x[%d]: %f" % (i, x[i].optimized_value))
opt_obj = prob.solve(solver=flow.programming, inputs={b: np.array([5., 6.])})
for i in range(N):
print("x[%d]: %f" % (i, x[i].optimized_value))
The following code shows how OptFlow solves the problem with dynamic programming (model-based reinforcement learning), which requires the problem to be represented as a sequential one
# Author: Anonymized for paper review
# Case Study: Capital Budgeting
# https://web.mit.edu/15.053/www/AMP-Chapter-09.pdf
# item 1 2 3
# contribution 2 3 4
# cash 1 2 4
# manpower 2 1 4
# Total cash: 4; total manpower: 4 --> optimal solution: 1 / 1 / 0
# Total cash: 5; total manpower: 6 --> optimal solution: 1 / 0 / 1
import optflow as flow
import numpy as np
N, M = 3, 2
x = flow.Variable(cat=flow.binary, shape=(N, ))
c = flow.Constant(dtype=flow.float64, shape=(N, ), value=np.array([2., 3., 4.]))
a = flow.Constant(dtype=flow.float64, shape=(N, M), value=np.array([[1., 2.], [2., 1.], [4., 4.]]))
b = flow.Input(dtype=flow.float64, shape=(M, ))
obj = flow.Constant(0.)
total_cash = flow.Constant(0.)
total_manpower = flow.Constant(0.)
constraints = []
with flow.ForLoop(N) as i:
with flow.IfCond(x[i]):
constraints.append(total_cash + a[i, 0] <= b[0])
constraints.append(total_manpower + a[i, 1] <= b[1])
total_cash += a[i, 0]
total_manpower += a[i, 1]
obj += c[i]
prob = flow.Problem(objective=obj, constraints=constraints, sense=flow.maximize)
# dynamic programming
opt_obj = prob.solve(solver=flow.dp, inputs={b: np.array([4., 4.])})
for i in range(N):
print("x[%d]: %f" % (i, x[i].optimized_value))
prob.policy = None
opt_obj = prob.solve(solver=flow.dp, inputs={b: np.array([5., 6.])})
for i in range(N):
print("x[%d]: %f" % (i, x[i].optimized_value))
[Run Online Demo] (password: )