問題タブ [integer-programming]

次のリソース割り当て/スケジューリングの問題に適した決定論的アルゴリズムはどれですか?

P1、P2、P3、および P4 のプレーヤーのセットを考えてみましょう。各プレーヤーは、携帯電話基地局からデータを受信します (ワイヤレス ネットワークなど)。タワーは 1 秒のブロックでデータを送信します。5ブロックあります。各プレーヤーは、任意の数のブロックでデータを受信するようにスケジュールできます。

ここで、各ブロックで受信されるデータの量は、定数 (C) を同じブロックでスケジュールされている他のプレイヤーの数で割ったものになります (帯域幅を共有する必要があるため)。貪欲なアプローチでは、各プレーヤーを各ブロックに割り当てますが、ブロックごとに受信されるデータは減少します。

ネットワークによって配信されるデータの量が最大になるように、プレーヤーの時間ブロックへの割り当てをどのように見つけることができますか? 私はこの問題に対していくつかのヒューリスティックな方法 (遺伝的アルゴリズム、Sim Anneal) を試しましたが、うまくいきました。ただし、最適なスケジュールを解決したいと考えています。

多くの (変化する) 制約または目的のコンポーネントを含む問題を解決する場合、書式設定された方程式の形式でドキュメントを作成するのは非常に困難です。

LP/MPS ファイルからフォーマットされた数式 (LaTeX、PDF など) を自動的に作成する簡単な方法はありますか?

これは私にとって大きな助けになるでしょう。

前もって感謝します！

私はアルゴリズムについて勉強していて、最近興味深い課題を見つけました。

行/列が得られます。私たちの使命は、一度だけ表示され、行と列の合計が指定された行/列に等しい整数 1~N でテーブルを埋めることです。

チャレンジの簡単な例:

ありがとう

Gurobi では、問題を実際に最適化せずに、一連の制約と変数が実行可能かどうかを確認できますか? 目的が一定の場合、Gurobi は最適な解を見つけるために大量の計算を実行しますが、これは必要ありません!

私の問題の要約：
私はこのようなペトリネットから線形方程式系を持っています（ILP）：

これらの問題には、さらに多くの変数と制約が含まれる可能性があります。方程式は決して不等式ではありません。また、最大化または最小化することもできます。

すべての整数の問題についていくつかの例を確認しましたが、それらは制約よりも多くの変数を持つシステムを処理できませんでした。

lp_solveのようなソフトウェアではこれらの問題を処理できますが、このソリューションでは、多くの .dll ファイルとラッパーを処理する必要があります。

Java または簡単な埋め込みライブラリで解決策を探しています。ちょっと行き詰まっているので、助けていただければ幸いです。

分岐と価格(または列生成) アルゴリズムを実装しています。最適化中に生成する変数 (または列) には、オフセット付きのコストがあります。たとえば、新しい変数を導入したい場合は、スケーリングxiするコスト係数と一定のコストの両方があります。cixici'

総コスト = すべての i の合計 (ci * xi + ci')

私の変数xiは連続しています。

これをどのように処理すればよいですか？

変数に関連するコストが相殺されないように問題を再定式化する必要がありますか? たとえば、列の生成が最適なソリューションにつながることを保証するためです。

私の最初のアイデアは、ペアで変数を生成することです: 元のxi変数と関連するバイナリ変数ですbi。bi = 0次に、 ifxi = 0およびbi = 1ifという追加の制約を追加しますxi > 0。これは合理的なアプローチですか？バイナリ変数の導入以外の欠点は何ですか?