Test Instance Generation | Format of the Benchmark Sets |
A Function Reading the Input |
DOWNLOAD
To achieve scenarios of relevance for the real life application, each
set of instances is generated by specifying the time horizon (720
Minutes and 1440 Minutes) and the number of channels (20 and 50). The
generator sequentially fills the channels by starting each new program
one minute after the last. For each new program a class is
being chosen randomly. That class then determines the interval from
which the length is chosen randomly. We consider 5 different
classes. The lengths of programs in the classes vary from 5 +- 2
minutes to 150 +- 50 minutes. The disc space necessary to store each
program equals its length, and the storage capacity is randomly chosen
as 45% to 55% of the entire time horizon.
To achieve a complete instance, it remains to choose the associated
profits of programs. We use four different strategies for the
computation of an objective function:
1. For the class usefulness (CU) instances, the associated
profit values are determined with respect to the chosen class, where
the associated profit values of a class can vary between zero and
600 +- 200.
2. In the time strongly correlated (TSC) instances, each 15 minute time
interval is assigned a random value between 0 and 10. Then, the profit
of a program is determined as the sum of all intervals that program
has a non-empty intersection with.
3. For the time weakly correlated (TWC) instances, that value is
perturbed by a noise of +-20\%.
4. In the strongly correlated data files finally, the profit of a
program simply equals its length.
The different objectives try to emulate some effects we believe to
hold real life instances. In the CU instances for example, programs of
the same class cause similar attractions. And the TC and TWC instances
cause many conflicts regarding the choice of programs that are being
broadcasted at the same time.
We identify a test set by giving the parameters the generator was
started with. According to the above description those parameters are:
Consider the following example:
void readInput (char *name, int **profit, int **weight,
int **start, int **end, int &n, int &c)
Test Instance Generation
Format of the Benchmark Sets
Line 1: Number of Programs (N) in the File
Line 2: Disk Capacity (in minutes)
Line 3 - Line N+3: Start-Time | End-Time | Duration | Profit,
whereby Duration naturally equals End-Time - Start-Time.
Lines starting with a %-sign are ignored.
%IVCR Instance constructed by GenLP-5-1
%
% Arguments:
% Number of Channels -> 2
% Number of Minutes -> 7
% Filename -> 5cu_2_7_0.ins
%
% Number of Nodes
3
%
% Capacity
4
%
% Start End Weight Profit
0 7 7 12
0 4 4 8
5 7 2 5
%
%END
A Function Reading the Input
// provided with the filename "name", the function allocates
// and reads the arrays profit, weight (=duration),
// start (containing the start-times of the programs) and
// end (containing the end-times of the programs).
// n returns the number of programs, c the disk capacity
{
char line[100];
FILE *fp;
cerr << "Reading File" << endl;
fp = fopen(name, "r");
if (!fp) {
cerr << " No file " << name << endl;
exit(-1);
}
line[0] = '\0';
// read number of nodes
fgets(line, 100, fp);
while (line[0] == '%')
fgets(line, 100, fp);
n = atoi(line);
// read capacity
fgets(line, 100, fp);
while (line[0] == '%')
fgets(line, 100, fp);
c = atoi(line);
cerr << "Number of Programs: " << n << endl;
cerr << "Capacity: "<< c << endl;
*profit = new int [n];
*weight = new int [n];
*start = new int [n];
*end = new int [n];
// read nodes
fgets(line, 100, fp);
while (line[0] == '%')
fgets(line, 100, fp);
sscanf (line, " %d %d %d %d", &(*start)[0], &(*end)[0],
&(*weight)[0], &(*profit)[0]);
//cerr << (*start)[0] << " " << (*end)[0] << " " << (*weight)[0] << " "
// << (*profit)[0] << endl;
for (int i = 1; i < n; i++)
{
fgets(line, 100, fp);
sscanf (line, " %d %d %d %d", &(*start)[i], &(*end)[i],
&(*weight)[i], &(*profit)[i]);
//cerr << (*start)[i] << " " << (*end)[i] << " " << (*weight)[i] << " "
// << (*profit)[i] << endl;
}
fclose(fp);
}