Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

こんにちは。
今日は席替え問題を通じて整数計画問題やpulpの基礎的な内容について紹介したいと思います。

整数計画問題とは最適化問題の解が整数である制約を入れているものになります。

今日は席替え問題と僕が勝手に名付けた問題を用いて整数計画問題について説明します。

席替え問題とは決められた席数の中で各々の人がそれぞれの席に対して希望度を持っていて、全体の希望をなるべく満たすような席替えを決めるという問題です。
図で考えると以下のようになります。
スクリーンショット 2018-03-23 12.18.17.png

定式化

数学的に定式化していきます。

生徒$i$は席数次元の希望度ベクトル$W_i$を持っています。
生徒$i$の座席の所属を表すベクトルを$x_i$で定義し、座席$j$に座るならば1、座らないならば0が入るベクトルです。この$x_i$が求める変数になります。

生徒集合を$I$で、座席集合を$S$で定義します。

目的関数は、$\displaystyle \sum_{i \in I} {W_i}^t x_i$になります。全体の希望度を最大化したいのでこの目的関数を最大化します。

制約を入れて行きます。

制約① 1つの席には1人しか座れない
\displaystyle \sum_{i \in I} x_{ij} = 1 \ (\forall j)
制約② 1人につき1つの席にしか座れない
\displaystyle \sum_{j \in S} x_{ij} = 1 \ (\forall i)
制約③ 席には座るか否か
x_{ij} \in \{ 0 ,1 \} \ (\forall i\in I, \forall j\in S )

まとめて書くと今回解く最適化問題は以下のようになります。

\begin{align}
Maximize \hspace{22pt}& \displaystyle \sum_{i \in I} {W_i}^t x_i\\
subject \ to \displaystyle \sum_{i \in I} x_{ij} &= 1 \ (\forall j)\\
\displaystyle \sum_{j \in S} x_{ij} &= 1 \ (\forall i)\\
x_{ij} &\in \{ 0 ,1 \} \ (\forall i, \forall j )
\end{align}

pulpによる実装

定式化が完了したのでpulpを用いて実装して行きます。

pulpの使い方については以下の記事が非常にまとめられています。
https://qiita.com/mzmttks/items/82ea3a51e4dbea8fbc17

seat_change.py
import pulp
import random
import numpy as np


def main():
    n = 10
    seat = n
    W = np.zeros([seat,n])

    #値を入れる
    for i in range(seat):
        for j in range(n):
            W[i,j] = random.random()

    # 各行を割合に変換
    sumbox = W.sum(axis=0, dtype='float') 
    W /= sumbox


    # 問題の宣言
    problem = pulp.LpProblem(name='change seat', sense=pulp.LpMaximize)

    # 変数の宣言
    x = {(i,j):pulp.LpVariable(name='x_{}_{}'.format(i, j), cat='Binary') for i in range(seat) for j in range(n)}

    # 目的関数
    problem += pulp.lpSum([W[i,j]*x[i,j] for i in range(seat) for j in range(n)])

    #一つの席には一人だけ
    for i in range(seat):
        problem.addConstraint((pulp.lpSum([x[i,j] for j in range(n)]) == 1),"seat_limitation_{}".format(i))

    #ユーザーは1つの席のみに入る
    for j in range(n):
        problem.addConstraint((pulp.lpSum([x[i,j] for i in range(seat)]) == 1),"user_gets_onlyoneseat_{}".format(j))

    status = problem.solve()
    print(pulp.LpStatus[status])
    print("目的関数値 = {}".format(pulp.value(problem.objective)))


    for j in range(n):
        for i in range(seat):
            if pulp.value(x[i,j]) > 0:
                print(f'user {j} seat {i} : {pulp.value(x[i,j])}')



if __name__ == '__main__':
    main()

③の制約は変数の宣言の際に'Binary'という形によって入っています。
また、生徒の希望度は今回、乱数を用いています。

実行すると以下のような結果が得られます。
スクリーンショット 2018-03-23 12.59.49.png

このようにして席替え問題をpulpを用いて解くことができました。

最後に

整数計画法として解くことのいい面の1つとして、この基本の問題に対して制約を追加することでやりたい問題を解くことができることです。

例えば、
人に重み付けをして優先度を考慮する
隣り合う人の条件を加える
などが考えられます。どのように定式化するのかは考えてみてください。

cheerfularge
数学科
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away