Overview

This is a quick introduction to writing programs for solving optimization models using Julia and Julia for Mathematical Programming (JuMP) for the Windows Operating System. This is not an exhastive guide but is aimed at providing a quick introduction. The goal for this tutorial is to help undergraduate and graduate students with interest in transportation and freight network analysis and limited knowledge of programming to start writing basic code to solve linear, integer, and nonlinear formulations.

There are several very good detailed sources for Julia and JuMP.

The repository contains all the codes used in this tutorial.

Installing Julia and JuMP

This section describes how to install Julia and JuMP for the Windows Operating System.

Download Julia

Download Julia from the official website: http://julialang.org/downloads/. Pick the right version - 32 bit or 64 bit depending on the Windows Operating Systems installed on your computer.

Pick Installation Directory

For the installation directory, pick something simple like C:\julia.

Modifying the PATH variable

Add the C:\julia\bin to the PATH variable. Details on changing the PATH variable can be obtained from this website: http://www.computerhope.com/issues/ch000549.htm.

Julia Interface

In the Command Prompt, type julia and press enter. You should now get the julia command interface shown below.

Adding Packages

You can now add packages to julia using the Pkg.add() command. Type the following command at the julia prompt and press enter to add the open source Linear Programming solver Clp.

julia> Pkg.add("Clp")

Similarly, type the following command and press enter to install JuMP a modeling language for optimization.

julia> Pkg.add("JuMP")

If you want to install the Gurobi solver, in the julia prompt type the following command and press enter. Make sure you have installed Gurobi in your computer before adding the Gurobi package.

julia> Pkg.add("Gurobi")

The list of all solvers supported by JuMP can be found here: https://jump.readthedocs.org/en/latest/installation.html#getting-solvers

Testing your first code

In this code, you will learn how to solve the following Linear Program using JuMP.

\[ \begin{aligned} \text{Min} \,\, 10x + 26y & \\ 11x + 3y & \ge 21 \\ 6x + 20y & \ge 39 \\ x \ge 0 ,& y \ge 0 \end{aligned} \]

Copy the following code into a file created using your favorite text editor. I use Notepad++. Save the file as LP1.jl.

using JuMP
m = Model()
@variable(m, x >=0)
@variable(m, y >=0)
@objective(m, Min, 10x + 26y)
@constraint(m, const1,  11x + 3y >=  21)
@constraint(m, const2,   6x + 20y >= 39)
status = solve(m)
println("Status = $status")
println("Optimal Objective Function value: ", getobjectivevalue(m))
println("Optimal Solutions:")
println("x = ", getvalue(x))
println("y = ", getvalue(y))

Go the directory where you saved LP1.jl and open the command prompt window. You can do that by navigating to the corresponding folder, pressing Shift and then Right Click. You should see Open Command Window here in the resulting window. You can run the julia code in two ways. In the command window run the following command:

C:\Users\avinash> julia LP1.jl

Type julia and press enter to open the julia command prompt and run the following command.

julia> include("LP1.jl")

In both cases you should get the optimal objective function of 54.0 and corresponding optimal solutions.

Explanation of the Program LP1.jl

This section is heavily based on the JuMP documentation available at: https://jump.readthedocs.org/en/latest/.

Creating a Model

using JuMP

This indicates you are using JuMP in your model.

m = Model()

m is a Julia object created by calling the constructor Model(). All the variables and constraints in the formulation is associated with this object. Note that m is just a name given to the object and you can replace it by other names also.

If you want to use other solvers such as Gurobi replace the above two lines by the following:

using JuMP, Gurobi
m = Model(solver=Gurobisolver())

Creating Variables

@variable(m, x >=0)
@variable(m, y >=0)

In the above example, two variables x and y are created using the @variable macro. Note that the first argument m is the model object. Lower bounds and upper bounds can be added to variables as shown below:

@variable(m, x >= LB)
@variable(m, x <= UB)
@variable(m, LB  <=  x  <= UB)

Integer and Binary restrictions can be enforced as shown below with a third argument.

@variable(m, x >=0, Int)
@variable(m, x >=0, Bin)

The following expression defines a two dimensional array variable with dimension M*N.

@variable(m, x[1:M,1:N]  >= 0)

Conditions can be enforced on the indices. Initial values can be assigned as shown below:

@variable(m, x[i=1:5], start=(i))

Defining Objective Function and Constraints

The following expression defines the minimization objective function. The second argument defines whether it is a minimization or a maximization.

@objective(m, Min, 10x + 26y)

The following expressions defines the two constraints. Use operators such as sum which simplifies handling array expressions.

@constraint(m, const1,  11x + 3y >=  21)
@constraint(m, const2,   6x + 20y >= 39)

The solver can have the following statuses: Optimal, Unbounded, Infeasible, UserLimit, Error, and NotSolved.

status = solve(m)
println("Status = $status")

The following commands print the objective function value and the optimal solution.

println("Optimal Objective Function value: ", getObjectiveValue(m))
println("Optimal Solutions:")
println("x = ", getValue(x))
println("y = ", getValue(y))

Make the above problem an integer program by enforcing integrality on x and y. Save the resulting file as IP1.jl. Run the program. You should get the optimal objective function value of 66.0.

Basics of Julia

The objective of this section is to provide a brief introduction to Julia needed for writing programs to solve network optimization and mathematical programming problems. A more detailed version can be found at:

First Julia Program

Open Notepad++. Create a new file. Save as Hello_World.jl. Go to the directory where it is saved. Open Command Window. Open Julia. Run the program by typing the following command and the pressing enter at the Julia prompt. You should see the output Hello World.

julia> include("HelloWorld.jl")

You can exit Julia using the quit() command.

julia> quit()

Data types and variables

This section focuses on integer, floating points, boolean data types and associated arithmetic operations.

5 is an example of an integer data type whereas 5.0, 6.2 are examples of floating point data types. Within integer and floating point data types, Julia has 8, 16, 32, 64, and 128 bit variants for integers and 16, 32, and 64 bit variants for float. In integer, there is the signed and unsigned variant.

The actual data type depends on whether you have 32 bit or 64 bit architecture. To get the actual datatype use the typeof() command.

In the Julia prompt type typeof(5) and press Enter. I got the output as Int64.

julia> typeof(5)   # The output should be Int64 or Int32

Try typeof(8.3) and check the output.

All standard arithmetic operators are defined.

julia> 3 + 2    # The output should be 5
julia> 3 - 2    # The output should be 1
julia> 3/2      # The output should be 1.5
julia> div(3,2) # The output should be 1
julia> 3^2      # The output should be 9
julia> 3%2      # The output should be 1

Julia has the following comparison operators on all relevant data types:

  • equal to ==
  • not equal to !=
  • less than <
  • less than or equal to <=
  • greater than >
  • greater than or equal to >=

Boolean is another data type which can take two values-true or false.

julia> 3==2   #False
julia> 3!=2   #True
julia> 3>=2   #True

In julia, there is no need to declare variables before assigning them.

julia> x=2    # Assigns 3 to an integer variable x
julia> y=5.2  # Assigns 5.2 to a float variable y
julia> x+y    # Answer is 8.2

Arrays can be used to store a sequence of values. In julia, array indexes start at 1 (and not at 0 as in C or C++). Different ways of creating arrays are shown below.

julia> a=[8,9,10] # Creates an array with three values 8,9, and 10
julia> a[1]       # Output is 8
julia> b=[8;9;10] # Creates and array with three values 8,9, and 10
julia> b[2]       # Output is 9
julia> b[end]     # Output is 10
julia> push!(b,2) # Array becomes 8,9,10,2
julia> pop!(b)    # Array becomes 8,9,10
julia> push!(b,2) # Array b becomes 8,9,10,2
julia> sort!(b)   # Array b becomes 2,8,9,10
julia> length(b)  # Returns the length of the array 4
julia> b[2:4]     # Returns the last three values 8,9,and 10
julia> append!(a,b) # Returns 8,9,10,2,8,9,10. Fuses the two arrays

Julia also has multi-dimensional arrays.

julia> c[1:2:8]   # Creates a single dimensional array 1,3,5, and 7
julia> d = [1 2 3;8 9 10] # Creates a multi-dimensional array with 2 rows and 3 columns

You can use the same concept to create lists of non-integers also.

julia> cities=["Nasvhille","Austin","Pittsburgh"]

Dictionaries can be used to create maps in julia.

julia> population=["Nashville"=>200,"Austin"=>500,"Pittsburgh"=>300]
julia> keys(population) # Output is the three cities
julia> values(population) # Output is the three values

Conditional Statements and Loops

IF loops can be used to execute codes based on conditions. Copy the following code into a new Julia file and execute it. You should get the output as x is larger than 5.

x=10
println(x)
if(x > 5)
  println("x is larger than 5")
elseif(x < 5)
  println("x is smaller than 5")
else
  println("x is equal to 5")
end

While loops execute a section of code until a condition is met. The following code prints 1 through 10.

y=0
while y<=x
  println(y)
  y=y+1
end

Julia has multiple forms of FOR loops. The following loop should print the three cities in three consecutive lines.

cities = ["Nashville", "Austin" , "Pittsburgh"]
for a in cities
  println(a)
end

The output of the following loops should be 2,3,6,8, and 10.

z=[1:10]
for i in z
  if i%2==0
    println(i)
  end
end

Functions

Naming conventions in Julia:

  • Underscores are discouraged even in word separation
  • Names of Types begin with capital letters
  • Names of functions are in lower case without underscores
  • Functions which modify inputs have their names end in !, for example append!()

Most functions in julia have the following format.

FUNCTION namefunc(args)
  RETURN arg1,arg2,arg3
END

The capitalized terms above are julia keywords. For example the following function adds two numbers an returns 11.

function add2(a,b)
  return a+b
end
x=5
y=6
z=add2(x,y)
println(z)

Note that the above function can be written in a more compact manner as shown below.

add2comp(a,b) = a + b

Basic Julia/JuMP Programs

LP1.jl, IP1.jl, and NLP1.jl provide examples of a simple linear program, integer program, and nonlinear program solved using JuMP.

You may need to add the Graphs package before running several of the programs listed in this section. The repository contains several introductory programs.

NetworkInput.jl should provide you with a sample file to read input from file and write output to file. Make sure NetworkInput.jl and AhujaNet.txt are in the same directory.

Djikstra.jl is a sample file demonstrating the use of in built Djikstra’s algorithm function in determining shortest path. The output can be found in Output.txt

ShortPath.jl is a sample file demonstrating solution of shortest path using a Linear Programming formulation.

CapFl.jl is a capacitated facility location model. The input cap41.txt file corresponds to the standard cap41 dataset available at: http://people.brunel.ac.uk/~mastjjb/jeb/orlib/capinfo.html

HubLoc.jl is a Single Allocation Hub Network Design formulation based on the modification of SALP formulation originally provided by

Ernst, A.T., Krishnamoorthy, M., 1999. Solution algorithms for the capacitated single allocation hub location problem. Annals of Operations Research 86 (0), 141-159.

The modified formulation is presented in

Alumur, S.A., Nicketl, S., Saldanha-da-Gama, F., 2012. Hub Location under Uncertainty. Transportation
Research Part B, 46(12), 529-543.

The CAB data set PHUB4 is used in this model.