問題タブ [linear-programming]

数理最適化（線形計画法、凸最適化、またはより一般的なタイプの問題）を実行するそのようなライブラリを知っている人はいますか？私はMATLABのようなものを探していますが、より大きな問題を処理する機能を備えています。独自の実装を作成する必要がありますか、それともそれらの商用製品（CPLEXなど）の1つを購入する必要がありますか？

私は、方程式と不等式のセットに要約されるプログラミングの問題に取り組んでいます。

入力と リスト およびとから構成される のX絶対最小値を与える の値を解きたいと思います。CDABa[0 - n]b[0 - n ]

現時点では Python で問題を解決していますが、一般的な問題は言語に依存しません。

明確化の更新: 係数x[0 - n]は負でない整数のセットに制限されます。

興味深い問題を解決するために、大規模な線形計画法モデルをセットアップしたいと考えています。私はJavaで最も快適です。どのようなツール/ライブラリが利用可能ですか?

私は、速度を大幅に向上させる必要があるmatlabアプリケーションに取り組んでいます。私は linprog を使用して、0 と 1 で囲まれた約 10,000 の変数を持つ 2 制約線形計画法を解いています。Linprog は私のアプリケーションでは非常に遅いです。速度を改善するために再定式化できる方法はありますか? または、便利な matlab 互換のシェアウェア (私は予算が限られています) を知っていますか?

私は、1つのひねりを加えた標準的な線形計画問題のように見える問題を解決しようとしています。

入力として、それぞれに重みがある「フレーズ」のセットがあります。総重量を最大化するために、テキスト内の各フレーズを繰り返す回数を選択する必要がありますが、最大文字長の制限があります。

これは、あるフレーズが別のフレーズのサブフレーズである可能性があるという事実を除けば、単純な線形計画問題のように見えます。したがって、たとえば、入力フレーズに「foo bar」と「foo」が含まれている場合、「foo bar」というフレーズを繰り返すと、「foo」というフレーズも繰り返されます。線形計画モデルでこれを処理する方法がわかりません。

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

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

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

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

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

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

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

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

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

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

Perl には次の制約セットがあります (実際に必要なものではなく、制約のサンプル セットにすぎません)。

($a, $b, $c)そして、制約を満たすリストを見つける必要があります。私の素朴な解決策は

現在、このソリューションは終了することが保証されておらず、一般的にかなり非効率的です。Perlでこれを行うより良い方法はありますか?

編集: ランダム テスト ジェネレーターにはこれが必要なので、ソリューションでは などのランダム関数を使用する必要がありますrand()。完全に決定論的なソリューションでは不十分ですが、そのソリューションで可能な組み合わせのリストが得られる場合は、インデックスをランダムに選択できます。

編集 2: ここでの制約は、力ずくで簡単に解決できます。ただし、可能な値の範囲が広い変数が多数ある場合、ブルート フォースは選択肢になりません。

サイズnの集合Sが与えられ、これはサイズn1、..、nkのクラス（s1、..、sk）に分割されます。当然、n = n1 + ...+nkであることが成り立ちます。

このパーティショニングの要素を組み合わせて、各組み合わせに各クラスの要素が1つだけ含まれるようにする方法の数を知りたいと思います。

s1からn1要素、s2からn2要素などを選択できるので、n1 + .. + nkを保持する任意のn1、.. nkのmax（n1 * .. * nk）の解を探しています。 =n。

これは線形最適化の問題だと感じていますが、学部生として学んだので長すぎます。誰かがこれを計算する方法を覚えていることを願っています。