問題タブ [mathematical-optimization]

私は巨大な最適化モデル (10 万を超える変数) を解決するために CPLEX を使用しています。現在、オープン ソースの代替手段を見つけられるかどうかを確認したいと考えています。混合整数問題 (MILP) を解決し、CPLEX はうまく機能しますが、スケーリングしたいので、代替手段を見つけるか、独自のアドホック最適化ライブラリの作成を開始する必要があります (これは苦痛です)

任意の提案/洞察をいただければ幸いです

最適化ライブラリを探しています。私の2つの要件は、JNIを使​​用しないことと、複数のコンピューターで商用利用することを妨げるライセンス制限がないことです。これらの要件を満たすのはChocoだけですが、使用できないほどバグがあります。

Java プログラムで非線形最小化 (N 個の未知数の最小残差二乗) 問題を解決する必要があります。これらを解決する通常の方法は、Levenberg-Marquardtアルゴリズムです。いくつか質問があります

• 利用可能なさまざまな LM 実装の経験がある人はいますか? LM には少し異なる種類があり、アルゴリズムの正確な実装がその数値安定性に大きな影響を与えると聞いています。私の関数はかなりうまく機能しているので、これはおそらく問題にはなりませんが、もちろん、より良い代替手段の 1 つを選択したいと思います。ここに私が見つけたいくつかの選択肢があります：

  • FPL 統計グループの非線形最適化 Java パッケージ。これには、従来の Fortran MINPACK ルーチンの Java 翻訳が含まれています。

  • JLAPACK、別の Fortran 翻訳。

  • 最適化アルゴリズム ツールキット.

  • Javanumerics .

  • 一部の Python 実装。純粋な Python は、jythonc を使用して Java にコンパイルできるため、問題ありません。

• LM が必要とする最初の推測を行うために一般的に使用されるヒューリスティックはありますか?

• 私のアプリケーションでは、ソリューションにいくつかの制約を設定する必要がありますが、幸いなことにそれらは単純です: ソリューションが (物理的なソリューションであるために) 非負であることを要求するだけです。わずかにマイナスの解は、データの測定の不正確さの結果であり、明らかにゼロである必要があります。「通常の」LMを使用することを考えていましたが、未知数の一部が負になる場合はゼロに設定し、それから残りを解決するように繰り返します。本物の数学者はおそらく私を笑うでしょうが、これでうまくいくと思いますか?

ご意見ありがとうございます。

更新: これはロケット科学ではありません。解決するパラメーターの数 (N) は最大で 5 であり、データセットは解決を可能にするのに十分な大きさではないため、Java はこれを解決するのに十分効率的であると思います。そして、この問題は賢い応用数学者によって何度も解決されていると信じているので、自分で料理するのではなく、すぐに使える解決策を探しているだけです. たとえば、Scipy.optimize.minpack.leastsq は、純粋な Python であれば問題ないでしょう。

問題: 2 つの重なり合う 2D 形状 A と B があり、それぞれの形状のピクセル数は同じですが、形状が異なります。形状の一部が重なり合っており、重なり合っていない部分がいくつかあります。私の目標は、形状 A のすべての重複しないピクセルを形状 B の重複しないピクセルに移動することです。各形状のピクセル数は同じなので、1 対 1 のマッピングを見つけることができるはずです。ピクセル。制限は、移動したすべてのピクセルが移動した合計距離を最小にするマッピングを見つけたいということです。

ブルート フォース:この問題を解決するためのブルート フォース アプローチは明らかに問題外です。なぜなら、n 個あると思われるすべての可能なマッピングの合計距離を計算する必要があるからです。(ここで、n は 1 つのシェイプ内の重複しないピクセルの数です) を、マッピング内のポイントの各ペアの距離を計算する計算 n 倍すると、合計 O( n * n! ) または同様の値が得られます。

バックトラッキング:私が考えることができる唯一の「より良い」解決策は、バックトラッキングを使用することでした。これにより、これまでの現在の最小値を追跡し、特定のマッピングを評価している任意の時点で、その最小値に達するか超えた場合、私は次のマッピングに進みます。これでも O( n! ) よりもうまくいきません。

合理的な複雑さでこの問題を解決する方法はありますか?

また、ポイントを最も近くにある隣接ポイントに単純にマッピングするという「明白な」アプローチでは、常に最適なソリューションが得られるとは限らないことにも注意してください。

より単純なアプローチ?:二次的な質問として、実行可能な解決策が存在しない場合、重複しない各セクションを小さな領域に分割し、これらの領域をマッピングして、マッピングの数を大幅に削減することが 1 つの可能性として考えられます。2 つの領域間の距離を計算するには、重心 (領域内のピクセル位置の平均) を使用します。ただし、これは、最適に近い答えを得るためにパーティショニングをどのように行うべきかという問題を提示します。

どんなアイデアでも大歓迎です!!

病院の看護師にシフトを最適に割り当てるアプリケーションを開発しています。これは離散変数を使用した線形計画法の問題であり、したがっておそらく NP 困難であると思います。

• 毎日、各看護師 (約 15 ～ 20 歳) にシフトが割り当てられます。
• 少数 (約 6) の異なるシフトがあります。
• 1 日に関して、または従業員に関して、かなりの数の制約と最適化基準があります。
  • 毎日、各シフトに割り当てられる最小人数が必要です
  • 一部のシフトは重複しているため、中間シフトを行っている人がいる場合は、早いシフトの人が 1 人少なくても問題ありません。
  • 早いシフトを好む人もいれば、遅いシフトを好む人もいますが、より高いシフト勤務賃金を得るには、最小限のシフト変更が必要です。
  • ある日は遅番、翌日は早番で働くことは認められていません（最低休憩時間の規定による）。
  • 割り当てられた週の勤務時間のミーティング (人によって異なります)
  • ...

したがって、基本的に、それぞれが少数の離散値を取ることができる多数の (aout 20*30 = 600) 変数があります。

現在、私の計画は、修正されたMin-conflicts アルゴリズムを使用することです

• ランダムな割り当てから始める
• 一人一人、毎日のためのフィットネス機能を持っています
• 最悪のフィットネス値を持つ人または日を選択します
• その日/人の割り当ての 1 つをランダムに選択し、最適なフィットネス値をもたらす値に設定します
• 繰り返しの最大回数に達するか、選択した日/人に改善が見られなくなるまで繰り返します

より良いアイデアはありますか？局所最適に陥ってしまうのではないかと少し心配です。何らかの形式のシミュレーテッド アニーリングを使用する必要がありますか? それとも、一度に 1 つの変数を変更するだけでなく、具体的には 2 人の間でシフトを切り替えること (現在の手動アルゴリズムの主要コンポーネント) を検討しますか? 変更される可能性があるため、現在の制約に合わせてアルゴリズムを調整することは避けたいと思います。

編集:厳密に最適なソリューションを見つける必要はありません。名簿は現在手動で作成されており、ほとんどの場合、結果はかなり最適化されていないと確信しています-それを打ち負かすのは難しいことではありません. 短期的な調整と手動によるオーバーライドも間違いなく必要ですが、これが問題になるとは思いません。過去の割り当てと手動割り当てを「修正済み」としてマークすると、実際には、ソリューション スペースが減り、タスクが単純化されます。

みんな。私は大学のタイムテーブル スケジューラ プロジェクトに取り組んでいます。主にタブー検索をしていますが、お聞きしたいのですが、

一般的な検索では、現在の状態のすべての近傍を探索し、フィットネスまたは評価関数に従って最適な状態を取ることができますが、そのようなプロジェクトでは、すべての近傍を生成するとパフォーマンスが低下します。私はそのような問題をバイパスしますか？たとえば、1 つの州に対してのみ子を生成し、検索プロセス中に他のすべての州に対してこの生成の恩恵を受けることはできますか?

私はそのような問題に一生懸命取り組んできたので、そのようなアルゴリズムの専門家がいる場合は教えてください。

問題があります：

私はクラス A とクラス B を持っています。これらのインスタンス オブジェクトは、さまざまな量で互いに似ているか異なっているかをプログラムで調べることができます。たとえば、それらは完全に一致する場合もあれば、まったく異なる場合もあります (クラスが異なっていても、同じ情報を表し、同じスコアを付けることができます)。

ここで、A の 1 つと B の 1 つの 2 つのコレクションがある場合、A と B をペアにして、どちらかのコレクションが他のコレクションよりも大きいか、 As または B の一部が単純に一致するにはあまりにも異なる場合は?

私の最初の試みは、2 次元配列を作成することでした。各セルは一致の「スコア」 (0 = パーフェクト、数値が大きいほど悪い) であり、すべてのパスを再帰的に繰り返し、累積スコアが最も低いものを探します。これは機能し、結果は完璧ですが、非常に遅いです。

より効率的なアルゴリズムに関するアイデアはありますか?

ご参考までに、私の A クラスはオーディオ ミキサーの入力チャネルを表し、B は同じ (シーンと呼ばれる) 持続状態を表します。私が解決しようとしている問題は、既存のミキサーにシーンをインポートする方法です。この場合、シーン (B) は、既存のチャンネル (A) とわずかに、または大きく異なる場合があります。どちらかを少し変更して一致させることができれば、チャネル (A) を追加したくありません。たとえば、A にエフェクト インサートを追加して、B と完全に一致させ、別の A を追加する必要がないようにすることができます。

マイク

3 次元ポイントの 2 つのセット、ソース セットと宛先セットが与えられます。各セットのポイント数は任意です (ゼロの場合もあります)。タスクは、すべての距離の合計が最小になるように、すべての宛先ポイントに 1 つまたはまったくソース ポイントを割り当てないことです。宛先ポイントよりも多くのソース ポイントがある場合、追加のポイントは無視されます。

この問題には力ずくで解決する方法がありますが、ポイントの数が多くなる可能性があるため、実行できません。この問題は集合サイズが等しい 2D では簡単だと聞きましたが、残念ながらこれらの前提条件はここでは示されていません。

近似と正確な解の両方に興味があります。

編集：ははは、はい、宿題のように聞こえると思います。実際、そうではありません。多数の車の位置を受け取るプログラムを書いており、それらをそれぞれの駐車セルにマップしようとしています。:)

異常な方法で保存された 1 週間の範囲の日付の配列があります。

日付は次の数値形式で保存されます: 12150

左から右へ：

1 桁目は日を表します: 1 = 日曜日、2 = 月曜日、3 = 火曜日、....、7 = 土曜日

次の 2 桁は 24 時間制の時間を表します: 00 = 真夜中、23 = 午後 11 時

次の 2 桁は分を表します: 00-59

入力日と開始日と終了日が与えられた場合、入力日が開始日と終了日の間にあるかどうかを知る必要があります。

現在、100% の確率で機能すると思われるアルゴリズムがありますが、よくわかりません。

いずれにせよ、これを行うためのより適切で簡単な方法がおそらくあると思います。そのアルゴリズムが何であるかを誰かが知っているかどうか疑問に思っていました。

そうでない場合は、誰かが私の作業を再確認して、有効なケースの 100% で実際に機能することを確認できれば素晴らしいと思います.

私が今持っているものは次のとおりです。

最大約 100 x 100 の行列で行列演算を行うためのパッケージを探しています。

少なくとも、逆数、乗算、転置を行う必要があります。より高いパフォーマンスよりも、よりカプセル化されたインターフェイスを好みます。