java - Gurobi 模型最优但违反约束

Question

我正在使用 Gurobi 在 JAVA 中编写车辆路由问题 (VRP) 的扩展。我遇到的问题是，当我运行代码时，JAVA 说它是最优的，目标值为零。这不应该是这种情况，因为:

VRP 适用于弧和节点。是否使用弧线由 Xijk 变量指示(是否乘坐车辆 k 从节点 i 行驶到节点 j)。在 VRP 中，有一个限制，即每个客户都需要被恰好访问一次。这意味着客户 j 的至少一个 Xijk 需要为 1。使用哪辆车 k 以及之前访问过的节点 i 是什么，是您要求 Gurobi 找出的内容。

因此，只有当目标函数中存在成本因子为零的 Xijk 变量时，目标值等于 0 才符合逻辑。然而，对我来说情况并非如此，因为我在代码末尾(重新)编写了目标函数，并使用节点 i 到 j 之间的距离作为成本因子。即使当我查看由“model.write("constraintOutput.lp")”检索的模型公式时，我也会看到一个目标函数，其中包含成本因子 >0 的 Xijk 变量。

因此，我四处寻找解决方案，人们提到问题可能是:

a. 初始化变量时，第三个参数不应该为零，因为它说明了目标函数中变量的“成本因子”应该是什么。由于我在优化模型之前在代码的最后部分编写了约束，所以我相信这应该不重要。虽然我在初始化Xijk变量时已将此参数从0更改为1，但问题仍然存在。

b. 我应该在初始化变量和约束后更新我的模型。我已经这样做了，但问题仍然存在。

我什至通过删除一些约束来减少我的模型，但这没有帮助。

有人知道如何解决这个问题吗？

我的代码:

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<Node> allLocations;        //All locations
public ArrayList<Vehicle> vehicleList;      //Vehicles 
public double [][] dm;                      //distance matrix

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

    this.vehicleList = v;

    this.allLocations = new ArrayList<Node>();
    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<this.allLocations.size(); i++){
            for (int j = 0; j < this.allLocations.size(); j++){
                for (int k = 0; k < this.vehicleList.size(); k++){

                    double dij = f.getDistance(dm, this.allLocations.get(i).nodeID, this.allLocations.get(j).nodeID);
                    //get.Distance retrieves the distance between two nodes that are indicated by their IDs

                    x[i][j][k] = model.addVar(0.0, 1.0, dij, GRB.BINARY, "X" + i + j + k);              //arc between node i and j used by vehicle k or not             
                }//k
            }//j
        }//i

        //aik: arival time at customer i by vehicle k 

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

        for (int i = 0; i<this.allLocations.size(); i++){
            for (int k = 0; k < this.vehicleList.size(); k++){
                a[i][k] = model.addVar(0.0, GRB.INFINITY, 0.0, GRB.CONTINUOUS, "a" + i + k);                //arival time at node i by vehicle k 
            }//k
        }//i

        //dep: departure time from customer i by vehicle k

        GRBVar[][] dep = new GRBVar[nDepots][this.vehicleList.size()];

        for (int i = 0; i < nDepots; i++){
            for (int k = 0; k < this.vehicleList.size(); k++){
                dep[i][k] = model.addVar(0.0, GRB.INFINITY, 0.0, GRB.CONTINUOUS, "dep" + i + k);                //departure time from depot i by vehicle k 
            }//k
        }//i

        model.update();

        //3. DEFINE CONSTRAINTS 

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

            GRBLinExpr lhs = new GRBLinExpr();
            for(int i = 0; i < this.allLocations.size(); i++){
                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, "Constraint 1");
        }//j

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

            GRBLinExpr lhs = new GRBLinExpr();
            for(int j = 0; j < this.allLocations.size(); 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, "Constraint 2:");
        }//j

        //Constraint 3
        for (int s = nDepots; s < this.allLocations.size(); s++){
            for (int k = 0; k < this.vehicleList.size(); k++){

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

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

                model.addConstr(lhs, GRB.LESS_EQUAL, rhs, "Constraint 3");
            }//k
        }//s

        //Constraint 4
        for (int s = nDepots; s < this.allLocations.size(); s++){
            for (int k = 0; k < this.vehicleList.size(); k++){

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

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

                model.addConstr(lhs, GRB.LESS_EQUAL, rhs, "Constraint 4");
            }//k
        }//s

        //Constraint 5
        for (int k = 0; k < this.vehicleList.size(); k++){

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

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

            model.addConstr(lhs, GRB.LESS_EQUAL, rhs, "Constraint 5:");
        }//k

        //Constraint 6
        for (int k = 0; k < this.vehicleList.size(); k++){

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

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

            model.addConstr(lhs, GRB.LESS_EQUAL, rhs, "Constraint 6:");
        }//k        

        //Constraint 7: Capacity constraints of vehicles

        for (int k = 0; k < this.vehicleList.size(); k++){

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

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

            model.addConstr(lhs, GRB.LESS_EQUAL, rhs, "Constraint 7: Capacity");
        }//k

        //Constraint 8: #vehicles entering depot cannot exceed depot capacity
        for (int j=0; j < nDepots; j++){

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

            GRBLinExpr rhs = new GRBLinExpr();
            int pj = this.allLocations.get(j).vehicleCapacity;
            rhs.addConstant(pj);    

            model.addConstr(lhs, GRB.LESS_EQUAL, rhs, "Constraint 8");
        }//i

        //Constraint 9: TimeWindow
        for (int i = nDepots; i < this.allLocations.size(); i++){
            for (int k = 0; k < this.vehicleList.size(); k++){

                GRBLinExpr lhs = new GRBLinExpr();
                lhs.addTerm(1, a[i][k]);

                GRBLinExpr rhs = new GRBLinExpr();
                double stwi = this.allLocations.get(i).startTime;
                rhs.addConstant(stwi);

                model.addConstr(lhs, GRB.GREATER_EQUAL, rhs, "Constraint 9: ");
            }//k
        }//i

        //Constraint 10: TimeWindow
        for (int i = nDepots; i < this.allLocations.size(); i++){
            for (int k = 0; k < this.vehicleList.size(); k++){
                GRBLinExpr lhs = new GRBLinExpr();
                lhs.addTerm(1, a[i][k]);

                GRBLinExpr rhs = new GRBLinExpr();
                double etw = this.allLocations.get(i).endTime;
                rhs.addConstant(etw);

                model.addConstr(lhs, GRB.LESS_EQUAL, rhs, "Constraint 10:");
            }//for k
        }//i

        //Constraint 11: determine departure vehicle from depot 
        for (int i = 0; i < nDepots; i++){
            for (int k = 0; k < this.vehicleList.size(); k++){

                GRBLinExpr lhs = new GRBLinExpr();
                double eid = this.allLocations.get(i).startTime;
                lhs.addConstant(eid);

                GRBLinExpr rhs = new GRBLinExpr();
                rhs.addTerm(1, dep[i][k]);

                model.addConstr(lhs, GRB.LESS_EQUAL, rhs, "Constraint 11:" );
            }//k
        }//i

        //Constraint 12: determine returning time to depot
        for (int i = 0; i < nDepots; i++){
            for (int k = 0; k < this.vehicleList.size(); k++){

                GRBLinExpr lhs = new GRBLinExpr();
                lhs.addTerm(1, a[i][k]);

                GRBLinExpr rhs = new GRBLinExpr();
                double lid = this.allLocations.get(i).returningTime;
                rhs.addConstant(lid);

                model.addConstr(lhs, GRB.LESS_EQUAL, rhs, "Constraint 12: " );
            }//k
        }//i

        //Constraint 13: precedence constraint 1
        for (int i = nDepots; i < this.allLocations.size(); i++){
            for (int j = 0; j < this.allLocations.size(); j++){
                if (i != j){ 
                    for (int k = 0; k < this.vehicleList.size(); k++){

                        GRBLinExpr lhs = new GRBLinExpr();
                        lhs.addTerm(1, a[j][k]);

                        GRBLinExpr rhs = new GRBLinExpr();
                        rhs.addTerm(1, a[i][k]);
                        double si = this.allLocations.get(i).serviceTime;
                        rhs.addConstant(si);

                        double dtij = (this.allLocations.get(i).distance + f.getDistance(dm, this.allLocations.get(i).nodeID, this.allLocations.get(j).nodeID))/speed;
                        rhs.addConstant(dtij);

                        rhs.addConstant(-M);
                        rhs.addTerm(M, x[i][j][k]);

                        model.addConstr(lhs, GRB.GREATER_EQUAL, rhs, "Constraint 13: ");
                    }//k
                }//if 
            }//j
        }//i

        //Constraint 14: precedence constraint 2 - if previous node was depot
        for (int i = 0; i < nDepots; i++){
            for (int j = nDepots; j < this.allLocations.size(); j++){
                for (int k = 0; k < this.vehicleList.size(); k++){

                    GRBLinExpr lhs = new GRBLinExpr();
                    lhs.addTerm(1, a[j][k]);

                    GRBLinExpr rhs = new GRBLinExpr();
                    rhs.addTerm(1, dep[i][k]);

                    double dtij = (this.allLocations.get(i).distance + f.getDistance(dm, this.allLocations.get(i).nodeID, this.allLocations.get(j).nodeID))/speed;

                    rhs.addConstant(dtij);

                    rhs.addConstant(-M);
                    rhs.addTerm(M, x[i][j][k]);

                    model.addConstr(lhs, GRB.GREATER_EQUAL, rhs, "Constraint 14: ");
                }//for k
            }//for j
        }//for i

        model.update();

        //4. SET OBJECTIVE ---------------------------------------------------------------------------------------------------------------------------------------

        GRBLinExpr expr = new GRBLinExpr();

        for (int i = 0; i < this.allLocations.size(); i++){
            for (int j = 0; j < this.allLocations.size(); j++){
                if (i != j){
                    for (int k = 0; k < this.vehicleList.size(); k++){

                        double dtij = (this.allLocations.get(i).distance + f.getDistance(dm, this.allLocations.get(i).nodeID, this.allLocations.get(j).nodeID))/speed;
                        expr.addTerm(dtij, x[i][j][k]);
                    }//k
                }//if
            }//j
        }//i

        model.setObjective(expr, GRB.MINIMIZE);

        model.update();

        model.optimize();
        System.out.println("is the solution feasible? " + model.get(GRB.IntAttr.Status));
        model.write("constraintOutput.lp");

        //5. CONSTRUCT SOLUTION ---------------------------------------------------------------------------------------------------------------------------------------------
        double obj = model.get(GRB.DoubleAttr.ObjVal);

        for (int i = 0; i < this.allLocations.size(); i++){
            for (int j = 0; j < this.allLocations.size(); j++){
                if (i != j){
                    for (int k = 0; k < this.vehicleList.size(); k++){

                        if (x[i][j][k].get(GRB.DoubleAttr.X) > 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)主要问题

Answer 1

arc (depot,j), j customer 的值是多少？我有一个观察:var x[i][j][k]的定义，当你定义二进制时，放(0和1)，而不是(0.0和1.0)，如下所示:

x[i][j][k] = model.addVar(0, 1, dij, GRB.BINARY, "X" + i + j + k)