---
title: 【しっかり学ぶ数理最適化】4.4.1~4.4.2
tags: 
author: [京都大学人工知能研究会KaiRA](https://convert.docswell.com/user/kyoto-kaira)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/G7WZK24272.jpg?width=480
description: 【しっかり学ぶ数理最適化】4.4.1~4.4.2 by 京都大学人工知能研究会KaiRA
published: December 25, 25
canonical: https://convert.docswell.com/s/kyoto-kaira/K13LWG-2025-12-25-211448
---
# Page. 1

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

2025年後期輪読会
数理最適化
分枝限定法と切除平面法 (4.4.1~4.4.2)
京都大学 工学部 情報学科 数理工学コース
稲葉 陽孔
1


# Page. 2

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

アジェンダ
■ 概要
■ 分枝限定法
■ 切除平面法
2


# Page. 3

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

概要
文枝限定法と切除平面法とは
NP困難な組合せ最適化問題の解法アルゴリズム
文枝限定法
-
直接は解きにくい問題を小さい問題に分割(分枝操作)と、その子問題から本問題の最適解を得ら
れるかの判定(限定操作)を繰り返して解アルゴリズム
切除平面法
-
緩和問題の最適化から始め、実行可能解を残しつつ緩和問題の最適解を除去していく、制約条件
を組織的に追加し続けるアルゴリズム
3


# Page. 4

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

分枝限定法
アルゴリズム(整数計画問題)
・・限定操作
・・限定操作
・・分枝操作
整数計画問題
線形計画緩和問題
整数計画問題の制限をxj&gt;=0(j=1,,n)に変更したもの
子問題
整数計画問題において、ある１変数の値をとる範囲の制約を追加したもの
4


# Page. 5

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

分枝限定法
アルゴリズム(整数計画問題・分枝操作)
分枝操作による子問題の追加イメージ
5


# Page. 6

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

分枝限定法
アルゴリズム(整数計画問題・限定操作)
以下の特性をもとに、Step４により子問題Pが暫定解より優れいている解を持ちうるか判断し、
Step５で子問題Pをこれ以上深掘り(分枝操作)して実際の問題の解を探索する必要があるか判定
6


# Page. 7

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

分枝限定法
アルゴリズム(整数計画問題・探索の効率化)
分枝限定法では確かに最適解を求められるが、探索する子問題の数を抑えないと計算量が多いので、
・冗長な変数や制約条件の削除(前処理)
・考察に基づき最適性を失わずに一部の変数を固定する(変数固定)
などによって探索数を抑えようと考えられている。
また、子問題の選び方にも様々な工夫が存在する。
7


# Page. 8

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

分枝限定法
アルゴリズム(整数計画問題・子問題の選び方)
深さ優先探索
最後に生成された子問題を選ぶ手法
子問題への分枝の様子を探索木で表すと、
(手法の性質上)最も深い子問題を常に解いていくことになる
また、L内の子問題の数を抑えられるので記憶領域の使用量が減る
最良優先探索
子問題の最適値を推定し、その値が最大(最小化問題なら最小)となる子問題を選び続ける手法
推定値として、(子問題の)線形緩和問題の最適値を用いる
また、最終的に生成される子問題の数が最小になる(→アルゴリズムの計算量が抑えられる)
しかし、初期は探索木の上層にある子問題が選ばれる傾向にあり、記憶領域の使用量が多くなりがち
8


# Page. 9

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

切除平面法
アルゴリズム
切除平面
元々の制約式に重みをかけたり(式１)変形させたもの(式２)で、緩和問題の解を実行解から除去するも
の
また、制約式は整数計画問題の妥当式(全ての実行可能解が満たす式)でないといけない
(式１)
(式2：フバータル・ゴモリー不等式)
※式1・式2は整数計画問題の妥当式である。
9


# Page. 10

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

切除平面法
切除平面の作り方
考える問題
(スラック変数を用いて)条件を等式に変形した整数計画問題
切除したい実行可能解
線形計画緩和問題の最適基底解(x_b,x_n)
辞書となる式：
整数計画問題
線形計画緩和問題
10


# Page. 11

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

切除平面法
切除平面の作り方・最適基底解の更新
xiが非負より、緩和問題の
妥当不等式として成立
(整数計画問題では)xiは整数より左辺は整数で、
整数計画問題の妥当不等式になる
→切除平面として成立する
式3
この切除平面にスラック変数を導入し、式 3にするとスラック変数 x_{n+1}
の等式制約(式4)に変形できる。
しかし、x_{n+1}&lt;0になるので双対単体法で xの基底解を求める
※式4はx_Nが0なので式5となり、右辺&lt;0よりx_{n+1}&lt;0
式4
式5
11


