最適化問題は，式(1)に示される目的関数，制約条件，決定変数が持つ特徴に基づいて， 次のような点から分類される．

・目的関数および制約条件を定める関数は，は線形/非線形であるか， また凸関数/凹関数であるか．
・決定変数のとり得る値は連続/離散であるか．
・全ての値は決定的に定まるのか，確率的要素が含まれているのか．


代表的な最適化手法のいくつかを次に述べる．

線型計画法 (Linear Programming; LP)

目的関数と制約条件が 全て線形であり，決定変数が連続値をとる最適化問題を対象とする． 非常によく研究され，様々な場で使用されている手法である．代表的なアルゴリズムとして シンプレックス法がある．

分枝限定法 (Branch-and-Bound Method; BAB)

目的関数や制約 条件が非線形であっても，また決定変数が離散的であっても適用可能な手法であり， 組合せ最適化問題に対して適用されることが多い．1つの大きな(探索空間の広い)問題を， 複数の小さな部分問題に分解し，部分問題において理想的な条件が成立していると仮定することで求まる (部分問題の)最適値に基づいて，効率的な探索を行うための手法．適用範囲が広いが， 同時に適用対象の一般的な形式的表現を得ることが困難となっている． そのため汎用のアルゴリズムは存在せず，問題ごとにモデル化が行われ， それに基づいたアルゴリズムが構築される．

動的計画法 (Dynamic Programming; DP)

多段階決定問題に帰着 される組合せ最適化問題を主な対象とする手法．ただし， 対象問題においては“最適性の原理”が成り 立っていなければならない．

---

多スタート局所探索法(multi-start local search)

局所探索法 の初期点(通常はランダムに生成される)を多数選んで， より大域的な最適解を得ようとする方法．

シミュレーテッド・アニーリング(Simulated Annealing; SA)

受理判定の手続きに確率的要素を取り入れた方法で，改悪であっても確率的に暫定解が更新される． さらに，焼き鈍し(annealing)”における温度制御にならって，受理確率を温度パラメータで制御する.

タブーサーチ(tabu search)

近傍内での最良の解を求め，これが改悪であっても，現時点での解を更新することを基本とする． しかしながら，この操作をそのまま実行すると循環(cycling)が生じやすい． そこで，タブーリストTを用意しておき (例えば，過去何回かの繰り返しで，訪れた解のリスト)， T内への遷移を禁止することで循環を抑制している．

遺伝アルゴリズム(Genetic Algorithms; GAs)

自然界における生物・生体の集団遺伝に基づく進化の過程を模倣した最適値探索法であり， 複数個の候補解(集合)を保持して探索を進めるという点に特徴がある． 摂動に対応する手続きとしては，交叉(crossover)や突然変異(mutation)などの 遺伝的操作(genetic operation)が用いられる．

---