/*
 *    This code takes as input data files (mkdist.dat, mkrides.dat,
 *  and sec.dat) that describe an instance of the M7TP and produces
 *  as output a CPLEX ".lp" file (m7tp.lp) that contains a partial 
 *  IP formulation of that instance (the only constraints are the 
 *  degree constraints, the time-in-park constraint, and the subtour
 *  elimination constraints described in sec.dat).
 *
 *    This code was written by Michael Cardiff, Gwyneth Hughes, and
 *  Robert Bosch.  Feel free to modify it, but please do claim it as
 *  your own.  If you have comments or suggestions, please e-mail
 *  bobb@cs.oberlin.edu
 */
 
#include <stdio.h>
#include <stdlib.h>

#define MAX_RIDES 40
#define MAX_SECS 40
#define ZERO 0.01
#define TRUE 1
#define MAX_TIME 480
#define MAX_TERMS 6
#define KID_OBJ TRUE

int num_rides;
int num_sec;
float distance[MAX_RIDES+1][MAX_RIDES+1];
int subtour[MAX_SECS+1][MAX_RIDES+1];
int subtour_size[MAX_SECS+1];
float ride_time[MAX_RIDES+1];              /* waiting plus on-ride */
float fun_kid[MAX_RIDES+1];
float fun_parent[MAX_RIDES+1];

void get_data()
{
int i, j, trash; 

FILE *distance_file, *ride_file, *sec_file;

/*
 *  Open the file mkdist.dat.  This file is a list of
 *  floating point numbers.  Each number is the distance
 *  between a pair of rides.  The pairs of rides are 
 *  listed in the following order:  
 *
 *    0,1
 *    0,2  1,2
 *    0,3  1,3  2,3  
 *    0,4  1,4  2,4  3,4  
 *
 *  etc.
 */

if ((distance_file=fopen("mkdist.dat", "r")) == NULL) 
  {
    printf("Couldn't open mkdist.dat!\n");
    exit(0);
  }

for (j = 1; j <= MAX_RIDES; j++)
  for (i = 0; i < j; i++) 
    fscanf(distance_file, "%f", &distance[i][j]);

fclose(distance_file);

/*
 *  Open the file mkrides.dat.  The first line contains a 
 *  whole number that equals the total number of rides.  Each
 *  subsequent line corresponds to one ride and contains four
 *  numbers:
 * 
 *  1.  a whole number that identifies the ride,
 *  
 *  2.  a floating point number that equals the sum of the
 *      ride's wait time and on-ride time,
 *
 *  3.  a floating point number that equals the ride's fun
 *      value (the number of stars it was given by the
 *      MiniMickey guidebook) for preschoolers, and
 *
 *  4.  a floating point number that equals the ride's fun
 *      value for parents of preschoolers.
 */

if ((ride_file=fopen("mkrides.dat", "r")) == NULL) 
  {
    printf("Couldn't open mkrides.dat!\n");
    exit(0);
  }

fscanf(ride_file, "%d", &num_rides);

for (j = 0; j <= num_rides; j++)
  {
    fscanf(ride_file, "%d", &trash);
    fscanf(ride_file, "%f", &ride_time[j]);
    fscanf(ride_file, "%f", &fun_kid[j]);
    fscanf(ride_file, "%f", &fun_parent[j]);
  }

fclose(ride_file);

/*
 *  Open the file sec.dat.  The first line contains a whole
 *  number that equals the number of subtour elimination
 *  constraints to be included in the formulation.  The
 *  remaining lines (if there are any) give the size of
 *  each subtour and a list of its members.
 */

if ((sec_file=fopen("sec.dat", "r")) == NULL) 
  {
    printf("Couldn't open sec.dat!\n");
    exit(0);
  }

fscanf(sec_file, "%d", &num_sec);

for (i = 1; i <= num_sec; i++)
  {
    fscanf(sec_file, "%d", &subtour_size[i]);
    for (j = 1; j <= subtour_size[i]; j++)
      fscanf(sec_file, "%d", &subtour[i][j]);
  }

fclose(sec_file);

}


main ()
{
int i, j, k;
int num_terms;
     
FILE *lp_file;
     
get_data();
    
/*
 *  Open the file m7tp.lp.
 */

if ((lp_file=fopen("m7tp.lp", "w")) == NULL)
  {
    printf("Couldn't open m7tp.lp!\n");
    exit(0);
  }

/*
 *  Write the objective function to the file m7tp.lp.
 */

fprintf(lp_file, "maximize\n");

num_terms = 0;
for (i = 0; i <= num_rides; i++)
  {
    if (KID_OBJ == TRUE)
      fprintf(lp_file, " + %.1f Y%d", fun_kid[i], i);
    else
      fprintf(lp_file, " + %.1f Y%d", fun_parent[i], i);
    num_terms++;
    if (num_terms == MAX_TERMS)
      {
        num_terms = 0;
        fprintf(lp_file, "\n");
      }
  }

fprintf(lp_file, "\n");

/*
 *  Write the constraints to the file m7tp.lp.
 */

fprintf(lp_file, "subject to\n");
     
/*
 *  Write the "time in park" constraint.
 */

num_terms = 0;
for (i = 0; i <= num_rides-1; i++)
  for (j = i+1; j <= num_rides; j++)
    {
      fprintf(lp_file, " + %.1f X%d,%d", 
        distance[i][j], i, j);
      num_terms++;
      if (num_terms == MAX_TERMS)
        {
          num_terms = 0;
          fprintf(lp_file, "\n");
        }
    }
for (i = 0; i <= num_rides; i++)
  if (ride_time[i] > ZERO)
    {
      fprintf(lp_file, " + %.1f Y%d", ride_time[i], i);
	  num_terms++;
	  if (num_terms == MAX_TERMS)
	    {
          num_terms = 0;
		  fprintf(lp_file, "\n");
	    }
    }
fprintf(lp_file, " <= %d\n", MAX_TIME);

fprintf(lp_file, "\n");

/*
 *  Write the degree constraints.
 */

for (i = 0; i <= num_rides; i++)
  {
    num_terms = 0;
    for (j = 0; j < i; j++)
      {
        fprintf(lp_file, " + X%d,%d", j, i);
        num_terms++;
        if (num_terms == MAX_TERMS)
          {
            num_terms = 0;
            fprintf(lp_file, "\n");
          }
      }
    for (j = i+1; j <= num_rides; j++)
      {
        fprintf(lp_file, " + X%d,%d", i, j);
        num_terms++;
        if (num_terms == MAX_TERMS)
          {
            num_terms = 0;
            fprintf(lp_file, "\n");
          }
      }
    fprintf(lp_file, " - 2 Y%d = 0\n", i);
  }

fprintf(lp_file, "\n");

/*
 *  Write the subtour elimination constraints for the
 *  subtours listed in the file sec.dat.
 */

for (k = 1; k <= num_sec; k++)
  {
    num_terms = 0;
    for (i = 1; i <= subtour_size[k]-1; i++)
      for (j = i+1; j <= subtour_size[k]; j++)
        {
          fprintf(lp_file, " + X%d,%d", subtour[k][i], subtour[k][j]);
          num_terms++;
          if (num_terms == MAX_TERMS)
            {
              num_terms = 0;
              fprintf(lp_file, "\n");
            }
        }
    fprintf(lp_file, " <= %d\n", subtour_size[k]-1);
  }

fprintf(lp_file, "\n");

/*
 *  Write the variables' lower and upper bounds.
 */

fprintf(lp_file, "bounds\n");
     
for (i = 0; i <= num_rides-1; i++) 
  for (j = i+1; j <= num_rides; j++) 
    fprintf(lp_file, " 0 <= X%d,%d <= 1\n", i, j);

fprintf(lp_file, " Y0 = 1\n");

for (i = 1; i <= num_rides; i++)
    fprintf(lp_file, "0 <= Y%d <= 1\n", i);

fprintf(lp_file, "\n"); 

/*
 *  Indicate that the variables are integers.
 */

fprintf(lp_file, "integers\n");

for (i = 0; i <= num_rides-1; i++) 
  for (j = i+1; j <= num_rides; j++) 
    fprintf(lp_file, " X%d,%d\n", i, j);

for (i = 0; i <= num_rides; i++)
    fprintf(lp_file, " Y%d\n", i);
     
fprintf(lp_file, "end\n");
     
fclose(lp_file);

}