Originally posted by: UDOPS
Model, called as part of a larger flow control:
/*********************************************
Lagrangian Model for Railway Timetabling
See main file for further notes.
06/11/10 adapted from MIP model
*********************************************/
//Input data tuple forms
tuple prblm {int problem_id; string problem_label; int epsilon; int delta; int balance; string cellmode;
int headwayoff; int bonuszero; int delayzero; int stopzero; int layoverzero; int unlink; int idletransition;
int iterationlimit; float stepsize; float LB;} //"LB", lower bound or "Low Target" in 2007 version
tuple trackdata {int keyset; int tstart; int tend; int capacity;}
tuple celldata {int cell; int member;}
tuple train {int train_num; /*record serial key from database*/
string train_label; int early_start; int start_slack; int late_end; int origin; int destination;
float utility; float arrival_bonus; float delay_bonus; float stop_cost;
int mustrun; int successor; int tripid; int tripsegment; //record serial key of continuing train
float layover_cost; int layover_min; int layover_max; int headway;}
//Direction values 1: northbound, -1: southbound
tuple moov {int train_num; /*database key rec for train*/ int block_in; int block_to; int time; int direction;}
tuple arcdef {int train_num; /*database key rec for train*/ int block_in; int block_to; int time_from; int time_to; int direction;}
tuple blocktime {int block; int time;}
tuple turn {int old_train; int new_train; int time_end; int time_start;}
tuple turntime {int train; int time;}
tuple cellcoverage {int north; int south; int wait;}
tuple occheadway {int occ; int headway;}
//Data from mix of sources, added in flow control
prblm Problem
{1}=...;
{int} Blocks=...;
trackdata BlockData
Blocks=...;
{celldata} CellPairs=...;
{int} Trains=...;
train TrainData
Trains=...;
{moov} Moves=...;
{arcdef} Paths =...;
{blocktime} BlockNet=...;
{blocktime} CellNet=...;
{blocktime} BlockOccupied=...;
float UB=...; //called "bestdual" in 2007 version
float gamma=...;
int lagrprogress=...;
float target=...;
int kmax=5; //fixed parameter, defined to allow future modification
float LambdaBlock
BlockOccupied=...;
//
//Derived problem data
//
//define input for handling of train continuations
//
{turntime} PotentialLayoverStarts = {<r,tj> | r in Trains, <r,i,-1,ti,tj,d> in Paths: TrainData[r].successor>0};
{turn} Layover = {<r,TrainData[r].successor,tj,tii> | <r,tj> in PotentialLayoverStarts,
<TrainData[r].successor,TrainData[TrainData
http://r].successor.origin,jj,tii,tjj,d> in Paths:
tii>=tj+TrainData[r].layover_min && (TrainData[r].layover_max==0||tii<=tj+TrainData[r].layover_max)};
{int} TrainSuccessors= {r2 | <r,r2,tj,tii> in Layover}; //reference list of successors in linked trains
int TrainPredecessor
Trains =
<r,r2,tj,tii> in Layover;
{turntime} LayoverStarts={<r,t> | <r,r2,t,tii> in Layover}; //list of all train terminations into layover with time
{turntime} LayoverEnds={<r,t> | <r1,r,tj,t> in Layover}; //list of all train originations out of layover
//
//define cell networks
//
{int} CellMembers
<i,t> in CellNet = {m| <i,m> in CellPairs} union {i};
int CellCap
CellNet= [<i,t> : ( //capacity of cells in network
(Problem[1].cellmode=="Normal")? min(i in CellMembers
<i,t>) BlockData[i].capacity:
(Problem[1].cellmode=="Liberal")? max(i in CellMembers
<i,t>) BlockData[i].capacity:
1)| <i,t> in CellNet];
//
//determine which constraints will be potentially binding
//
execute { //pre-process block
//writeln ("\nPre-Process block.");
//writeln(PotentialLayoverStarts);
//writeln (Layover);
//debugging clauses
//writeln ("Source Train Data: ", TrainData);
//writeln(CellCap);
//writeln(CellNet);
//writeln(BlockNet);
} //end of execute
//
//configure variables and solver parameters
//
dvar boolean Dispatch
Paths;
dvar boolean Turnaround
Layover;
dexpr float BlockSlack
<i,t> in BlockOccupied=sum(<r,i,j,ti,tj,d> in Paths: t>=ti && t<tj) Dispatch
<r,i,j,ti,tj,d> - BlockData[i].capacity;
//
//submit objective and constraints
//
maximize sum(r in Trains) (
sum(<r,TrainData[r].origin,j,ti,tj,d> in Paths) (TrainData[r].utility+(1-Problem[1].delayzero)*TrainData[r].delay_bonus*(ti-TrainData[r].early_start))
*Dispatch[<r,TrainData
http://r].origin,j,ti,tj,d> //origin arc
+ sum(<r,i,-1,ti,tj,d> in Paths) (1-Problem[1].bonuszero)*TrainData[r].arrival_bonus*(TrainData[r].late_end-tj)*Dispatch
<r,i,-1,ti,tj,d> //destination arc
- sum(<r,i,i,ti,tj,d> in Paths) (1-Problem[1].stopzero)*TrainData[r].stop_cost*(tj-ti)*Dispatch
<r,i,i,ti,tj,d> //idle arcs, scaled for variable stop size
- sum(<r,r2,tj,tii> in Layover) (1-Problem[1].layoverzero)*TrainData[r].layover_cost*(tii-tj)*Turnaround
<r,r2,tj,tii> //layover linkage
) //end of primal objective
//start relaxed contraints
- sum(<i,t> in BlockOccupied) LambdaBlock
<i,t>*BlockSlack
<i,t> ; //end of maximize statement
subject to {
forall(r in Trains diff TrainSuccessors: TrainData[r].mustrun !=1 ) //network flow source
sum(<r,TrainData[r].origin,j,ti,tj,d> in Paths)Dispatch[<r,TrainData
http://r].origin,j,ti,tj,d><=1;
forall(r in Trains diff TrainSuccessors: TrainData[r].mustrun ==1) //same as above, but "must run" equality
sum(<r,TrainData[r].origin,j,ti,tj,d> in Paths)Dispatch[<r,TrainData
http://r].origin,j,ti,tj,d>==1;
forall(r in Trains, <i,t> in BlockNet: i!=TrainData[r].origin) //flow conservation at blocks
sum(<r,a,i,ti,t,d> in Paths) Dispatch
<r,a,i,ti,t,d> == sum(<r,i,j,t,tj,d> in Paths) Dispatch
<r,i,j,t,tj,d>;
forall(r in Trains: TrainData[r].successor==0) //network sink
sum(<r,TrainData[r].destination,-1,ti,tj,d> in Paths)Dispatch[<r,TrainData
http://r].destination,-1,ti,tj,d><=1;
forall(<r,t> in LayoverStarts) //flow conservation at layover start
sum(<r,TrainData[r].destination,-1,ti,t,d> in Paths) Dispatch[<r,TrainData
http://r].destination,-1,ti,t,d> == sum(<r,r2,t,tii> in Layover) Turnaround
<r,r2,t,tii>;
forall(<r,t> in LayoverEnds) //flow conservation at layover end
sum(<r,TrainData[r].origin,j,t,tj,d> in Paths) Dispatch[<r,TrainData
http://r].origin,j,t,tj,d> == sum(<r1,r,tj,t> in Layover) Turnaround
<r1,r,tj,t>;
if(Problem[1].balance==1) { //balance train count, equal count in both directions
sum(r in Trains, <r,TrainData[r].destination,-1,ti,tj,1> in Paths: TrainData[r].successor==0)Dispatch[<r,TrainData
http://r].destination,-1,ti,tj,1> ==
sum(r in Trains diff TrainSuccessors, <r,TrainData[r].origin,j,ti,tj,-1> in Paths) Dispatch[<r,TrainData
http://r].origin,j,ti,tj,-1>;
}
/* additional side constraints commented out
//cell occupancy (transition) constraint, without waiting (stopped) arcs
if(Problem[1].idletransition!=1) {forall(<a,t> in CellNet: CellOcc
<a,t>.north+CellOcc
<a,t>.south > CellCap
<a,t>)
sum(i in CellMembers
<a,t>, j in CellMembers
<a,t>, tj in (t+1-Problem[1].epsilon)..(t+1+Problem[1].delta), <r,i,j,ti,tj,1> in Paths) Dispatch
<r,i,j,ti,tj,1> +
sum(i in CellMembers
<a,t>, j in CellMembers
<a,t>, tj in (t+1-Problem[1].epsilon)..(t+1+Problem[1].delta), <r,i,j,ti,tj,-1> in Paths) Dispatch
<r,i,j,ti,tj,-1><=CellCap
<a,t>;
}
//cell occupancy (transition) constraint including waiting arcs
if(Problem[1].idletransition==1) {forall(<a,t> in CellNet: CellOcc
<a,t>.north+CellOcc
<a,t>.south + CellOcc
<a,t>.wait > CellCap
<a,t>)
sum(i in CellMembers
<a,t>, j in CellMembers
<a,t>, tj in (t+1-Problem[1].epsilon)..(t+1+Problem[1].delta), <r,i,j,ti,tj,1> in Paths) Dispatch
<r,i,j,ti,tj,1> +
sum(i in CellMembers
<a,t>, j in CellMembers
<a,t>, tj in (t+1-Problem[1].epsilon)..(t+1+Problem[1].delta), <r,i,j,ti,tj,-1> in Paths) Dispatch
<r,i,j,ti,tj,-1> +
sum(i in CellMembers
<a,t>, tj in (t+1-Problem[1].epsilon)..(t+1+Problem[1].delta), <r,i,i,ti,tj,d> in Paths) Dispatch
<r,i,i,ti,tj,d> <=CellCap
<a,t>;
}
//northbound headway constraint
//for each constraint, test if trains exist in headway shadow, and then also if total shadow occupancy exceeds capacity
if(Problem[1].headwayoff!=1) {forall(<i,t> in BlockNet: NBOcc
<i,t>.headway>0 && NBOcc
<i,t>.occ+NBOcc
<i,t>.headway>BlockData[i].capacity)
sum(<r,i,j,ti,tj,1> in Paths: t>=ti && t<tj)Dispatch
<r,i,j,ti,tj,1>+
sum(<r,a,i,ti,tj,1> in Paths: TrainData[r].headway>0 && t>=ti && t<tj ) Dispatch
<r,a,i,ti,tj,1> +
sum(<r,a,i,ta,ti,1> in Paths, <r,b,a,tb,ta,1> in Paths: TrainData[r].headway>1 && t>=tb && t<ta ) Dispatch
<r,b,a,tb,ta,1> <=BlockData[i].capacity;
} //
//southbound headway constraint
if(Problem[1].headwayoff!=1) {forall(<i,t> in BlockNet: SBOcc
<i,t>.headway>0 && SBOcc
<i,t>.occ+SBOcc
<i,t>.headway>BlockData[i].capacity)
sum(<r,i,j,ti,tj,-1> in Paths: t>=ti && t<tj)Dispatch
<r,i,j,ti,tj,-1>+
sum(<r,a,i,ti,tj,-1> in Paths: TrainData[r].headway>0 && t>=ti && t<tj) Dispatch
<r,a,i,ti,tj,-1> +
sum(<r,a,i,ta,tj,-1> in Paths, <r,b,a,tb,ta,-1> in Paths: TrainData[r].headway>1 && t>=tb && t<ta) Dispatch
<r,b,a,tb,ta,-1> <=BlockData[i].capacity;
} */
} //end of constraint block
/******************************* Process Results **************************************/
/* tuple solverresult {int solve_code; float obj_value; float obj_bound; int rows; int cols; int time; int problem_id;}
float currBound; int currResult; int currRows; int currCols; int currTime;
{solverresult} ProblemSolution={<currResult, currObj, currBound, currRows, currCols, currTime, Problem[1].problem_id>};
string DeleteSolution; //derived query for deletion of existing solution in database
tuple schedule {int problem_id; int train_num; /*database key rec for train* / int blockseti; int blocksetj; int block_in; int block_to; int time_from; int time_to; int trip_sequence; int tripnum;}
{schedule} TrainSchedule = { <Problem[1].problem_id,r,BlockData[i].keyset, BlockData[j].keyset,i,j,ti,tj,
((TrainData[r].origin==i && TrainPredecessor[r]==0) ? 1 : (j==-1 && TrainData[r].successor==0) ? -1 : 0),
((TrainPredecessor[r]==0) ? r : TrainPredecessor[r])> | <r,i,j,ti,tj,d> in Paths: Dispatch
<r,i,j,ti,tj,d>==1 }; */
float currObj; float newUB; float newgamma; int newlagrprogress; float newtarget;
float lowbound=Problem[1].LB;
float Theta=(currObj-newtarget)/pow(sum(<i,t> in BlockOccupied) BlockSlack
<i,t>,2);
float NewLambdaBlock
<i,t> in BlockOccupied=maxl(0,LambdaBlock
<i,t>+Theta*BlockSlack
<i,t>);
execute { //process Lagrangian result, update stepsize, etc. here
currObj=cplex.getObjValue();
newlagrprogress=lagrprogress+1;
if (currObj<UB) {
newUB=currObj; newgamma=gamma; newlagrprogress=0;
newtarget=((1-newgamma)*newUB) + (newgamma*lowbound);
}
else {
newUB=UB;
if (newlagrprogress>kmax) {
newgamma=gamma/2;
newtarget=((1-newgamma)*newUB) + (newgamma*lowbound);
}
else {
newgamma=gamma; newtarget=target;
}
}
} //end of execute
//End of model
#DecisionOptimization#OPLusingCPLEXOptimizer