問題タブ [integer-programming]

私はRにかなり慣れていないので、Excelでソルバーを使っていたスクリプトを書こうとしています。以下のデータには、職種が AE のワーカーのリストがあります。各労働者には給与と生産率があります。R に実行させたいのは、累積給与が 100,000 未満の 10 人の労働者から得られる最大生産量を見つけることです。制約は、正確に合計 10 人のワーカーが必要であり、ジョブ タイプ AD から 2 つ、E から 1 つ、任意のタイプの 1 つが必要であるということです。

私は optim や IpSolve などでこれを行う方法を検索し、検索しましたが、私の限られた知識ではあまり運がありませんでした。

ご協力ありがとうございました！

私の仕事では、次の問題に遭遇しました: $d_{i,j} \in \Re$ がオブジェクト $i$ と $j$ 間の類似性を表す類似性行列 D が与えられた場合、$k を選択したいと思います。 $ オブジェクト、$k \in {1, \dots, n}$ について、選択されたオブジェクト間の類似性を最小限に抑えるような方法で。この問題を正式に定式化する最初の試みは、次の整数プログラムを使用することでした。

$\minimize$ $d_{1,2}X_1X_2 + d_{1,3}X_1X_3 + \dots + d_{1,n}X_1X_n + d_{2,1}X_2X_1 + \dots + d_{n,n-1 }X_nX_{n-1} $

$X_1 + X_2 + \dots + X_n = k$ および $X_y \in {0,1}$ で、$y=1,\dots,n$ の場合

上記のプログラムでは、$X_y$ はオブジェクト $y$ が選択されたかどうかを示します。明らかに、上記のプログラムは線形ではありません。オブジェクト $X_1$ と $X_2$ の両方が選択されているかどうかを示す変数 $X_{1,2} $ を使用して、目的関数を線形にしようとしました。ただし、正確に $k$ 個のオブジェクトを選択する必要があるという制約、つまり前の制約 $X_1 + X_2 + \dots + X_n = k$ を定式化するのに苦労しています。

私は数理計画法の専門家ではないので、これについて教えていただけないでしょうか。

前もって感謝します！ではごきげんよう、

アーサー

最適化の問題を解決するために、matlab に cplex を使用しようとしていました。しかし、cplex は 2 次目的関数と 2 次制約のある PURE 整数計画問題しか解けないように思えました。確かに細かいグリッドを使用して連続パラメーターを離散化できますが、これは私の最初のオプションではありません。

私の質問は次のとおりです。

1. これは本当ですか？それとも私は混乱していますか？
2. 私の印象が正しければ、それができる信頼できるソルバーを知っている人はいますか?

大きな数 (少なくとも 336 ビット) の整数計画問題を解くことができる無料のソルバーはありますか? 私が調べたすべてのソルバーは、倍精度のみを想定しているように見えますが、任意の精度を主張するソルバーを見つけることができませんでした。

私はナップザックの問題を解決しようとしていますが、これは整数プログラミングの問題でもあります。動的計画法、貪欲アルゴリズム、分枝限定アルゴリズム、遺伝的アルゴリズムなど、いくつかの近似解を見てきました。これらのアルゴリズムの一部またはすべてを実装するのに役立つライブラリを (任意の言語で) 教えてもらえますか?

前もって感謝します。

I have a list of products and a list of features. Each product has its own cost and delivers its own subset of the features.

I would like an algorithm such that I tell it which of the features I require and it will tell me the set of products I need to buy to get all of those features at the lowest total combined cost.

Does anyone have a recipe for doing something like that? I'd like to have it in JavaScript.