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

您可能想要迭代地添加 subtour 消除约束（因为它们太多了）。你想这样做：

  1. 在没有子旅游消除约束的情况下解决 Gurobi 中的问题。
  2. 检查并查看违反了哪些 subtour 消除约束。
  3. 将违反的约束添加到您的模型中。重复 1-3 直到你没有违反 subtour 消除约束。

使用这种方法通常很难在超过 10 个停靠点的情况下将实例求解到最优。

于 2013-06-10T17:19:44.107 回答