# p-cycle SCP IP Model for AMPL - Version 1.0
# 11-December-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 p-cycle network design. 
# This model optimizes p-cycles only... working capacity is provided as inputs.

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



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

set SPANS;
# Set of all spans.

set PCYCLES;
# Set of all p-cycles.


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

param Cost{j in SPANS};
# Cost of each unit of capacity on span j.

param Work{j in SPANS};
# Number of working links placed on span j.

param Xpi{p in PCYCLES, i in SPANS} default 0;
# Number of paths a single copy of p-cycle p provides for restoration of failure of
# span i (2 if straddling span, 1 if on-cycle span, 0 otherwise).

param pCrossesj{p in PCYCLES, j in SPANS} := sum{i in SPANS: i = j and Xpi[p,j] = 1} 1;
# Equal to 1 if p-cycle p passes over span j, 0 otherwise.
# i.e. if Xpi[p,j] = 1, then p-cycle p crosses span j.


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

var p_cycle_usage{p in PCYCLES} >=0 integer, <=10000;
# Number of copies of p-cycle p used.

var spare{j in SPANS} >=0 integer, <=10000;
# Number of spare links placed on span j.


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

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


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

subject to full_restoration{i in SPANS}: 
Work[i] <= sum{p in PCYCLES} Xpi[p,i] * p_cycle_usage[p];

subject to spare_capacity_placement{j in SPANS}:
spare[j] = sum{p in PCYCLES} pCrossesj[p,j] * p_cycle_usage[p];