# Joint Modular Span-Restorable Meta-Mesh Model With Chain Bypass Spans
# 27 July 2001 by Wayne D. Grover and 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 model is designed to jointly place working and spare capacity on a 
# (sparsely connected) network with chain bypass spans added to provide a 
# glass-through route through a chain for non-local traffic to use.  The 
# arc-path approach is used.



# ************************
# SETS
# ************************

set SPANS;
	# set of all spans
set DIRECT_SPANS;
	# set of spans that are not bypassed (i.e. not a part of any bypassed chain)
set BYPASS_SPANS;
	# set of spans that act as bypasses for chains
set CHAIN_SPANS := {SPANS diff (DIRECT_SPANS union BYPASS_SPANS)};

set REST_ROUTES{i in SPANS};
	# set of all restoration paths for each span failure i
set DEMANDS;
 	# set of all demand pairs or node pairs
set WORK_ROUTES{r in DEMANDS};
	# set of all working routes for each demand pair r


# ************************
# PARAMETERS
# ************************

param Bypass{i in CHAIN_SPANS} symbolic;

param Cost{j in SPANS} default 1;
# cost of a unit of capacity on span j

param DemandUnits{r in DEMANDS} default 0;
# number of demand units between node pair r

param DeltaRestRoutes{i in SPANS, j in SPANS, p in REST_ROUTES[i]} default 0;	
# equal to 1 if pth restoration route for failure of span i uses span j and 0 otherwise

param ZetaWorkRoutes{j in SPANS, r in DEMANDS, q in WORK_ROUTES[r]} default 0;
# equal to 1 if qth working route for demand between node pair r uses span j and 0 otherwise


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

var gwrkflow{r in DEMANDS, q in WORK_ROUTES[r]} >=0, <=10000;
# working capacity required by qth working route for demand between node pair r

var flowrest{i in SPANS, p in REST_ROUTES[i]} >=0, <=10000;
# restoration flow through pth restoration route for failure of span i

var work{j in SPANS} >=0, <=100000 integer;
# number of working links placed on span j

var spare{j in SPANS} >=0, <=100000 integer;
# number of spare links place on span j


# OBJECTIVE FUNCTION
minimize totcost: sum{j in SPANS} Cost[j] * (spare[j] + work[j]);


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

subject to restn1{i in DIRECT_SPANS}: 
sum{p in REST_ROUTES[i]} flowrest[i,p] = work[i];

subject to restn2{i in CHAIN_SPANS, k in BYPASS_SPANS: k=Bypass[i]}: 
sum{p in REST_ROUTES[i]: DeltaRestRoutes[i,k,p] = 0} flowrest[i,p] = work[i];

subject to restn3{i in CHAIN_SPANS, k in BYPASS_SPANS: k=Bypass[i]}: 
sum{p in REST_ROUTES[k]: DeltaRestRoutes[k,i,p] = 0} flowrest[k,p] = work[k];

subject to sparasst1{i in DIRECT_SPANS, j in SPANS: i <> j }:
spare[j] >= sum{p in REST_ROUTES[i]} DeltaRestRoutes[i,j,p] * flowrest[i,p];

subject to sparasst2{i in CHAIN_SPANS, j in SPANS, k in BYPASS_SPANS: i <> j <> k and k=Bypass[i]}:
spare[j] >= sum{p in REST_ROUTES[i]} DeltaRestRoutes[i,j,p] * flowrest[i,p] + 
sum{p in REST_ROUTES[k]} DeltaRestRoutes[k,j,p] * flowrest[k,p];

subject to demmet{r in DEMANDS}:
sum{q in WORK_ROUTES[r]} gwrkflow[r,q] = DemandUnits[r];

subject to workasst{j in SPANS}:
work[j] = sum{r in DEMANDS, q in WORK_ROUTES[r]} ZetaWorkRoutes[j,r,q] * gwrkflow[r,q];