2022年8月29日月曜日

KISSATの衝撃

 SAT Competition2020の結果をよくみると、KISSATが突出した性能を備えていることが分かります。で、2022以降、全てKISSATベースのソルバが上位を独占することになります。これは、CHB以来の衝撃ではないでしょうか。数理ソルバの実装をしている間に、SATの進歩がありました。

理由の一つとして、ローカルサーチかな位に考えていたのですが、主因は、メモリ消費量だろうと考えを改めました。というのも、KISSATのメモリ消費は、1/3から1/4になっており、キャッシュヒット率の向上というのが貢献していることが理由です。MINISAT以来、伝統のClause構造体を一新しており、その複雑怪奇な構造変更が、2年経っても、未だincremental ソルバが出てこない理由ではないかと推察しています。

A)SATパラレルの問題点は、コアを増やしても性能が向上しないばかりか劣化することです。この点でmerge_satや、DPSは、決定的なソルバであり、コア数が決定されれば、性能は安定していますが、予備実験によれば性能向上は期待したほどではありませんでした。

B)最適化を行うには、incremental機能は不可欠です。Kissatのソースを期待を込めて読んでみたのですが、ソース上は対応していませんでした。(option でincremental指定はありますが、ソースを見ると対応していませんでした。)

ここ2-3年のSAT性能の向上を取り入れることによりAlgorithm1をReplaceすることを計画したいと思います。目標は、

■ マルチコア時の安定した性能向上

です。既にAlgorithm1は、他と比べて圧倒的な性能を有していますが、マルチコア時に難がありました。 数理ソルバの実装には、数年を要したのですが、この分野は自分の専門領域でもあり、一月程度で結果は出せると思います。




2022年8月22日月曜日

最新のSATサーベイ

こちらのIntel NadalさんのlectureNoteが分かりやすいです。 

SAT/SMT/AR/CP Summer School 2022 (sat-smt-ar-school.gitlab.io)

Kissatのパフォーマンス向上が最近ではトピックになっています。背景として、CDCLにローカルサーチを組み込んだことが大きいのではないかと思っています。論文は、

Deep Cooperation of CDCL and Local Search for SAT

こちらもparallel satの覇者Shaowei Cai教授によるものです。この方は、私が競技会に参加していた頃から、ローカルサーチ手法を用いて参加していました。当時、評価したものの、利点はあまりなかったように感じましたが、ここに来て長年の研究が実を結んできたように思います。

しかし、Kissatもそうですが、incremental solvingに対応していないので、使用しづらい面があります。そこで、最近の成果を盛り込みかつincremental なSATということで、NadalさんIntelSAT等を使用することも考えられます。

しかしながら、最近の成果は、optimization problemには、効果がない、というNadalさんの指摘もあります。

が、来年以降、並列SATの分野で、性能向上が見込めます。そこで、ここ2-3年の成果を取り込んでマルチプロセシング向けの基幹系を実装しておくことは意味があると思います。


2022年8月21日日曜日

フェーズパターンの拡張

 次の例では、4直3交代です。

一つの制約が2列になっていて下段がシフト上段が従来のフェーズパターンです。シフトとフェーズの関係は、ANDでマッチします。シフトは無くても構いません。

下の例では、1勤務の残業回数を計測する制約ですが、フェーズパターンのみで記述する方法と、シフトとフェーズパターンの両方を用いる記述の二通りを記しています。どちらを使っても差異はありません。


次の制約では、2勤務の早残同シフト残業を禁止する制約です。早残を両方やると8+4+45=16h働くことになりますが、流石にこれはありえないので禁止してやる必要があります。
従来パターンでは、早と残でそれぞれ禁止が必要となりますが、シフトを用いたパターンでは、ひとつのパターンで記述が可能になります。たとえば、
下は、勤務2シフト AND phase 1 =Not NoTaskVar(=Working) AND phase4=NoTaskVar(=Working)のときにマッチします。



次の例は、早残回数の規制と、早残連続3回の禁止制約のための記述です。

最終的にはフェーズ集合を作って


いつものように、制約します。
従来は、Python記述をするより方法がなかったのですが、フェーズ機能の拡張により対応が可能になりました。

これで、一応フェーズ関係の拡張設計は終了しました。かなり大規模な拡張を行っていますが、現状の仕様については、影響がないようにしていますので、お客さまのプロジェクトに影響することはありません。


2022年8月20日土曜日

フェーズ変数の拡張

 次のようなフェーズ状態であるとします。

このとき、フェーズ変数は、フェーズに+-1が存在するので、+-分拡張されます。(-があると、+-分、+があると+分のみ拡張されます)

フェーズ変数1は、+1Dayに跨っており、フェーズ変数2は、-1Dayに跨っています。
注意点は、フェーズ変数1を最終日には置けません。また、フェーズ変数1は、最初の日には置けません。フェーズ変数の定義は、各要素のANDです。フェーズ1を最終日に予定として置いたとすると、+1Day日は、定義不能ですからANDは成立しません。ハード予定として記述することは、成立することを要求しているので、矛盾となり、解はありません。

上で早番や、夜勤は、上記フェーズ変数と同じように+-1Dayを定義していますが、こちらは最終日や初日に予定として置いても問題なく動作します。


2022年8月19日金曜日

フェーズ定義の拡張機能追加

 フェーズ関係の実装を見直し、拡張機能を搭載しました。

<名称変更>

コアフェーズと別名フェーズに名称を変更しました。フレックスタイムでコアタイムという呼び名がありますが、それを模した名称にしました。

以下は、NoTaskVarを用いることを前提としています。

<コアフェーズ>

1日内でフェーズ(タイムスライス)を定義します。コアフェーズは、1日内で完結している必要があり、一日を1分でも超えて定義することは出来ません。

茶色にチェックされたフェーズは、必ずNoTaskVar以外のタスクが割り当てられます。

<別名フェーズ>

コアフェーズでの定義を参照するフェーズになります。+-1日内でのコアフェーズの定義参照が可能です。コアをチェックしないときは、NoTaskVarが許容されます。コアをチェックすると、NoTaskVarは、許容されません。

このようにする目的は、必ず働く時間帯(コアフェーズ)と必ず働くと決まっている訳ではないが、働く可能性がある(残業する)時間帯を分けることにより、GUI・Pythonでの記述負荷を減らすことが出来ます。今までPythonで記述するしかなかったところが、GUIで記述できるメリットがあります。


次の例は、4直3交代の例です。

こちらでも説明されています。

普段は、コアタイム分2コマ分だけ働きます。ただし、他のタスクの負荷状況や、有給休暇等により、不足分が生じる場合があります。下図は、その様子を表したものです。作業長タスクは、スタッフ1が早残、スタッフ2が遅残をすることにより、一人分の作業長不足を補っている様子です。

フェーズ参照は、前日または、次の日に跨ることがあるので、+-1日に限り参照できるようにしています。これが別名フェーズの機能です。

2022年8月16日火曜日

Last Pattern 曜日タイプ追加

 行制約 最大・最小パターン では、パターン最後の曜日タイプは、サポートしていませんでしたが、次のリリースからサポートします。

パターンの最後の曜日基準でカウントする場合に役にたつかもしれません。




2022年8月15日月曜日

Post_main only プロジェクト

 本来の機能である、制約して充足解を出力する機能は全く使っていません。

Excel表シートの整形のみを目的としたプロジェクト例です。

作り方は、何も定義せずに下の青部をチェックして求解します。



今回のプロジェクト例は、列制約を予定制約基数制約に置き換える例です。工場現場において各プロセスに必要な人員は、生産予定数量・スキル・休日等で月々変動します。列制約とDay集合で各々定義してもよいのですが、各曜日で必要人員を予定基数制約で置き換えた方がすっきりする場合もあります。こうすると、月々予定基数制約をインポートすれば、列制約自体を書き換える必要がなくなります。

予定基数制約に書き換えるためのプロジェクト例を紹介します。(Pythonのソースのみに意味があります。)

下は、列制約の解を示しています。これを、Pythonで予定基数制約形式に書き換えてみます。


下が、Pythonで書き換え後のImport用ファイルです。


Exportした列制約の最大・最小部を書き換えます。

予定基数制約を参照するように書き換えました。

インポートします。
インポート後の予定基数制約です。



これをインポートして求解して次の解を得ました。




Pythonソース

def post_main():
    
    import pdb
    #pdb.set_trace()
    print('\n\n*********ポスト処理を実行中です。*************\n')
    import win32com.client#pywin32をインポート
    import os

#すでにExcelが起動されている場合はそのタスクが使われる
#エラー終了するとタスクは残ります
    try :
        xl = win32com.client.Dispatch("Excel.Application")
    except:
        print("can not invoke excel")
        exit()
    #動いている様子を見てみる
    xl.Visible = True
    os.chdir(project_file_path)
    file=os.path.join(project_file_path,"出力SC解.xlsx")

    wb = xl.Workbooks.Open(file)
    # Excelシートオブジェクト
    ws = wb.Worksheets("SC解")

    # 指定したシートを選択
    # Select()の使用前にシートのActivate()が必要
    ws.Activate()
    lastRow = ws.UsedRange.Rows.Count
    lastCol = ws.UsedRange.Columns.Count
    c=ws.Range("A1:A200").Find("列制約項目")
 
    nrows=lastRow-(c.Row+1)+1
    ncols=0
    for col in range(3,lastCol+1):#曜日がDrawされている範囲がActual範囲
        if ws.Cells(c.Row,col).Text=="":
            break
        ncols+=1

    nphases=0
    text=""
    for col in range(3,lastCol+1):#phase数取得 同じ曜日が続く数を数える囲
        if ws.Cells(c.Row,col).Text=="":
            break
        if col==3:
            text=ws.Cells(c.Row,col).Text
            nphases+=1
        elif text==ws.Cells(c.Row,col).Text:
            nphases+=1
        else:
            break
    days=ncols/nphases
    days_rem=ncols%nphases
    if days_rem !=0:
        print("days がnphasesで割り切れません",ncols,nphases)
        exit()
    print("rowmax=",lastRow,"列制約開始=",c.Row+1,"nrows=",nrows,"ncols=",ncols,"nphases=",nphases,"days=",days)
    list2 = [['' for i in range(ncols)] for j in range(nrows)]#Constructor
    list=['' for j in range(nrows)]
    Row=0
    for row in range(c.Row+1,lastRow):
        if ws.Cells(row,1)=="":
            continue
        for col in range(3,3+ncols):
            Col=col-3
            #print(Row,Col)
            list2[Row][Col]=ws.Cells(row,col).Text
            list[Row]=ws.Cells(row,1).Text
        Row+=1
    nRows=Row
    print("nRows=",nRows)
            #print(ws.Cells(row,col).Text,end=" ")
        #print("")
    wb.Close(False)# Trueで保存。False=Defaultでブックを保存せずにクローズ
    for row in range(nRows):
        for col in range(ncols):
            if col%nphases !=0:
                r=col%nphases
                if row>=r:
                    list2[row-r][col]=list2[row][col]
    for row in range(nRows):
        print(list[row],end=" ")
        for col in range(ncols):
            print(list2[row][col],end=" ")
        print("")

    #Open Target Excel
    file=os.path.join(project_file_path,"RevisedD.xlsx")
    wb = xl.Workbooks.Open(file)
    # Excelシートオブジェクト
    ws = wb.Worksheets("タスク 予定入力基数制約")
    ws.Activate()
    c=ws.Range("A1:A200").Find("タスク名")
    row_start=c.Row+1
    print("row_start=",row_start)
    Row=0
    for row in range(nRows):
        #print(list[row],end=" ")
        has_data=False
        for col in range(ncols):
            if list2[row][col] !="":
                has_data=True
                break
        if has_data:
            #print(list[row])
            ws.Cells(Row+row_start,1).Value=list[row]
            for col in range(ncols):
                ws.Cells(Row+row_start,col+3).Value=list2[row][col]
                ws.Cells(Row+row_start+1,col+3).Value=list2[row][col]
            Row+=2
    wb.Close(True)# Trueで保存。False=Defaultでブックを保存せずにクローズ
    # Excel終了
    xl.Quit()
    print('\n\n*********ポスト処理を実行終了しました。*************\n')


2022年8月11日木曜日

Parallel-Solverの進展

SAT Competition 2022でSolvers Descriptionが公開され、各Solverの概要が明らかになりました。

一位の Shaowei Cai教授が率いるグループの結果は衝撃的です。VBSというバーチャルなソルバーが解いた問題数と、実際のソルバが解いた問題数が殆ど同じ、という結果になっています。今まで、殆ど見たことのない結果です。SAT手法のありえる限界点に到達しつつあると言え、いわば自己新記録が常に世界記録となるような突出した性能を備えている、ということが言えます。

Literal Assumption and Random Shuffle

パラレルへのアプローチの仕方としては、多数の異なる求解パラメータを持つソルバ群をスレッド駆動するポートフォーリオと、問題そのものを子問題に分割するパーティションベースがあります。Shaowei Cai教授が取ったアプローチは、パーティションベースです。闇雲に分割すればよいのではなく、ある発見があったようです。crucial variablesというKeyとなるPivotが見つかったとき、あるいは見つからなくても有効なSAT手法が発見できた、ということのようです。

数理ソルバにおいてもBranchingNodeの選び方は、重要で特にRoot付近となるNodeの選出については、StrongBranchingという手法があります。数理的アプローチもSAT的アプローチも最適化を目指しているのは同じですから、未だ、今後の進展が期待できそうな分野だと思います。



2022年8月10日水曜日

SAT Competition 2022結果

こちらでOverviewできます。 

https://satcompetition.github.io/2022/slides/satcomp22slides.pdf

鍋島先生の研究グループがパラレルトラックSATで第2位の快挙です。素晴らしい。

DPS: a Framework for Deterministic Parallel SAT Solvers

で見ることが出来ます。今年は、SeqTrackは、ほぼ横ばいですが、ParallelとCloudについては、顕著な性能改善が見られます。その中での2位は、本当に価値があります。

SAT2022関係のPaperは、期間限定だと思いますが、こちらで見ることが出来ます。


IntelのNadalさんがIntelSATを公開しています。近年の研究成果を公開Solverとして提供していることに敬意を表します。