paint-brush
Linear optimization using Juliaby@jayantakshirsagar
3,972 reads
3,972 reads

Linear optimization using Julia

by Jayanta KshirsagarFebruary 26th, 2018
Read on Terminal Reader
Read this story w/o Javascript
tldt arrow

Too Long; Didn't Read

In this article, we will be focusing on modeling linear optimization problems using Julia.

Company Mentioned

Mention Thumbnail
featured image - Linear optimization using Julia
Jayanta Kshirsagar HackerNoon profile picture

Write your first Julia code to solve linear optimization problem.

In this article, we will be focusing on modeling linear optimization problems using Julia.


To know more about Julia, please find link here.To know more about linear optimization, please find link here.


Julia has a package named JuMP for modeling optimization problems.JuMP is a domain specific modeling language which can be used for linear, mixed -integer, non-linear problems.

JuMP internally uses MathProgBase. MathProgBase provides solver independent high level functions, which can be used for interaction with number of solvers like Cbc, Clp, CPLEX, Gurobi etc. In this example, We will be using Cbc as a solver. Cbc is an open source mathematical solver which supports linear, as well as mixed integer problems.

1. Create a model


using JuMPusing Cbc

lpModel = Model(solver = CbcSolver(seconds = 3600))

Before we create model using JuMP, let’s make sure that we install JuMP and Cbc.


Pkg.add(“JuMP”)Pkg.add("Cbc")

2. Define variables


@variable(lpModel, x <= 5)@variable(lpModel, y >= 6)

We are creating two variables, namely x and y with the predefined bounds.

3. Create constraints


@constraint(lpModel, x+y <= 20)@constraint(lpModel, 2x + 3y >= 28)

4. Create an Objective

@objective(lpModel, Max, x + y)

5. Solve and read the answer

status = JuMP.solve(lpModel)


getvalue(x)getvalue(y)

Let’s take an example.

Once, group of 18 students entered newly set up cafe. The cafe had just two items and menu card was something like this.


1. Tea INR 20 2. Coffee IN R30


Out of 18, 5 of the students asked for Tea and 6 said they would have Coffee. Remaining 7 were okay with either of the beverage.Also, they did not want to spend more than 470 INR. That confused the hotel manager. He used to get INR 2of profit on Tea and INR 3 of profit on Coffee. He wanted to maximize the profit and wasn’t sure how to do that. Let’s try and help him.

Solution

Assume, x is number of students asking for Tea and y be the number of students who want coffee.

At least 5 of them want Tea.


x >= 5Similarly, y >= 6


We know, there are total 18 students, and hence, x + y = 18.Total expense can not be more than 470, and hence

20x + 30y <= 470

The goal is to maximize profit, which means

Maximize profit, denoted by 2x + 3y, as every cup of Tea will generate profit of INR 2, and every mug of coffee will generate profit of INR 3.


using JuMPusing Cbc

lpModel = Model(solver = CbcSolver(seconds = 3600))


@variable(lpModel, x >= 5)@variable(lpModel, y >= 6)


@constraint(lpModel, x+y == 18)@constraint(lpModel, 20x + 30y <= 470)

@objective(lpModel, Max, 2x + 3y)

status = JuMP.solve(lpModel)


println("Number of Tea Cups: $(getvalue(x))")println("Number of Coffee Mugs : $(getvalue(y))")

Above code should output


Number of Tea cups: 7.0Number of Coffee Mugs : 11.0

Which would mean, the maximum profit should be

2 * 7 + 3 * 11 = INR 47

Now, let’s make the problem a bit more interesting. Instead of total budget being INR 470, let’s assume the budget is INR 475.

So, we need to modify one of the constraints.

@constraint(lpModel, 20x + 30y <= 475)

That’s easy. Let’s run the entire code with modified constraint and see what the output is.


Number of Tea Cups: 6.5Number of Coffee Mugs : 11.5

What went wrong? Cause, there’s no point serving someone with half cup of Tea and half mug of coffee, right? We need to make sure, that ‘x’ and ‘y’ are discrete integer variables and not continuous.Let’s change the variable declarations to


@variable(lpModel, x >= 5, Int)@variable(lpModel, y >= 6, Int)

This would also lead to same output as that of earlier.


Number of Tea Cups: 7.0Number of Coffee Mugs : 11.0

Thanks for reading. Your feedback is highly appreciated.