Gurobi model optimal but constraints violated

Question

I'm writing an extension of the Vehicle Routing Problem (VRP) in JAVA by using Gurobi. The problem that I have, is that when I run my code, JAVA says that it is optimal with an objective value of zero. Which should not be te case, since:

A VRP works with arcs and nodes. Whether an arc is used is indicated by the Xijk variable (whether you travel from node i to node j by vehicle k). In the VRP one constraints inter alia that each customer needs to be visited exactly once. Meaning that at least one Xijk for customer j needs to be one. Which vehicle k is used and what the previous visited node i was, is something you ask Gurobi to find out.

So only when there are Xijk variables that have a zero cost-factor in the objective function, it seems logic that the objective value equals to zero. However, for me that is not the case, since I (re)write the objective function at the end of my code and use the distance between node i to j as the cost-factor. Even when I look into the model formulation which is retrieved by "model.write("constraintOutput.lp")", I see an objective function that contains Xijk variables with a cost-factor of >0.

So, I have searched around for a solution and people have mentioned that the problem could be:

a. When initializing the variables, the third parameter should not be zero since it says what the "cost-factor" of the variable should be in the objective function. Since I write my constraint at the last part of my code before optimizing my model, this should not matter, I believe. Though I have changed this parameter from zero to one when initializing Xijk variables, but the problem still remains.

b. I should update my model after initializing my variables and constraints. I have done this, but again the problem still remains.

I have even reduced my model by removing some constraints, but this does not help.

Does anybody have an idea of how to solve this problem?

My code:

import java.util.ArrayList;
import gurobi.GRB;
import gurobi.GRBEnv;
import gurobi.GRBException;
import gurobi.GRBLinExpr;
import gurobi.GRBModel;
import gurobi.GRBVar;

public class VRP {

public int M;                               //big number
public int speed;                           //speed km/h
public int nDepots;                         //number of depots
public int nCustomers;                      //number of customers to be visited
public ArrayList allLocations;        //All locations
public ArrayList vehicleList;      //Vehicles 
public double [][] dm;                      //distance matrix

public VRP(ArrayList n, ArrayList d, ArrayList dummyd, ArrayList v, double [][] distanceMatrix) throws Exception {
    this.M = 1000;
    this.speed = 60000;

    this.vehicleList = v;

    this.allLocations = new ArrayList();
    this.allLocations.addAll(d);
    this.allLocations.addAll(n);

    this.nDepots = d.size();
    this.nCustomers = n.size();

    this.dm = distanceMatrix;
}

public void solution() throws Exception{

    Functions f = new Functions();

    // 1. DEFINE MODEL ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 
    try{
        GRBEnv env = new GRBEnv ();
        env.set(GRB.IntParam.OutputFlag, 0);        //set to 1 to get constraint overview

        GRBModel model = new GRBModel(env);
        model.set ( GRB.StringAttr.ModelName, "VRP" );

        // 2. DEFINE VARIABLES ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- 

        //Xijqk

        GRBVar[][][] x = new GRBVar[this.allLocations.size()][this.allLocations.size()][this.vehicleList.size()];       

        for (int i = 0; i 0){
                            System.out.println(x[i][j][k].get(GRB.StringAttr.VarName) + " " + x[i][j][k].get(GRB.DoubleAttr.X));
                            System.out.println("Node: " + (i+1) + " goes to node: " + (j+1) + " by vehicle: " + (k+1));
                        }//if
                    }//k
                }//if
            }//j
        }//i

        System.out.println("The objective value is: " + obj);


        //6. DISPOSE OF MODEL AND ENVIRONMENT
        model.dispose();
        env.dispose();

    }catch  (GRBException e ){
        e.printStackTrace();
    }//catch
}//solution

}//public main problem

Rebecca · Accepted Answer

So I found the solution:

//Constraint 1
        for (int j = nDepots; j < this.allLocations.size(); j++){

            GRBLinExpr lhs = new GRBLinExpr();
            for(int i = 0; i < this.allLocations.size(); i++){
                if(i != j) {
                    for (int k = 0; k < this.vehicleList.size(); k++){
                        lhs.addTerm(1, x[i][j][k]);
                    }//k
                }
            }//i

            GRBLinExpr rhs = new GRBLinExpr();
            rhs.addConstant(1);

            model.addConstr(lhs, GRB.EQUAL, rhs, "C1 - j"+j);
        }//j

I have not included Xijk variables in my objective function where i = j. Since I know beforehand that such variables are invalid answers. However, I forgot to do the same for the constraints. Meaning, I have to add an if loop with (i!=j) as shown in the above example. Now my code is working!

Gurobi model optimal but constraints violated

Answers (2)

Related Questions