Decision Optimization

Decision Optimization

Delivers prescriptive analytics capabilities and decision intelligence to improve decision-making.


#Analytics
#DecisionOptimization
#DecisionOptimization
 View Only
  • 1.  Mathematical formulation CVRPTW in CPLEX

    Posted 10/04/21 02:12 AM
    Hi. Recently, i m working on converting mathematical model into OPL language for CPLEX. i managed to run the code but no solution computed. Hope someone can give me some guidance and advices. Thank you. Here are the code and the mathematical formulation. 

    Mod.File: 

    int v=...; //number of customers

    range V=1..v; //customers - where 1 is the depot

    int k=...;//number of vehicles

    range K=1..k; //number of vehicles
    float Distance [V][V] = ...;//Distance between customers and depot
    float Capacity= ... ;//Capacity per vehicle
    float Demand[V] = ...; //demand for each customer
    dvar boolean x[V][V];// route driven between customer i and j
    dvar float+ y[V];

    //Objective Function
    minimize
    sum(i, j in V: i != j)
    x[i][j]*Distance[i][j];

    subject to {

    //Constraints 1: Exactly one vehicle in
    forall(j in V: j != 1)
    sum (i in V)
    x[i][j] == 1;

    //Constraints 2: Exactly one vehicle out
    forall(i in V: i != 1)
    sum (j in V)
    x[i][j] == 1;

    //Constraints 1: Exactly one vehicle in

    sum (j in V, k in K )
    x[1][j] == k;


    //Constraints 2:

    // sum (i in V, k in K )
    // // x[i][1] == k;

    //Constraints 4: flow conservation or to ensure that the same vehicle in and out
    forall( h in V:h!=1)
    sum(i in V) x[i][h] - sum(j in V) x[h][j]== 0;

    forall(i,j in V)
    x[i][j] + x[j][i] <= 1;

    forall(i ,j in V: i != 1) //i in V: i!= 1,j in V:j!= 1 && j!=i
    y[j] >= y[i] + Demand[j]*x[i][j]- Capacity*(1-x[i][j]);

    forall(j in V: j!= 1)
    y[j] >= Demand[j] ;

    forall(j in V: j!= 1)
    y[j] <= Capacity;

    }

    Dat File: 

    v=7; // number of customers
    k=3 ; //number of vehicles

    Distance= [
    [ 0 15 10 30 15 35 22 ],
    [ 15 0 24 23 20 36 12 ],
    [ 10 24 0 36 11 37 13 ],
    [ 30 23 36 0 42 38 23 ],
    [ 15 20 11 42 0 39 14 ],
    [ 35 36 37 38 39 0 15 ],
    [ 22 12 13 23 14 15 0 ]
    ]; // Distance between customers and depot

    Capacity = 120;// capacity of the vehicle
    Demand = [0 30 50 40 30 50 40];// demand for each customer

    ------------------------------
    Kien Hua Ting
    ------------------------------

    #DecisionOptimization


  • 2.  RE: Mathematical formulation CVRPTW in CPLEX

    Posted 10/04/21 03:30 AM
    Edited by System Admin 01/20/23 04:14 PM
    If you use named constraints also known as constraint label, then the IDE will automatically launch a feasopt when the model is infeasible to determine which constraint is blocking.
    Example:
    ```
    //Constraints 1: Exactly one vehicle in
    forall(j in V: j != 1)
    c1: sum (i in V)
    x[i][j] == 1;
    //Constraints 2: Exactly one vehicle out
    forall(i in V: i != 1)
    c2: sum (j in V)
    x[i][j] == 1;
    ```
    If you label all the constraints of your model, then CPLEX detects some issues with customer number 3.


    This debug feature will help you determine if you formulation is bad, if data is bad, or control what CPLEX can relax or not (by default, when OPL uses feasopt, it uses only named constraints).

    A good pointer in the documentation is How relaxation and conflict search works
    Ibm remove preview
    How relaxation and conflict search works
    Relaxations and conflicts both express the infeasibility of a model and propose steps towards feasibility. After you have had hands-on experience with the nurse scheduling example, learn how to differentiate between Relaxations and Conflicts.
    View this on Ibm >


    ------------------------------
    Vincent Beraudier
    ------------------------------