Take the 2-minute tour ×

%An example to solve MILP using gurobi optimizer in matlab interface is given as follows:

function[] = mip1() 

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

    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);  


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

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

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



After running this code we have output like this:

      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


Now I want to generalize this code to solve school bus routing problem.

I have modeled SBRP problem like this:

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};


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

c_{ij} is cost

v(s) is an lower bound on the number of vehicles required to visit all vertices of s in the optimal solution.

S is a subset of V/{1}, where V is the set of bus stops.

Please help me.

Thanking you,


share|improve this question
What you have here is the VRP formulation. (SBRP has a few more constraints, bus capacity and total distance a student travels.) As roulcousins points out, sub-tour elimination will trip you up. Start with a small problem (5 or nodes/bus stops) and keep building it up, depending on what you are trying to achieve/learn. Gurobi is fine, the trick is in loading the formulation & handing it over to the solver. –  Ram Narasimhan Jun 10 '13 at 21:28
@ Ram Narasimhan Thanks, it helped me alot. –  Ajay Shankar Bidyarthy Nov 14 '13 at 10:28
add comment

1 Answer

You probably want to add the subtour elimination constraints iteratively (since there are so many of them). You want to do this:

  1. Solve the problem in Gurobi without subtour elimination constraints.
  2. Check and see which subtour elimination constraints are violated.
  3. Add the violated constraint to your model. Repeat until 1-3 until until you get no violated subtour elimination constraints.

It's often difficult to solve instances to optimality with more than about 10 stops with this method.

share|improve this answer
add comment

Your Answer


