Network Capacity Planning

Problem Description

Put description here.

Test Problems

Here are the data sets used in simulation. Each data file contains N: sample size in the main loop, N1: sample size used in estimating reliability at the end, K: number of samples used in estimation, a: initial parameter vector, c: link costs, p: link reliabilities, and Cmax: total budget.

Problem 1
Parameter values used in simulation.

$n$	6	$N$	300	$N_1$	1000	$K$	50
$C_{\max}$	1	$\varrho$	0.1	$\alpha$	0.7	$\beta$	0.02

The following table shows the cost, reliability and initial purchase probability of each link.

link	$c_i$	$p_i$	$a_i$	link	$c_i$	$p_i$	$a_i$	link	$c_i$	$p_i$	$a_i$
1	0.26104	0.65403	0.5	6	0.25338	0.68058	0.5	11	0.29296	0.67635	0.5
2	0.28815	0.64780	0.5	7	0.20307	0.65316	0.5	12	0.28077	0.66468	0.5
3	0.20209	0.65180	0.5	8	0.23228	0.66519	0.5	13	0.20881	0.61881	0.5
4	0.20573	0.69176	0.5	9	0.24805	0.61017	0.5	14	0.26406	0.68385	0.5
5	1.30000	0.63323	0.5	10	0.22233	0.63467	0.5	15	0.26160	0.68489	0.5

All the parameter values and vectors are stored in testproblem1.mat.

The table below presents the results of the CE method based on 10 independent reprications.

Inputs:
Rep	-	replication counter
$T$	-	final iteration counter
$\widehat{r^*}$	-	estimated network reliability
RE	-	relative error
CPU	-	CPU time in seconds
pn	-	purchase number

Rep	$T$	$\widehat{r^*}$	RE	CPU	pn
1	7	0.70106	0.02065	18.566	6147
2	7	0.69498	0.02095	19.498	6147
3	6	0.68634	0.02138	15.312	6147
4	7	0.70094	0.02066	19.568	6147
5	7	0.69642	0.02088	20.239	6147
6	8	0.70142	0.02063	22.913	6147
7	6	0.68194	0.02160	16.204	6147
8	7	0.69536	0.02093	20.479	6147
9	8	0.70546	0.02043	23.293	6147
10	7	0.69894	0.02075	19.909	6147

The graphical representation of the network with purchase number 6147 is given in Figure 1.

Figure 1: The graphical representation of the optimal network for test problems 1 and 2.

Problem 2
This problem is similar to the first test problem.

The table shown below presents the results obtained using the CE method.

Rep	$T$	$\widehat{r^*}$	RE	CPU	pn
1	11	0.99162	0.00291	33.728	6147
2	9	0.99110	0.00300	26.358	6147
3	8	0.98928	0.00329	23.183	6147
4	7	0.98808	0.00347	18.497	6147
5	6	0.98876	0.00337	18.166	6147
6	7	0.98806	0.00348	18.226	6147
7	8	0.98908	0.00332	25.917	6147
8	9	0.98778	0.00352	29.773	6147
9	9	0.98984	0.00320	27.840	6147
10	8	0.98834	0.00343	24.164	6147

The true optimal reliabilty is 0.99233. The graphical representation of the optimal network is given in Figure 1.

Problem 3
The following is the list of CE parameter values used in simulation.

$n$	10	$N$	1000	$N_1$	1000	$K$	50
$C_{\max}$	2	$\varrho$	0.1	$\alpha$	0.7	$\beta$	0.02

The following table shows the cost and reliability of each link.

link	$c_i$	$p_i$	$a_i$	link	$c_i$	$p_i$	$a_i$	link	$c_i$	$p_i$	$a_i$
1	0.22208	0.45412	0.50	16	0.20807	0.48370	0.50	31	0.25918	0.42205	0.50
2	0.27631	0.40680	0.50	17	0.19559	0.47005	0.50	32	0.22657	0.44544	0.50
3	0.10417	0.45821	0.50	18	0.20361	0.44661	0.50	33	0.20031	0.49043	0.50
4	0.11146	0.44887	0.50	19	0.28353	0.49186	0.50	34	0.29759	0.41516	0.50
5	0.25829	0.42546	0.50	20	0.16646	0.49376	0.50	35	0.20339	0.47594	0.50
6	0.20676	0.48908	0.50	21	0.26115	0.44104	0.50	36	0.28987	0.42078	0.50
7	0.10614	0.49081	0.50	22	0.20632	0.49483	0.50	37	0.13698	0.46095	0.50
8	0.16457	0.40702	0.50	23	0.23037	0.46965	0.50	38	0.16299	0.45416	0.50
9	2.30000	0.48615	0.50	24	0.12034	0.47508	0.50	39	0.11693	0.40779	0.50
10	0.14465	0.45516	0.50	25	0.16935	0.45356	0.50	40	0.10794	0.48412	0.50
11	0.28593	0.47752	0.50	26	0.25270	0.46119	0.50	41	0.10861	0.48570	0.50
12	0.26154	0.40283	0.50	27	0.22935	0.40642	0.50	42	0.14394	0.44254	0.50
13	0.11763	0.40379	0.50	28	0.13762	0.46445	0.50	43	0.12103	0.44023	0.50
14	0.22813	0.41422	0.50	29	0.26770	0.45563	0.50	44	0.23937	0.44088	0.50
15	0.22321	0.40577	0.50	30	0.26978	0.44106	0.50	45	0.28127	0.41284	0.50

The numerical results obtained using the CE method is given in the table below.

Rep	$T$	$\widehat{r^*}$	RE	CPU	pn
1	25	0.72614	0.01942	702.906	25014158001194
2	59	0.71982	0.01973	1642.578	16217798640682
3	36	0.72638	0.01941	1022.094	25014158001194
4	21	0.72336	0.01956	599.297	25014158001194
5	30	0.71998	0.01972	853.578	16217798640682
6	28	0.72606	0.01942	789.500	25014158001194
7	29	0.71748	0.01984	819.437	16217798640682
8	94	0.72602	0.01943	2651.719	7421703656490
9	24	0.72772	0.01934	722.172	25014158001194
10	78	0.72328	0.01956	2509.813	7421703656490

The optimal network reliability is 0.726429. The graphical representation of the optimal network is given in Figure 2.

Figure 2: The graphical representation of the optimal network for test problems 3 and 4.

testproblem3.mat

Programs

ncp.m
This programs optimizes finds the best possible, that is most reliable, network subject to the constraint on total budget.

Usage:

Call the program from MATLAB, with the following syntax:

ncp('file')

where file is the name of the data file given above. Alternatively, if you wish to change the parameter values, open ncp.m in command window and make necessary changes. After changes have been made, call the program from MATLAB, with the following syntax:

ncp

vect2mat.m - This program converts a 1 x m vector into n x n matrix where m= n(n-1)/2.

uniperm.m - This program is used internally to generate a random purchase vector using uniform permutation.

estrel1.m - This program is used internally to estimate the reliability of the network.

structure.m - This program is used internally to compute the structure function value.

network.m - This program is used internally to plot the best possible network obtained via simulation.

uniformrand.m - This program is used internally to generate a random vector from uniform distribution.

If you have any questions/suggestions/improvements regarding this problem and/or Matlab programs, please email to Sho Nariai.