D4GC 2022 - Optimization Workshop
  • AI Chat
  • Code
  • Report
    • Beta
    Spinner

    D4GC 2022 - Optimization Workshop

    # Install the pulp package
!pip install pulp
    # Import some useful packages
from pulp import *
import pandas as pd

    Linear Programming

    Optimization is an important technique is used in many different domains. We all have finite resources and time and we want to make the most of them. From using your time productively to solving supply chain problems for your company – everything uses optimization. It’s an especially interesting and relevant topic in data science.

    Linear Programing (LP) is a powerful modeling tool that is used for optimization. This optimization method uses a mathematical model whose requirements are linear relationships.

    There are three basic components in LP:

    1. Decision variables: Unknowns of the problem
    2. Objective function: Mathematical expression reflecting a single quantity to be either maximized or minimized
    3. Constraints: Mathematical expression representing any kind of limitation on the values that the decision variables they take

    Let's look at some examples!

    Example 1: Beer manufacturing

    Consider a brewery that produces only two beverage types – Ale and Beer. The recipes for both beverages require corn, hops, and malt. However, they each need different proportions of these resources. To manufacture one barrel of Ale and Beer, the following quantities are required:

    BeverageCornHopsMalt
    Ale5435
    Beer15420

    For each day in the near future, the brewery will have the following quantities of the raw materials available to them: 480 units of Corn, 160 units of Hops, and 1190 units of Malt. On each sale, the brewery makes a profit of $13 per barrel Ale sold, and $23 per barrel Beer sold.

    Now, the company wishes to maximize its profit. How many barrels of Ale and Beer should it produce respectively?

    1.1 Identifying the basic components of the LP

    Decision variables

    There are two decision variables (unknowns in our problem):

    • Number of Ale barrels
    • Number of Beer barrels

    Objective function

    The objective function, which we want to maximize, is the total profit:

    • MAX(13 * number of Ale barrels + 23 * number of Beer barrels)

    Constraints

    The brewery is limited by the amount of raw materials they have available to them:

    • (5 * number of Ale barrels) + (15 * number of Beer barrels) ≤ 480
    • (4 * number of Ale barrels) + (4 * number of Beer barrels) ≤ 160
    • (35 * number of Ale barrels) + (20 * number of Beer barrels) ≤ 1190

    And the decision variables need to be positive since we cannot produce, for example, -3 barrels of Ale.

    • number of Ale barrels ≥ 0
    • number of Beer barrels ≥ 0

    1.2 Solving the problem in python

    We will use the PuLP package to solve this linear programming problem.

    A variable called model1 is created using the LpProblem() function. It has two parameters, the first being the arbitrary name of this problem (as a string), and the second parameter being either LpMinimize or LpMaximize depending on the type of LP you are trying to solve:

    # Initialize the model
model1 = LpProblem("Maximize Brewery Profit", LpMaximize)

    The decision variables are created using the LpVariable class. It has four parameters, the first is the arbitrary name of what this variable represents, the second is the lower bound on this variable, the third is the upper bound, and the fourth is essentially the type of data (discrete or continuous).

    The options for the fourth parameter are 'Continuous' or 'Integer', with the default as 'Continuous'. If we were modelling the number of barrels to produce, we would need to input 'Integer' since we're dealing with discrete data. The bounds can be entered directly as a number, or None to represent no bound, with None as the default.

    # Define decision variables
AleBarrels = LpVariable('Ale Barrels', lowBound=0, upBound=None, cat='Integer')
BeerBarrels = LpVariable('Beer Barrels', lowBound=0, upBound=None, cat='Integer')

    The variable model1 now begins collecting problem data with the += operator. We define the objective function first:

    # Define objective function
model1 += 13 * AleBarrels + 23 * BeerBarrels

    The constraints are now entered. This is done with the += operator again, since we are adding more data to the model1 variable. The constraints are logically entered after this.

    Note that any "non-negative" constraints were already included when defining the decision variables.

    # Define constraints
model1 += 5 * AleBarrels + 15 * BeerBarrels <= 480
model1 += 4 * AleBarrels + 4 * BeerBarrels <= 160
model1 += 35 * AleBarrels + 20 * BeerBarrels <= 1190

    The LP is solved using the solve() function.

    ‌
    ‌
    ‌