Decision Optimization

 View Only
  • 1.  All entries at implied bounds

    Posted Mon June 22, 2020 05:08 AM
    1. I have a set of cars with scheduled time originaltime[cars] to arrive at destination. However, based on the sequence of arrival, they have to be some time apart (given by data input separate[cars][cars]).
    2. My objective is to minimize the delay of the cars from the original time while respecting the necessary separation.
    3. The cars can only come 60seconds before their scheduled time originaltime[cars] and 1800seconds after.
    4. I fix the sequence to enforce first-come-first-served based on their scheduled time originaltime[cars]

    It should be a straight forward implementation, however i encountered problems with some entries at implied bounds. I looked at my input data and constraints and I am really not sure why. 

    I've written the CPLEX code below for my attempts at the problem. Thank you for helping in advance.

    modelcode:

    //index of the cars considered
    {string} cars = ...;
    //original scheduled time
    int originaltime[cars] = ...;
    //time separation apart based on arrival sequence
    int separation[cars][cars] = ...;
    //decision variables
    //the modified time to minimized the delays
    dvar float assignedtime[cars];
    //the earliest and latest time the cars can arrive
    dvar float earliesttime[cars];
    dvar float latesttime[cars];
    //0-1 variable to specify the order of the cars
    dvar boolean order[cars][cars];
    //to measure the delay of each car
    dvar float indvdelay[cars];
    //decision expression to calculate objective ( separated them because I've simplified the problem)
    dexpr float objcost[f in cars] = indvdelay2[f];
    dexpr float totalobjcost = sum(f in cars) objcost[f];
    dexpr float overallobjcost = (1.3*totalobjcost); 
    //objective functionn
    minimize
        overallobjcost;    
    //constraints;
    subject to{ 
    //obj remove modulus constraint (to account for +/- delay numbers so that it is always positive)
        forall(f in cars)
          indvdelay[f] >= assignedtime[f] -originaltime[f];
        forall(f in arrflights)
          indvdelay[f] >= -(assignedtime[f] -originaltime[f]);  
    //earliest and latest times
        forall(f in cars)
          earliesttime[f] == (originaltime[f]-60);
        forall(f in cars)
          latesttime[f] == (originaltime[f] + 1800);  
    //constraint to set order precedence based on original time FCFS
      forall(i in cars)
        forall(j in cars: i!=j)
          ctest:(originaltime[j] - originaltime[i])<= (100000*order[i][j] - 0.0005);
      forall(i in cars)
        forall(j in cars: i!=j)
          ctest1b:(originaltime[j] - originaltime[i])>= (-100000*(1-order[i][j]));
          
    //order precedence
      forall( i in cars)
        forall(j in cars: i == j)
          ctAA:order[i][j] == 0;
      forall( i in cars)
        forall(j in cars: j > i)
          ctBB:order[i][j] + order[j][i] == 1;    
     //separation 
      forall(i in cars)
        forall(j in cars: i != j)
          ctCC:assignedtime[j] >= assignedtime[i] + separation[i][j] - (100000*(1-order[i][j]));
     //time window constraint 
      forall(f in cars)
        ctDD:assignedtime[f] >= earliesttime[f];
      forall(f in cars)
        ctEE:assignedtime[f] <= latetesttime[f];
          }  


    data file code:

    SheetConnection sheet("stage2errortest.xlsx");
    cars from SheetRead(sheet,"'ARR'!B2:B25");
    originaltime from SheetRead(sheet,"'ARR'!C2:C25");
    separation from SheetRead(sheet,"'septable1arr'!A1:X24");
    
    assignedttime to SheetWrite(sheet,"'ARR'!E2:E25");
    indvdelay to SheetWrite(sheet,"'ARR'!F2:F25");


    datafile link

    https://drive.google.com/file/d/14oMZR6DPxR5Gvvh0US00WXpsjozJJYha/view



    ------------------------------
    marvin cheung
    ------------------------------

    #DecisionOptimization


  • 2.  RE: All entries at implied bounds

    Posted Mon June 22, 2020 05:43 AM
    Have you tried using the conflict refiner? See here for a tutorial on how to handle unexpected infeasibilities.

    ------------------------------
    Daniel Junglas
    ------------------------------



  • 3.  RE: All entries at implied bounds

    Posted Wed June 24, 2020 05:54 AM
    Thanks Daniel, I think I have figured out where is the source of infeasibility.

    By any chance, is there some posts u can direct me to on using CPLEX on cloud? (I have spoken to the support for the cluster, they need to execute CPLEX through command line)

    I have access to some cloud computing cluster, I am wondering if CPLEX supports that.

    I'm currently running my existing problems on ILOG CPLEX Optimization Studio, and I am wondering if running it on 32cores could speed up the optimization.

    ------------------------------
    marvin cheung
    ------------------------------



  • 4.  RE: All entries at implied bounds

    Posted Thu July 09, 2020 09:07 AM
    In order to solve a .mod and .dat file from the command line you can use the oplrun command line tool. Using up to 32 threads to solve a problem may indeed give a speedup.

    ------------------------------
    Daniel Junglas
    ------------------------------