6. 変数の上下限と制約条件#

6.1. 導入#

制約条件とよく似た概念に「変数の上下限 1bound constraint や variable bound のこと.upper bound, lower bound などのように upper/lower が付く場合が多く,その場合は上限(上界),下限(下界)などの訳語が定まるが,bound constraint および variable bound 単体での定訳はない.単に,bound という場合も,境界と訳すことは数理最適化ではあまりなく,バウンドと呼称されやすい.また,bound と constraint の二つの対比をここでは議論しているため,bound constraint というのはややわかりにくい.本項目の話題に限って言えば,variable bound がわかりやすい.なお,constraint 自体に条件という意味合いがあるため,bound constraint で一つの用語として成立している.このため,二重表現となる bound constraint conditions とは普通は言わない.」があり, 複雑な定式化を図る中で,これらの違いが問われることがある. ここで変数の上下限とは変数の定義域で,制約条件以前にその変数が動ける範囲のことである.

6.2. 構文構造の違い#

例えば \(x\geq 0\) という非負条件があった場合に, ただこれだけの情報であれば,制約条件なのか,変数の上下限なのかが判別がつかない.

モデリング言語は数式ベースの構文を採用することを概念的な基礎としているため, どのようにして変数の上下限を制約条件と区別して記述すればよいかは,非自明である.

実際,モデリング言語 SIMPLE の場合,C++SIMPLE と PySIMPLE とで, これら記述方法は異なる.

6.2.1. C++SIMPLE の場合#

「変数と定数の比較」が変数の上下限として解釈される.それ以外はすべて制約条件として扱われる. ここでいう「変数と定数の比較」とは,(変数クラス)(比較演算子)(定数) のパターンで記述される不等式もしくは等式のことである.

例えば x, y を変数,A を定数とするとき,以下の場合はパターン 1 から 3 のみが変数の上下限で,他は制約条件を C++SIMPLE では表す. ただし,場合によってはパターン 4 も変数の上下限となりえる.

1x >= 0;           // pattern 1
2x >= A;           // pattern 2
3x[i] >= A[i];     // pattern 3
4sum(x[i],i) >= A; // pattern 4
5x >= y;           // pattern 5
6x + y >= A;       // pattern 6
72*x >= A;         // pattern 7

ここで特にパターン 7 の左辺は一見変数だけのように見えるが,2* という演算が行われており, 2*x は変数クラスではなく式クラスとしての扱いとなるため,変数の上下限とは解釈されない. 同様に 1*x も式クラスである.

現在の上下限値の確認は,下限であれば x.lb.val.print() によって, 上限であれば x.ub.val.print() で確認できる.

パターン 4 が変数の上下限となる場合は, 制約式が展開された結果,一つの変数のみだった場合である. これは「変数の上下限」として扱われる.

次にサンプルコードを示す.

1Set I = "0";
2Element i(set=I);
3Variable x(index=i);
4x[i] >= 0;
5x[i] <= 1;
6sum(x[i], i) >= 2; // 制約式 (A)
7solve();

この場合、制約式 (A) は変数 x[0] のみのため,「変数の上下限」として扱われる.

6.2.2. PySIMPLE の場合#

変数を宣言する際に,その変数の下限 lb と上限 ub を設定できる. 唯一,ここでの設定が変数の上下限の設定となっており, 以後,問題クラスに追加する不等式や等式はすべて制約条件として解釈される.

注釈

唯一とあるが,より厳密には V26 (PySIMPLE 1.5.0) で追加された fix メソッドでも bound 扱いになる.

https://www.msi.co.jp/solution/nuopt/docs/pysimple/guide/fix.html

6.3. 変数の上下限と制約条件の違いが重要となる状況#

実行不可能 (infeasible) な求解結果であった場合に, ある変数は制約条件に違反することになるが, 変数の上下限に違反することはない.

よってこの場合には SIMPLE では次のエラーが報告されやすい.

(NUOPT 2) infeasible(linear constraints and variable bounds).

例えば PySIMPLE の場合,次のサンプルコードに prob += x[i] == -1 を追加した場合である.

 1from pysimple import Problem, Element, Variable, Sum, Parameter
 2
 3i = Element(value=range(1, 6))
 4a = Parameter(index=i, value={1: 2, 2: 3, 3: 6, 4: 2, 5: 4})
 5b = Parameter(value=0)  # `value=0` は省略可能
 6x = Variable(index=i, lb=0)
 7prob = Problem(type=min)  # `type=min` は省略可能
 8prob += Sum(a[i]*x[i], i) >= b
 9prob += Sum(x[i], i)
10prob.solve()

このため求解後にある一部の解を固定した前提で新たに求解したいと考え, 変数に対して PySIMPLE で等式制約条件を新たに設定した場合に, その設定が infeasible であったらならば, 追加した条件はあくまでも制約条件のため, 出力された解は値固定が保証されないこととなる.

つまり値固定が変数の上下限としてなされたのならば,その値を前提に求解が行われ, infeasible であることは値固定がなされていない変数が負うことになる. しかし値固定が制約条件の意味であったならば,その固定した変数も infeasible であることの整合関係として含められることとなる.

関連

リソース

引用書式

BibTeX