トップ > 製品概要 > NUOPT の更新情報 > NUOPT 7 の更新情報 > SIMPLEによる問題記述の具体例

NUOPT7の更新情報

制約充足アルゴリズム(wcsp)の SIMPLE による問題記述の具体例

  1. 時間割問題
  2. ナーススケジューリング問題
  3. 集合被覆問題
  4. 一般化割り当て問題
  5. 2 次割り当て問題
  1. 時間割問題


    Set Lecture = "1 .. 30"; // 講義
    Set Period = "1 .. 30"; // 10 コマを 3 教室で行う
    Set Professor = "1 .. 13"; // 教授
    Set Student = "1 .. 60";

    Element i(set = Lecture);
    Element j(set = Period);
    Element p(set = Professor);
    Element s(set = Student);

    Element jt(set = "1 4 7 10 13 16 19 22 25 28");

    DiscreteVariable lecture(dom = Period, index = i);

    Set lp(index = p); // 教授の受け持つ講義
    Set ls(index = s); // 生徒の希望講義
    Set np(index = p); // 教授の都合

    Parameter nlc(index = (i,j));

    /// C1 /// 各講義は各コマ、各教室に一つ割当られる
    hardConstraint();
    alldiff(lecture[i]);

    /// C2 /// 各教授は一つの時限には一つしか講義出来ない
    hardConstraint();
    sum(Boolean(lecture[i] == j), (i, j, i < lp[p], jt <= j <= jt+2)) <= 1;

    /// C3 /// 各生徒の受講希望
    softConstraint(1);
    sum(Boolean(lecture[i] == j), (i, j, i < ls[s], jt <= j <= jt+2)) <= 1;

    /// C4 /// 各教授の都合の悪い時間
    softConstraint(1);
    sum(Boolean(lecture[i] == j), (i, j, i < lp[p], j < np[p])) <= 0;

    /// C5 /// 座席数の為、講義が開けない教室がある
    hardConstraint();
    Boolean(lecture[i] == j) == 0, nlc[i,j] != 0;

    solve();

    (注)本問題は以下の論文に挙げられているものです

    S. Miyazaki, K. Iwama and Y. Kambayashi, Database Queries as Combinatorial Optimization Problems, Proceedings of International Symposium on Cooperative Database Systems for Advanced Applications (CODAS'96), 448-454, 1996.

  2. ナーススケジューリング問題


    Set Nurse = "1 .. 25";
    Set Day = "1 .. 30";
    Set Shift = "day evening night meeting off";
    Set TeamA = "1 .. 13";
    Set TeamB = "14 .. 25";
    Set Leader = "1 2 3 4 5 6 14 15 16 17 18";

    Set Dummy = "1 .. 30";
       
    Element i(set = Nurse);
    Element j(set = Day);
    Element k(set = Shift);
    Element it(set = Dummy);

    DiscreteVariable nurse(dom = Shift, index = (i,j));

    ////C5//// (シフト数、休日数の上下限)
    hardConstraint();
    sum(Boolean(nurse[i,j] == k), j) >= lb[i,k];
    sum(Boolean(nurse[i,j] == k), j) <= ub[i,k];

    ////C6//// (各看護婦は、連続7日の間に少なくとも1回の昼シフトを得る)
    hardConstraint();
    sum(Boolean(nurse[i,j] == "day"), (j, it <= j <= it+6)) >= 1, 1 <= it <= 24;

    ////C7//// (夜シフトに入ったら次の夜シフトまで6日空ける)
    hardConstraint();
    Boolean(nurse[i,j] == "night") + Boolean(nurse[i,j+it] == "night") <= 1, j + it < Day, 3 <= it <= 6;

    ////C8//// (各看護婦は、連続7日の間に少なくとも1回の休日を得る)
    hardConstraint();
    sum(Boolean(nurse[i,j] == "off"), (j, it <= j <= it+6)) >= 1, 1 <= it <= 24;

    ////C9//// (3連続夜シフトは避ける)
    hardConstraint();
    sum(Boolean(nurse[i,j] == "night"), (j, it <= j <= it+2)) <= 2, 1 <= it <= 28;

    ////C10//// (4連続夕シフトは避ける)
    hardConstraint();
    sum(Boolean(nurse[i,j] == "evening"), (j, it <= j <= it+3)) <= 3, 1 <= it <= 27;

    ////C11//// (5連続昼シフトは避ける)
    hardConstraint();
    sum(Boolean(nurse[i,j] == "day"), (j, it <= j <= it+4)) <= 4, 1 <= it <= 26;

    ////C13//// (夜シフトは2夜連続で行う)
    softConstraint(100);
    Boolean(nurse[i,1] == "night") + Boolean(nurse[i,2] == "day") + Boolean(nurse[i,2] == "evening")
        + Boolean(nurse[i,2] == "meeting") + Boolean(nurse[i,2] == "off") <= 1, i != 2;

    Boolean(nurse[i,j] == "day") + Boolean(nurse[i,j] == "evening") + Boolean(nurse[i,j] == "meeting") +Boolean(nurse[i,j] == "off") + Boolean(nurse[i,j+1] == "night") + Boolean(nurse[i,j+2] == "day") + Boolean(nurse[i,j+2] == "evening") + Boolean(nurse[i,j+2] == "meeting") + Boolean(nurse[i,j+2] == "off") <= 2, j+2 < Day;

    ////C14//// (休日,勤務,休日のパターンは避ける)
    softConstraint(10);
    Boolean(nurse[i,j] == "off") + Boolean(nurse[i,j+1] == "day") + Boolean(nurse[i,j+1] == "evening") + Boolean(nurse[i,j+1] == "night") + Boolean(nurse[i,j+1] == "meeting") + Boolean(nurse[i,j+2] == "off") <= 2, j+2 < Day;

    ////C15//// (各看護婦個人の要望)
    hardConstraint();
    C15[i,j] * Boolean(nurse[i,j] == "night") == C15[i,j];
     
    ////C16//// (看護婦にはあらかじめ会議日が割り付けられている)
    hardConstraint();
    C16[i,j] * Boolean(nurse[i,j] == "meeting") == 0;
     
    ////C17//// (夜シフトの次に昼シフト,夕シフト,会議は避ける)
    hardConstraint();
    Boolean(nurse[i,j] == "night") + Boolean(nurse[i,j+1] == "day") + Boolean(nurse[i,j+1] == "evening") + Boolean(nurse[i,j+1] == "meeting") <= 1, j+1 < Day;

    ////C18//// (夕シフトの次に昼シフト,会議は避ける)
    hardConstraint();
    Boolean(nurse[i,j] == "evening") + Boolean(nurse[i,j+1] == "day") + Boolean(nurse[i,j+1] == "meeting") <= 1, j+1 < Day;

    solve();

    (注)本モデルは以下の論文で挙げられている問題の一部を抜粋して定式化したもの です。完全な形ではなく、例えば「前月からのつなぎの条件」と許されない勤 務の並び「深夜勤-休み-日勤の条件」は含まれておりません。

    Atsuko Ikegami and Akira Niwa, A Subproblem-centric Model and Approach to the Nurse Scheduling Problem, Mathematical Programming 97, 517-541, 2003.

    モデル全体、ならびにデータは上記論文を参考にしてください。

  3. 集合被覆問題


    Set I;  // City
    Set J;  // City
    Element i(set = I);
    Element j(set = J);

    Parameter a(index = (i, j));
    Parameter d(index = j);

    IntegerVariable z(dom = "0 1", index = j);


    Objective f(type = minimize, target = 1930);
    f = sum(d[j] * z[j], j);

    // 全ての i が少なくとも 1 つの z[j] に cover される
    Constraint coverCons(index=i);
    coverCons[i] = sum(a[i, j] * z[j], j) >= 1;

    solve();

  4. 一般化割り当て問題


    Set Agent;
    Set Job;

    Element i(set = Agent);
    Element j(set = Job);

    DiscreteVariable job(dom = Agent, index = j);

    Parameter resource(index = (i,j));

    Parameter capacity(index = i);
    Parameter cost(index = (i,j));

    Objective totalCost(type = minimize, target = 0.0);
    totalCost = sum(cost[i,j] * Boolean(job[j] == i) , (i,j));

    // 容量制約
    hardConstraint();

    Constraint r(index=i);

    r[i] = sum( resource[i,j] * Boolean(job[j] == i), j ) <= capacity[i];

    solve();

  5. 2 次割り当て問題


    Set S;

    Element i(set=S);
    Element j(set=S);
    Element k(set=S);
    Element l(set=S);

    Parameter a(index=(i,j));
    Parameter b(index=(k,l));
     
    IntegerVariable x(index = (i,k), type=binary);

    // 目的関数は 2 次
    Objective f(type=minimize,target = 0);
    f = sum(a[i,j]*b[k,l]*x[i,k]*x[j,l],(i,j,k,l));

    hardConstraint();
    sum(x[i,k],i) == 1;
    selection(x[i,k],k);

    solve();