Skip to content

Modelling and solving the "Maximum Profit Project Portfolio" optimization problem

In this tutorial, you'll model and solve the "Maximum Profit Portfolio" optimization problem using Paramita.

Paramita also supports modelling and solving optimization problems, where you have a linear objective to maximize or minimize subject to some hard constraints. While decision problems ask "is there a satisfying assignment?", optimization problems ask "what is the best assignment under a cost/benefit/objective function?".

Prerequisite

Before starting, we recommend going through the Modelling and solving the "Light Up" decision puzzle

The "Maximum Profit Project Portfolio" problem

Assume you are a project manager that have a set of potential projects, each with a profit and a cost. You must decide which projects to fund.

  • Some projects require other projects to be funded first (e.g., project B depends on project A).
  • Some projects are mutually exclusive (they use the same scarce resource, so you cannot fund both).
  • You have a total budget that cannot be exceeded.

Your goal is to maximize the total profit.

Modelling the problem

Let's define first the data for our problem:

projects = ["A", "B", "C", "D"]
profits = {"A": 10, "B": 15, "C": 8, "D": 6}
costs = {"A": 6, "B": 4, "C": 5, "D": 3}
max_budget = 12
dependencies = {
    "A": [],
    "B": ["A"],
    "C": [],
    "D": ["C"],
}
exclusions = {("A", "C")}

To encode the problem, we should first define some boolean variables that represent which projects we fund:

from paramita.modelling import Bool, If

A, B, C, D = map(Bool, projects)
project_vars = (A, B, C, D)

Each variable will be true iff. the project is funded.

Now let's encode our first constraint: "we cannot exceed the budget". 

subject_to = sum(costs[p.name] * p for p in project_vars) <= max_budget

Then, we can encode the dependencies on the projects: 

for project, deps in dependencies.items():
    for dep in deps:
        subject_to &= If(Bool(project), Bool(dep))

To encode the mutual exclusions between projects, we can enforce that both cannot be true at the same time: 

for p1, p2 in exclusions:
    subject_to &= ~(Bool(p1) & Bool(p2))

And finally, we can encode our objective function:

objective = sum(profits[p.name] * p for p in project_vars)

Solving the problem

Prerequisites

You need a MaxSAT solver compiled as a Paramita extension. Start by fetching EvalMaxSAT2022 from the Paramita Plugins repository using the CLI helper:

paramita plugins build cmake "#maxsat-solvers/mse22-EvalMaxSAT2022"

For more information you can check the Building an external Plugin section.

Now, we can use a MaxSAT solver to find a solution to the problem:

from paramita.solvers import MaxSatSolver
from paramita.modelling import DimacsVariablePool, add_to_weighted_container, to_cnf

s = MaxSatSolver.from_name("EvalMaxSAT2022")

pool = DimacsVariablePool()
constant = add_to_weighted_container(
    obj=objective,
    subject_to=subject_to,
    cnf_transformer=to_cnf,
    container=s,
    var_pool=pool,
)

s.solve()

m = s.model()

for lit in m:
    if lit > 0:
        var = pool.decode_literal(lit).name
        if var in projects:
            print("Project", var, "selected")

As with the "Light Up" decision problem, we are using a DimacsVariablePool to record the mapping between solver variables and the modelled variables. In this case, we use the add_to_weighted_container, which receives the same parameters as add_to_container plus the objective function objective. Also, instead of a SAT solver here we are using a MaxSAT solver.

Source code

This is the source code for the full example:

# Problem data:
projects = ["A", "B", "C", "D"]
profits = {"A": 10, "B": 15, "C": 8, "D": 6}
costs = {"A": 6, "B": 4, "C": 5, "D": 3}
max_budget = 12
dependencies = {
    "A": [],
    "B": ["A"],
    "C": [],
    "D": ["C"],
}
exclusions = {("A", "C")}

# Boolean variables definition:
from paramita.modelling import Bool, If

A, B, C, D = map(Bool, projects)
project_vars = (A, B, C, D)

# Restrictions:
subject_to = sum(costs[p.name] * p for p in project_vars) <= max_budget

for project, deps in dependencies.items():
    for dep in deps:
        subject_to &= If(Bool(project), Bool(dep))

for p1, p2 in exclusions:
    subject_to &= ~(Bool(p1) & Bool(p2))

# Objective
objective = sum(profits[p.name] * p for p in project_vars)

# Solve
from paramita.solvers import MaxSatSolver
from paramita.modelling import DimacsVariablePool, add_to_weighted_container, to_cnf

s = MaxSatSolver.from_name("EvalMaxSAT2022")

pool = DimacsVariablePool()
constant = add_to_weighted_container(
    obj=objective,
    subject_to=subject_to,
    cnf_transformer=to_cnf,
    container=s,
    var_pool=pool,
)

s.solve()

m = s.model()

for lit in m:
    if lit > 0:
        var = pool.decode_literal(lit).name
        if var in projects:
            print("Project", var, "selected")