Decision Optimization

 View Only
  • 1.  Filtering on the sets on DoCplex

    Posted Sat May 21, 2022 05:31 AM
    HI,

    I am working on a variant of the CVRP and trying to solve this problem with different sub-tour elimination constraints. In the OPL-CPLEX it is straightforward to do that, but in DoCplex I have some issues. The problem is:
    Nodes    = ["depot", "node1", "node2", "node3", "node4", "node5"];
    Nodes_1  = ["node1", "node2", "node3", "node4", "node5"];
    Vehicles = ["v1", "v2"];
    depots   = ["depot"]
    
    I   = range(len(Nodes))
    J   = range(len(Nodes))
    I_1 = range(len(Nodes_1))
    J_1 = range(len(Nodes_1))
    P   = range(len(Nodes))
    K   = range(len(Vehicles))
    I_2 = range(len(depots))
    J_2 = range(len(depots))
    
    
    capacity = [5, 5]
    demand   = [0, 1, 1, 1, 1, 1]
    cost = [
    [1000,13,11,12,11,12],
    [13,1000,10,13,14,12],
    [11,10,1000,12,13,15],
    [12,13,12,1000,15,15],
    [11,14,13,15,1000,13],
    [12,12,15,15,13,1000]
    ]
    
    for i in I:
      if(i>0):
        for j in J:
          if(j>0):
            for k in K:
              if(i!=j):
                mdl.add_constraint(u[i] - u[j] + (5*x[(i,j,k)]) <= (5-demand[i]), "c6")​


    I have defined different subsets to do the appropriate filtering, but when the problem is run the following error is rising:

    ---------------------------------------------------------------------------
    KeyError                                  Traceback (most recent call last)
    <ipython-input-50-5c1f8a616afd> in <module>()
         54         for k in K:
         55           if(i!=j):
    ---> 56             mdl.add_constraint(u[i] - u[j] + (5*x[(i,j,k)]) <= (5-demand[i]), "c6")
         57 
         58 # The solve section
    
    KeyError: 5


    Also, writing the above constraint as follows still results the different solutions:

    for i,i1 in enumerate(I_1):
      for j in J_1:
        for k in K:
          if(i!=j):
            mdl.add_constraint(u[i] - u[j] + (5*x[(i,j,k)]) <= (5-demand[i1]), "c6")



    The sub-tour I am trying to write is a special case of the MTZ and defined as:

    forall i,j in Nodes and i,j >1 and i!=j;
    u[i] - u[j] + A*x(i,j,k) <= A-demand(i)if(demand[i]+demand[j] < A);


    Would you please, how we can fix that?

    Best regards



    ------------------------------
    Abbas Omidi
    ------------------------------



  • 2.  RE: Filtering on the sets on DoCplex

    Posted Wed May 25, 2022 05:58 AM
    Dear Abbas,

    It looks like your 'u' array doesn't have an entry for 5. 
    How is it initialized?
    Cheers,

    ------------------------------
    Renaud Dumeur
    ------------------------------



  • 3.  RE: Filtering on the sets on DoCplex

    Posted Sat May 28, 2022 04:11 AM
      |   view attached
    Dear Renaud,

    Many thanks for your reply and sorry for the delay. Actually, I am trying to formulate the above problem with two different codings in SEC, and in both cases, the results seem to be incorrect. Please, see the attached file. My main questions are,
    1) how can we define the mentioned SEC in the previous post as a DoCplex expression?
    2) And why with defining the sub-sets and using them, the results are different?


    Best regards

    ------------------------------
    Abbas Omidi
    ------------------------------

    Attachment(s)

    py
    CVRP.py   2 KB 1 version


  • 4.  RE: Filtering on the sets on DoCplex

    Posted Tue May 31, 2022 04:42 AM
    Edited by Renaud Dumeur Tue May 31, 2022 04:56 AM
    Dear Abbas,

    Again, the error comes from that:
    - the 'u' dict has entries ranging from 0 to 4 (which len(Nodes_1)) 
    - your loop that add 'second type'  constraints uses 'j' as a key in 'u' that ranges from 0 to 5, for 'J' is defined as range(len(Nodes)).
    So I don't understand how you choose to index your nodes in the TMZ formulation and why you have two node arrays.
    You should have a single array describing the nodes, and your indices should range from 1 to lastNode instead of starting from 0, since you want to exclude the depot.
    I suggest that you have a look at https://how-to.aimms.com/Articles/332/332-Miller-Tucker-Zemlin-formulation.html
    which should help you model your problem correctly.


    ------------------------------
    Renaud Dumeur
    ------------------------------



  • 5.  RE: Filtering on the sets on DoCplex

    Posted Tue May 31, 2022 05:46 AM
    Dear Renaud,

    Many thanks for your comments. Actually, I could resolve the raised issue and the model seems to work fine. But, as a following up on the second question I would like to know why by defining the subset in a whole model (not in the definition of the variables and also not only in the sec constraint) the results are wrong? (For more clarification, I defined the subset in the pre-processing part to avoid directly creating filters on the constraints. But, the results are quite different.)

    Now, the thing that is somewhat strange to me is the achieved lower bound in the optimal solution from the python code in comparison with the one I achieved from GAMS/Cplex. In the python code, the LB is around 40 while in the GAMS/Cplex it is around 62!! In both cases, the optimal solution is 70 with the reasonable solution.

    Thanks in advance
    regards

    ------------------------------
    Abbas Omidi
    ------------------------------



  • 6.  RE: Filtering on the sets on DoCplex

    Posted Tue May 31, 2022 04:49 PM
    Dear Abbas,

    I'm happy to see you have resolved your issue. 
    The difference in behavior is strange. I suspect your python model may differ from the one you wrote using GAMS/Cplex.  If you dump both cplex models and compare them you should be able to spot the cause for this change of behavior.
    Cheers,

    ------------------------------
    Renaud Dumeur
    ------------------------------



  • 7.  RE: Filtering on the sets on DoCplex

    Posted Thu June 02, 2022 04:44 AM
    Dear Abbas,

    One more thing, if your want to assess the performances of your models, you may use the 'tools runseed'  command of the 'cpoptimizer' interactive solver. which will provide results for different random seeds and will estimate statistics on the objective.
    Cheers,

    ------------------------------
    Renaud Dumeur
    ------------------------------



  • 8.  RE: Filtering on the sets on DoCplex

    Posted Sun June 05, 2022 07:33 AM
    Dear Renaud,

    Thanks for your informative comments. Actually, I am using MILPs to solve the instances and I am not sure how CP optimizer can help analysing MILPs.

    Best regards
    Abbas

    ------------------------------
    Abbas Omidi
    ------------------------------



  • 9.  RE: Filtering on the sets on DoCplex

    Posted Tue June 07, 2022 04:05 AM
    Dear Abbas,

    Sorry for the mistake! But luckily,  you also have the 'tools runseeds' command in the interactive 'cplex' executable shipped with the cplex studio distribution!
    Cheers,

    ------------------------------
    Renaud Dumeur
    ------------------------------



  • 10.  RE: Filtering on the sets on DoCplex

    Posted Wed June 08, 2022 02:20 AM
    Dear Renaud,

    Thank you so much for the clarification. I will try using that. 

    Cheers
     


    ------------------------------
    Abbas Omidi
    ------------------------------