Originally posted by: SystemAdmin

[UDOPS said:]

I wanted to thank the responders for their assistance to my model building this week.  I am sharing this model for the benefit of other readers. This is a working model (assuming you have the odbc data tables to match). There are lots of structures and syntax to study here! Suggestions for improving the model are welcome.

To really view this, you will probably want to copy and paste to your text editor.

DATA FILE

[tt]/*********************************************
* OPL 6.0 Data
* Author: Harrodst
* Creation Date: Jul 25, 2008 at 3:49:13 PM

Purpose
This file specifies the data sources for the feasible network pre-processing problem.

Revision History
07/31/08 First complete model
  *********************************************/
DBConnection db("odbc", "Rail/admin/");
//moved these query definitions to model file to make them easier to maintain
//Problems from DBRead(db, "SELECT KEYrec, ProblemName, KEYTracks, TransitionEpsilon, TransitionDelta FROM Problems WHERE KEYrec IN (SELECT ProblemKey FROM SolveQueue)");
//TrainData from DBRead(db, "SELECT T.KEYrec, T.TrainNumber, T.Early_Start, T.Late_End, T.Origin, T.Destination, T.Utility, T.Arrival_Bonus, T.Departure_Delay_Bonus, T.Stop_Cost, T.KEY_continuation, T.Layover_Cost, T.Minimum_Layover, T.Maximum_Layover, T.FLAG_must_run, T.Start_Slack, T.Move_Set, M.SetLabel, M.TrainSpeed, M.Headway FROM Trains T, MoveSets M WHERE T.Move_Set = M.SetID AND T.KEYset in (SELECT KEYTrainSet FROM ProblemTrainJoin WHERE KEYproblem =1407)"); // in (SELECT ProblemKey FROM SolveQueue)  )");
//
//Profile from DBRead(db, "SELECT Block_Number, Block_Capacity, Speed_Restriction, FLAG_no_wait FROM Blocks WHERE KEYset IN (SELECT KEYTracks FROM Problems WHERE KEYrec IN (SELECT ProblemKey FROM SolveQueue))");
//Orders from DBRead(db, "SELECT Time_Start, Time_End, Block_Number, Block_Capacity, Speed_Restriction, FLAG_no_wait FROM BlockExceptions WHERE KEYset IN (SELECT KEYTracks FROM Problems WHERE KEYrec IN (SELECT ProblemKey FROM SolveQueue))");
//
//MoveExc from DBRead(db,"SELECT M.SetID, E.Start_Block, E.End_Block FROM MoveExceptions E, MoveSets M WHERE E.Restriction_Type = 'Deny' AND E.KEYset = M.KEYrec AND M.SetID IN (SELECT Move_Set FROM Trains WHERE KEYset IN (SELECT KEYTrainSet FROM ProblemTrainJoin WHERE KEYproblem in (SELECT ProblemKey FROM SolveQueue)  ))");
//MoveAdd from DBRead(db,"SELECT M.SetID, E.Start_Block, E.End_Block FROM MoveExceptions E, MoveSets M WHERE E.Restriction_Type = 'Allow' AND E.KEYset = M.KEYrec AND M.SetID IN (SELECT Move_Set FROM Trains WHERE KEYset IN (SELECT KEYTrainSet FROM ProblemTrainJoin WHERE KEYproblem in (SELECT ProblemKey FROM SolveQueue)  ))");
//MoveSpd from DBRead(db,"SELECT M.SetID, S.Block_Number, S.Speed FROM CustomSpeeds S, MoveSets M WHERE S.KEYset = M.KEYrec AND M.SetID IN (SELECT Move_Set FROM Trains WHERE KEYset IN (SELECT KEYTrainSet FROM ProblemTrainJoin WHERE KEYproblem in (SELECT ProblemKey FROM SolveQueue)  ))");

Problems from DBRead(db, Problemquery);
TrainSet from DBRead(db, Trainquery);
Trains,TrainData from DBRead(db, TrainArrayquery);
Profile from DBRead(db, Profilequery);
Orders from DBRead(db, Orderquery);
MoveExc from DBRead(db, Excquery);
MoveAdd from DBRead(db, Addquery);
MoveSpd from DBRead(db, Spdquery);[/tt]

MODEL FILE

[tt]/*********************************************
* OPL 6.0 Model
* Author: Harrodst
* Creation Date: Jul 25, 2008 at 3:49:02 PM

Purpose
This model (sub-problem) pre-processes performance and resource data to define an initial network for a master problem.

Revision History
07/31/08 First complete model

*********************************************/

/******************************* Retrieve Problem Data from Database **************************************/

//Alternative query forms not used:
//string Problemquery="SELECT KEYrec, ProblemName, KEYTracks, TransitionEpsilon, TransitionDelta FROM Problems WHERE KEYrec IN (SELECT ProblemKey FROM SolveQueue)";
//string Trainquery="SELECT T.KEYrec, T.TrainNumber, T.Early_Start, T.Late_End, T.Origin, T.Destination, T.Utility, T.Arrival_Bonus, T.Departure_Delay_Bonus, T.Stop_Cost, T.KEY_continuation, T.Layover_Cost, T.Minimum_Layover, T.Maximum_Layover, T.FLAG_must_run, T.Start_Slack, T.Move_Set, M.SetLabel, M.TrainSpeed, M.Headway FROM Trains T, MoveSets M WHERE T.Move_Set = M.SetID AND T.KEYset in (SELECT KEYTrainSet FROM ProblemTrainJoin WHERE KEYproblem IN (SELECT ProblemKey FROM SolveQueue))";
//string Profilequery="SELECT Block_Number, Block_Capacity, Speed_Restriction, FLAG_no_wait FROM Blocks WHERE KEYset IN (SELECT KEYTracks FROM Problems WHERE KEYrec IN (SELECT ProblemKey FROM SolveQueue))";
//string Orderquery="SELECT Time_Start, Time_End, Block_Number, Block_Capacity, Speed_Restriction, FLAG_no_wait FROM BlockExceptions WHERE KEYset IN (SELECT KEYTracks FROM Problems WHERE KEYrec IN (SELECT ProblemKey FROM SolveQueue))";
//string Excquery="SELECT M.SetID, E.Start_Block, E.End_Block FROM MoveExceptions E, MoveSets M WHERE E.Restriction_Type = 'Deny' AND E.KEYset = M.KEYrec AND M.SetID IN (SELECT Move_Set FROM Trains WHERE KEYset IN (SELECT KEYTrainSet FROM ProblemTrainJoin WHERE KEYproblem in (SELECT ProblemKey FROM SolveQueue)  ))";
//string Addquery="SELECT M.SetID, E.Start_Block, E.End_Block FROM MoveExceptions E, MoveSets M WHERE E.Restriction_Type = 'Allow' AND E.KEYset = M.KEYrec AND M.SetID IN (SELECT Move_Set FROM Trains WHERE KEYset IN (SELECT KEYTrainSet FROM ProblemTrainJoin WHERE KEYproblem in (SELECT ProblemKey FROM SolveQueue)  ))";
//string Spdquery="SELECT M.SetID, S.Block_Number, S.Speed FROM CustomSpeeds S, MoveSets M WHERE S.KEYset = M.KEYrec AND M.SetID IN (SELECT Move_Set FROM Trains WHERE KEYset IN (SELECT KEYTrainSet FROM ProblemTrainJoin WHERE KEYproblem in (SELECT ProblemKey FROM SolveQueue)  ))";

string Problemquery="SELECT P.KEYrec, P.ProblemName, P.KEYTracks, P.TransitionEpsilon, P.TransitionDelta FROM SolveQueue Q, Problems P WHERE P.KEYrec=Q.ProblemKey";
string Trainquery="SELECT T.KEYrec, T.TrainNumber, T.Early_Start, T.Late_End, T.Origin, T.Destination, T.C_Direction, MIN(T.Origin, T.Destination), MAX(T.Origin, T.Destination), T.Utility, T.Arrival_Bonus, T.Departure_Delay_Bonus, T.Stop_Cost, T.KEY_continuation, T.Layover_Cost, T.Minimum_Layover, T.Maximum_Layover, T.FLAG_must_run, T.Start_Slack, T.Move_Set, M.SetLabel, M.TrainSpeed, M.Headway FROM SolveQueue Q, ProblemTrainJoin P, Trains T, MoveSets M WHERE Q.ProblemKey=P.KEYproblem AND P.KEYTrainSet=T.KEYset AND T.Move_Set=M.SetID";
string TrainArrayquery="SELECT T.KEYrec, T.KEYrec, T.TrainNumber, T.Early_Start, T.Late_End, T.Origin, T.Destination, T.C_Direction, MIN(T.Origin, T.Destination), MAX(T.Origin, T.Destination), T.Utility, T.Arrival_Bonus, T.Departure_Delay_Bonus, T.Stop_Cost, T.KEY_continuation, T.Layover_Cost, T.Minimum_Layover, T.Maximum_Layover, T.FLAG_must_run, T.Start_Slack, T.Move_Set, M.SetLabel, M.TrainSpeed, M.Headway FROM SolveQueue Q, ProblemTrainJoin P, Trains T, MoveSets M WHERE Q.ProblemKey=P.KEYproblem AND P.KEYTrainSet=T.KEYset AND T.Move_Set=M.SetID";
string Profilequery="SELECT B.Block_Number, B.Block_Capacity, B.Speed_Restriction, B.FLAG_no_wait FROM SolveQueue Q, Problems P, Blocks B WHERE Q.ProblemKey=P.KEYrec AND P.KEYTracks=B.KEYset";
string Orderquery="SELECT B.Time_Start, B.Time_End, B.Block_Number, B.Block_Capacity, B.Speed_Restriction, B.FLAG_no_wait FROM SolveQueue Q, Problems P, BlockExceptions B WHERE Q.ProblemKey=P.KEYrec AND P.KEYTracks=B.KEYset";
string Excquery="SELECT M.SetID, E.Start_Block, E.End_Block FROM SolveQueue Q, ProblemTrainJoin P, Trains T, MoveSets M, MoveExceptions E WHERE Q.ProblemKey=P.KEYProblem AND T.KEYset=P.KEYTrainSet AND M.SetID=T.Move_Set AND E.KEYset=M.KEYrec AND E.Restriction_Type='Deny'";
string Addquery="SELECT M.SetID, E.Start_Block, E.End_Block FROM SolveQueue Q, ProblemTrainJoin P, Trains T, MoveSets M, MoveExceptions E WHERE Q.ProblemKey=P.KEYProblem AND T.KEYset=P.KEYTrainSet AND M.SetID=T.Move_Set AND E.KEYset=M.KEYrec AND E.Restriction_Type='Allow'";
string Spdquery="SELECT M.SetID, S.Block_Number, S.Speed FROM SolveQueue Q, ProblemTrainJoin P, Trains T, MoveSets M, CustomSpeeds S WHERE Q.ProblemKey=P.KEYProblem AND T.KEYset=P.KEYTrainSet AND M.SetID=T.Move_Set AND S.KEYset = M.KEYrec";

//Input data tuple forms
tuple problem { key int problem_id; string problem_label; int tracks; int epsilon; int delta;}
tuple  train {int train_num;  /*record serial key from database*/
string train_label; int early_start; int late_end; int origin; int destination;
int direction; int blockmin; int blockmax;
int utility; int arrival_bonus; int delay_bonus; int stop_cost; int successor;  //record serial key of continuing train
int layover_cost; int layover_min; int layover_max; int must_run; int start_slack; string move_set;  //key field for move set
string move_label; int base_speed; int headway;}
tuple track {int block; int capacity; int time_minimum; int no_wait;}
tuple trackchange {int time_from; int time_to;  /*timings are inclusive*/ int block; int capacity; int time_minimum; int no_wait;}
tuple movenot { string move_set; int block_in; int block_to;}  //Prohibited moves by train move set
tuple moveallow { string move_set; int block_in; int block_to;} //Special allowed moves, overrides any track profile, speed from move set only
tuple customspeed { string move_set; int block; int speed;}  //Custom speeds by move set and block

//Derived set tuples
tuple trackexpand {int block; int time; int capacity; int time_minimum; int no_wait;}
tuple arc {int train_num;  /*database key rec for train*/ int block_in; int block_to; int time_from; int time_to;}


//Initialize data from odbc queries in data file
{problem} Problems=...; {track} Profile=...; {trackchange} Orders=...;
{train} TrainSet=...; {int} Trains=...; train TrainData[trains]=...; {movenot} MoveExc = ...;
{moveallow} MoveAdd =...; {customspeed} MoveSpd = ...;

//Check input data for agreement, hidden inconsistencies
assert forall(r in TrainSet) endafterstart: r.late_end>r.early_start;
assert forall(r in TrainSet) pathvalid: forall(i in minl(r.origin, r.destination)..maxl(r.origin, r.destination))
card({<i, c, t, n> | <i, c, t, n> in Profile})!=0;

/******************************* Construct Sub-Problem Feasible Region **************************************/

/*Build a trackplan (profile) over the time horizon that considers the base profile and
any additional track restrictions (Orders)*/
int Ts = min (r in TrainSet) r.early_start;
int Te = max (r in TrainSet) r.late_end;

{trackexpand} TrackPlan = {<p.block, time,<br /> minl(p.capacity, min(o in Orders: time>=o.time_from && time<=o.time_to) o.capacity),<br /> maxl(p.time_minimum, max(o in Orders: time>=o.time_from && time<=o.time_to) o.time_minimum),<br /> maxl(p.no_wait, max(o in Orders: time>=o.time_from && time<=o.time_to) o.no_wait)>
| p in Profile, time in Ts..Te};

/*Build initial feasible arcs for trains
Set consists of interior moves, origin starts, destination moves, idle moves, special additional moves defined by train
Interior moves:
defined over time range of train, path of train
limited by TrackPlan (capacity, speed), limited by train/move set (speed, denied block pairs)
Origin Starts:
defined over time range of train, origin
limited by TrackPlan (capacity, speed), limited by train/move set (speed, denied block pairs)
limited by start slack for train
Destination Moves:
defined over time range of train, destination, off network block (-1)
limited by TrackPlan (capacity, speed), limited by train/move set (speed)
Idle Moves:
defined over time range of train, path of train
limited by TrackPlan (capacity, no waits), limited by train/move set (denied block pairs)
Special Moves:
defined over time range of train, MoveAdd
limited by TrackPlan (capacity), speed from train/move set and TrackPlan
*/
{arc} Network = /*Interior moves*/ {<r.train_num,b,b+r.direction,ti,<br /> ti+maxl(r.base_speed,max(<b, time, cap, spd, wait> in TrackPlan: time>=ti && time<ti+r.base_speed) spd, <br /> max(<r.move_set, b, custspeed> in MoveSpd ) custspeed)> |
r in TrainSet,
b in minl(r.origin, r.destination)+1..maxl(r.origin, r.destination)-1, ti in r.early_start..r.late_end,
<b, time2, cap2, spd2, wait2> in TrackPlan: time2>=ti && time2<ti+maxl(r.base_speed,spd2) && cap2>=1 &&  <r.move_set, b, b+r.direction> not in MoveExc}

union /*Origin Starts*/{<r.train_num,r.origin,r.origin+r.direction,ti,<br /> ti+maxl(r.base_speed,max(<r.origin, time, cap, spd, wait> in TrackPlan: time>=ti && time<ti+r.base_speed) spd, <br /> max(<r.move_set, r.origin, custspeed> in MoveSpd ) custspeed)> |
r in TrainSet, ti in r.early_start..r.late_end,
<r.origin, time2, cap2, spd2, wait2> in TrackPlan: time2>=ti && time2<ti+maxl(r.base_speed,spd2) && cap2>=1 &&
<r.move_set, r.origin, r.origin+r.direction> not in MoveExc && (r.start_slack==0 || ti<=r.early_start+r.start_slack) }<br />
union /*Destination Moves*/ {<r.train_num,r.destination,-1,ti,<br /> ti+maxl(r.base_speed,max(<r.destination, time, cap, spd, wait> in TrackPlan: time>=ti && time<ti+r.base_speed) spd, <br /> max(<r.move_set, r.destination, custspeed> in MoveSpd ) custspeed)> |
r in TrainSet, ti in r.early_start..r.late_end,
<r.destination, time2, cap2, spd2, wait2> in TrackPlan: time2>=ti && time2<ti+maxl(r.base_speed,spd2) && cap2>=1}

union /*Idle Moves*/{<r.train_num,b,b,ti,ti+1> |
r in TrainSet,
b in minl(r.origin, r.destination)+1..maxl(r.origin, r.destination)-1, ti in r.early_start..r.late_end-1,
<b, ti, cap2, spd2, wait2> in TrackPlan: wait2!=1 && cap2>=1 &&  <r.move_set, b, b> not in MoveExc}

union /*Special Moves*/ {<r.train_num,b1,b2,ti,<br /> ti+maxl(r.base_speed,max(<b1, time, cap, spd, wait> in TrackPlan: time>=ti && time<ti+r.base_speed) spd, <br /> max(<r.move_set, b1, custspeed> in MoveSpd ) custspeed)> |
r in TrainSet, <r.move_set, b1, b2> in MoveAdd, ti in r.early_start..r.late_end,
<b1, time2, cap2, spd2, wait2> in TrackPlan: time2>=ti && time2<ti+maxl(r.base_speed,spd2) && cap2>=1};

//test data {arc} Network = {<234,1,2,4,7>, <234,2,3,7,9>, <234, 3,5,9,10>};
 
  int networksize= card(Network);
 
  execute {
  writeln("Model Rail Feasible is processing: "networksize" arcs derived from input data.");
  for (var r in TrainSet) {
  writeln(r.train_label+" ("r.train_num")");
  for (var a in Network)if (r.train_num==a.train_num){
  write("(..,"a.block_in","a.block_to","a.time_from","a.time_to")");
  };
  writeln();
  } //end for statement
  } //end execute

/******************************* Define the Sub-Problem **************************************/

dvar boolean Move[Network];

maximize sum(a in Network)Move[a];

subject to {

/*Cover backward constraint, for each train, at each block except origin,
arcs entering need to equal or exceed arcs exiting*/
forall (a in Network: a.block_in!=TrainData[a.train_num].origin)
sum(b in Network: b.train_num==a.train_num && b.block_to==a.block_in && b.time_to==a.time_from)Move[b]-Move[a]>=0;


/*Cover forward constraint, for each train, at each block except destination,
arcs exiting need to equal or exceed arcs entering*/
forall (a in Network: a.block_in!=TrainData[a.train_num].destination)
sum(b in Network: b.train_num==a.train_num && b.block_in==a.block_to && b.time_from==a.time_to)Move[b]-Move[a]>=0;

}

/******************************* Process Results **************************************/

{arc} OperationalNetwork = { a | a in Network: Move[a]==1 };
int operationalsize=card(OperationalNetwork);
execute {
writeln("Result ("operationalsize" pre-processed arcs)= ");
  for (var r in TrainSet) {
  writeln(r.train_label+" ("r.train_num")");
  for (var a in OperationalNetwork)if (r.train_num==a.train_num){
  write("(..,"a.block_in","a.block_to","a.time_from","a.time_to")");
  };
  writeln();
  }
}

//End of model[/tt]
#DecisionOptimization
#OPLusingCPLEXOptimizer