ＳＤＰ ( SemiDefinite Programming )
既に退官されている某名誉教授から、
ある問題に対して定式化したのだけど、
ワシャもう歳やから、そっちで計算して共同研究として発表できないかという依頼。
なんでも定式化を行ったところ0-1整数計画問題となったそうで、
変数が多くなるため、分枝限定法などの方法では
解くのに時間がかかりそうだから、
別の問題で緩和して解くことになるんじゃないか？
その先生曰く、ＳＤＰ緩和がよさそうだと。
しかもそのソフトも存在するとか。
ただし、UNIXベースだそうですが。
ＳＤＰ緩和というのが何かわからないので、
とりあえずネットで検索。
ついでにそのUNIXベースのソフトも検索。
東工大の小島先生という方が、pdfファイルにより
いろいろな文書を公開されていて、
ついでに、そのソフトとやらもそこにあるよう。
で、いろいろな文書を見ながら、ＳＤＰ緩和の適用可能性を考えてみるが、
どうも0-1整数計画問題では、ＳＤＰ緩和はＬＰ緩和と同じになってしまうらしく、
より緩和をきつくすると、ＳＤＰ緩和のメリットが生じるが、
制約式が多くなってしまい、実際には解きにくくなるらしい。
というわけで、ＳＤＰ緩和の適用性に疑問が生じました。
かといって、ＬＰ緩和しても、もとの問題の実行可能解が
得られるとは限らないので、どうしたもんか。
と、いうようなことを、朝から夜までやっているうちに、
時間が過ぎてしまったので、
元々今日やろうとしていたことが何もできずじまい。
無駄に過ごしたわけではないけど、効率が悪いなあ。
