📂Optimization

Solving Linear Programming Problems with Julia

Overview

To solve optimization problems, one can use the JuMP package[^1]. JuMP stands for Julia Mathematical Programming. Compared to other languages, coding in Julia is almost like directly transcribing mathematical formulas, which is very intuitive.

Code

$$\begin{matrix} \text{Maximize} & & x_{1} & + & x_{2} \\ \text{subject to} &-& x_{1} & + & x_{2} & \le & 1 \\ & & x_{1} & & & \le & 3 \\ & & & & x_{2} & \le & 2 \end{matrix}$$

As a simple example, let’s solve the maximization problem described in $x_{1} , x_{2} \ge 0$. At the shrimp sushi restaurant, this problem was solved manually using the simplex method, and the solution $\left( x_{1}^{\ast}, x_{2}^{\ast} \right) = (3,2)$ is known. This linear programming problem can be transcribed and solved as follows.

Full Code

using JuMP
using GLPK
model = Model(GLPK.Optimizer)

@variable(model, x₁ ≥ 0)
@variable(model, x₂ ≥ 0)

@objective(model, Max, x₁ + x₂)

@constraint(model, c1, - x₁ + x₂ ≤ 1)
@constraint(model, c2,   x₁       ≤ 3)
@constraint(model, c3,         x₂ ≤ 2)

print(model)

optimize!(model)

@show objective_value(model)
@show value(x₁)
@show value(x₂)

Model(), GLPK.Optimizer

julia> using JuMP

julia> using GLPK

julia> model = Model(GLPK.Optimizer)
A JuMP Model
Feasibility problem with:
Variables: 0
Model mode: AUTOMATIC
CachingOptimizer state: EMPTY_OPTIMIZER
Solver name: GLPK

By using Model(), one can create a linear programming problem and use GLPK.Optimizer as the optimization algorithm. Note that GLPK is also an independent package and needs to be installed separately.

@variable(), @objective(), @constraint()

julia> @variable(model, x₁ ≥ 0)
x₁

julia> @variable(model, x₂ ≥ 0)
x₂

julia> @objective(model, Max, x₁ + x₂)
x₁ + x₂

julia> @constraint(model, c1, - x₁ + x₂ ≤ 1)
c1 : -x₁ + x₂ <= 1.0

julia> @constraint(model, c2,   x₁      ≤ 3)
c2 : x₁ <= 3.0

julia> @constraint(model, c3,        x₂ ≤ 2)
c3 : x₂ <= 2.0

Variables are added with @variable(), the objective function is set with @objective(), and constraints are added with @constraint(). Honestly, it’s almost like directly writing down the equations. If we print out this model, we can see that the problem is defined almost exactly as the formulas.

julia> print(model)
Max x₁ + x₂
Subject to
 c1 : -x₁ + x₂ <= 1.0
 c2 : x₁ <= 3.0
 c3 : x₂ <= 2.0
 x₁ >= 0.0
 x₂ >= 0.0

optimize!(), @show

julia> optimize!(model)

julia> @show objective_value(model)
objective_value(model) = 5.0
5.0

julia> @show value(x₁)
value(x₁) = 3.0
3.0

julia> @show value(x₂)
value(x₂) = 2.0
2.0

The optimize!(model) method is used to perform the optimization, and @show is used to display the results. The results are, as we already knew, x₁$=x_{1} = 3$, x₂$=x_{2} = 2$.

Environment

• OS: Windows
• julia: v1.7.0
• JuMP v0.21.5

See Also

• How to solve linear programming problems with Excel
• How to solve linear programming problems in Julia with JuMP.jl
• How to solve linear programming problems in Python with scipy
• How to solve linear programming problems in MATLAB with Optimization Toolbox
• How to solve linear programming problems in R with lpSolve

---

概要

JuMPパッケージを使えばいい[^1]。JuMPは Julia Mathematical Programmingの略だ。他の言語と比べた場合、Juliaでのコーディングはほぼそのまま数式を移して書くレベルで直感的だ。

コード

$$\begin{matrix} \text{Maximize} & & x_{1} & + & x_{2} \\ \text{subject to} &-& x_{1} & + & x_{2} & \le & 1 \\ & & x_{1} & & & \le & 3 \\ & & & & x_{2} & \le & 2 \end{matrix}$$

簡単な例として、$x_{1} , x_{2} \ge 0$にあるような最大化問題を解いてみよう。生エビ寿司屋では、この問題をシンプレックスメソッドを使って手で解いてみて、その答えが$\left( x_{1}^{\ast}, x_{2}^{\ast} \right) = (3,2)$であることを知っている。この線形計画問題は以下のように転写して解ける。

全体コード

using JuMP
using GLPK
model = Model(GLPK.Optimizer)

@variable(model, x₁ ≥ 0)
@variable(model, x₂ ≥ 0)

@objective(model, Max, x₁ + x₂)

@constraint(model, c1, - x₁ + x₂ ≤ 1)
@constraint(model, c2,   x₁       ≤ 3)
@constraint(model, c3,         x₂ ≤ 2)

print(model)

optimize!(model)

@show objective_value(model)
@show value(x₁)
@show value(x₂)

Model(), GLPK.Optimizer

julia> using JuMP

julia> using GLPK

julia> model = Model(GLPK.Optimizer)
A JuMP Model
Feasibility problem with:
Variables: 0
Model mode: AUTOMATIC
CachingOptimizer state: EMPTY_OPTIMIZER
Solver name: GLPK

Model()を使って線形計画問題を作り、最適化アルゴリズムとしてGLPK.Optimizerを使用する。なお、GLPKも独立したパッケージなので、別途インストールする必要がある。

@variable(), @objective(), @constraint()

julia> @variable(model, x₁ ≥ 0)
x₁

julia> @variable(model, x₂ ≥ 0)
x₂

julia> @objective(model, Max, x₁ + x₂)
x₁ + x₂

julia> @constraint(model, c1, - x₁ + x₂ ≤ 1)
c1 : -x₁ + x₂ <= 1.0

julia> @constraint(model, c2,   x₁      ≤ 3)
c2 : x₁ <= 3.0

julia> @constraint(model, c3,        x₂ ≤ 2)
c3 : x₂ <= 2.0

@variable()で変数を追加し、@objective()で目的関数を定め、@constraint()で制約条件を追加する。正直なところ、数式をそのまま書いているのと同じだ。このモデルを出力してみると、次のようにほぼそのままの数式で問題が定義されていることが確認できる。

julia> print(model)
Max x₁ + x₂
Subject to
 c1 : -x₁ + x₂ <= 1.0
 c2 : x₁ <= 3.0
 c3 : x₂ <= 2.0
 x₁ >= 0.0
 x₂ >= 0.0

optimize!(), @show

julia> optimize!(model)

julia> @show objective_value(model)
objective_value(model) = 5.0
5.0

julia> @show value(x₁)
value(x₁) = 3.0
3.0

julia> @show value(x₂)
value(x₂) = 2.0
2.0

optimize!(model)メソッドを使って最適化を行い、@showを使って結果を表示する。その結果は、我々がすでに知っていた通り、x₁$=x_{1} = 3$, x₂$=x_{2} = 2$である。

環境

• OS: Windows
• julia: v1.7.0
• JuMP v0.21.5

関連項目

• エクセルで線形計画問題を解く方法
• Juliaで線形計画問題を解く方法 JuMP.jl
• Pythonで線形計画問題を解く方法 scipy
• MATLABで線形計画問題を解く方法 Optimization Toolbox
• Rで線形計画問題を解く方法 lpSolve

---