CarrierBrokerMappingModel.mos

model CarrierBrokerPathModel
uses "mmxprs"; !gain access to the Xpress-Optimizer solver

options explterm
options noimplicit

uses "mmxprs", "mmsystem";

parameters
	! Data file to read from
	Data = 'data/medium_multi.txt';
	! Minimum proportion of total backup requirement reserved on an arc
	MinBackupProportion = 0.25;
	! Time limit for runtime,  maximum number of seconds for optimisation
	TimeLimit = -1;	
end-parameters

writeln("Model Parameters:");
writeln("Data:", Data);
writeln("MinBackupProportion(beta):", MinBackupProportion);
writeln("TimeLimit:", TimeLimit);

declarations
	timetracker:	real; ! used to log timestamps for time consumption output
end-declarations

writeln("Building model...");
timetracker := timestamp; ! assigns current "timestamp" to timetracker

!setparam("XPRS_presolve", 0);	! uncomment to turn of presolve
if(TimeLimit>0.0) then
	setparam("XPRS_maxtime", TimeLimit);
end-if

setparam("XPRS_verbose", true);	! Turn on message printing
setparam("XPRS_MIPLOG", 1);	! only output summary message in the end of MIP-process 
							!(alternatively use -N for report every Nth node)
!!!!!!!!!!!!!!!!!!!!!!!!
! SETS
!!!!!!!!!!!!!!!!!!!!!!!!

declarations
! Set sizes
	n_Customers: 			integer; ! number of customers
	n_Services:				integer; ! number of services
	n_Nodes:				integer; ! number of nodes in total
	n_Paths:				integer; ! number of paths
	n_Mappings:				integer; ! number of mappings
	
! Sets	
	Customers:				set of integer; 
	! Used as shorthand for 'cc in Customers, ss in S_ServiceForCustomer(cc)' when cc is not needed 
	Services:				set of integer;
	! Set of nodes in the network. 
	! - First we have the customer nodes, then the internal nodes, the the provider nodes.
	Nodes:					set of integer;
	! Set of paths
	Paths:					set of integer; 
	! Set of mappings
	Mappings:				set of integer;
	
end-declarations

initializations from Data
	n_Customers;
	n_Services;
	n_Nodes;
	n_Paths;
	n_Mappings;
end-initializations
	
Customers:= 1..n_Customers;
Services:= 1..n_Services;  
Nodes:= 1..n_Nodes;
Paths := 1..n_Paths;
Mappings := 1..n_Mappings;


finalize(Customers);
finalize(Services);
finalize(Nodes);
finalize(Paths);
finalize(Mappings);

! INDEXED SETS

declarations
	! services of services for customer
	S_ServicesForCustomer:										set of set of integer;
	! Possible mappings for each pair of service and provider
	M_MappingsPerService:		dynamic array(Services)				of set of integer;
	! mappings using path as primary path
	M_PrimaryMappingsPerPath:	dynamic array(Paths)				of set of integer;
	! mappings using path as backup path
	M_BackupMappingsPerPath:	dynamic array(Paths)				of set of integer;
	! set of paths  using each link
	L_PathsUsingArc:			dynamic array(Nodes,Nodes)			of set of integer;
end-declarations

initialisations from Data
	S_ServicesForCustomer;
	M_MappingsPerService;
	M_PrimaryMappingsPerPath;
	M_BackupMappingsPerPath;
	L_PathsUsingArc;
end-initialisations

!!!!!!!!!!!!!!!!!!!!!!!
! PARAMETERS
!!!!!!!!!!!!!!!!!!!!!!!

declarations
	! R_Revenue from serving each customer
	R_Revenue:					dynamic array(Customers)			of real;
	! Bandwidth capacity between each pair of nodes
	F_BandwidthCap:				dynamic array(Nodes,Nodes)			of real;
	! bandwidth usage for path
	U_PathBandwidthUsage:		dynamic array(Nodes,Nodes,Paths)	of real;
	! cost of using path k
	C_PathCost:					dynamic array(Paths)				of real;
	! cost per bandwidth used for backup paths on arc
	C_BackupCost:				dynamic array(Nodes,Nodes)			of real;
	! backup bandwith usage on arc ii,jj with mapping mm
	Q_BackupReservation:		dynamic array(Nodes,Nodes,Mappings) of real;
end-declarations

initialisations from Data	
	R_Revenue;
	F_BandwidthCap;
	U_PathBandwidthUsage;
	C_PathCost;
	C_BackupCost;
end-initialisations


forall(mm in Mappings) do
	forall(ii in Nodes, jj in Nodes | exists(L_PathsUsingArc(ii,jj))) do
		Q_BackupReservation(ii,jj,mm) := maxlist(
			0,
			sum(kk in L_PathsUsingArc(ii,jj)) (
				sum(nn in M_BackupMappingsPerPath(kk) | nn = mm)(
					U_PathBandwidthUsage(ii,jj,kk)
				)
			)
			-
			sum(kk in L_PathsUsingArc(ii,jj))(
				sum(nn in M_PrimaryMappingsPerPath(kk) | nn = mm)(
					U_PathBandwidthUsage(ii,jj,kk)
				)
			)
		);
	end-do
end-do

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
! VARIABLES
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

declarations	
	!Variables
	! - y: binary, serving of a customer
	y_Serve:			dynamic array (Customers)					of mpvar;
	! - u: binary, indicates which paths are used
	w_UseMapping:		dynamic array (Mappings)					of mpvar; 
	! - lambda: continous, amount of capacity reserved on a link for backup
	l_Lambda:			dynamic array(Nodes,Nodes)					of mpvar;
	! - l: binary, indicates if two services' primary paths overlap
	l_Overlap:			dynamic array(Services,Services)			of mpvar;
end-declarations

! - for all customers
forall(cc in Customers) do
	create(y_Serve(cc));
	y_Serve(cc) is_binary;
end-do

forall(mm in Mappings) do
	create(w_UseMapping(mm));
	w_UseMapping(mm) is_binary;
end-do

forall (ii in Nodes, jj in Nodes | exists(F_BandwidthCap(ii,jj))) do
	create(l_Lambda(ii,jj));
end-do

forall (ss in Services, tt in Services | ss < tt) do
	create(l_Overlap(ss,tt));
	l_Overlap(ss,tt) is_binary;
end-do

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
! CONSTRAINTS
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

declarations
! Objective function
	Total_Profits:															linctr;

! Constraints
	AllocateMapping:		dynamic array(Services)							of linctr;
	ArcCapacity:			dynamic array(Nodes,Nodes)						of linctr;
	SumBackupLimit:			dynamic array(Nodes,Nodes)						of linctr;
	SingleBackupLimit:		dynamic array(Nodes,Nodes,Services)				of linctr;
	BackupOverlap:			dynamic array(Nodes,Nodes,Services, Services)	of linctr;
	PrimaryOverlap:			dynamic array(Nodes,Nodes,Services, Services)	of linctr;
end-declarations

write(" - obj. fn. ..");	

! OBJECTIVE FUNCTION
! - total profits from serving customers
Total_Profits := sum (cc in Customers) (
			! R_Revenue from any served customers
			R_Revenue(cc)*y_Serve(cc)
		)
		- 
		! for all paths
		sum(kk in Paths) (
			! cost of using path as primary
			C_PathCost(kk)
			! for all mappings using path as primary
			sum(mm in M_PrimaryMappingsPerPath(kk)) (
				w_UseMapping(mm)
			)
		)
		-
		! for each arc
		sum(ii in Nodes, jj in Nodes | exists(F_BandwidthCap(ii,jj)))(
			! costs for bandwidth reserved for backup
			C_BackupCost(ii, jj)*l_Lambda(ii, jj)
	);

write("DONE\n - use path cnstr. ..");	

! ALLOCATE MAPPING CONSTRAINTS
! All services of a customer that is to be served must be allocated one mapping
forall(cc in Customers) do
	forall(ss in S_ServicesForCustomer(cc) | exists(M_MappingsPerService(ss))) do
		AllocateMapping(ss) := y_Serve(cc) - sum(kk in M_MappingsPerService(ss)) w_UseMapping(kk) = 0.0;
	end-do
end-do

write("DONE\n - arc cap cnstr. ..");	

! ARC CAPACITY CONSTRAINT
! The total used bandwidth for primary paths and reserved for backup paths must not exceed the
! arcs capacity
forall(ii in Nodes, jj in Nodes | exists(L_PathsUsingArc(ii,jj))) do
	ArcCapacity(ii,jj) := 
		! for each path using link
		sum(kk in L_PathsUsingArc(ii,jj) | exists(M_PrimaryMappingsPerPath(kk))) (
			! add bw req for path for each mapping using path being used
			U_PathBandwidthUsage(ii,jj,kk)
			*
			(
				sum(mm in M_PrimaryMappingsPerPath(kk))w_UseMapping(mm)
			)
		)
		! add bandwidth reserved for backup paths on arc
		+ l_Lambda(ii,jj) 
		<= F_BandwidthCap(ii,jj);
end-do

write("DONE\n - backup path bw use cnstr. 1 ..");

! MIN BACKUP PATH BANDWIDTH CONSTRAINT
! bandwidth reserved for backup paths must be at least as high as the bandwidth required by the
! the most demaning single service
forall(ii in Nodes, jj in Nodes | exists(L_PathsUsingArc(ii,jj))) do
	forall (ss in Services) do
		SingleBackupLimit(ii,jj,ss) := (
			! for all mappings of service
			sum(mm in M_MappingsPerService(ss))(
				Q_BackupReservation(ii,jj,mm)*w_UseMapping(mm)
			) 
			-
			l_Lambda(ii,jj)
			<= 0
		);
	end-do
end-do

writeln("DONE\n - service and backup overlap cnstrs.");

! ACCUMULATIVE BACKUP PATHS BANDWIDTH CONSTRAINTS
! bandwidth reserved for backup paths on an arc is at least a fraction of the total bandwidth of all
! backup paths using that arc
forall(ii in Nodes, jj in Nodes | exists(L_PathsUsingArc(ii,jj))) do
	SumBackupLimit(ii,jj) := (
		MinBackupProportion
		*
		sum(mm in Mappings) ( ! for all mappings
			Q_BackupReservation(ii,jj,mm)
			*w_UseMapping(mm)
		)
		-
		l_Lambda(ii,jj)
		<= 0
	);
end-do

write("DONE\n - backup path bw use cnstr. 2 ..");

! - for every distinct pair of services
forall(ss in Services, tt in Services | ss < tt) do
	writeln("  - service pair: ", ss, ", ", tt);
	! - for every arc in network (with paths using it)
	forall(ii in Nodes, jj in Nodes | exists(L_PathsUsingArc(ii,jj))) do
	
		! only for evey link (ii < jj) (failured happen at link level -> failing both arcs)
		if(ii < jj) then
		
			! SERVICE PATH OVERLAP CONSTRAINTS
			! Two services have overlapping primary paths if for any LINK both paths are represented
			PrimaryOverlap(ii,jj,ss,tt):=
				sum(kk in L_PathsUsingArc(ii,jj))(
					sum(mm in M_MappingsPerService(ss)*M_PrimaryMappingsPerPath(kk))(
						w_UseMapping(mm)
					)
				)
				+
				sum(kk in L_PathsUsingArc(ii,jj))(
					sum(mm in M_MappingsPerService(tt)*M_PrimaryMappingsPerPath(kk))(
						w_UseMapping(mm)
					)
				)
				-
				l_Overlap(ss, tt)
				<= 1;
			
		end-if
		
		! BACKUP PATH OVERLAP CONSTRAINT
		! backup paths may not overlap at an ARC if their primary paths overlap at any LINK
		! - backup bandwidth collisions happen at arc level (may not need bandwidth in both directions)
		BackupOverlap(ii,jj,ss,tt):= 
			sum(kk in L_PathsUsingArc(ii,jj))(
				sum(mm in M_MappingsPerService(ss)*M_BackupMappingsPerPath(kk) 
					| (Q_BackupReservation(ii,jj,mm) + Q_BackupReservation(jj,ii,mm)) > 0)(
					w_UseMapping(mm)
				)
			)
			+
			sum(kk in L_PathsUsingArc(ii,jj))(
				sum(mm in M_MappingsPerService(tt)*M_BackupMappingsPerPath(kk)
					| (Q_BackupReservation(ii,jj,mm) + Q_BackupReservation(jj,ii,mm)) > 0)(
					w_UseMapping(mm)
				)
			)
			+
			l_Overlap(ss, tt)
			<= 2;
	end-do
end-do

writeln("  - DONE");

writeln("\nModel building completed in ", timestamp - timetracker, " seconds");

writeln("\nSolving model...");
timetracker := timestamp;
maximize(Total_Profits);

if (getprobstat=XPRS_OPT) then
	writeln("\nModel solved in ", timestamp - timetracker," seconds");
else
	writeln("\nModel was not solved after ", timestamp - timetracker," seconds");
end-if

writeln("\nTotal Profits: ", getobjval);

writeln("\nTotal Backup Costs: ", sum(nn in Nodes)(sum(mm in Nodes)(C_BackupCost(nn, mm)*getsol(l_Lambda(nn, mm)))));

! for all customers

forall(cc in Customers) do
	! Check if customer is served
	if (getsol(y_Serve(cc)) > 0.1) then
		! output served customer and generated profits for customer
		writeln(
			"\nCustomer ", cc, " (node ",cc,") is being served\n - R_Revenue: ",
			R_Revenue(cc)*getsol(y_Serve(cc))
		);
		forall(ss in S_ServicesForCustomer(cc)) do
			forall(mm in M_MappingsPerService(ss)) do
				if (getsol(w_UseMapping(mm)) > 0.1) then
					writeln("  - Service ",ss," uses mapping ",mm);
					forall(kk in Paths) do
						forall(jj in M_PrimaryMappingsPerPath(kk) | jj = mm) do
							writeln("   - Primary path: ", kk, ", cost: ", C_PathCost(kk));
						end-do
					end-do
					forall(kk in Paths) do
						forall(jj in M_BackupMappingsPerPath(kk) | jj = mm) do
							writeln("   - Backup path: ", kk);
						end-do
					end-do
				end-if
			end-do
		end-do
	end-if
end-do

writeln("\nTotal backup usage");
writeln(
	strfmt("arc ",10), 
	strfmt("reserved",10),
	strfmt("max req",10),
	strfmt("sum reqs*",10),
	strfmt("cost/bw",10),
	strfmt("paths",10)
);

declarations
	temp: real;
end-declarations

forall(ii in Nodes, jj in Nodes | exists(L_PathsUsingArc(ii,jj))) do
	temp := 0.0;
	forall(cc in Customers) do
		forall(ss in S_ServicesForCustomer(cc) | exists(M_MappingsPerService(ss))) do
			if(sum(kk in L_PathsUsingArc(ii,jj))(
					U_PathBandwidthUsage(ii,jj,kk)
					* sum(mm in M_BackupMappingsPerPath(kk)*M_MappingsPerService(ss))getsol(w_UseMapping(mm))
					-
					U_PathBandwidthUsage(ii,jj,kk)
					* sum(mm in M_PrimaryMappingsPerPath(kk)*M_MappingsPerService(ss))getsol(w_UseMapping(mm))		
				) > temp) then
				temp := (
					sum(kk in L_PathsUsingArc(ii,jj))(
						U_PathBandwidthUsage(ii,jj,kk)
						* sum(mm in M_BackupMappingsPerPath(kk)*M_MappingsPerService(ss))getsol(w_UseMapping(mm))
						-
						U_PathBandwidthUsage(ii,jj,kk)
						* sum(mm in M_PrimaryMappingsPerPath(kk)*M_MappingsPerService(ss))getsol(w_UseMapping(mm))
					)
				);
			end-if
		end-do
	end-do
	if(getsol(l_Lambda(ii,jj)) > 0.001) then
		write(
			strfmt("("+ ii+ ", "+ jj+ ")",10),
			strfmt(+getsol(l_Lambda(ii,jj)), 10),
			strfmt(temp, 10),
			strfmt(sum(kk in L_PathsUsingArc(ii,jj)) (
				! add bw req for path for each mapping using path being used
				U_PathBandwidthUsage(ii,jj,kk)
				*(sum(mm in M_PrimaryMappingsPerPath(kk))getsol(w_UseMapping(mm)))
			), 10),
			strfmt(C_BackupCost(ii,jj), 10),
			"     "
		);
		forall(kk in L_PathsUsingArc(ii,jj)) do
			forall(mm in M_BackupMappingsPerPath(kk) | getsol(w_UseMapping(mm)) > 0.001) do
				write(kk, ", ");
			end-do
		end-do
		write("\n");
	end-if
end-do

end-model