2
  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.

//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");

I've included the excel datafile exceldata file

gawdzilla
  • 45
  • 7
  • Exactly the same question was asked here: https://community.ibm.com/community/user/datascience/communities/community-home/digestviewer/viewthread?MessageKey=e3e96011-9c80-4a38-b757-c34b28884dfc&CommunityKey=ab7de0fd-6f43-47a9-8261-33578a231bb7&tab=digestviewer&SuccessMsg=Thank%20you%20for%20submitting%20your%20message. You should use the conflict refiner to figure out what the infeasible constraints are. – Daniel Junglas Jun 22 '20 at 13:01
  • 1
    Or, try with a smaller set of data that you know has a solution. Add constraints one at a time to enforce a known solution and see where it breaks. You can also save the generated model as an LP file which is quite reaable, and check that the model really is what you expect. – TimChippingtonDerrick Jun 23 '20 at 08:15
  • Thank you, I found the source of infeasibility. – gawdzilla Jun 24 '20 at 09:55

1 Answers1

3

The message "all entries at implied bounds" means that the problem instance is infeasible and that CPLEX was able to prove that in presolve. You can use the conflict refiner to investigate this and figure out the reason for this infeasibility.

Daniel Junglas
  • 5,830
  • 1
  • 5
  • 22