0-1 整数計画法によるオフィスの割り当て: 問題ベース

この例では、最適化問題アプローチを使用して、0-1 整数計画によって割り当ての問題を解く方法を説明します。ソルバーベースのアプローチについては、0-1 整数計画法によるオフィスの割り当て: ソルバーベースを参照してください。

オフィス割り当て問題

Marcelo、Rakesh、Peter、Tom、Marjorie および Mary Ann の 6 人を 7 つのオフィスに割り当てたいと思います。各オフィスに配置できるのは 1 人だけで、各人は正確に 1 つのオフィスにのみ割り当てられます。そのため、空きオフィスが 1 つになります。これらの人はオフィスを選ぶことができ、彼らの選好を考慮する際は年功が基準とされます。MathWorks での勤続年数が長いほど年功が高くなります。窓のあるオフィスと窓のないオフィスがあり、また、1 つの窓は他より小さくなっています。さらに、Peter と Tom はよく一緒に働いているため、隣接するオフィスに配置する必要があります。Marcelo と Rakesh もよく一緒に働いているため、隣接するオフィスに配置する必要があります。

オフィスのレイアウト

オフィス 1、2、3、および 4 は建物の内側にあり、窓がありません。オフィス 5、6 および 7 には窓がありますが、オフィス 5 の窓は他の 2 つのオフィスよりも小さいです。ここで、これらのオフィスの配置方法を示します。

officelist = {'Office 1','Office 2','Office 3','Office 4','Office 5','Office 6','Office 7'};
printofficeassign(officelist)

問題の定式化

この問題を数学的に定式化する必要があります。人がオフィスを占有しているかどうかを示す 2 値変数を作成します。人の名前のリストは、次のとおりです。

namelist = {'Mary Ann','Marjorie','Tom','Peter','Marcelo','Rakesh'};

オフィス番号と名前でインデックス付けされた 2 値変数を作成します。

occupy = optimvar('occupy',namelist,officelist,...
    'Type','integer','LowerBound',0,'Upperbound',1);

年功

MathWorks での勤続年数が長いほど選好が重視されるように、年功に基づいて選好に重みを付けたいと思います。年功は以下のようになっています。Mary Ann は 9 年、Marjorie は 10 年、Tom は 5 年、Peter は 3 年、Marcelo は 1.5 年、Rakesh は 2 年です。年功に基づいて、正規化された重みベクトルを作成します。

seniority = [9 10 5 3 1.5 2];
weightvector = seniority/sum(seniority);

人々のオフィスの好み

行がオフィスに対応し、列が人に対応するような選好行列を設定します。各社員の希望は数値で示されています。各人が各オフィスについて値を入れ、その選択の合計、つまり列の値の合計が 100 になるように依頼します。ここでは第一希望のオフィスの数値が最も大きくなります。各人の選好が列ベクトルにリストされます。

MaryAnn = [0, 0, 0, 0, 10, 40, 50];
Marjorie = [0, 0, 0, 0, 20, 40, 40];
Tom = [0, 0, 0, 0, 30, 40, 30];
Peter = [1, 3, 3, 3, 10, 40, 40];
Marcelo = [3, 4, 1, 2, 10, 40, 40];
Rakesh = [10, 10, 10, 10, 20, 20, 20];

各人の選好ベクトルの i 番目の要素は、その人物が i 番目のオフィスをどの程度評価しているかを示しています。つまり、選好行列を組み合わせたものは次のようになります。

prefmatrix = [MaryAnn;Marjorie;Tom;Peter;Marcelo;Rakesh];

年功が列の基準となるように、weightvector を使用して選好行列に重みを付けます。

PM = diag(weightvector) * prefmatrix;

目的関数

目的は、年功によって重みが付けられた選好の満足度を最大限にすることです。これは線形目的関数 sum(sum(occupy.*PM)) です。

最適化問題を作成し、目的関数を含めます。

peopleprob = optimproblem('ObjectiveSense','maximize','Objective',sum(sum(occupy.*PM)));

制約

最初の制約セットでは、各人が正確に 1 つのオフィスを得ることが求められます。つまり、各人について、該当する人に対応する occupy 値の合計が正確に 1 であることが求められます。

peopleprob.Constraints.constr1 = sum(occupy,2) == 1;

第 2 の制約セットは不等式です。これらの制約により、各オフィスで 1 人を超えないように指定されます。

peopleprob.Constraints.constr2 = sum(occupy,1) <= 1;

Tom と Peter には、互いに隣接したオフィスを割り当てたいと思います。Marcelo と Rakesh についても同様です。

Tom と Peter のオフィス番号が互いに 1 しか離れないように制約を設定します。

peopleprob.Constraints.constrpt1 = occupy('Tom','Office 1') + sum(occupy('Peter',:)) - occupy('Peter','Office 2') <= 1;
peopleprob.Constraints.constrpt2 = occupy('Tom','Office 2') + sum(occupy('Peter',:)) - occupy('Peter','Office 1') ...
    - occupy('Peter','Office 3') - occupy('Peter','Office 5') <= 1;
peopleprob.Constraints.constrpt3 = occupy('Tom','Office 3') + sum(occupy('Peter',:)) - occupy('Peter','Office 2') ...
    - occupy('Peter','Office 4') - occupy('Peter','Office 6') <= 1;
peopleprob.Constraints.constrpt4 = occupy('Tom','Office 4') + sum(occupy('Peter',:)) - occupy('Peter','Office 3') ...
    - occupy('Peter','Office 7') <= 1;
peopleprob.Constraints.constrpt5 = occupy('Tom','Office 5') + sum(occupy('Peter',:)) - occupy('Peter','Office 2') ...
    - occupy('Peter','Office 6') <= 1;
peopleprob.Constraints.constrpt6 = occupy('Tom','Office 6') + sum(occupy('Peter',:)) - occupy('Peter','Office 3') ...
    - occupy('Peter','Office 5') - occupy('Peter','Office 7') <= 1;
peopleprob.Constraints.constrpt7 = occupy('Tom','Office 7') + sum(occupy('Peter',:)) - occupy('Peter','Office 4') ...
    - occupy('Peter','Office 6') <= 1;

ここで、Marcelo と Rakesh のオフィス番号が互いに 1 しか離れないようにする制約を作成します。

peopleprob.Constraints.constmr1 = occupy('Marcelo','Office 1') + sum(occupy('Rakesh',:)) - occupy('Rakesh','Office 2') <= 1;
peopleprob.Constraints.constmr2 = occupy('Marcelo','Office 2') + sum(occupy('Rakesh',:)) - occupy('Rakesh','Office 1') ...
    - occupy('Rakesh','Office 3') - occupy('Rakesh','Office 5') <= 1;
peopleprob.Constraints.constmr3 = occupy('Marcelo','Office 3') + sum(occupy('Rakesh',:)) - occupy('Rakesh','Office 2') ...
    - occupy('Rakesh','Office 4') - occupy('Rakesh','Office 6') <= 1;
peopleprob.Constraints.constmr4 = occupy('Marcelo','Office 4') + sum(occupy('Rakesh',:)) - occupy('Rakesh','Office 3') ...
    - occupy('Rakesh','Office 7') <= 1;
peopleprob.Constraints.constmr5 = occupy('Marcelo','Office 5') + sum(occupy('Rakesh',:)) - occupy('Rakesh','Office 2') ...
    - occupy('Rakesh','Office 6') <= 1;
peopleprob.Constraints.constmr6 = occupy('Marcelo','Office 6') + sum(occupy('Rakesh',:)) - occupy('Rakesh','Office 3') ...
    - occupy('Rakesh','Office 5') - occupy('Rakesh','Office 7') <= 1;
peopleprob.Constraints.constmr7 = occupy('Marcelo','Office 7') + sum(occupy('Rakesh',:)) - occupy('Rakesh','Office 4') ...
    - occupy('Rakesh','Office 6') <= 1;

割り当て問題を解く

solve を呼び出してこの問題を解きます。

[soln,fval,exitflag,output] = solve(peopleprob);

LP:                Optimal objective value is -33.836066.                                           


Optimal solution found.

Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value,
options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance,
options.IntegerTolerance = 1e-05 (the default value).

解の表示 -- 誰がどのオフィスを獲得したか

numOffices = length(officelist);
office = cell(numOffices,1);
for i=1:numOffices
    office{i} = find(soln.occupy(:,i)); % people index in office
end

whoinoffice = officelist; % allocate
for i=1:numOffices
    if isempty(office{i})
        whoinoffice{i} = ' empty  ';
    else
        whoinoffice{i} = namelist(office{i});
    end
end

printofficeassign(whoinoffice);
title('Solution of the Office Assignment Problem');

解の質

この問題の場合、年功による選好の満足度が fval の値まで最大化されます。exitflag の値は、solve が最適解に収束したことを示します。出力構造体は、探索されたノードの数や分枝計算における下限と上限のギャップなど、解法プロセスに関する情報を提供します。この場合、分枝限定ノードは生成されませんでした。つまり、分枝限定ステップを経ずに問題が解かれました。ギャップの絶対値は 0 です。これは、解が最適であり、目的関数で内部計算された下限と上限の間に差がないことを意味します。

fval,exitflag,output

fval = 33.8361

exitflag = 1

output = struct with fields:
        relativegap: 0
        absolutegap: 0
      numfeaspoints: 1
           numnodes: 0
    constrviolation: 0
            message: 'Optimal solution found.↵↵Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the default value).'
             solver: 'intlinprog'