# PathSCP-arc-path IP model for AMPL - version 1.1 
# 5-September-2000 by John Doucette and Wayne D. Grover
# Copyright (C) 2000 TRLabs, Inc. All Rights Reserved.

# ********************************************************

# TRLabs
# 7th Floor 
# 9107 116 Street NW
# Edmonton, Alberta, Canada
# T6G 2V4

# +1 780 441-3800
# www.trlabs.ca

# ********************************************************

# This model, including any data and algorithms contained herein, is the
# exclusive property of TRLabs, held on behalf of its sponsors. Except
# as specifically authorized in writing by TRLabs, the recipient of this
# model shall keep it confidential and shall protect it in whole or
# in part from disclosure and dissementation to all third parties.

# If any part of this model, including any data and algorithms contained
# herein, is used in any derivative works or publications, TRLabs shall be
# duly cited as a reference.

# TRlabs makes no representation or warranties about the suitability of
# this model, either express or implied, including but not limited to
# implied warranties of merchantability, fitness for a particular purpose,
# or non-infringement. TRLabs shall not be liable for any damages suffered
# as a result of using, modifying or distributing this model or its
# derivatives.



# This is an AMPL model for PATH-RESTORABLE SPARE CAPACITY DESIGN using
# the arc-path approach on an already determined working path routing.

# An AMPL data file to accompany this model can be generated using
# PathSCP-arc-path-datfile-preparation.exe, software written in C.
# See the readme file for more information 
# (readme.txt or PathSCP-arc-path-datfile-preparation.txt).

# Explicit route representations for working paths are given as inputs
# (not variables) and a set of eligible restoration routes are given for each
# demand pair for restoration. 

# Working traffic routing (assumed to be shortest path) allows demand 
# splitting.  If a span failure affects only one of several working paths
# for a specific demand, the surviving working paths remain and only the
# affected working path is dropped and restored.

# Stub release is performed on surviving spans of an effected working path
# such that the working capacity they carry is released and allowed to be
# re-used as spare capacity if the restoration mechanism re-routes over some
# of those same surviving spans.

# A given span cut is first transformed into the O-D relations affected 
# and hence into the overall pattern of O-D pairs affected, with a restoration
# magnitude associated with each. 

# From that point on we view the problem as a flow assignment to 
# eligible restoration routes on a path replacement basis for each affected 
# O-D pair. Eligible restoration routes are excluded if they 
# cross the failure span. In addition spare span quantities will get
# the benefit of a "stub release" credit. 



# ************************
# TOPOLOGY DEFINITION
# ************************

set SPANS;	
# Set of all physical spans in the network (no chain reductions used here).

set DEMAND_PAIRS;
# Set of all demands that exist. Will contains only those non-zero members as read in from dat file

param span{SPANS} symbolic;
# Whereas the SET SPANS is an indexing of spans that exist, span[j] is the actual NAME of the jth span in the set.

param Cost{j in SPANS};
# The cost of a unit of working or spare capacity on span j.


# ************************
# DESCRIPTION OF WORKING DEMANDS AND THEIR NORMAL ROUTING
# ************************

param DemUnits{r in DEMAND_PAIRS} default 0;
# Number of demand units between node pair r.

set WORK_ROUTES{r in DEMAND_PAIRS};
set WORK_ROUTE_VECTORS{r in DEMAND_PAIRS, p in WORK_ROUTES[r]} within {j in SPANS};
param Work_Route_Vectors{r in DEMAND_PAIRS, p in WORK_ROUTES[r], j in WORK_ROUTE_VECTORS[r,p]} symbolic;	

# N.B. Everywhere in this model a route is specified as a sequence of the names of spans that 
# comprise the route. This is a more compact form that replaces the prior encoding of routes by 1 / 0 representation
# of membership in the route for every span of the network


# ************************
# FAILURE SCENARIO DEFINITIONS
# ************************

set DEMANDS_AFFECTED{i in SPANS} 
:= {r in DEMAND_PAIRS : exists {p in WORK_ROUTES[r], j in WORK_ROUTE_VECTORS[r,p]} Work_Route_Vectors[r,p,j] = span[i] };
# This builds a set of the demand pairs that are damaged by each possible span failure i  

set WORK_ROUTES_AFFECTED{i in SPANS, r in DEMANDS_AFFECTED[i]} 
:= {p in WORK_ROUTES[r] : exists {j in WORK_ROUTE_VECTORS[r,p]} Work_Route_Vectors[r,p,j] = span[i] };
# This generates the list of working routes affected by failure of span i.

param Stub_release {i in SPANS, r in DEMANDS_AFFECTED[i], j in SPANS: span[i] <> span[j]}
:= sum {p in WORK_ROUTES_AFFECTED[i,r]: exists {k in WORK_ROUTE_VECTORS[r,p]} Work_Route_Vectors[r,p,k] = span[j] } 
DemUnits[r] / card{WORK_ROUTES[r]} * card{WORK_ROUTES_AFFECTED[i,r]: exists {k in WORK_ROUTE_VECTORS[r,p]} Work_Route_Vectors[r,p,k] = span[j]} ;
# Stub_release[r,i,j] is the amount of surviving working capacity on span[j] that is in a stub of a working route severed
# by failure of span [i]



# ************************
# ELIGIBLE ROUTES FOR PATH-LEVEL RESTORATION OF O-D PAIRS
# ************************

set REST_ROUTES{r in DEMAND_PAIRS};
set REST_ROUTE_VECTORS{r in DEMAND_PAIRS, p in REST_ROUTES[r]} within {j in SPANS};
param Rest_Route_Vectors{r in DEMAND_PAIRS, p in REST_ROUTES[r], j in REST_ROUTE_VECTORS[r,p]} symbolic;

# There is one set of restoration routes, indexed within each set by dummy variable p, for each r. (r,p) is subsequently
# used directly as a tuple so that AMPL will index over only the (r, p) combinations actually presented in the data file.
# The DAT file will present params Rest_routes[r,p,j] which will be for each relation r, a set of horizontal lists
# numbered locally by p, each list being a of vectors of span names that are included in the pth eligible route for 
# relation r. 


# ************************
# VARIABLES
# ************************

var rest_flow {i in SPANS, r in DEMANDS_AFFECTED[i], p in REST_ROUTES[r], q in WORK_ROUTES_AFFECTED[i,r]} >=0, <=10000;
# There is one restoration flow assignment variable for each REST_ROUTES with regard to
# each possible failure scenario (i in SPANS)
 
var spare{j in SPANS} >=0, <=10000 integer;
# Total number of spare links placed on span j.



# ************************
# OBJECTIVE FUNCTION
# ************************

minimize cost_of_mesh_sparing: sum{j in SPANS} spare[j]* Cost[j];



# ************************
# CONSTRAINTS
# ************************

subject to path_restorability {i in SPANS, r in DEMANDS_AFFECTED[i], q in WORK_ROUTES_AFFECTED[i,r]}:
sum{p in REST_ROUTES[r]: forall {j in REST_ROUTE_VECTORS[r,p]} Rest_Route_Vectors[r,p,j] <> span[i]} 
rest_flow[i,r,p,q] = DemUnits[r] / card{WORK_ROUTES[r]};
# For each span failure i, all demand pairs affected by the cut must be restorable
# through restoration flow assignments to eligible routes for those relations, such routes not
# containing the failure span i themselves.

subject to spare_capacity {i in SPANS, j in SPANS: span[i] <> span[j]}: 
spare[j] >= sum {r in DEMANDS_AFFECTED[i], p in REST_ROUTES[r], q in WORK_ROUTES_AFFECTED[i,r]: 
exists {k in REST_ROUTE_VECTORS[r,p]} Rest_Route_Vectors[r,p,k] = span[j]} 
rest_flow[i,r,p,q] - sum {r in DEMANDS_AFFECTED[i]} Stub_release[i,r,j];
# Sufficient spare capacity must be placed on each span j to carry the restoration flows assigned
# in the previous constraint set.