スケジュールナースのブログ: UnaryCounter

2023年11月26日日曜日

「半人前」を実現するために導入した制約関数であり、通常の制約関数とは異なります。

この関数は、2種類のリストの一部としか機能しません。2種類のリストとは、

■sc3.SeqError(min,max,allowable_errors,list)

■sc3.SoftLinearComp(eq_mode, CoffA, CoffB, offset, allowable_errors,listA,listB);

です。この2種類しかサポートしません。

パラメータは、二つしかなく、

■sc3.UnaryCounter(bitstart,bit_interval)

です。

UnaryCounterとは、1進加算器のことであり、ビットの桁数は、入力の個数だけあります。

つまり桁上がりがないカウンタになります。

ビットスタート０、ビットインターバル１だと、そのままの出力になります。

ビットインターバル２だと、一つ飛びに出力されます。/2されるイメージです。

ビットスタートは、mod演算に対応します。下図は、bit interval=2のときの様子ですが、

同じbit interval=2でも、bitstartによって、エンコードの様子が異なります。

余りがないときは、どちらも同じですが、一人のときを1人と数えるか0人と数えるかの違いがあります。どちらのエンコードを指定するかは、bit_startを指定すれば決まります。

この論理構造は、次で実現できます。

これは、アルゴリズム３/4でのグラフ構造になります。アルゴリズム１は、同じ１進加算を使いますが、また別の構造により実現します。

アルゴリズム2と３/4の数理表現では、次のような記述になっています。

上のような回路構造の記述と異なり、数理的な表現になります。

ip.add_constraint(num_working <= (bit_interval) * x+bit_start, x);

ip.add_constraint(num_working >= (bit_interval) * x-(bit_interval-1-bit_start), x);

つまり、同じUnaryCouter機能を実現するのに、アルゴリズム毎に記述を変える必要があります。どれも、同じ機能には違いないのですが、テクノロジーが違うと全く違う表現になる様子を紹介しました。

組み合わせ最適化は、一つのテクノロジだけでは、網羅できません。広範囲のテクノロジーを組み合わせて、スケジュールナース最適化は成っているのです。

スケジュールナースのブログ