要素数を最大化する組合せ最適化問題について

質問

要素数を最大化するような組合せ最適化問題(線形計画問題)を解こうとしていますが、
要素数を一度に計算したり、ソートしたりすることはできません。
(そのような関数を線形式で定義するのは難しいと思いますので。)
一方、２つの要素が同一かどうかのみの計算は簡単にできるので、
全ての２要素間で一致／不一致を判断し、不一致の数が最大となるように目的関数を設定して、この問題を解こうかと思っています。
この方法は正しいでしょうか。

例えば、
ある変数の組合せにおいて、
Ａ１＝Ｘ， Ａ２＝Ｙ， Ａ３＝Ｘ
といった結果になるとすると、
ｂｉｎ１＝｜Ａ１－Ａ２｜（＝１、不一致）
ｂｉｎ２＝｜Ａ１－Ａ３｜（＝０、一致）
ｂｉｎ３＝｜Ａ２－Ａ３｜（＝１、不一致）
という風に要素の一致／不一致を計算し、
不一致数（＝ｂｉｎ１＋ｂｉｎ２＋ｂｉｎ３）を最大化するという風に目的関数を定義しようかと思っています。

当然、不一致数と要素数は一致しないわけですが、
不一致数が最大のときに、必ず要素数が最大となるのであれば、
目的関数として問題ないと考えています。

なんとなく正しい気もしますが、本当に正しいのかよくわかりません。

よろしくお願いします。

回答No.2

k_kota

一応補足を受けたので追加しますが、
まず、目的はなんなのか、問題は何なのかがはっきりしてないのでなんとも言えません。

どうしても線形計画問題として解きたいならその形式で問題を記述する必要があります。
少なくともあなたの書いている式は日本語の内容との兼ね合いが理解できません。
あなたが理解しているならそれで良いしやってみれば良いと思いますが、他人に理解させたいなら明確な形での記述をお願いします。

ちなみに、手段を問わないならバブルソートもどきでやれますね。
第一要素に一つめの値を入れる。次の要素を比較して大きければ後ろに、小さければ全体をずらして入れる、同じ値なら何もせず終了。

これをクイックソートもどきでやればオーダーは nlognでしょう。
まあ、規模が小さいならオーダーは気にしないでいいです。

とりあえず、問題を共有できる状態にして下さい。

回答No.1

k_kota

とりあえず、問題をわかりやすく説明したほうがいいと思います。
制限だけ書かれてもちょっと困ります。

＞要素数を一度に計算したり、ソートしたりすることはできません。
＞(そのような関数を線形式で定義するのは難しいと思いますので。)

私はそのように思いません。そうなるような条件があるのかも分かりませんし。

あと、数式を書いていますが、多分間違っていますよ。
線形計画問題と言うものを取り違えて解釈しているのではないでしょうか。

とりあえず、多数の整数要素があって、それらの値がかぶらない最大の要素数と言うことであれば、アホなやり方でもn^2のオーダーで出せるでしょう。
内容的にはLPじゃなくてソートの問題に見えます。

なので、一旦内容を整理して欲しいです。
私が無知で理解できていないのであれば反省致します。

補足

説明不足ですみません。

今回の問題は線形計画問題でないかもしれませんが、
線形計画問題に落とし込めないかということを考えています。

背景として、
CPLEXを使って評価したいが、
CPLEXではif文などの条件式などが恐らく使えないからです。

ご指摘の通り、問題自体は、
ソートのアルゴリズムと関連がありそうな気はするのですが、if文を使わずに記述する方法がわかりませんでした。
この辺りも勉強不足かもしれません。

私が検討している方法もオーダーはn^2になりますので、
アホな方法だということはわかっているのですが、
検討している目的関数の設定が正しければ、
式の記述は簡単にできるのでうれしいわけです。