梅谷先生のlectureです。
如何にして、問題を解決していくか？について道筋を述べられています。
https://speakerdeck.com/recruitengineers/brainpad-meetup-umetani
2024年12月19日木曜日
2024年12月18日水曜日
Printemps メタヒューリスティクスソルバ
メタヒューリスティクスに基づく汎用線形整数計画ソルバーの開発 - Speaker Deck
ベースになっているのは、法政大学の野々部先生のWCSPです。WCSPは、汎用国産ソルバNuorium Optimizer にも組み込まれています。
野々部先生のWCSPは、第一回のナーススケジューリング国際競技会で、3位に入賞されています。野々部先生とは、以前RAMP講演でお会いしました。
その系統であるPrintempsもシフトスケジューリング問題に期待が持てるかもしれません。オープンソースでMPSファイルも読み取れます。オプションで連続変数を整数として読むことも出来ます。
Optimization Night#9に参加できなさそうなので発表されるPRINTEMPSで一人遊んでみた #最適化 - Qiita
こうしたソルバは、分枝限定法ソルバの初期段階でのUBを得るのに有効な場合があります。以前は、Feasibility Pump しかありませんでしたが、最近では、
GitHub - GioniMexi/FeasPumpCollection: Using multiple reference vectors in the Feasibility Pump.
CAI教授のローカルソルバシリーズ、
GitHub - shaowei-cai-group/NuPBO: A local search solver for PBO
等あります。
2024年12月17日火曜日
n100w8_1_2-4-7-9-3-9-2-8 solved!
It took us five months to solve this problem. The challenge lies in proving that it is optimal.
n100w8_1_2-4-7-9-3-9-2-8: LB=2145 UB=2145
While the upper bound (UB) of 2145 is relatively easy to obtain, demonstrating that there is no better solution is quite difficult. With the standard Branch and Bound method, you could run the algorithm for a million seconds and still not achieve a proof.
The initial gap between the lower bound (LB) and upper bound (UB) is less than 10, which may seem manageable, but it is actually one of the most challenging problems.
Throughout this process, we have learned a lot and gained valuable knowledge. What makes this particular instance unique is the extremely low gap-narrowing gain (a term we coined). We believe this is due to structural symmetry. To address this, we would need to implement symmetry breaking, but we will discuss that another time.
There are now only two remaining unresolved instances for INRC2 8weeks on our side!
n080w814-4-9-9-3-6-0-5
n080w820-4-0-9-1-9-6-2
2024年12月8日日曜日
Optimization Night 9
CDCLによるMILP解法が興味深いです。日本でも、このような方がいらしたのですね。NTT DATA出身の方らしいのですが、この会社は、OR業界の重鎮が在籍され、東大・京大出身の方が多い、印象です。（⇒RAMP講演の懇談会で名刺交換させていただいたことがありました。そのときは、NTT DATAに所属されていました。当時、私もSATの限界を感じ分枝限定法の勉強を始めたばかりでMILPのヒュリスティクスについて質問させていただいたのですが、丁寧に教えて頂いたことがあります。）
INTSATについては、その後、RoundingSATやExact系に引き継がれていると思いますが、Benders Decompositionを用いるというのは、聞いたことがありません。CDCLでBenders Cutを用いるのは新しいと思います。研究の最前線だと思いますので今後も要注目です。
CDCL による厳密解法を採用した MILP ソルバー - Speaker Deck
2024年12月7日土曜日
Q 日勤リーダを２－３日間ずつ、A/Bチーム各１名とするには？
Ans.
休日も含めて、全日リーダを各１名配置した解です。
制約なし（何回でもOK）の人はブランクにします。
行制約です。１日単リーダを禁止、４日連続を禁止とすれば、残りは、２－３日間連続のリーダとなります。また、日勤リーダの間隔が短くなりすぎないようにしています。
列制約で、「今月平日」、「今月休日」を追加変更します。今月休日では、日勤リーダを不可とします。
以上の変更で、平日のみ２－３日間、日勤リーダの実装が完了しました。
以上で、全日リーダ、２－３日間A/Bチーム各１名の実装が完了しました。
日勤者数管理は、リーダを含めて日勤者数とするか、リーダを含めない日勤者数とするかは、列制約による実装となります。ここでは示しませんが考えてみてください。
＜平日日勤リーダのみの場合＞
平日のみ日勤リーダにしたい場合は、以下を変更します。このようにすると、全てのパターンは、平日ついて作用することに注意してください。
先月部を含めるとハード制約では、矛盾が生じる可能性があるので、全てソフト制約とします。
下の解を見ると、休日を跨いで、２－３日間、日勤リーダが実現出来ていることが分かります。
先月休日は、リーダが割り当てられています。これは、先月予定部がフィルインされていないことと、先月休日に対しては、なんの制約もしていないためです。先月予定部がフィルインされていれば、解消するので上の制約で問題ありません。
2024年12月5日木曜日
sloppy24
Solving Linear Optimization Problems for Pseudo-Booleans and Yonder
の略らしいです。ワークショップです。
確かに、SATを一般のMIP問題に適用しようとすると、CNF表現では、無理があると思います。これを疑似ブーリアンと抽象化することで、IP問題と親和性が生まれます。で、そこにCutting Proofを入れるという発想は自然なものとなります。
ただし、一般にLPの速度は、CDCLのバックトラックに比べ、二けた以上遅いので毎回行う訳には行きません。LPソルバを導入した場合、この辺をどうバランスを取っていくかというのが実装上の問題かと思います。
2024年12月4日水曜日
Yinyu Ye教授の講演集
内点法の大御所の講演集です。
web.stanford.edu/~yyye/talks.html
特に、
は、最近のLPの動向について詳しく大変参考になります。
COPTに関して妙に詳しいので、もしかしたら、COPTの創業者達は、教授の門下生？かもしれません。
登録:
投稿 (Atom)