4

cを最小化するベクトルxを見つけます。x制約mの対象。x> = b、x整数。

サンプル入力セットは次のとおりです。

c : {1,2,3}
m : {{1,0,0},
     {0,1,0},
     {1,0,1}}
b : {1,1,1}

出力あり：

x = {1,1,0}

この種の問題を解決するための優れたツールとその使用方法の例は何ですか？

4

7 に答える 7

5

GLPK

私はGLPK の glpsolを使用して回答を提供していますが、これを行うためのより良い方法があることを願っています (線形計画問題のこの種の単純な特殊なケースでは、GLPK が過度に強力/一般的であるようです):

以下に示す .mps ファイルを生成するには、行列を行単位で連立方程式に分割する必要があるため、問題の説明は次のようになります。

minimize

cost = 1 x_1 + 2 x_2 + 3 x_3

s.t. constraints:

S1 = 1 x_1 + 0 x_2 + 0 x_3
S2 = 0 x_1 + 1 x_2 + 0 x_3
S3 = 1 x_1 + 0 x_2 + 1 x_3

S1 >= 1
S2 >= 1
S3 >= 1

0 <= x1 <= 1
0 <= x2 <= 1
0 <= x3 <= 1

GLPK ドキュメントには .mps 形式に関する詳細情報がありますが、行、列、右辺、および境界を指定します。ROWS セクションでは、'N' と 'G' は制約のタイプ (それぞれ数値とより大きい) を指定します。BOUNDS セクションの 'UI' は、境界が上限の整数型であることを指定し、解を強制的に整数にします。

問題の仕様に対してソルバーを実行するには、次のようにします。

> glpsol --freemps example.mps -o example.out

example.mps ファイル:

NAME          VM
ROWS
 N cost
 G S1
 G S2
 G S3
COLUMNS
 x_1    cost    1.0
 x_1    S1      1.0
 x_1    S3      1.0
 x_2    cost    2.0
 x_2    S2      1.0
 x_3    cost    3.0
 x_3    S3      1.0
RHS 
 RHS1 cost   0.0
 RHS1 S1     1.0
 RHS1 S2     1.0
 RHS1 S3     1.0
BOUNDS
 UI BND1 x_1 1.0
 UI BND1 x_2 1.0
 UI BND1 x_3 1.0
ENDATA

出力:

Problem:    VM
Rows:       4
Columns:    3 (3 integer, 3 binary)
Non-zeros:  7
Status:     INTEGER OPTIMAL
Objective:  cost = 3 (MINimum)

   No.   Row name        Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
     1 cost                        3
     2 S1                          1             1
     3 S2                          1             1
     4 S3                          1             1

   No. Column name       Activity     Lower bound   Upper bound
------ ------------    ------------- ------------- -------------
     1 x_1          *              1             0             1
     2 x_2          *              1             0             1
     3 x_3          *              0             0             1

Integer feasibility conditions:

INT.PE: max.abs.err. = 0.00e+00 on row 0
        max.rel.err. = 0.00e+00 on row 0
        High quality

INT.PB: max.abs.err. = 0.00e+00 on row 0
        max.rel.err. = 0.00e+00 on row 0
        High quality

End of output

また、このセクションの上記の出力にエンコードされていますが、問題を解決する x ベクトルを直接取得する方法については明確ではありません。

  No. Column name       Activity     
------ ------------    ------------- 
     1 x_1          *              1 
     2 x_2          *              1 
     3 x_3          *              0
于 2009-12-28T18:14:46.043 に答える
2

純粋な整数計画問題を指定しました。ほとんどの実用的なアプリケーションには通常、一部の変数のみが整数である混合整数プログラミングと呼ばれるものが含まれます。この件に関するかなり簡潔なチュートリアルとエッセイは、次の場所にあります。

http://mat.gsia.cmu.edu/orclass/integer/integer.html

IP 問題の典型的な解決方法は、動的プログラミングまたは分岐限定です。これらの用語で検索すると、フリーウェア、シェアウェア、またはアカデミック コードを見つけるのに役立ちます。

幸運を

于 2009-12-29T19:38:45.270 に答える
1

Mathematica

Mathematicaにはこれが組み込まれています（注：Mathematicaはフリーソフトウェアではありません）。

LinearProgramming[c, m, b, Automatic, Integers]

出力：

{1, 1, 0}
于 2009-12-28T18:01:04.043 に答える
1

このような単純な問題は、制約プログラミングと呼ばれる手法を使用して解決することもできます。対応するウィキペディアのエントリから、これらの問題を解決するために利用できる技術と無料および商用のソルバーの詳細を見つけることができます。整数変数を含む問題があなたが言及したものよりも複雑な場合は、汎用線形計画法/整数計画法ソルバー (GLPK など) を検討することをお勧めします。いくつかの名前があります: LPSOLVE (無料)、IBM ILOG CPLEX (商用)。

于 2009-12-30T21:58:39.773 に答える
1

パイソン:パルプ

于 2009-12-28T18:07:33.360 に答える
1

Python & Pyomo を使用しています。プロジェクトの Web サイトには、利点の概要がよくまとめられています: http://www.pyomo.org

于 2015-02-14T16:08:23.437 に答える
0

scicomp.stackexchange.com にも同様の質問があり、いくつかのライブラリをリストした回答があります。

于 2012-01-11T02:22:39.297 に答える