問題タブ [branch-and-bound]

最適化の問題を解決するのに役立つ最適な手法やリソースを見つけようとしています。問題は、会議の出席者を事前定義された役割と最適に一致させることです。会議の前に、参加者は役割ごとに次のことを決定します。

• 可能であれば積極的にその役割を果たそうとする (「A」)
• 喜んでその役割を果たすが、それについて強く感じていない ("W")
• 役割を果たしたくない（「U」）。

たとえば、可能な入力行列は次のようになります。

目的は、次の制約の下で、「A」とマークされた役割を持つ出席者の一致数を最大にすることです。

• すべての役割は、正確に 1 人の出席者によって満たされます
• 「U」マークのついた参加者が禁止されている試合

この例では、最適なソリューションは次のようになります。ここでは、4/5 の役割が "A" 一致を使用して満たされます。

この種の問題をブルート フォースよりも優れた方法で解決できるかどうかを知っている人はいますか? 自分で実装する最適化アルゴリズム (タブー検索、遺伝的アルゴリズム、分枝限定など) の一般的な提案や、OptaPlannerなどの既存のパッケージ内の機能へのポインターに対してもオープンです。

ありがとう！

分岐限定法を使用して最長共通部分列 ( LCS ) 問題を解決する方法はありますか。分岐限定は理解していますが、LCS を解くための手法を適用できません。フォーラムの意見を正しい方向に向けて解決策を見つけてもらいたかっただけです。

私はSCIPの初心者です。ブランチと価格のフレームワークとして SCIP を使用したいと考えています。私はすでに C++ で問題をコーディングしており、プライサーまたは列生成を関数として実装しています。実際、Cplex.dll をプロジェクトにリンクすることでルート ノードの BP アルゴリズムを実装しました。次に、分岐ツリーをコーディングする必要があり、この目的のために SCIP を使用することにしました。SCIP と私が持っている古いコードを使用して問題を解決できる最速の方法を知りたいですか? それとも、GCG を使用する方がより適切で高速な方法でしょうか? GCG のドキュメントを読みましたが、プライサーを自分で再度実装する必要があるかどうかわかりません。実際、私はこれら 2 つ (SCIP と GCG) の違いを理解していません。ありがとう。

私のコードは最初の数回の反復では機能しますが、while ループを数回繰り返した後、配列要素が削除されているように見えます。

入力パラメーターから構築された配列から数値を取得していますが、2 回渡された数値に到達するとエラーが発生するということしかわかりません。

私はこのようにスクリプトを呼び出しています

これを出力として取得する必要があります

これは私のスクリプトです

これが出力されるものです

C++ での代入問題に対して Branch and Bound Algorithm を開始しましたが、適切な解決策が見つかりません。まずは課題問題例： 課題課題

各人に 1 つの仕事を割り当てることができます。アイデアは、すべての仕事が最も迅速に完了するように、各仕事を 1 人に割り当てることです。

これまでの私のコードは次のとおりです。

私は軌道から外れているかもしれないことを知っています。最初は下限を使用しませんでした。実際、このアルゴリズムが正確にどのように機能するか少し混乱しています。そのため、アルゴリズムの段階的なウォークスルーでも役立ちます。