Assignment #1: Airline Scheduling

OBJECTIVES

To experience the process of designing an algorithm (without anybody telling you how you have to do it), implementing the algorithm (Java, C++, or C), and testing it.

ASSIGNMENT

Consider a sparse 2-dimensional 0-1 matrix, where each column is assigned a weight. The task is to select a subset of the columns so that the each row contains exactly one 1 in the selected columns. The cost of the solution is the sum of the costs of the selected columns. A solution of lowest cost is desired.

Example:

1 2 3 4 5 6 7 8
1
0
0
0
0
0
1
0
1
2
1
0
0
1
1
1
0
0
3
0
1
0
1
0
0
1
0
4
0
1
0
0
1
1
0
0
5
1
0
1
0
0
0
1
0
Cost
4
3
7
2
8
7
6
2

Data Format

Data sets will be in the format:

first line: number of rows, number of columns

remaining lines, one for each column:

column cost, number of rows covered, list of rows covered

Here are the first few lines of some sample data with forty rows and 3076 columns. This file has 3077 lines. I think that no column will cover more than fifteen rows in any data file that I have.

40 3076

3006 6 1 4 5 11 34 38

2620 4 1 4 10 11

9484 1 1

3438 6 2 12 13 21 29 32

2168 5 2 21 37 39 40

2830 4 2 21 37 39

2152 4 2 21 39 40

2830 3 2 21 39

Data Sets

There are real life files that are 50M or more. We'll not try that big for now. Here are some data sets from JE Beasley of various sizes. 
/u/css/classes/5110/Fall2014/setcover/data1.txt
/u/css/classes/5110/Fall2014/setcover/data2.txt
/u/css/classes/5110/Fall2014/setcover/data3.txt
/u/css/classes/5110/Fall2014/setcover/data4.txt