/*

09/10/01

This is an encoding of the delivery variant 
of the vehicle routing problem 
with one base and a homogeneous fleet 
reformulated as an instance of the open shop scheduling problem.

In this representation we have nonzero transition times, 
alternative resources and no precedence constraints on activities.
Each vehicle is considered a machine on th4e factory
floor and is represented as a pair: 
<unary resource deal with transition costs, discrete resource
to deal with capacities>. 
Each visit is an activity.

PRECONDITIONS:

1.  ILOG Scheduler 5.0;
2.  Data file in the following format:

    *************************************   
    0  x_base y_base 0        earliest_start   latest_end    0
    1  x_1    y_1    demand_1 earliest_start_1 lateststart_1 service_time_1
    ...
    i  x_i    y_i    demand_i earliest_start_i lateststart_i service_time_i
    ...
    *************************************

    The base and customers each are described
    by seven numbers in a separate line, 
    in this order: (i) index (0 - for the base), 
    (ii and iii) x and y coordinates of the base 
    in the 2D right Cartesian reference frame;
    (iv) demand>=0 (0 for the base); (v) earliest start;
    (vi) latest end (for the base) and latest 
    start (for customers); and (vii) service time.
3.  Output file 1 (here we store all the information 
    about the obtained solutions);
4.  Output file 2 (here we store in a concise form
    the indexes of solutions,
    cost values and comutational expenses);
5.  Turn on/off <enter 1 or 0, respectively> the edge finder algorithm.
6.  Resource selector <1..4> for forward ranking resource constraints;
7.  Resource constraint selector <1..4> for forward ranking resource constraints;
8.  Alternative resource selector <1..4>;
9.  Activity selector for assigning start times <1..4>;
10. Discrepancy count <1,2,..> for limited discrepancy search;
11. Time limit in seconds.


POSTCONDITIONS:

1.  Output file 1. Solutions in the format:
    
    ****************************    
    No. of solution Cost
   
    vehicle_1:
      tour
    ..
    vehicle_i:
      tour
    ..

    sum of transition costs on vehicle_1
    ..
    sum of transition costs on vehicle_i
    ..
    ****************************    

2.  Output file 2. Solutions in the format:
    
    ************************************************************************* 
    Solution# Cost  Veh  Fails    ChoicePts  FailsSummed  ChoicePtsSummed
    *************************************************************************    
    
    Here Veh is the number of used vehicles, Fails is the number of fails
    for this solution, ChoicePts is the number of choice points for this solution,
    FailsSummed is the overall number of fails, ChoicePtsSummed is the overall
    number of choice points. 

*/

#include <ilsched/iloscheduler.h> 
#include <conio.h> 
#include <string.h> 
#include <time.h> 
#include <dos.h> 
 
ILOSTLBEGIN 
 
const IloInt Capacity = 200; 
const IloInt SetupActivityDuration = 1; 
const IloInt TeardownActivityDuration = 1; 
const IloInt NbMachines = 25; 
const IloInt NbCustomers = 100; 
IloInt BasicTimeLimit;  
//in seconds, overall amount of time spent on search 
IloInt NbFailsSummed; 
IloInt NbChoicePointsSummed; 
 
IloInt DiscrepancyCount; 
IloBool isEdgeFinderOn; 
 
IloInt  ResourceSelector, 
        ResourceConstraintSelector, 
	PossibleResourceSelector, 
	ActivitySelector; 
 
IloInt NbActPerTour;  
//the maximum number of activities per tour (setup + all the customers + teardown) 
IloInt NbAct;         
//the overall number of activities (group 1 and group 2 ones) 
 
IloNum VrpData [150*7];  
 
inline IloInt computeDistance(IloInt i, IloInt j) { 
	return (IloInt) IloPower((VrpData[i*7+1]-VrpData[j*7+1])* 
		                 (VrpData[i*7+1]-VrpData[j*7+1])+ 
		                 (VrpData[i*7+2]-VrpData[j*7+2])* 
				 (VrpData[i*7+2]-VrpData[j*7+2]), 0.5); 
} 
 
inline IloNum getDemand (IloInt i) { 
	return VrpData[i*7+3]; 
} 
 
inline IloNum getEarliestStartTime (IloInt i) { 
	return VrpData[i*7+4]; 
} 
 
inline IloNum getLatestCompletionTime (IloInt i) { 
	return VrpData[i*7+5]; 
} 
 
inline IloNum getActivityDuration (IloInt i) { 
	return VrpData[i*7+6]; 
} 
 
 
IloModel DefineModel(const IloEnv env,  
		     IloNumVar& transCostSum, 
		     IloNumVarArray& transCostArr, 
		     IloTransitionParam& ttParam, 
		     ofstream& fout) { 
 
	IloModel model(env); 
	IloInt i,j; 
	char buffer[128]; 
 
	IloNum origin  = VrpData[4]; 
	IloNum horizon = VrpData[5]; 
 
	IloSchedulerEnv schedEnv(env); 
 
	schedEnv.getResourceParam().setCapacityEnforcement(IloHigh); 
	schedEnv.setHorizon(horizon); 
 
	//Initializing two pairs of resources representing two machines 
	IloDiscreteResourceArray capResources(env,NbMachines); 
	IloUnaryResourceArray unarResources(env,NbMachines); 
 
	for (i = 0;i<NbMachines;i++) { 
		sprintf(buffer,"cap_machine%d", i+1);		 
		capResources[i] = IloDiscreteResource(env, Capacity, buffer); 
		capResources[i].setCapacityMax(origin,horizon,Capacity); 
		capResources[i].setCapacityMin(origin,horizon,0); 
		sprintf(buffer,"unar_machine%d", i+1);		 
		unarResources[i] = IloUnaryResource(env, buffer); 
		unarResources[i].setCapacityMax(origin,horizon,1); 
		unarResources[i].setCapacityMin(origin,horizon,0); 
	} 
 
	//transition times and costs 
	ttParam = IloTransitionParam(env, NbActPerTour, IloFalse); 
 
	IloInt sum = 0; 
 
	for (i = 0; i < NbActPerTour; i++) { 
		for (j = 0; j < NbActPerTour; j++) { 
			ttParam.setValue(i,j,computeDistance(i,j)); 
			if (i==0) sum += 2*computeDistance(i,j); 
		} 
	}	 
 
	fout<<"The upper bound is "<<sum<<endl; 
	 
	IloTransitionCost enrTrans; 
 
	for (i = 0; i<NbMachines; i++) { 
		IloTransitionTime(unarResources[i],ttParam); 
		enrTrans = IloTransitionCost(unarResources[i],ttParam); 
		model.add(transCostArr[i]==enrTrans.getCostSumVar()); 
	} 
 
	model.add(IloSum(transCostArr) == transCostSum); 
 
	IloActivityArray activities(env,NbAct), activities_(env,NbAct-2*NbMachines); 
 
	//Each activity should have a unique name  
	//and its distinct transition type  
 
	//Setup activities. They consume nothing 
 
	IloInt index = 1; 
	for (i = 0;i<NbMachines;i++) { 
		sprintf(buffer, "setup%d",index); 
		activities[i] = IloActivity(env, SetupActivityDuration, 0, buffer); 
		index++; 
	} 
	 
	//actual activities 
	index = 1; 
	for (i = NbMachines; i<NbAct-NbMachines; i++) { 
		sprintf(buffer,"task%d", index); 
		activities[i] = IloActivity(env, getActivityDuration(index), index, buffer); 
		activities_[i-NbMachines]= IloActivity(env, getActivityDuration(index), index, buffer); 
		index++; 
	} 
 
	//teardown activities. They consume nothing 
	index = 1; 
	for (i = NbAct-NbMachines; i<NbAct; i++) { 
		sprintf(buffer, "teardown%d", index); 
		activities[i] = IloActivity(env, TeardownActivityDuration, NbActPerTour-1, buffer); 
		index++; 
	} 
 
	//Temporal constraints 
 
	for (i = 0;i<NbMachines;i++) { 
		model.add(activities[i].startsAfter(origin)); 
	} 
 
	index = 1; 
	for (i = NbMachines; i<NbAct-NbMachines; i++) { 
		model.add(activities[i].startsAfter(getEarliestStartTime(index))); 
		model.add(activities[i].endsBefore(getLatestCompletionTime(index) 
			                           + getActivityDuration(index))); 
		index++; 
	} 
	 
	for (i = NbAct-NbMachines; i<NbAct; i++) { 
		model.add(activities[i].endsBefore(horizon)); 
	} 
 
	//Resource constraints 
	IloResourceConstraint rc1,rc2; 
	for (i = 0; i<NbMachines; i++) { 
		rc1 = activities[i].requires(unarResources[i]); 
		rc1.setSetup(); 
		model.add(rc1); 
	} 
 
	//Creating an alternative set of discrete resources 
	IloAltResSet ResourcesAltSet(env); 
	for (i = 0; i<NbMachines; i++) { 
		ResourcesAltSet.add(unarResources[i]); 
	} 
 
	IloAltResConstraint alternative; 
	IloActivity activity,activity_; 
	 
	index = 1; 
	for (i = NbMachines; i < NbAct-NbMachines; i++) { 
		activity = activities[i]; 
		activity_ = activities_[i-NbMachines]; 
 
		alternative = activity.requires(ResourcesAltSet,1); 
 
		for (j=0;j<NbMachines;j++) { 
			model.add(alternative.select(unarResources[j])== 
				  activity_.consumes(capResources[j],getDemand(index))); 
		} 
		index++; 
		model.add(alternative); 
	} 
	 
	index = 0; 
	for (i = NbAct-NbMachines; i<NbAct; i++) { 
		rc1 = activities[i].requires(unarResources[index]); 
		rc1.setTeardown(); 
		model.add(rc1); 
		index++; 
	} 
 
	//adding for future extraction by the solver 
	model.add(transCostSum); 
	model.add(transCostArr); 
 
	return model; 
} 
 
///////////////////////////////////////////////////////////////////////// 
// 
// ENHANCING SEARCH WITH EDGE FINDER
// 
///////////////////////////////////////////////////////////////////////// 
 
ILOCPGOAL1(MakePrecedenceGraphConstraints,ofstream&,fout) { 
 
  IloSolver solver = getSolver(); 
  IlcScheduler scheduler = IlcScheduler(solver); 
 
  for (IlcDiscreteResourceIterator dResIter_(scheduler); dResIter_.ok(); ++dResIter_) { 
	IlcDiscreteResource dRes_ = *dResIter_; 
	dRes_.makeDisjunctiveConstraint(); 
  } 
 
  for (IlcResourceIterator resIter_(scheduler); resIter_.ok(); ++resIter_) { 
	IlcResource res_ = *resIter_; 
	res_.makePrecedenceGraphConstraint(); 
  } 
 
  IlcInt edgeFinder = 2, level = 2; 
 
  for (IlcDiscreteResourceIterator dResIter(scheduler); dResIter.ok(); ++dResIter) { 
	IlcDiscreteResource dRes = *dResIter; 
	dRes.setEdgeFinder(edgeFinder); 
	dRes.setPrecedencePropagation(level); 
  } 
  return 0; 
} 
 
/////////////////////////////////////////////////////////////////////////////// 
// 
// PRINTING SOLUTIONS 
// 
/////////////////////////////////////////////////////////////////////////////// 
 
void PrintSolution(const IloSolver solver,  
		   const IloNumVar transCostSum,  
		   const IloNumVarArray transCostArr, 
		   ofstream& fout, 
		   ofstream& fout1, 
		   const IloInt SolutionNb, 
		   const IloInt NbFailsSummed, 
		   const IloInt NbChoicePointsSummed) 
{ 
  IlcScheduler scheduler(solver); 
  IloEnv env = solver.getEnv(); 
  char buffer[128], buffer_[128]; 
  IloInt NbMachinesUsed = 0; 
 
  fout << "Cost Function Value: "<<solver.getIntVar(transCostSum).getMin()<<endl; 
  fout << endl; 
 
  for (IlcUnaryResourceIterator uri(scheduler); uri.ok(); ++uri) { 
	  fout<<(*uri).getName()<<endl; 
	  sprintf(buffer,(*uri).getName()); 
	  for (IlcAltResSetIterator resIte (scheduler); resIte.ok(); ++resIte) { 
		for (IlcAltResConstraintIterator ite(*resIte); ite.ok(); ++ite) { 
		  sprintf(buffer_,(*ite).getSelected().getName()); 
		  if (!strcmp(buffer,buffer_)) { 
			if ((*ite).getNumberOfPossible() == 1) { 
				fout << "\t" << (*ite).getActivity() << endl; 
			} 
		  } 
		} 
	  } 
  } 
 
  fout<<endl; 
  fout<<"The sums of transition costs on each machine: "<<endl; 
  for (int i = 0; i<NbMachines; i++) { 
	fout<<"transCostArr["<<i<<"]: min = "<<solver.getIntVar(transCostArr[i]).getMin() 
                              <<" max = "<<solver.getIntVar(transCostArr[i]).getMax()<<endl; 
	if (solver.getIntVar(transCostArr[i]).getMin()!=0) NbMachinesUsed++; 
  } 
 
  fout<<endl; 
  fout<<"The sum of transition costs on all machines: " 
	  <<" min = "<<solver.getIntVar(transCostSum).getMin() 
	  <<" max = "<<solver.getIntVar(transCostSum).getMax()<<endl; 
 
 
  fout<<endl; 
 
  fout << "Number of fails             : " << solver.getNumberOfFails()<<endl; 
  fout << "Number of choice points     : " << solver.getNumberOfChoicePoints()<<endl; 
  fout << "Number of constraints       : " << solver.getNumberOfConstraints()<<endl; 
  fout << "Elapsed time since creation : " << solver.getTime()<<endl; 
 
  fout1<<SolutionNb<<"\t"<<solver.getIntVar(transCostSum).getMin()<<"\t"<<NbMachinesUsed<<"\t"; 
  fout1<<solver.getNumberOfFails()<<"\t"<<solver.getNumberOfChoicePoints()<<"\t"; 
  fout1<<NbFailsSummed<<"\t"<<NbChoicePointsSummed<<endl; 
 
} 
 
/////////////////////////////////////////////////////////////////////////////// 
// 
// MAIN FUNCTION 
// 
/////////////////////////////////////////////////////////////////////////////// 

int main(int argc, char* argv[]) { 
 
  try { 
 
	IloEnv env; 
 
	if (argc!=11) { 
		cout<<endl; 
		cout<<"Usage: <file_name>.exe <data_file_name> <resfile1_name>\n"; 
		cout<<"       <resfile2_name> isEdgeFindingOn <0/1>\n"; 
		cout<<"       ResourceSelector <1..4> ResConstrSelector <1..4>\n"; 
		cout<<"       AltResSelector <1..4> SetStartTimesActivitySelector <1..4>\n"; 
		cout<<"       DiscrepancyCount <1,2,..> TimeLimit <seconds>\n"; 
		return 0; 
	} 
 
	ofstream fout,fout1; 
	ifstream fin; 
	fin.open(argv[1], ios::in); 
	fout.open(argv[2], ios::out); 
	fout1.open(argv[3], ios::out); 
 
	fout1 << "Solution\tCost\tNbMachines\tFails\tChoicePoints\tFailsSummed\tChoicePointsSummed"<<endl; 
 
	NbAct = NbCustomers + 2 + 2*(NbMachines - 1);	 
	NbActPerTour = NbCustomers + 2;  
 
	isEdgeFinderOn = atoi(argv[4]); 
	fout<<"isEdgeFinderOn : "<<isEdgeFinderOn<<endl; 
 
	ResourceSelector = atoi(argv[5]); 
	fout<<"ResourceSelector : "<<ResourceSelector<<endl;  
 
	ResourceConstraintSelector = atoi(argv[6]); 
	fout<<"ResourceConstraintSelector : "<<ResourceConstraintSelector<<endl;  
 
	PossibleResourceSelector = atoi(argv[7]); 
	fout<<"PossibleResourceSelector : "<<PossibleResourceSelector<<endl;  
 
	ActivitySelector = atoi(argv[8]); 
	fout<<"ActivitySelector : "<<ActivitySelector<<endl;  
 
	DiscrepancyCount = atoi(argv[9]); 
	fout<<"DiscrepancyCount : "<<DiscrepancyCount<<endl;  
 
	BasicTimeLimit = atoi(argv[10]); 
	fout<<"BasicTimeLimit : "<<BasicTimeLimit<<endl;  
 
	IloResourceSelector rSel; 
	if (ResourceSelector==1) rSel = IloSelResMinGlobalSlack; //default 
	if (ResourceSelector==2) rSel = IloSelResMinLocalSlack; 
	if (ResourceSelector==3) rSel = IloSelResSequenceMinGlobalSlack; 
	if (ResourceSelector==4) rSel = IloSelResSequenceMinLocalSlack; 
 
	IloResourceConstraintSelector rcSel; 
	if (ResourceConstraintSelector==1) rcSel = IloSelFirstRCMinEndMax; //default 
	if (ResourceConstraintSelector==2) rcSel = IloSelFirstRCMinStartMax; 
	if (ResourceConstraintSelector==3) rcSel = IloSelLastRCMaxEndMin; 
	if (ResourceConstraintSelector==4) rcSel = IloSelLastRCMaxStartMin; 
 
	IloResourceSelector prSel; 
	if (PossibleResourceSelector==1) prSel = IloSelResMinGlobalSlack; 
	if (PossibleResourceSelector==2) prSel = IloSelResMinLocalSlack; 
	if (PossibleResourceSelector==3) prSel = IloSelResMinCapacity; 
	if (PossibleResourceSelector==4) prSel = IloSelAltRes; //default 
 
	IloActivitySelector aSel; 
	if (ActivitySelector==1) aSel = IloSelFirstActMinEndMax; //default 
	if (ActivitySelector==2) aSel = IloSelFirstActMinEndMin; 
	if (ActivitySelector==3) aSel = IloSelLastActMaxStartMin; 
	if (ActivitySelector==4) aSel = IloSelLastActMaxStartMax; 
 
 
        ///////////////////////////////////////////////////////////////////////////// 
        // 
        // Reading in data from the data file 
        // 
        ///////////////////////////////////////////////////////////////////////////// 

	IloInt i; 
 
	//We use the VrpData array to store the read in data

	for (i=0;i<NbActPerTour*7;i++) { //*7 because of the format of data files 
		if (i<7*NbActPerTour-7)  
			fin>>VrpData[i];  
		else   
			VrpData[i] = VrpData[i-7*NbActPerTour+7];  
		        //additional line corresponding to teardown activity, repeats the first one 
	} 

	//transCostSum variable is to store the sum of transition 
	//costs on all machines (more precisely, on all unary 
	//resources associated with machines); 
	//An element of the transCostArr array stores the sum of transition 
	//costs on a particular machine (more precisely, on the  
	//respective unary resource 
 
	IloNumVar transCostSum(env,0,IloInfinity,ILOINT); 
	IloNumVarArray transCostArr(env,NbMachines,0,IloInfinity,ILOINT); 
	IloSchedulerSolution solution(env); 
	IloTransitionParam ttParam; 
 
	IloModel model = DefineModel(env,  
		                     transCostSum,  
				     transCostArr, 
                                     ttParam, 
			       	     fout); 
 
        // Algorithm 
	IloSolver solver(model); 
	IlcScheduler scheduler(solver); 
 
	//The Search Goal 
	IloGoal goal = IloRankForward(env,rSel,rcSel)
	               //ranking resource constraints on resources is critical for future
	               //assignments of resource constraints to resources
                       &&IloAssignAlternative(env,prSel)
		       //picking out an alternative resource and assigning it to
	               //a resource constraint 
		       && IloSetTimesForward(env,aSel); 
	               //assigning a start time to all activities in the schedule 
 
	//Applying LDS 
	goal = IloApply (env, goal, IloLDSEvaluator(env, DiscrepancyCount)); 
 
	if (isEdgeFinderOn) goal = MakePrecedenceGraphConstraints(env,fout) && goal; 
 
	//Getting the First Solution  
	//(getting it separately is necessary  
	//to obtain the first value of the objective function) 
 
	NbFailsSummed = 0; 
	NbChoicePointsSummed = 0; 
 
	struct tm *ptr; 
	time_t lt; 
 
 
	clock_t start,finish; 
	start = clock(); 
 
	lt = time(NULL); 
	ptr = localtime(&lt); 
	fout<<asctime(ptr); 
	cout<<asctime(ptr); 
 
	/////////////////////////////////////////////////////////////
	//
	// Searching for solutions
	//
	/////////////////////////////////////////////////////////////

	// the first solution

	if (solver.solve(IloLimitSearch(env, goal, IloTimeLimit(env, BasicTimeLimit)))) { //if there is a solution 
		finish = clock()-start; 
		env.out()<<endl; 
		env.out()<<"Solution 1 : " 
			 <<solver.getIntVar(transCostSum).getMin()<<endl; 
		env.out()<<endl; 
		fout<<endl; 
		fout<<"****************** Solution 1 ******************"<<endl; 
		solver.printInformation(); 
                NbFailsSummed += solver.getNumberOfFails(); 
		NbChoicePointsSummed += solver.getNumberOfChoicePoints(); 
		PrintSolution(solver,transCostSum,transCostArr,
                              fout,fout1,1,NbFailsSummed,NbChoicePointsSummed); 
	} else { 
		solver.out() << "No Solutions" << endl; 
		lt = time(NULL); 
		ptr = localtime(&lt); 
		fout<<asctime(ptr); 
		cout<<asctime(ptr); 
		fout.close(); 
		fout1.close(); 
		env.end(); 
		exit(1); 
	} 
 
	IloInt SolutionCtr = 2; 
 
	// Getting the var TimeLimit depending on how much time is spent previously on search. 
	// In fact, Time Limit is what is left for search from BasicTimeLimit. 

	IloNum TimeSpent = (double) finish / CLOCKS_PER_SEC; 
	cout<<"TimeSpent : "<<TimeSpent<<endl; 
 
	IloNum TimeLimit = BasicTimeLimit - TimeSpent; 
	cout<<"TimeLimit : "<<TimeLimit<<endl; 
 
	start = clock(); 
	
	// subsequent solutions of less cost
	
	while (TimeLimit>0 && solver.solve(IloAddConstraint(transCostSum <= solver.getIntVar(transCostSum).getMin()-1) 
		                           && IloLimitSearch(env, goal, IloTimeLimit(env,TimeLimit)))) { 
		env.out()<<endl; 
		env.out()<<"Solution "<<SolutionCtr<<" : " 
			     <<solver.getIntVar(transCostSum).getMin()<<endl; 
		env.out()<<endl; 
		fout<<endl; 
		fout<<"****************** Solution "<<SolutionCtr<<" ******************"<<endl; 
		solver.printInformation(); 
                NbFailsSummed += solver.getNumberOfFails(); 
		NbChoicePointsSummed += solver.getNumberOfChoicePoints(); 
		PrintSolution(solver,transCostSum,transCostArr,
                              fout,fout1,SolutionCtr,NbFailsSummed,NbChoicePointsSummed); 
		SolutionCtr++; 
 
		finish = clock(); 
		TimeSpent += (double) (finish - start) / CLOCKS_PER_SEC; 
		cout<<"TimeSpent : "<<TimeSpent<<endl; 
		TimeLimit = BasicTimeLimit - TimeSpent; 
		cout<<"TimeLimit : "<<TimeLimit<<endl; 
		start = finish; 
	} 
 
	cout<<"No More Solutions"<<endl; 
 
	lt = time(NULL); 
	ptr = localtime(&lt); 
	fout<<asctime(ptr); 
	cout<<asctime(ptr); 
	fout.close(); 
	fout1.close(); 
	env.end(); 
    
  } catch (IloException& exc) { 
    cout << exc << endl; 
  } 
  return 0; 
}