24 August 2021

Linear Optimization – Part I

Nowadays, many daily problems aim to find the best way to accomplish some task. These problems can often be solved by finding a function for which you want to find a minimum or a maximum value, such as the minimum travel time or the maximum profit you can make from selling a range of products. When this happens, we are dealing with an optimization problem [2].

What is an optimization problem?

The main goal of the optimization problem is to find values of variables in a function that minimize or maximize its result while satisfying the problem’s constraints. In other words, an optimization problem is a problem whose goal is to find the best solution out of a set of all possible solutions. Sometimes, based on the type of problem that we have in our hands, finding any feasible solution can be enough.

These types of problems are common in areas such as engineering and industry, becoming challenging when there are a large number of decision variables involved. Calculating all possible combinations and determining the best one becomes an unfeasible task, demanding high computational resources [7]. Some libraries, like Google OR-Tools, use algorithms that restrict the search set in order to find an optimal (or close to optimal) solution [5].

A well-known and typical optimization problem is the Transportation Problem.

Transportation Problem

The goal of the transportation problem is to minimize the transportation cost of a given commodity from source or origin (e.g.: factories) to destination (e.g.: warehouses, final customers), respecting all the restrictions demanded not only by the origin (e.g.: maximum number of goods that can be sent from it) but also by the destination (e.g.: minimum number of products that need to be shipped to the warehouse, number of products requested by each client). In addition to these restrictions, it is also necessary to consider the cost of shipping the goods from origin to destination (transportation cost – Cij) [1].

Figure 1 – Transportation Problem

 

Figure 1 shows a typical example of a transportation problem. This figure shows a scenario where a company has three factories (A, B and C) with different production capacities. Factories A, B and C have the capacity to produce, daily, 500, 400 and 200 products, respectively. Every single day, the company uses its fleet of trucks to deliver its products to four warehouses (1, 2, 3 and 4). Each warehouse is able to receive a minimum number of products, by day. So, warehouses 1, 2, 3 and 4 expect to receive, at least, 80, 270, 160 and 150 products, every day, respectively. There are also fixed transportation costs to deliver one unit of goods from factory i to warehouse j, as you can see in Table 1.

 

Table 1 – Transportation Costs from Factory i to Warehouse j.

Given this scenario, our task is to find out what is the necessary amount of products that should be sent from factory i to warehouse j, at minimal total transportation cost and, at the same time, satisfy the minimum warehouses’ reception capacity, as well as the maximum factories production capacity.

How to solve an optimization problem?

The first step in solving an optimization problem is to build an appropriate model for the problem under analysis. Modelling is the process of identifying the decision variables, the restrictions and the objective function of the problem that we want to optimize [3].

  • Decision Variables: The decision variables are the components of the system for which we want to find values. For the scenario mentioned above, the variables that we have are the quantities of products to be sent from factory i to warehouse j, which can be represented by:

E.g.: = quantity of products sent from factory A to warehouse 1.

  • Constraints: The constraints are functions (equations and/or inequalities) that describe the relationships among decision variables and define the minimum and maximum allowable values for these variables. In the scenario shown in Figure 1, we have 3 constraints:

1. Maximum production capacity of each factory: Factories A, B and, C has a fixed production capacity, so they can only manage to produce, at most, 500, 400 and 200 products, respectively. Mathematically, these constraints can be expressed as follows:

Which is equivalent to:

 

2. Minimum reception requirements of each warehouse: Warehouses 1,2,3 and 4 only expect to receive, at least, 80, 270, 160 and 150 products by day, respectively. Mathematically, these constraints can be expressed as follows:

Which is equivalent to the following formula:

 

3. Minimum quantity of products: The number of products shipped from factory i to warehouse j must be a positive integer, greater or equal to 0. Mathematically, these constraints can be described as follows:

 

Which is equivalent to the following generic expression:

 

  • Objective Function: The objective function represents the quantitative measure we want to minimize or maximize. For the scenario used as an example, our function has to be a function that calculates the transportation cost for any quantity of products shipped from factory i to warehouse This function will be used to identify the decision variables values that guarantee the lowest total transportation cost. Mathematically, our function will be defined as follows:

 Which is the same as:

After the definition of the optimization model, the second step is to identify the optimization problem type that we wish to solve. There are many different types of optimization problems in the world. For each of those types, there are different approaches and algorithms for finding an optimal solution. So, before start implementing our model, we need to identify what type of problem we are dealing with and then choose an appropriate solver (an algorithm for finding an optimal solution). Coming back to the previous example, our simplified transportation problem can be classified as Integer Linear Programming since variables can only take integer values and both the objective function and model constraints are represented as linear expressions.

How to implement the model that describes the optimization problem?

Currently, there are several libraries that can be used to implement an optimization model. These libraries allow us to model, programmatically, our optimization problem and call a solver to solve it. Solvers are algorithms that implement methods used in solving linear programming problems such as simplex and branch-and-bound. One of those libraries is called Google OR-Tools.

What is Google OR-Tools?

Google OR-Tools is an open-source library from Google that provides a set of high-level API’s that allow you to model different combinatorial optimization problems. Google OR-Tools can be used to find the best solution to a problem out of a very large set of possible solutions. Here are some examples of problems that OR-Tools solves [5]:

  • Linear or Mixed-Integer Programming Problems (in the Mixed-Integer Programming – some or all of the decision variables in the model are required to be integers). OR-Tools seeks to find the optimal value of the objective function, given a set of linear inequalities as constraints, expressed in the model.
  • Constraint Problems (the purpose of these problems is to use a set of techniques for finding feasible solutions to a problem expressed as constraints in the model. E.g.: a room cannot be used for 2 events simultaneously).
  • Vehicle Routing (find the best route for a vehicle among all possible routes given a set of constraints).
  • Graph Problems (find the shortest paths in graphs, min or max-cost flows)

 

How to implement an optimization model with Google OR-Tools?

Google OR-Tools is written in C++, but it can also be used with Python, Java or C#. Regardless of the chosen language, to implement the optimization model you have to follow a sequence of steps. The current section describes the main steps in solving a linear optimization model, applied to the transportation problem presented in Figure 1.

1. Import the required libraries

Figure 2 – Import the Google OR-Tools libraries.

 

2. Create and instantiate the data model

Creating the data model is an optional step. For larger problems it’s more convenient to define a data model to represent the variables and constraints. Having this will allow looping it over arrays.

Figure 3 – Function to create the data model.

 

3. Declare the solver

The next step is to import and declare a MIP solver (Mixed Integer Programming solver). These types of solvers are the most appropriate ones for the linear programming problems, when it’s required to have some or all variables with integer values. For this example, we chose to use the SCIP solver.

Figure 4 – Importing and declaring the SCIP solver.

4. Create the decision variables

solver.IntVar() is used to define the minimum and maximum value that a variable can assume. In our transportation problem example, one of the constraints was to have variables whose values are equal or greater to 0, with no established maximum limit.

Figure 5 – Decision variables.

 

5. Define the constraints

solver.Add() is used to add each of the inequalities that represent the constraints defined in the model. In the scenario being studied, these restrictions represent, not only the maximum production capacity of each factory but also the minimum reception requirements of each warehouse.

Figure 6 – Constraints.

 

6. Define the objective function

When defining the objective function, each of its mathematical terms that computes the total transportation cost is created and added to an array. In the end, we call the solver.Sum() function to sum all the terms of the objective function and the solver.Minimize() function to minimize the total transportation cost. By doing this, we intend to find out the number of products that should be sent from factories A, B and C to warehouses 1,2,3 and 4, so that this cost is as low as possible.

 

Figure 7- Objective function.

 

7. Call the solver and display the results

The last step is nothing more than calling the solver.Solve() and displaying the results, i.e., the value that each decision variable should take, in order to minimize the transportation cost.

Figure 8 – Call the solver and display the results.

In Figure 8, we only have printed the variables whose decision variable is different from 0. Looking at this image, we realize that the lowest transportation cost that we get, by sending products from factories to warehouses and respecting the required restrictions, is 1680. This value can be achieved if we ship:

  • 80 products from Factory A to Warehouse 1 and 160 products to Warehouse 3;
  • 270 products from Factory B to Warehouse 2 and last, but not least
  • 150 products from Factory C to Warehouse 4.

In summary, in this article, we have seen what an optimization problem is and explored a typical example of such problems: the transportation problem. Using a fictitious scenario, we saw how to solve and implement an optimization problem with an open-source library: Google OR-Tools.

In the upcoming article (Part II), we will see how an optimization problem can be applied to a real use case.

   
   
    Sabrina Masson                       
     AI Consultant                  

 

Blog