問題タブ [integer-programming]

つまり、現在、IQPをILPに変更しようとしています。古い実装では約2日かかりましたが、現在は線形ツールを使用しています。速度が上がるはずです。基本的に問題は最大化することです（約50のバイナリ変数で）：

$$ \ sum_ {g = 1} ^ {5} sum_ {p = 1} ^ {10}（S [p] x[g][p]-倦怠感[g][p]-眠気[g][p ]）$$

アップデート

デビッドは正しい方向に進んでいると思いますが、ボーナス変数を使用して式を最大化しようとすると、毎回ゼロになります。なぜですか。いくつかのコードの下では、スコアはのようになりS[1..10]=[1,2,3,4,5,6,7,8,9,10];ます。

私はc ++でコードを書いており、それを解決するためにCPLEXを呼び出しています。非常に優れたソリューションはすぐに見つかりますが、それを改善しようとすると非常に長い時間がかかります。したがって、コードを終了するためにギャップをより大きな値に設定したいので、これを使用します。

しかし、コンパイラEpGapは、宣言されていない識別子であるというエラーを表示します。相対ギャップのデフォルト名は?

CPLEX Java API で MIP 開始を効率的に使用する方法が見つかりません。

制約を 1 つだけ変更するか目的を変更することで何度も解決する必要がある線形問題があるため、(MIP 開始を使用して) 解から開始することが計算を高速化する良い方法であると考えました。

そのため、最初に問題を解決した後、すべての変数を IloNumVar の配列に保存し、cplex.addMIPStart を使用して他の cplex オブジェクトに渡します。

問題は、何も高速化されず、速度が低下し、次のメッセージが表示されることです。

警告: 1 つの MIP 開始から解決策が見つかりません。

したがって、MIP にすべての変数を開始させるべきではないかもしれませんが、どの変数を与えるべきかをどのように知ることができますか?

また、MIP の開始努力を変更しようとしましたが、違いはないようです...

なぜ計算が速くならないのですか? わずかな違いしかない多くの問題を解決するためのより良い方法はありますか?

Optimization Toolboxのbintprogコマンドは、不等式制約とオプションの等式制約を使用して 0-1 プログラミング問題を解きます: Ax <= b ここで、A は行列で、ba 列ベクトルです。

|Ax| の形式の問題があります。<= b、または同等の -b <= Ax <= b。この種の問題を Matlab で解決する方法はありますか?

$A$ の場所から $B$ の場所まで歩きたいとしますが、その間にいくつかの川があります。$A$ の場所から $B$ の場所まで歩くには、川ごとに橋を架ける必要があります。

数種類の板をご用意しております。厚板の種類が異なればコストと長さも異なりますが、同じ種類の厚板は同じコストと長さです。厚板を使って橋を架けることができます。ただし、利用できる板の数は限られています。私たちの目的は、厚板の総コストを最小限に抑えながら、各川に橋を架けることです。

問題をよりよく説明するために、問題を説明する図を描きます。

必要な橋の長さがそれぞれ $d_1$、$d_2$、$d_3$ の 3 つの川があります。

$4$ 種類の厚板があります。$l_i$ と $c_i$ は、$i$ 番目のタイプの厚板の長さとコストを示します。$\delta_i$ が利用可能な $i$ 番目の種類の厚板の数を表すとします。$n_{ij}$ が橋 $j$ を構築するために使用される厚板の数を表すとします。

次に、問題は次のように定式化できます。

$\sum_{j=1}^3 \sum_{i=1}^4 n_{ij}c_i$ を最小化

st

$\sum_{i=1}^4 n_{ij}l_i \geq d_j$

$\sum_{j=1}^3 n_{ij} \leq \delta_i$

$n_{ij}\geq 0$ & $n_{ij} \in Z$

この問題は整数計画問題であるため、NP-Hard である必要があると思います。これは本当ですか？この問題を解決する方法を知っている人はいますか？最適ではないソリューションでさえ。