Knapsack Problem

The following code shows how OptFlow solves the knapsack problem with mathematical programming, metaheuristics and search

# Author: Anonymized for paper review
# Case Study: Knapsack Problem

import optflow as flow
import numpy as np
import time

np.random.seed(0)

# N, max_weight = 5, 10
# weight = flow.Constant(value=np.array([2, 2, 6, 5, 4]))
# value = flow.Constant(value=np.array([6, 3, 5, 4, 6]))
N = 100
max_weight = N * 5
weight = flow.Constant(value=np.random.randint(1, max_weight // N * 5, N))
value = flow.Constant(value=np.random.randint(1, max_weight // N * 5, N))
x = flow.Variable(cat=flow.binary, size=N, shape=(N, ))
obj = flow.sum([value[i] * x[i] for i in range(N)])
constraints = [flow.sum([weight[i] * x[i] for i in range(N)]) <= max_weight]
prob = flow.Problem(constraints=constraints, objective=obj, sense=flow.maximize)

# opt_obj = prob.solve(solver=flow.programming)
# print(opt_obj)
# print(x.optimized_value)

# opt_obj = prob.solve(solver=flow.search)
# print(opt_obj)
# print(x.optimized_value)

opt_obj = prob.solve(solver=flow.metaheuristics, params={'jit': True})
print(opt_obj)
print(x.optimized_value)

opt_obj = prob.solve(solver=flow.metaheuristics)
print(opt_obj)
print(x.optimized_value)

[Run Online Demo] (password: )

The following code shows how OptFlow solves the problem with MCTS, dynamic programming (model-based reinforcement learning), model-free reinforcement learning and MCTS + RL, which requires the problem to be represented as a sequential one

# Author: Anonymized for paper review
# Case Study: Knapsack Problem

import optflow as flow
import numpy as np

np.random.seed(0)

# N, max_weight = 5, 10
# weight = flow.Constant(value=np.array([2, 2, 6, 5, 4]))
# value = flow.Constant(value=np.array([6, 3, 5, 4, 6]))
N = 10
max_weight = N * 5
weight = flow.Input(shape=(N, ), dtype=flow.int64)
value = flow.Input(shape=(N, ), dtype=flow.int64)
# weight = flow.Constant(value=np.random.randint(1, max_weight // N * 5, N))
# value = flow.Constant(value=np.random.randint(1, max_weight // N * 5, N))
consumed_weight = flow.Constant(value=0)
x = flow.Variable(cat=flow.binary, size=N, shape=(N, ))
obj = flow.Constant(value=0, dtype=flow.int64)

constraints = []
with flow.ForLoop(N) as i:
    with flow.IfCond(x[i]):
        constraints.append(consumed_weight + weight[i] <= max_weight)
        obj += value[i]
        consumed_weight += weight[i]

prob = flow.Problem(constraints=constraints, objective=obj, sense=flow.maximize)

weight_ = np.random.randint(1, max_weight // N * 5, N, dtype=np.int64)
value_ = np.random.randint(1, max_weight // N * 5, N, dtype=np.int64)
inputs = {weight: weight_, value: value_}
print(inputs)

# prob.train(trainer=flow.dp, inputs=inputs)
opt_obj = prob.solve(solver=flow.dp, inputs=inputs, params={'jit': True})
print(opt_obj, x.optimized_value)

prob.policy = None
opt_obj = prob.solve(solver=flow.dp, inputs=inputs, params={'jit': False})
print(opt_obj, x.optimized_value)
print(np.sum(value_ * x.optimized_value))

class DataGenerator(flow.DataGenerator):
    def __call__(self, *args, **kwargs):
        weight_ = np.random.randint(1, max_weight // N * 5, N, dtype=np.int64)
        value_ = np.random.randint(1, max_weight // N * 5, N, dtype=np.int64)
        inputs = {weight: weight_, value: value_}
        return inputs

generator = DataGenerator()

prob.train(trainer=flow.rl, inputs_generator=generator, params={'algorithm': 'dqn', 'num_exploration_episodes': 10, 'num_episodes': 100})

opt_obj = prob.solve(solver=flow.search, params={'algorithm': 'mcts', 'mcts_playouts': 100}, inputs=inputs)
print(opt_obj, x.optimized_value)
#
# prob.load_model(r'knapsack_20_checkpoint')
# opt_obj = prob.solve(solver=flow.rl, inputs=inputs)
# print(opt_obj, x.optimized_value)
#
# opt_obj = prob.solve(solver=flow.search, params={'algorithm': 'mcts', 'mcts_playouts': 100}, inputs=inputs)
# print(opt_obj, x.optimized_value)

[Run Online Demo] (password: )