席替え問題による整数計画問題入門(pulp) - Qiita

こんにちは。 今日は席替え問題を通じて整数計画問題やpulpの基礎的な内容について紹介したいと思います。 整数計画問題とは最適化問題の解が整数である制約を入れているものになります。 今日は席替え問題と僕が勝手に名付けた問題を用いて整数計画問題について説明します。 席替え問題とは決められた席数の中で各々の人がそれぞれの席に対して希望度を持っていて、全体の希望をなるべく満たすような席替えを決めるという問題です。 図で考えると以下のようになります。 #定式化 数学的に定式化していきます。 生徒$i$は席数次元の希望度ベクトル$W_i$を持っています。 生徒$i$の座席の所属を表すベクトルを$x_i$で定義し、座席$j$に座るならば１、座らないならば０が入るベクトルです。この$x_i$が求める変数になります。 生徒集合を$I$で、座席集合を$S$で定義します。 目的関数は、$\displaysty