Decision Optimization

Decision Optimization

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

 View Only

  • 1.  Resource‐Constrained Project Scheduling Problem (RCPSP) using CPLEX optimizer

    Posted Mon July 30, 2018 07:13 PM

    Originally posted by: krisna87


    Can somebody help me to transform Resource‐Constrained Project Scheduling Problem (RCPSP) from Constraint Programming code below to CPLEX code ? Because I want to measure CPLEX performance to solve RCPSP problem.

     

    using CP;
     
    int NbTasks = ...;
    int NbRsrcs = ...;
     
    range RsrcIds = 0..NbRsrcs-1; 
     
    int Capacity[r in RsrcIds] = ...;
     
    tuple Task {
      key int id;
      int     pt;
      int     dmds[RsrcIds];
      {int}   succs; 
    }
     
    {Task} Tasks = ...;
     
    dvar interval itvs[t in Tasks]  size t.pt;
     
    cumulFunction rsrcUsage[r in RsrcIds] = 
      sum (t in Tasks: t.dmds[r]>0) pulse(itvs[t], t.dmds[r]);
     
    execute {
    cp.param.FailLimit = 10000;
    }
     
    minimize max(t in Tasks) endOf(itvs[t]);
    subject to {
      forall (r in RsrcIds)
        rsrcUsage[r] <= Capacity[r];
      forall (t1 in Tasks, t2id in t1.succs)
        endBeforeStart(itvs[t1], itvs[<t2id>]);
    }
     
    execute {
      for (var t in Tasks) {
        writeln("Task " + t.id + " starts at " + itvs[t].start);
      }
    }

     


    #CPLEXOptimizers
    #DecisionOptimization


  • 2.  Re: Resource‐Constrained Project Scheduling Problem (RCPSP) using CPLEX optimizer

    Posted Tue July 31, 2018 12:48 AM

    Originally posted by: nlp7


    You will need a mathematical model to solve the RCPSP in CPLEX.

    A simple model would be a discrete time model, you can see slide 6 of this presentation that I found online, which involves 3 groups of constraints, the objective function, and it involves only binary variables.

     


    #CPLEXOptimizers
    #DecisionOptimization


  • 3.  Re: Resource‐Constrained Project Scheduling Problem (RCPSP) using CPLEX optimizer

    Posted Tue July 31, 2018 05:33 AM

    Originally posted by: krisna87


    is the model similar to the CP code ? Can you give me the example cplex code ? Because this is my first time using CPLEX and CP


    #CPLEXOptimizers
    #DecisionOptimization


  • 4.  Re: Resource‐Constrained Project Scheduling Problem (RCPSP) using CPLEX optimizer

    Posted Tue July 31, 2018 10:19 AM

    This paper by Ku and Beck compares Constraint Programming to various MIP formulations. It concludes with:

    Comparing the best MIP results with that of CP, results show that MIP performs similarly to CP for smaller problems in terms of proving optimality. However, CP dominates MIP for larger problems both in terms of proving optimality and solution quality.

    You will find there some examples of MIP formulations that you can probably use to write RCPSP.

    I would be surprised if you find very different results for RCPSP than Job Shop.


    #CPLEXOptimizers
    #DecisionOptimization


  • 5.  Re: Resource‐Constrained Project Scheduling Problem (RCPSP) using CPLEX optimizer

    Posted Tue July 31, 2018 10:41 AM

    Originally posted by: PhilippeLaborie


    In complement to Xavier's answer, there is also this comparison I did some time ago between a CP Optimizer model and a naive time indexed MIP formulation: https://www.slideshare.net/PhilippeLaborie/an-introduction-to-cp-optimizer. You will find it on the slides 15-19. The problem with MIP models for RCPSP (and in general for scheduling problems) is that they will scale poorly with problem size. The classical academical instances are very small (up to a bit more than 100 tasks only) and not really representative of real life problems. Note also that there are many many different MIP formulations for the RCPSP (see for instance https://opus4.kobv.de/opus4-zib/files/6020/Tesch_Compact_MIP_Models_for_the_RCPSP.pdf) but they all suffer from scaling issues, if only because the size of the MIP grows in n^2 or even n^3 with the number of tasks. 


    #CPLEXOptimizers
    #DecisionOptimization


Related Content