0

%Matlab インターフェースで gurobi オプティマイザを使用して MILP を解く例を以下に示します。

function[] = mip1() 

names = {'x'; 'y'; 'z'}; 

try 
    clear model;  
    model.A = sparse([1 2 3; 1 1 0]);  
    model.obj = [1 1 2];  
    model.rhs = [4; 1];  
    model.sense = '<>';  
    model.vtype = 'B';  
    model.modelsense = 'min';  

    clear params;  
    params.outputflag = 0;  
    params.resultfile = 'mip1.lp';  

    result = gurobi(model, params);  

    disp(result)  

    for v=1:length(names)  
        fprintf('%s %d\n', names{v}, result.x(v));  
    end  

    fprintf('Obj: %e\n', result.objval);  

catch gurobiError  
    fprintf('Error reported\n');  
end  

end

======================================

このコードを実行すると、次のような出力が得られます。

      status: 'OPTIMAL'
 versioninfo: [1x1 struct]
      objval: 1
     runtime: 0
           x: [3x1 double]
       slack: [2x1 double]
    objbound: 1
   itercount: 0
baritercount: 0
   nodecount: 0

x 0
y 1
z 0
Obj: 1.000000e+000

=========================================

ここで、このコードを一般化して、スクール バスの経路指定の問題を解決したいと思います。

SBRP の問題を次のようにモデル化しました。

minimize sum_{i!=j} c_{ij} x_{ij}

subject to sum_{j=1}^{n} x_{ij} = 1, for i=1,2,...,n

           sum_{i=1}^{n} x_{ij} = 1, for j=1,2,...,n



           sum_{i,j \in s} <=|s|-v(s);

           s c V\{1};

           |s|>=2;

           x_{ij} \in {0,1}; i,j =1,2,...,n; i!=j

c_{ij}コストです

v(s)sは、最適解で のすべての頂点を訪れるために必要な車両数の下限です。

Sは のサブセットでV/{1}、Vはバス停のセットです。

私を助けてください。

ありがとう、

アジェイ

4

1 に答える 1

1

おそらく、サブツアー除去制約を繰り返し追加したいと思うでしょう (非常に多くの制約があるため)。あなたはこれをしたい：

  1. サブツアー除去制約なしで Gurobi の問題を解きます。
  2. どのサブツアーの除外制約に違反しているかを確認してください。
  3. 違反した制約をモデルに追加します。違反したサブツアー削除制約がなくなるまで、1 ～ 3 まで繰り返します。

この方法では、約 10 ストップを超えるインスタンスを最適化することはしばしば困難です。

于 2013-06-10T17:19:44.107 に答える