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: )