Decision Optimization

 View Only
  • 1.  CPLEX taking too long to solve an MILP

    Posted Wed October 21, 2020 10:16 AM
    Hello,
    I have developed a deterministic combined vehicle routing and scheduling problem that includes time precedence and operation synchronization constraints. I am trying to solve a very small problem instance with 3 customers and 2 vehicles but it is taking days to solve.

    Before switching to the use of a solution algorithm or heuristic, I am wondering whether there is any parameters to adjust in CPLEX to improve computation time? Also is there a way to detect whether the model is weak? and what about the use of an HPC server?

    Note that the problem is formulated in java using AMPL API. I have attached the node log. 

    Thanks!

    ------------------------------
    G Hn
    ------------------------------

    #DecisionOptimization


  • 2.  RE: CPLEX taking too long to solve an MILP

    IBM Champion
    Posted Wed October 21, 2020 01:31 PM
    I suspect your model contains an error. The log says that the lower bound is stuck on zero, meaning that in the absence of integrality restrictions you could satisfy all constraints without doing anything that would contribute to the objective function. (The model also seems rather large for an instance with three customers and two variables -- over 17,000 variables! -- but perhaps you are scheduling hourly for several months?)

    Paul

    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------



  • 3.  RE: CPLEX taking too long to solve an MILP

    Posted Wed October 21, 2020 02:54 PM
    Thank you so much for your reply Prof. Rubin.

    I agree the problem have a relatively significant number of variables. It is because I want to determine routing and scheduling decisions. A binary variable xv,ui,j,u is equal to 1 if the uth task of vehicle v consists of going from i to j. And another variable yv,u determines the time at which task u for vehicle v starts. These variables are primarily needed to implement operation synchronizations among vehicles. Also, a given node along the network may be visited multiple times.

    It is correct, when integrality constraints are relaxed, the objective function is zero and this is due to the nature of the objective function which does not minimize travel costs but service durations. 

    Do you mean there should be an error in the formulation? or do you think another formulation with different variables should be used?

    ------------------------------
    GJ Hn
    ------------------------------



  • 4.  RE: CPLEX taking too long to solve an MILP

    IBM Champion
    Posted Wed October 21, 2020 05:08 PM
    1. It's not clear to me how a continuous relaxation of a proper model could have zero service duration.
    2. Your x variable has both a superscript u and a subscript u. If that is not a typographical error, I would look at whether it really needs both instances of u. (I doubt this directly explains the zero lower bound, but it might be related).
    3. You said something about synchronizations among vehicles, but did not explain what that means (which is okay -- I'm not sure I want to know). It's common for variables in routing problems to have subscripts for which vehicle, which arc and/or which customer, but the index u of the task seems odd to me. If you do not explicitly need to know that vehicle 1 going from node i to node j is task 13 for that vehicle, getting away from having that index might lead to a tighter formulation.
    4. Another consideration is that your model is not going to scale well unless you can bring down the number of variables significantly.
    5. From what I saw in the log, your primal bound (incumbent solution) was improving fairly steadily. The best bound being stuck on zero is likely a pointer to why your run time is so long. So finding a model where the LP relaxation has a strictly positive objective (that increases as you fix some of the binary variables) is probably where your focus should be.


    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------