/*
 *  presolve.c
 *  
 *
 *  Created by Armin Fuegenschuh, Benjamin Hiller, and YOU.
 *  Copyright 2009 Zuse Institute Berlin. All rights reserved.
 *
 */

#include "stdio.h"
#include "stdlib.h"
#include "math.h"

/*
  In this exercise your task is to implement bound-strengthening presolving for the school bus
  problem. 

  Below you find the necessary data structures for the problem data and the global variables that
  contain the problem data. The program takes care of reaing the data, showing some statistics,
  invoking the presolve, showing statistics after presolving and writing the presolved problem
  data.

  All you need to do is implement the function presolve() below, in which you can freely
  manipulate the problem data.

  We suggest that you proceed as follows:

  1. Have a look at the data structures below to get an idea on how the problem data is represented.
     The ZIMPL model in the file model.zpl might be helpful, too.

  2. Figure out how bound-strengthening can help and how it works out for the relevant contraints.

  3. Implement this basic bound-strengthening presolve for the relevant constraints.

  4. Test and verify your implementation.

  5. If everything works, think about how to apply "higher-order bound-strengthening" to fix / eliminate
     binary variables for the deadheads.

     Hint: This technique can be applied to deduce that a bus cannot serve two trips meeting at a
           school or transfer point.

  6. Implement and test your ideas for this additional fixing of binary variables.


  Note: The program can be compiled via

     gcc presolve.c -o presolve -lm
*/


// Data of a school
typedef struct {
  int minBegin;    // Earliest start time for this school.
  int maxBegin;    // Earliest start time for this school.
} School;


// Data of a bus trip.
typedef struct {
  int runningTime;  // Total time the trip takes.
  int minStart;     // Earliest start time of the trip.
  int maxStart;     // Latest start time of the trip.
} Trip;


// Data of a visit to a school on a trip.
typedef struct {
  int trip;         // Trip this stops belongs to.
  int school;       // School the bus stops at.
  int rideTime;     // Time in minutes from the start time of the trip at which the bus arrives at the school.
  int minWalkTime;  // Minimum time before school start the bus has to be at this school.
  int maxWalkTime;  // Maximum time before school start the bus has to be at this school (bus must not be too early).
} Schooltrip;

// Data for visiting a transfer point (bus stop where two trips A, B meet and pupils change from A to B) on a trip.
typedef struct {
  int fromTripA;    // Trip from which pupils transfer.
  int toTripB;      // Trip to which pupils transfer.
  int rideTimeA;    // Time in minutes from the start time of trip A at which the bus arrives at the transfer point.
  int rideTimeB;    // Time in minutes from the start time of trip B at which the bus arrives at the transfer point.
  int minWaitTime;  // Minimum waiting time for allowing to transfer.
  int maxWaitTime;  // Maximum waiting time (pupils must not wait too long).
} Transfer;

// Data of a feasible deadhead connection between trips.
typedef struct {
  int fromTrip;     // Previous trip of deadhead connection. 
  int toTrip;       // Next trip of deadhead connection. 
  int deadheadTime; // Time needed for deadhead connection.

  int eliminated;   // Flag indicating whether this deadhead has been eliminated by presolve.
} Deadhead;	


// variables

// arrays to store the instance data

Trip* trip = NULL;
School* school = NULL;
Schooltrip* schooltrip = NULL;
Transfer* transfer = NULL;
Deadhead* deadhead = NULL;

// number of data per type
// IMPORTANT: we start the arrays with index 1 (not 0, which is not used),
//            and the last element is numberOf...

int numberOfTrips = 1;
int numberOfSchools = 1;
int numberOfSchooltrips = 1;
int numberOfTransfers = 1;
int numberOfDeadheads = 1;



void presolve()
{	
	// INSERT YOUR PRESOLVE CODE HERE
		
	printf("PRESOLVE IS RUNNING\n");

}



// Auxiliary functions defined below.
void read_data();
void show_size_statistics();
void write_data();


int main () {
	int i;

	read_data();
	
	show_size_statistics();

	presolve();
	
	show_size_statistics();

	write_data();
	
	return 0;
}



void read_data()
{
	// time window variables
	
	int totalWidthOfSchoolTimeWindows = 0;
	int totalWidthOfTripTimeWindows = 0;
	
	// count the number of fixed variables (i.e., lower bound = upper bound)
	
	int fixedBinaryVariables = 0;
	
	// file pointer for reading
	
	FILE *fp;
	
	// auxiliary variables (for loops etc.)
	
	int i;
	
	
	// reading trips from file
	
	fp = fopen("trips.dat","r");
	
	do {
		// read the next line from file
		int id;
		Trip tmp;
		
		fscanf(fp,"%d %d %d %d",
			   &id,
			   &tmp.runningTime,
			   &tmp.minStart,
			   &tmp.maxStart);
		
		if (!feof(fp)) {
			if (id != numberOfTrips) { 
				// checking if id in file differs from number of trips
				// this would indicate an error
				printf("*** error: missing data, %d vs. %d\n",
					   id,
					   numberOfTrips);
				exit(1);
			}
			
			// get more memory
			trip = realloc(trip,
						   (numberOfTrips + 1) * sizeof(Trip));
			
			// copy tmp to array of trips
			trip[numberOfTrips].runningTime = tmp.runningTime;
			trip[numberOfTrips].minStart = tmp.minStart;
			trip[numberOfTrips].maxStart = tmp.maxStart;
			
			numberOfTrips++;
		}
	} while (!feof(fp));
	
	fclose(fp);
	
	numberOfTrips--; // correction of the last

	
	// reading schools from file
		
	fp = fopen("schools.dat","r");
	
	do {
		// read the next line from file
		int id;
		School tmp;
		
		fscanf(fp,"%d %d %d",
			   &id,
			   &tmp.minBegin,
			   &tmp.maxBegin);
		
		if (!feof(fp)) {
			if (id != numberOfSchools) { 
				// checking if id in file differs from number of trips
				// this would indicate an error
				printf("*** error: missing data, %d vs. %d\n",
					   id,
					   numberOfSchools);
				exit(1);
			}
			
			// get more memory
			school = realloc(school,
							 (numberOfSchools + 1) * sizeof(School));
			
			// copy tmp to array of schools
			school[numberOfSchools].minBegin = tmp.minBegin;
			school[numberOfSchools].maxBegin = tmp.maxBegin;
			
			numberOfSchools++;
		}
	} while (!feof(fp));
	
	fclose(fp);
	
	numberOfSchools--; // correction of the last

	
	// reading schooltrips from file
	
	
	fp = fopen("schooltrips.dat","r");
	
	do {
		// read the next line from file
		Schooltrip tmp;
		
		fscanf(fp,"%d %d %d %d %d",
			   &tmp.school,
			   &tmp.trip,
			   &tmp.rideTime,
			   &tmp.minWalkTime,
			   &tmp.maxWalkTime);
		
		if (!feof(fp)) {			
			// get more memory
			schooltrip = realloc(schooltrip,
								 (numberOfSchooltrips + 1) * sizeof(Schooltrip));
			
			// copy tmp to array of schooltrips
			schooltrip[numberOfSchooltrips].school = tmp.school;
			schooltrip[numberOfSchooltrips].trip = tmp.trip;
			schooltrip[numberOfSchooltrips].rideTime = tmp.rideTime;
			schooltrip[numberOfSchooltrips].minWalkTime = tmp.minWalkTime;
			schooltrip[numberOfSchooltrips].maxWalkTime = tmp.maxWalkTime;
			
			numberOfSchooltrips++;
		}
	} while (!feof(fp));
	
	fclose(fp);

	numberOfSchooltrips--; // correction of the last


	// reading transfers from file
		
	fp = fopen("transfers.dat","r");
	
	do {
		// read the next line from file
		Transfer tmp;
		
		fscanf(fp,"%d %d %d %d %d %d",
			   &tmp.fromTripA,
			   &tmp.toTripB,
			   &tmp.rideTimeA,
			   &tmp.rideTimeB,
			   &tmp.minWaitTime,
			   &tmp.maxWaitTime);
		
		if (!feof(fp)) {			
			// get more memory
			transfer = realloc(transfer,
							   (numberOfTransfers + 1) * sizeof(Transfer));
			
			// copy tmp to array of schooltrips
			transfer[numberOfTransfers].fromTripA = tmp.fromTripA;
			transfer[numberOfTransfers].toTripB = tmp.toTripB;
			transfer[numberOfTransfers].rideTimeA = tmp.rideTimeA;
			transfer[numberOfTransfers].rideTimeB = tmp.rideTimeB;
			transfer[numberOfTransfers].minWaitTime = tmp.minWaitTime;
			transfer[numberOfTransfers].maxWaitTime = tmp.maxWaitTime;
			
			numberOfTransfers++;
		}
	} while (!feof(fp));
	
	fclose(fp);

	numberOfTransfers--; // correction of the last

	
	// reading deadheads from file
		
	fp = fopen("deadheads.dat","r");
	
	do {
		// read the next line from file
		Deadhead tmp;
		
		fscanf(fp,"%d %d %d",
			   &tmp.fromTrip,
			   &tmp.toTrip,
			   &tmp.deadheadTime);
		
		if (!feof(fp)) {			
			// get more memory
			deadhead = realloc(deadhead,
							   (numberOfDeadheads + 1) * sizeof(Deadhead));
			
			// copy tmp to array of schooltrips
			deadhead[numberOfDeadheads].fromTrip = tmp.fromTrip;
			deadhead[numberOfDeadheads].toTrip = tmp.toTrip;
			deadhead[numberOfDeadheads].deadheadTime = tmp.deadheadTime;
			
			// set eliminated flag
			deadhead[numberOfDeadheads].eliminated = 0;
			
			numberOfDeadheads++;
		}
	} while (!feof(fp));
	
	fclose(fp);

	numberOfDeadheads--; // correction of the last
	
	
	// some statistics
	
	printf("number of trips: %d\n",numberOfTrips);
	printf("number of schools: %d\n",numberOfSchools);
	printf("number of school trips: %d\n",numberOfSchooltrips);
	printf("number of transfers: %d\n",numberOfTransfers);
	printf("number of deadheads: %d\n",numberOfDeadheads);
}


void show_size_statistics()
{
        // time window variables
	
	int totalWidthOfSchoolTimeWindows = 0;
	int totalWidthOfTripTimeWindows = 0;
	
	// count the number of fixed variables (i.e., lower bound = upper bound)
	
	int fixedBinaryVariables = 0;
	
	// auxiliary variables (for loops etc.)
	
	int i;
	
	// compute size of trip time windows
	
	totalWidthOfTripTimeWindows = 0;
	
	for (i=1; i<=numberOfTrips; i++) {
		totalWidthOfTripTimeWindows += trip[i].maxStart - trip[i].minStart;
	}
	
	printf("total width of all trip time windows: %d\n",totalWidthOfTripTimeWindows);
	
	
	// compute size of school time windows
	
	totalWidthOfSchoolTimeWindows = 0;
	
	for (i=1; i<=numberOfSchools; i++) {
		totalWidthOfSchoolTimeWindows += school[i].maxBegin - school[i].minBegin;
	}
	
	printf("total width of all school time windows: %d\n",totalWidthOfSchoolTimeWindows);

	
	// compute number of fixed binary (deadhead) variables
	
	fixedBinaryVariables = 0;
	
	for (i=1; i<=numberOfDeadheads; i++) {
		if ( deadhead[i].eliminated ) {
			fixedBinaryVariables++;
		}
	}
	
	printf("number of fixed binary variables: %d\n",fixedBinaryVariables);
}


void write_data()
{
	// file pointer for reading
	
	FILE *fp;
	
	// auxiliary variables (for loops etc.)
	
	int i;
	
	// writing presolved trips to file
	
	fp = fopen("trips.presolved.dat","w");
	
	for (i=1; i<=numberOfTrips; i++) {
		fprintf(fp,"%d\t%d\t%d\t%d\n",
				i,
				trip[i].runningTime,
				trip[i].minStart,
				trip[i].maxStart);
	}
	
	fclose (fp);
	
	
	// writing presolved schools to file
	
	fp = fopen("schools.presolved.dat","w");
	
	for (i=1; i<=numberOfSchools; i++) {
		fprintf(fp,"%d\t%d\t%d\n",
				i,
				school[i].minBegin,
				school[i].maxBegin);
	}
	
	fclose (fp);

	
	// writing presolved deadheads to file
	
	fp = fopen("deadheads.presolved.dat","w");
	
	for (i=1; i<=numberOfDeadheads; i++) {
		if ( !deadhead[i].eliminated ) {
			fprintf(fp,"%d\t%d\t%d\n",
					deadhead[i].fromTrip,
					deadhead[i].toTrip,
					deadhead[i].deadheadTime);
		}
	}
	
	fclose (fp);
}