---
title: 【しっかり学ぶ数理最適化】4.4.3~4.5.2
tags: 
author: [京都大学人工知能研究会KaiRA](https://convert.docswell.com/user/kyoto-kaira)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/YJ6L8MVGEV.jpg?width=480
description: 【しっかり学ぶ数理最適化】4.4.3~4.5.2 by 京都大学人工知能研究会KaiRA
published: January 08, 26
canonical: https://convert.docswell.com/s/kyoto-kaira/Z2QDXN-2026-01-08-212039
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/YJ6L8MVGEV.jpg)

しっかり学ぶ数理最適化
4.4.3-4.5.2
工学部B3
野村隆晃
0


# Page. 2

![Page Image](https://bcdn.docswell.com/page/GJ519ZDX74.jpg)

アジェンダ
◼ 整数計画ソルバーの利用
◼ 近似解法について
1


# Page. 3

![Page Image](https://bcdn.docswell.com/page/LE31Y9M475.jpg)

アジェンダ
◼ 整数計画ソルバーの利用
◼ Proximal Policy Optimization
2


# Page. 4

![Page Image](https://bcdn.docswell.com/page/8EDX5G65JG.jpg)

問題の定式化の手法
解きたい整数計画問題のsolverでの表現方法が複数あり、一長一短
LP (Liner Programing方式)
maximize
obj: 2 x1 + 3 x2
subject to
c1: 2 x1 + x2 &lt;= 10
c2: 3 x1 + 6 x3 &lt;= 40
bounds
x1 &gt;= 0
x2 &gt;= 0
general
x1 x2
end
MPS (Mathematical Programing System)
NAME
sample
ROWS
N obj
L c1
L c2
COLUMNS
INTSTART &#039;MARKER&#039;
&#039;INTORG&#039;
x1
obj
-2 c1
2
x1
c2
3
x2
obj
-3 c1
1
x2
c2
6
INTEND &#039;MARKER&#039;
&#039;INTEND&#039;
RHS
RHS
c1
10 c2
40
BOUNDS
PL Bound x1
PL Bound x2
ENDATA
3


# Page. 5

![Page Image](https://bcdn.docswell.com/page/V7PPG3YD78.jpg)

アジェンダ
◼ 整数計画ソルバーの利用
◼ 近似解法
4


# Page. 6

![Page Image](https://bcdn.docswell.com/page/2JV264GGJQ.jpg)

近似解法の性能評価
ある最小化問題Qに対するインスタンスI ∈ Qに対してのアルゴリズムAの性能評価
として、近似比率rを導入 (最適値との比率を定数倍で抑える)
今から紹介するビンパッキング問題に対する近似解法NF法とFF法は2-近似解法
5


# Page. 7

![Page Image](https://bcdn.docswell.com/page/5EGRNKDDJL.jpg)

Next Fit algorithm
各ワゴンに貪欲に詰めて、ワゴンが埋まったら次のワゴンへ詰める方法
1. 𝑖 = 0, 𝑗 = 0として𝑊𝑖 = 0 𝑖 = 0,1, ⋯ , 𝑛 として初期化
2. 𝑊𝑖 + 𝑤𝑗 &lt; 𝐶ならば𝑊𝑖 = 𝑊𝑖 + 𝑤𝑗 , 𝑗 = 𝑗 + 1、収まらないなら𝑖 = 𝑖 + 1
3. j &gt; nになるまで継続
𝑊𝑖 + 𝑊𝑖+1 &gt; 𝐶より、𝑖 = 1,2, … , 𝐴 𝐼 − 1に対して、
𝑊1 + 𝑊2 + 𝑊2 + 𝑊3 + ⋯ + 𝑊𝐴 𝐼 −1 + 𝑊𝐴 𝐼 &gt; 𝐶 𝐴 𝐼 − 1
左辺は2 σ𝑛𝑗=1(𝑤𝑗 ) − 𝑊1 − 𝑊𝐴 𝐼 なので
𝑛
𝐶 ⋅ 𝐴 𝐼 − 1 + 𝑊1 + 𝑊𝐴 𝐼
&lt; ෍ 𝑤𝑗 ≤ 𝐶 ⋅ 𝑂𝑃𝑇 𝐼
2
𝑗=1
6


# Page. 8

![Page Image](https://bcdn.docswell.com/page/4JQVQN1X7P.jpg)

First Fit algorithm
NF法同様に貪欲法だが、無駄を減らした手法
1. 𝑗 = 1として𝑊𝑖 = 0 𝑖 = 0,1, ⋯ , 𝑛 として初期化
2. 𝑾𝒊 + 𝒘𝒋 &lt; 𝑪を満たす最小の𝒊に対して𝑊𝑖 = 𝑊𝑖 + 𝑤𝑗 , 𝑗 = 𝑗 + 1を行う
3. j &gt; nになるまで継続
𝐶
arg𝑚𝑖𝑛 𝑊𝑖 の箱を除いて、すべての箱において𝑊𝑖 ≤
2
(容量を半分以上使っていない箱は一つのみ)
𝐴 𝐼
𝑛
𝑖=1
𝑗=1
𝐶 𝐴 𝐼 −1
&lt; ෍ 𝑊𝑖 − min 𝑊𝑖 &lt; ෍ 𝑤𝑗 ≤ 𝐶 ⋅ 𝑂𝑃𝑇 𝐼
𝑖=1,…,𝐴 𝐼
2
7


# Page. 9

![Page Image](https://bcdn.docswell.com/page/K74MNGR2J1.jpg)

First Fit Decreasing 法
3
重さを降順に並べてからFF法を適用すれば2 近似法になる.
2
FFDでの最適値を𝐴 𝐼 として𝑘 = A(I) とする。
3
𝑊k &gt; CΤ2の場合は、FFDの性質より𝑊𝑗 &gt; CΤ2 (j = 1,2, ⋯ , k − 1)であるため、OPT(I) &gt; 2Τ3A(I)
𝑊k &lt; CΤ2の場合は、 𝑊𝑗 &gt; CΤ2 (j = k, k + 1, ⋯ , A(I))であり、重さの降順で荷物を入れてるため、
j = k, k + 1, ⋯ , A(I)では、すべてのコンテナに2個以上の荷物
j = k, k + 1, ⋯ , A(I)の荷物をj = 1,2, ⋯ , k − 1に移動すれば
n
C ⋅ OPT(I) &gt; ෍
j=1
𝑤𝑗 &gt; C(k − 1) よりOPT(I) &lt; 3Τ2 A(I)
8


