Tag Archives: Linear programming

Optimization with JuMP in Julia

By: Jaafar Ballout

Re-posted from: https://www.supplychaindataanalytics.com/optimization-with-jump-in-julia/

As a result of the emergence and progress of open-source languages SCM and OR analysts have access to a growing number of constantly improving tools and solvers. Julia, for example, is a flexible dynamic open-source programming language that is appropriate for scientific and numerical computing. Julia’s source code is available on GitHub and the programming language is supported by a growing number of frameworks and applications for optimization and scheduling.

I introduced Julia in one of my previous posts already, covering a linear programming example. In this article I will give a more comprehensive introduction to Julia, comparing it with other programming languages, and specifically focusing on optimization.

JuMP: A package for mathematical programming in Julia

JuMP (Julia for Mathematical Programming) is a package available in Julia. This modelling framework allows users to formulate an optimization problem (linear, mixed-integer, quadratic, conic quadratic, semidefinite, and nonlinear) with easy-to-read code. The problem can then be solved by optimizers (solvers) written in low-level languages. The selected solver for this demonstration is GLPK which is a state-of-art open-source solver for linear programming (LP) and mixed-integer programming (MIP) problems. It incorporates algorithms such as the simplex method and the interior-point method.

Comparing Julia vs. Matlab for optimization problems

At first, a quick comparison between Julia and Matlab is necessary to appreciate the power of open-source programming languages.

Criteria Julia 🙂 Matlab 🙁
Cost Free Hundreds of dollars per year
License Open-Source One year user license
Source Non-profitable foundation and community MathWorks company
Scope Mainly numeric Numeric only
Performance Excellent Faster than Python but slower than Julia
Editor/IDE Jupyter is recommended IDE already included
Packaging Pkg manager included Toolboxes included
Usage Generic Industry and research in academia
Fame Young but starts to be known Old and well-known
Support Community MathWorks
Documentation Growing Okay

JuMP and GLPK packages for optimization with Julia

JuMP:

  • Modeling language and collection of supporting packages for mathematical optimization in Julia
  • Supported solvers: GLPK, CLP, CBC, CPLEX, ECOS, GUROBI, HiGHS, MOSEK, XPRESS, OSQP, PATH, ProxSDP SCIP, SCS, SDPA.

The first step is to add the required packages: JuMP and GLPK. This is done using Pkg which is a built-in package manager in Julia. I can add the requried or desired packages using the following commands in Julia REPL. If Julia is installed, typing Julia in the command line is enough to open REPL (Julia run command).

using Pkg
Pkg.add("JuMP")
Pkg.add("GLPK")

Now, I should import the necessary packages in the IDE which is a Jupyter notebook in our case.

# Import pacakges: JuMP and GLPK 
using JuMP # Julia package - high level programming language
using GLPK # open-source solver - low level language

A test problem

Let us consider the following optimization model:

The feasible region (as x and y are continuous decision variables) is shown below:

According to the gradient of the objective (the red arrow) and direction of the optimization (maximization), the green point is the optimal solution, in which x=3.75, y=1.25, and the optimal value of the objective function is 23.75. I will solve this simple continuous linear programming model with the JuMP package in Julia and comment on its syntax.

Solving the problem

The following commented code aims to solve the proposed linear programming model with JuMP (the name of the package) in Julia:

# Define the model
m = Model(); # m stands for model

# Set the optimizer
set_optimizer(m,GLPK.Optimizer); # calling the GLPK solver

# Define the variables
@variable(m, x>=0);
@variable(m, y>=0);

# Define the constraints 
@constraint(m, x+y<=5);
@constraint(m, 10x+6y<=45);

# Define the objective function
@objective(m, Max, 5x+4y);

# Run the solver
optimize!(m);

# Output
println(objective_value(m)) # optimal value z
println("x = ", value.(x), "\n","y = ",value.(y)) # optimal solution x & y

In future work I will explore the power of Julia in solving supply chain management problems, specifically mixed integer programming (MIP).

The post Optimization with JuMP in Julia appeared first on Supply Chain Data Analytics.

Linear programming in Julia with GLPK and JuMP

By: Jaafar Ballout

Re-posted from: https://www.supplychaindataanalytics.com/linear-programming-in-julia-with-glpk-and-jump/

In previous posts we have covered various linear programming examples in both Python and R. We have e.g. introduced lpSolve in R, PuLP in Python, Gekko in Python, MIP in Python, ortools in Python as well as many other packages and modules for linear programming. In this post I will demonstrate how one can implement linear programming in Julia.

Julia is a flexible dynamic language that is appropriate for scientific and numerical computing. Besides, Julia is an open-source project. Its source code is available on GitHub. Using Julia provides access to many packages already developed for this language. For the linear programming example presented in this post I will use the Julia packages GLPK and JuMP.

Financial engineering example utilizing JuMP and GLPK in Julia

Logo of Julia programming language

The demonstrated example is about a bank loan policy. This simple example will help us understand the power of linear programming in solving most of the problems we face in supply chain management and the financial fields. Indeed, Julia will be incorporated to solve the optimization problem. The example is adapted from Hamdy Taha’s book available on Amazon.

Type of loan Interest rate Bad-debt ratio
Personal 0.14 0.1
Car 0.13 0.07
Home 0.12 0.03
Farm 0.125 0.05
Commercial 0.10 0.02

A bank is in the process of devising a loan policy that involves a maximum of $12 million. The table, shown above, provides the data about the available loans. It is important to note that bad debts are unrecoverable and produce no interest revenue. Competition with other financial institutions dictates the allocation of at least 40% of the funds to farm and commercial loans. To assist the housing industry in the region, home loans must equal at least 50% of the personal, car, and home loans. The bank limits the overall ratio of bad debts on all loans to at most 4%.

Developing a mathematical problem statement

The hardest part of any optimization problem is building the mathematical model. The steps to overcome this hardship are as follows:

  1. Define the decision variables
  2. Write down the objective function
  3. Formulate all the constraints

Decison variables

According to the given in the problem, we need to determine the amount of loan in million dollars. The table shows five categories or types of loans. Thus, we need five decision variables corresponding to each category.

  • x1 = personal loans
  • x2 = car loans
  • x3 = home loans
  • x4 = farm loans
  • x5 = commercial loans

Objective function

The objective function is to maximize profits (net return). The net return is the difference between the revenues, generated by interest rate, and losses due to the bad-debt ratio.

Then, the objective function is as follows:

Constraints

Total Loans should be less or equal to 12 million dollars

Farm and Commercial loans equal at least 40% of all loans

Home loans should equal at least 50% of the personal, car, and home loans

Bad debts should not exceed 4% of all loans

Non-negativity

Application of linear programming in Julia

The first step is to add the required packages to solve the linear program. This is done using the <Pkg> which is the built-in package manager in Julia. We can add the needed packages using the following commands in Julia REPL. If Julia is installed, typing Julia at the command line, in the computer command prompt, is enough to open REPL.

Julia REPL
using Pkg
Pkg.add("JuMP")
Pkg.add("GLPK")

The work presented below is done in a Jupyter notebook with a Julia kernel. JuMP is a modeling language for mathematical optimization in Julia while GLPK is the solver that we will use. After importing the packages in Jupyter, we defined the optimization problem by creating a variable BM that stands for Bank Model. The next step is setting the optimizer by declaring the solver (GLPK) and the model (BM). Moving on, we specified the decision variables, constraints, and objective function.

In [1]:

## Importing the necessary packages ## 
using JuMP
using GLPK

In [2]:

## Defining the model ##
BM = Model() # BM stands for Bank Model

## Setting the optimizer ##
set_optimizer(BM,GLPK.Optimizer)

## Define the variables ##
@variable(BM, x1>=0)
@variable(BM, x2>=0)
@variable(BM, x3>=0)
@variable(BM, x4>=0)
@variable(BM, x5>=0)

## Define the constraints ##
@constraint(BM, x1+x2+x3+x4+x5<=12)
@constraint(BM, 0.4x1+0.4x2+0.4x3-0.6x4-0.6x5<=0)
@constraint(BM, 0.5x1+0.5x2-0.5x3<=0)
@constraint(BM, 0.06x1+0.03x2-0.01x3+0.01x4-0.02x5<=0)

## Define the objective function ##
@objective(BM, Max, 0.026x1+0.0509x2+0.0864x3+0.06875x4+0.078x5)

## Run the optimization ##
optimize!(BM)

Declaring the objective function and constraints in Julia is easier because the algebraic equation can be inputted as it is (i.e. no need to show the multiplication operator between the variable and the constant). After running the optimization model, we can view the output of the model as follows:

In [3]:

BM

Out[3]:

A JuMP Model
Maximization problem with:
Variables: 5
Objective function type: AffExpr
`AffExpr`-in-`MathOptInterface.LessThan{Float64}`: 4 constraints
`VariableRef`-in-`MathOptInterface.GreaterThan{Float64}`: 5 constraints
Model mode: AUTOMATIC
CachingOptimizer state: ATTACHED_OPTIMIZER
Solver name: GLPK
Names registered in the model: x1, x2, x3, x4, x5

In [4]:

objective_value(BM)

Out[4]:

0.99648

In [5]:

objective_sense(BM)

Out[5]:

MAX_SENSE::OptimizationSense = 1

In [6]:

println("x1 = ", value.(x1), "\n","x2 = ",value.(x2), "\n", "x3 = ",value.(x3), "\n", "x4 = ",value.(x4), "\n", "x5 = ",value.(x5))
x1 = 0.0
x2 = 0.0
x3 = 7.199999999999999
x4 = 0.0
x5 = 4.8

Analyzing the output of the model, we can see that the bank should spend 7.2 million dollars on home loans and 4.8 million dollars on commercial loans. This distribution will help the bank maximize its net returns (i.e. profits) to 0.99648 million dollars.

Concluding remarks

In this post, we explored the power of linear programming in the banking sector and used Julia to solve the LP optimization problem. It is nice to see that open-source languages can solve these kinds of problems in an easy way without extensive hours of coding. In the future, we will have an insight into non-linear problems in supply chain management.

The post Linear programming in Julia with GLPK and JuMP appeared first on Supply Chain Data Analytics.