In my most recent post on linear programming I applied PuLP for solving below linear optimization problem, using two approaches. Approach #1 was based on solving a sub-problem with one objective only first, then adding the optimal outcome of that problem to a second sub-problem that considered objective two only. Approach #2 is based on combining all objectives into one overall objective function, combining single objectives with scalar weights.

In this post I want to show an alternative approach for solving below multi-objective linear optimization problem: I will use approach #1, but apply weights instead:

The approach I now use is to solve the problem in two steps, where a sub-problem with one objective only is solved first and its optimal outcome is added to a second sub-problem with only the the second objective as a constraint. This approach has been demonstrated by before, but this time I will apply a scalar weight-factor to that constraint, considering the optimal outcome of sub-problem with 0-100%.

Starting with the first objective, the first sub-problem to solve would be the following:

The optimal objective value to above sub-problem is 30.

After having solved the first sub-problem, the second objective would be considered by a second sub-problem adding the optimal outcome to above problem as a weighted constraint:

Here is the implementation in Python, using the PuLP module and applying a step-size of 0.01:

# import PuLP for modelling and solving problems
import pulp

# import matplotlib.pyplot for visualization
import matplotlib.pyplot as plt 

# import pandas and numpy for being able to store solutions in DataFrame
import numpy as np
import pandas as pd

# define step-size
stepSize = 0.01

# initialize empty DataFrame for storing optimization outcomes
solutionTable = pd.DataFrame(columns=["beta","x1_opt","x2_opt","obj_value"])

# declare optimization variables using PuLP and LpVariable
x1 = pulp.LpVariable("x1",lowBound=0)
x2 = pulp.LpVariable("x2",lowBound=0)

# model and solve sub-problem no. 1
linearProblem = pulp.LpProblem("First sub-problem",pulp.LpMaximize)
linearProblem += 2*x1 + 3*x2 # add objective no. 1
linearProblem += x1 + x2 <= 10 # add contraints from original problem statement
linearProblem += 2*x1 + x2 <= 15
solution = linearProblem.solve()

# store optimal outcome of sub-problem no. 1 into variable
optimalObj1 = pulp.value(linearProblem.objective)

# iterate through beta values from 0 to 1 with stepSize, and write PuLP solutions into solutionTable
for i in range(0,101,int(stepSize*100)):
        # declare the problem again
        linearProblem = pulp.LpProblem("Multi-objective linear maximization",pulp.LpMaximize)
        # add the second objective as objective function to this sub-problem
        linearProblem += 4*x1-2*x2
        # add the constraints from original problem statement
        linearProblem += x1 + x2 <= 10
        linearProblem += 2*x1 + x2 <= 15
        # add additional constraint at level beta, considering optimal outcome of sub-problem no. 1
        linearProblem += 2*x1 + 3*x2 >= (i/100)*optimalObj1
        # solve the problem
        solution = linearProblem.solve()
        # write solutions into DataFrame
        solutionTable.loc[int(i/(stepSize*100))] = [i/100,
                                                     pulp.value(x1),
                                                     pulp.value(x2),
                                                     pulp.value(linearProblem.objective)]

# visualize optimization outcome, using matplotlib.pyplot
# -- set figure size
plt.figure(figsize=(20,10))
# -- create line plot
plt.plot(solutionTable["beta"],solutionTable["obj_value"],color="red")
# -- add axis labels
plt.xlabel("beta",size=20)
plt.ylabel("obj_value",size=20)
# -- add plot title
plt.title("Optimal outcome of sub-problem 2, depending on beta",size=32)
# -- show plot
plt.show()

The results indicate that there is some range for beta where an increase in beta will not affect the optimal outcome of sub-problem 2, i.e. will not affect objective 2.

Linnart Felkl

Data scientist focusing on simulation, optimization and modeling in R, SQL, VBA and Python