# Shared Backup Path Protection SCP IP Model for AMPL - Version 1.0
# 6-June-2001 by John Doucette
# Copyright (C) 2001 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 determining the minimum-cost shared backup path
# protection mesh transport network design. 
# This model optimizes protection paths only... primary working paths are
# provided as inputs (equivalent to SCP).

# Each demand is routed over a single (short) working route and upon failure
# of a span on that route, that demand is restored end-to-end on a backup
# route that is span-disjoint from the original working route.  Spare
# capacity can be shared amongst multiple backup paths (so long as those
# backup paths are not simultaneously being used).


#****************************
# TOPOLOGY AND DEMAND DEFINITION
#****************************

set SPANS;
# Set of all physical spans in the network.

param Span{SPANS} symbolic;
# Where the Set SPANS is an indexing of spans that exist, span[j] is the
# actual NAME of the jth span in the set.  We structure it this way so that
# we can more easily identify spans and use them in logical statements (such
# as automatically building sets of demands affected by each span failure).

param Cost{j in SPANS} default 1;
# Cost of each spare link placed on span j.
# If no cost data is provided, it is assumed that we simply wish to minimize
# total number of links and so all costs are 1.

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

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


#****************************
# ROUTE DESCRIPTIONS
#****************************

set ROUTES{d in DEMANDS};
# Set of all eligible routes that can be used for each demand.

set ROUTE_VECTORS{d in DEMANDS, p in ROUTES[d]} within {j in SPANS};
# The sets of spans crossed by each of the above eligible routes.

param Route_Vectors{d in DEMANDS, p in ROUTES[d], j in ROUTE_VECTORS[d,p]} symbolic;
# The names of the spans in the above sets of spans crossing routes.

# Note: Throughout 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

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

param primary_flow {d in DEMANDS, p in ROUTES[d]} default 0;
# Equal to 1 if the primary working path for demand d is over route p, 0 otherwise.


#****************************
# FAILURE SCENARIO DEFINITION
#****************************

set ROUTES_CROSSING_SPANS{i in SPANS, d in DEMANDS} 
:= {p in ROUTES[d] : exists {k in ROUTE_VECTORS[d,p]} Route_Vectors[d,p,k] = Span[i] };
# This generates the lists of routes for demand d which cross span i.


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

var backup_flow {d in DEMANDS, b in ROUTES[d]} >=0, <=1 integer;
# Equal to 1 if the backup path for demand d is over route b, 0 otherwise.

var backup_capacity {j in SPANS} >=0, <=10000 integer;
# Total number of links of capacity placed on span j for use by backup paths.


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

minimize backup_capacity_cost: 
sum{j in SPANS} backup_capacity[j] * Cost[j];


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

subject to one_backup_path {d in DEMANDS}:
sum{b in ROUTES[d]} backup_flow[d,b] = 1;
# For each demand d, there must be one and only one backup path.
# This constraint is redundant since the path_protection constraint in combination
# with the capacity_placement constraint and the objective of minimizing total
# capacity cost, no demand should have more than a single backup path.
# That said, we add this constraint anyway in hopes that the IP will more directly
# restrict this and shorten solution time.

subject to primary_not_backup {d in DEMANDS, p in ROUTES[d]: primary_flow[d,p]=1}:
backup_flow[d,p] = 0;
# If a route is the primary path, then it cannot be the backup path.

subject to path_protection {i in SPANS, d in DEMANDS, p in ROUTES_CROSSING_SPANS[i,d]}:
sum{b in ROUTES[d]: forall {j in ROUTE_VECTORS[d,b]} Route_Vectors[d,b,j] <> Span[i]} 
backup_flow[d,b] >= primary_flow[d,p];
# For each route p for demand d that is affected by span failure i, there must be
# a backup route b not crossing that failed span if route p is used as a primary
# path (i.e. if primary_flow[d,p] = 1).  If route p is not used as a primary path
# (i.e. primary_flow[d,p] = 0), then there doesn't have to be a backup route b
# that doesn't cross that failed span.
# Note that greater than or equal to is used because the backup route b for demand d
# must be allowed to not cross the failed span even if route p is not used as the
# primary route (i.e. backup_flow[d,b] = 1 > 0).

subject to backup_capacity_placement {i in SPANS, j in SPANS: i <> j}: 
sum {d in DEMANDS, b in ROUTES_CROSSING_SPANS[j,d], p in ROUTES_CROSSING_SPANS[i,d]:
forall {k in ROUTE_VECTORS[d,p], l in ROUTE_VECTORS[d,b]} k <> l } 
primary_flow[d,p] * backup_flow[d,b] * DemUnits[d] <= backup_capacity[j];
# For failure of span i, we must place enough backup capacity on span j to
# simultaneously accomodate those demands using a primary path p (i.e. primary_flow[d,p] = 1)
# where the primary path p crosses failed span i AND using a backup path b (i.e.
# backup_flow[d,b] = 1) where the backup path crosses span j.
# Note that if route p is not the primary path, then primary_flow[d,p] = 0, so
# we require 0 backup capacity for span j.  Similarly is route b is not the backup
# path.