{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# 10-Solving Job Sequencing Problem with PyQUBO\n", "この節では、[Ising formulations of many NP problems](https://arxiv.org/pdf/1302.5843v3.pdf) から6.3. Job Eequencing with Integer LengthsをPyQUBOを用いて解きます。" ] }, { "cell_type": "markdown", "metadata": { "colab_type": "text", "id": "view-in-github" }, "source": [ "[![Open in Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/OpenJij/OpenJijTutorial/blob/master/source/ja/010-JobSequencingPyqubo.ipynb)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 整数長ジョブスケジューリング問題\n", "整数長ジョブスケジューリング問題は以下のような状況の最適解を求める問題であり、NP困難な問題の一つです。まずは具体的な問から考えてみましょう。" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 具体例\n", "分かりやすくするために具体的に以下のような問を考えます。\n", "> 10個の仕事と3個のコンピュータがあります。10個の仕事の長さは$1,2,\\cdots,10$です。\n", "> どのようにコンピュータに仕事を割り振れば仕事にかかる時間の最大値$\\max M_\\alpha$を最小化できるか考えます。\n", "> 例えば、$V_1=\\{9,10\\},V_2=\\{1,2,7,8\\},V_3=\\{3,4,5,6\\}$とすると$\\max(M_1,M_2,M_3)=19$となって問の最適解となります。" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "
\n", " \n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 問題の一般化\n", "まず、N個の仕事$\\{1,2,\\dots ,N \\}$とm個のコンピュータがあるとします。各仕事が$\\alpha$をindexとして持っているものと考えます。\n", "仕事にかかる時間のリスト$L$を作ります。\n", "\n", "$$L=\\{L_1,L_2,\\dots L_N\\}$$\n", "\n", "コンピュータ$\\alpha$で行われる仕事の集合を$V_\\alpha$としたとき、コンピュータ$\\alpha$で仕事を終えるまでの時間は$M_\\alpha = \\sum_{i\\in V_\\alpha} L_i$となります。コンピュータ$\\alpha$で行う仕事を表すバイナリ変数を$x_{i,\\alpha}$としたとき、コンピュータが仕事を終わらすためにかかる時間の最大値は以下のように表すことができます。\n", "\n", "$$max M_\\alpha=M_1 = \\sum_i L_ix_{i,1}\\tag{1}$$\n", "$$x_{i,\\alpha}=\\{0,1\\}\\tag{2}$$\n", "\n", "$$(\\forall \\alpha \\in \\{1,2,\\dots,N\\})$$\n", "\n", "この$M_1$を最小化することがこの問題の目的となります。" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## QUBO行列への変換方法\n", "まず、$M_1 = \\max M_\\alpha$として一般性を失わないことに注意します。\n", "[8-Solving Knapsack Problem with PyQUBO](https://openjij.github.io/OpenJijTutorial/build/html/ja/8-KnapsackPyqubo.html)でも解説されているようにQUBO行列を表現するにあたって式(1)で定義したバイナリ変数$x_{i,\\alpha}$に加えてコンピュータが仕事にかかる時間を表現するためのスラック変数yを導入します。" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "\n", "\n", "\n", "\n", "### One-hot encoding により仕事にかかる最大値と他との差を表現した制約項(2)の定義\n", "[Ising formulations of many NP problems](https://arxiv.org/pdf/1302.5843v3.pdf) ではOne-hot encodingを用いて仕事の実行時間を表しています。\n", "バイナリ変数$y_{n,\\alpha}$をノード1とノード$\\alpha$の仕事の長さの差を表すバイナリ変数とします。\n", "\n", "$$y_{n,\\alpha} = \\begin{cases}\n", " 1 & (M_1-M_\\alpha = n,\\alpha\\neq 1,n\\geq 0) \\\\\n", " 0 & (otherwise)\n", " \\end{cases}$$\n", "\n", "よってコンピュータ$\\alpha$の実行時間がコンピュータ1の実行時間より短い点に関して以下の式が成り立たなければなりません。\n", "\n", "$$\\sum_{n=0}^{\\mathcal{M}}ny_{n,\\alpha} = \\sum_{i=1}^N L_i(x_{i,1}-x_{i,\\alpha})\\tag{7}$$\n", "\n", "$$H_{A1} = A\\sum_{\\alpha=2}^m\\left(\\sum_{n=0}^{\\mathcal{M}}ny_{n,\\alpha} - \\sum_{i=1}^N L_i(x_{i,1}-x_{i,\\alpha})\\right)^2\\tag{8}$$\n", "\n", "このようにハミルトニアンを定めることでエネルギーが最小となった際にこの制約を満たすようなスピン状態を得ることができます。\n", "\n", "そして$\\alpha$を固定したときにただ一つだけの$y_{n,\\alpha}$だけが1となり、他は0となる必要もあります。\n", "\n", "$$H_{A0} = A\\left(1-\\sum_{n=0}^{\\mathcal{M}}y_{n,\\alpha}\\right)^2\\tag{9}$$\n", "\n", "更に、ある仕事iはいずれか一つのコンピュータで行われるという制約も加える必要があります。\n", "\n", "$$H_{A2} = A\\left(1-\\sum_{i=1}^{N}x_{i,\\alpha}\\right)^2\\tag{10}$$\n", "\n", "\n", "これらを踏まえるとハミルトニアンの制約項全体は正の定数$A$を用いて次のように定義されます。\n", "\n", "$$H_A = A(H_{A0}+H_{A1})+AH_{A2}\\tag{11}$$\n", "\n", "$\\mathcal{M}$はユーザーによって選ばれる値であり、コンピュータ$\\alpha$\n", "とコンピュータ1の差がどの程度存在するか表しています。最悪の場合$\\mathcal{M}$は$N\\max L_i$となります。\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Log encoding によるスラック変数を用いた制約項(2)の定義\n", "[8-Solving Knapsack Problem with PyQUBO](https://openjij.github.io/OpenJijTutorial/build/html/ja/8-KnapsackPyqubo.html)のようにLog encodingを用いて制約項を設定してみましょう。\n", "$\\mathcal{M}$はコンピュータ1とコンピュータ$\\alpha$の仕事の実行時間の差の上限であるため以下の不等式が成り立ちます。\n", "$$\\mathcal{M}\\geq \\sum_{i=1}^N L_i(x_{i,1}-x_{i,\\alpha}) = M_1-M_\\alpha\\tag{13}$$\n", "\n", "ここでコンピュータで行われる仕事が一つ以上割り振られ、仕事量が1以上であるとします。するとスラック変数Yを$0\\leq Y \\leq \\mathcal{M}-1$を満たすとして定義することができます。\n", "\n", "上記不等式(13)は等式制約に変換できると分かります。\n", "$$\\mathcal{M} = Y + M_1-M_\\alpha\\tag{14}$$\n", "スラック変数Yを具体的に記述すると以下のようになります。\n", "$$Y = \\sum_{n=1}^{\\lfloor\\log_2(\\mathcal{M}-1)\\rfloor} 2^n y_n\\tag{15}$$\n", "\n", "式(12)の第一項、第二項は以下の項に置き換えることができます。\n", "$$\\sum_{\\alpha=2}^m \\left(\\mathcal{M}-\\sum_{i=1}^N L_i(x_{i,1}-x_{i,\\alpha}) - \\sum_{n=1}^{\\lfloor\\log_2(\\mathcal{M}-1)\\rfloor} 2^n y_n\\right)^2\\tag{16}$$\n", "\n", "この方法を用いると、One-hot encodingに比べて少ないバイナリ変数$(\\lfloor\\log_2(\\mathcal{M}-1)\\rfloor+1)$個で整数を表現できる上に追加の制約項が不要になります。変数Yの最大値は$2^{\\lfloor\\log_2(\\mathcal{M}-1)\\rfloor}$となっているからです。また、スラック変数を用いているため、仕事量の差が$\\mathcal{M}$を上回ることもありません。" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### 目的項(1)の定義\n", "目的項はコンピュータで仕事を終えるまでの最大実行時間を最小化するためのものです。\n", "よってハミルトニアンは以下のように定義するとエネルギーが最小になったときに最大実行時間を最小化した解が得られます。\n", "$$H_B = B\\sum_{i=1}^N L_ix_{i,1}\\tag{17}$$\n", "ただし定数A,Bは目的項$H_B$によって制約項$H_A$を違反してはいけないため、$0