/* Heuristically solve a BLP Constrained Optimization Problem (COP)          */

/* Copyright (C) 2001  Dale Schuurmans, Finnegan Southey                     */
/* This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 * 
 * See the accompanying file "gpl.txt" for details.
 */


#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <sys/time.h>
#include <limits.h>
#include <values.h>
#include "cop.h"

#define SHOW_DETAILS 0

long seed;
struct timeval tv;
struct timezone tzp;

int compare();

/*********************************************************/
int main(int argc, char *argv[])
{
   int reps, REPS;
   int minsteps, maxsteps, sumsteps;
   int mindsteps, maxdsteps, sumdsteps;
   int *numsteps, *numdsteps, *numconsidered;
   int *condcumsteps; 
   double *condavgsteps, *cutsteps, mincut; 
   int found = 0;
   FILE *in;
   double par1, par2, par5;
   int par3, par4, par6, par7;
   double timeDiff;
   double timeSum = 0.0;
   struct timeval startTime, endTime;
	 char *lastslash;

   gettimeofday(&tv,&tzp);
   seed = (( tv.tv_sec & 0177 ) * 1000000) + tv.tv_usec;
   seed = 37;
   srandom(seed);
   
   if (argc > 10) {
      printf("Usage: <solvername> [reps] [input file] ");
      printf("[par1] ... [par7]\n");
      exit(1);
   }
   REPS = (argc < 2) ? 10 : atoi(argv[1]);
   in = (argc < 3) ? stdin : fopen(argv[2], "r");
   if (in == NULL) {
      printf("Error: failed to open input file\n");
      exit(1);
   }
   par1 = (argc < 4) ? 1.0 : atof(argv[3]);
   par2 = (argc < 5) ? 0.0 : atof(argv[4]);
   par3 = (argc < 6) ? 1 : atoi(argv[5]);
   par4 = (argc < 7) ? 1000 : atoi(argv[6]);
   par5 = (argc < 8) ? 0.1 : atof(argv[7]);
   par6 = (argc < 9) ? 100 : atoi(argv[8]);
   par7 = (argc < 10) ? 0 : atoi(argv[9]);

   numsteps = (int *) calloc(REPS, sizeof(int));
   numdsteps = (int *) calloc(REPS, sizeof(int));
   numconsidered = (int *) calloc(REPS, sizeof(int));
   condcumsteps = (int *) calloc(REPS, sizeof(int));
   condavgsteps = (double *) calloc(REPS, sizeof(double));
   cutsteps = (double *) calloc(REPS, sizeof(double));

   alloc_and_readCOP(in);
   
   gettimeofday(&startTime, NULL);

   ALLOCATE(par1, par2, par3, par4, par5, par6, par7);

   gettimeofday(&endTime, NULL);

	 /** Account for setup time for each REP. **/
	 timeDiff = (endTime.tv_sec - startTime.tv_sec)
            + (endTime.tv_usec - startTime.tv_usec) / 1000000.0;
   timeSum += timeDiff * REPS;


   for (reps = 0; reps < REPS; reps++) {

      gettimeofday(&startTime, NULL);

      SEARCH(par1, par2, par3, par4, par5, par6, par7);

      gettimeofday(&endTime, NULL);
      timeDiff = (endTime.tv_sec - startTime.tv_sec)
               + (endTime.tv_usec - startTime.tv_usec) / 1000000.0;
      timeSum += timeDiff;

      if (minfeasobj <= opt) {
         if (minfeasobj < opt) {
					 if (minfeasobj - opt == -1)
						 minfeasobj = opt;
					 else {
            printf("Error: minfeasobj %d less than opt %d\n", minfeasobj, opt);
            exit(1);
					 }
         }
         found++;
				 r++;
#if SHOW_DETAILS
         printf("%3d opt found,\t ", reps);
         printf("steps=%9i  dsteps=%9i  tries=%3i\n", steps, dsteps, r);
#endif
      } else {
#if SHOW_DETAILS
         printf("%3d NOT found,\t ", reps);
         printf("steps=%9i  dsteps=%9i  tries=%3i\n", steps, dsteps, r);
#endif
      }

      numsteps[reps] = steps;
      numdsteps[reps] = dsteps;
      numconsidered[reps] = considered;
   }
   CLEANUP();

   /***** report *****/
   minsteps = mindsteps = INT_MAX;
   maxsteps = sumsteps = maxdsteps = sumdsteps = 0;
   for (reps = 0; reps < REPS; reps++) {
      minsteps = (numsteps[reps] < minsteps) ? numsteps[reps] : minsteps;
      mindsteps = (numdsteps[reps] < mindsteps) ? numdsteps[reps] : mindsteps;
      maxsteps = (numsteps[reps] > maxsteps) ? numsteps[reps] : maxsteps;
      maxdsteps = (numdsteps[reps] > maxdsteps) ? numdsteps[reps] : maxdsteps;
      sumsteps += numsteps[reps];
      sumdsteps += numdsteps[reps];
   }
#if SHOW_DETAILS
   printf("\n");
   printf("    %3i found", found);
   printf("    minst=%9i  mindst=%9i\n", minsteps, mindsteps);
   printf("    %3i  fail", REPS-found);
   printf("    avgst=%9i  avgdst=%9i\n", sumsteps/REPS, sumdsteps/REPS);
   printf("          \t");
   printf(" maxst=%9i  maxdst=%9i\n", maxsteps, maxdsteps);
#endif
   
   /* Estimate optimal expected number of search steps with restarts */
   qsort(numsteps, REPS, sizeof(int), &compare);
   condcumsteps[0] = numsteps[0];
   condavgsteps[0] = (double) numsteps[0];
   for (reps = 1; reps < REPS; reps++) {
      condcumsteps[reps] = condcumsteps[reps-1] + numsteps[reps];
      condavgsteps[reps] = condcumsteps[reps] / (double) (reps+1);
   }
   for (reps = 0; reps < REPS; reps++) 
      cutsteps[reps] = numsteps[reps] * (REPS/(reps+1.0) - 1.0)
                        + condavgsteps[reps];
   mincut = DBL_MAX;
   for (reps = 0; reps < REPS; reps++)
      if (cutsteps[reps] < mincut) mincut = cutsteps[reps];
#if SHOW_DETAILS
   printf("                 optst=%9i\n", (int)(mincut+0.5));
   
   printf("total time=%gsec\ttime per step=%gmsec\n", timeSum, timeSum/sumsteps*1.0e6);
#endif


   lastslash = strrchr(argv[2], '/');
	 if (lastslash == NULL)
		 lastslash = argv[2];
	 else
		 lastslash++;

	 if (!haveopt) {
		 found = 0;
		 opt = 0;
	 }

	 printf("#Fail%%\tuStep\tuDStep\tExpStep\tBest%%\tBestVal\tOptVal\tTries\tTimeSum\tuFlipT\tExpTime\tGoods\tBids\tProb\n");
   printf("%g\t%d\t%d\t%d\t%g\t%d\t%d\t%d\t%g\t%g\t%g\t%d\t%d\t%s\n",  (1.0 - (double)found / REPS) * 100, 
			 sumsteps / REPS, sumdsteps / REPS, (int)(mincut+0.5), 
			 (double)minfeasobj / opt, -minfeasobj, -opt,
			 r,
			 timeSum, timeSum/sumsteps*1e6, timeSum/sumsteps * ((int)mincut+0.5),
       m, n,
			 lastslash);
	 
   freeCOP();
   return 1;
}

/*********************************************************/
int compare(const void *i, const void *j)
{
   if ( *((int *)i) < *((int *)j) ) 
      return -1;
   else if ( *((int *)i) == *((int *)j) )
      return 0;
   else 
      return 1;
}