//******************************************************
//  Copyright 1999 University of Paderborn
//
//  FILE : SA_Problem.h
//  
//  includes         : mpi.h, iostream.h
//  is included by   : SA_QAP.cc
//
//  description      : 
//    This SA_Problem instance represents an instance of the
//    quadratic assignment problem. The goal is to minimize
//    the value of
//       ___   ___
//       \     \ 
//       /     /    a     * b
//       ---   ---    ij      p(i)p(j)
//        i     j
//    where A = (a ij) and B = (b ij) are quadratic matrices
//    of size n and p is an permutation. The matrices A and B
//    are not supposed to be symetric.
//
//  authors:
//    Karsten Klohs
//  contact:
//    parsa@uni-paderborn.de
//  last update:
//    17.10.99
//
//******************************************************


#ifndef SA_Problem_H
#define SA_Problem_H

#define MELEMTYPE int

#include <iostream>

#ifdef MPI
  #include <mpi.h>
#endif

class SA_Problem;                     // forward declaration


//******************************************************
// class SA_Solution :
//	- contains a solution 
//	- can copy a solution in itsself
//
// class MUST be implemented by the user 
//****************************************************** 
// -- EXAMPLE: 
// --  
// -- one solution instance consists of the old permutation p,
// -- the suggested pair of numbers i and j which per-
// -- mutationvalues will be changed, the cost value of 
// -- the permutation oldcost and the value of the changed
// -- permutation newcost. 
// -- To access the permutation array its size n is also 
// -- needed
class SA_Solution
{
  friend class SA_Problem;

  public:
  int n;
  int *p;                              // the permutation
  int i,j;                             
  int oldcost, newcost;
  
//  ----- BASIC functions -------------------------------
   SA_Solution(); 
   void Copy(SA_Solution & source);

};
std::ostream & operator <<(std::ostream &, SA_Solution &);

//******************************************************
// class SA_Move :g
//      - contains a move 
//
// class CAN be implemented by the user
//****************************************************** 
// -- EXAMPLE:
// 

class SA_Move 
{ 
   public: 
 //----- constructor ---------------------------------  
   SA_Move();
   ~SA_Move();
   SA_Move(SA_Problem &);
   friend class SA_Problem;

};
// 
std::ostream & operator << (std::ostream &, SA_Move &);


//******************************************************
// class SA_Problem :
//      - representation of the problem
//      - generates initial solution
//      - neighborhood operation 
//      - cost function
//
//  class MUST be implemented by user
//****************************************************** 
class SA_Problem
{

public:
// ----- constructor / destructor ----------------------
// -- EXAMPLE: 
// -- The default constructor creates a simple SA_Problem instance. 
      	SA_Problem();
	~SA_Problem();

        void EvaluateOptions(int *argc,char ***argv);

// ----- methods for SEQUENTIAL SA ---------------------
// -- EXAMPLE:
// -- Reads the dimension n and the two matrices A and B 
// -- from a file
 
	int		ReadProblemData(char *);

	SA_Solution *	CreateSolution();
	
// -- EXAMPLE:
// -- As an deterministic initial solution we choose the 
// -- identity function
	void		GetInitialSolution(SA_Solution &);	

// -- EXAMPLE
// -- As an random initial solution we choose an random
// -- permutation
	void		GetRandomSolution(SA_Solution &);

// -- EXAMPLE
// -- The cost of a solution is the oldcost value minus
// -- the old products of a kl * b p(k)p(l) plus the
// -- new products of the changed permutation. These
// -- values are different only if k = i or l = j
	float		GetCost(SA_Solution &); 

// -- EXAMPLE
// -- The neighborhod operation is a random choice of two
// -- numbers i and j which permutation values should be 
// -- changed.
	void		GetNeighbor(SA_Solution &, float rel_temp);

// -- EXAMPLE
// -- A solution is reseted by setting newcost = oldcost,  
// -- i = j and resetting the permutation
	void		ResetSolution(SA_Solution &);

// -- EXAMPLE
// -- A solution is updated by setting newcost = oldcost and
// -- i = j
	void 		UpdateSolution(SA_Solution &);
	
// -- EXAMPLE
// -- The local neighborhodsize is the number of two element subsets
// -- of a n element set.
	float		GetLocalN();
// -- EXAMPLE
// -- The number of possible solutions is the number of 
// -- permutations of n elements, so n! .
	float		GetGlobalN();	

	void 		Copy(SA_Solution & source, SA_Solution & dest);		

// ----- methods for PARRALLEL SA ----------------------

//       ----- stream based communication --------------
	void		OutputSolution(std::ostream&, SA_Solution &);
	int		InputSolution(std::istream &,SA_Solution &);
			
#ifdef MPI								
//       ----- MPI based communication -----------------
	int 		BcastSolution(SA_Solution &sol, int root, MPI_Comm comm, int me_comm);
#endif

// ----- ADDITIONAL methods ----------------------------

//   ----- for using moves ... -------------------------
	SA_Move *	CreateMove();
	int		ExtractMove(SA_Solution &, SA_Move &);   
      	int             ApplyMove(SA_Solution &, SA_Move &);
	
//     ----- ...with stream based communication ---------
	void     	OutputMove(std::ostream &, SA_Move &);
	int		InputApplyMoves(std::istream &, SA_Solution &);	

#ifdef MPI
//     ----- ... with MPI based communication -----------
	int	        BcastApplyMove(SA_Solution &sol, int root, MPI_Comm comm, int me_comm);
#endif

//   ----- file-IO methods -------------------------------
	int		OutputSolution(char * filename,SA_Solution & sol);
	int		InputSolution(char * filename,SA_Solution & sol);
											// Liefert Anzahl der Durchgefuehrten Schritten oder 0, falls Fehler 												
//   ----- service methods for more complex applications -
	void            Postprocessing(SA_Solution &);
	int		Reoptimize(SA_Solution &);	
	void		ControlOutput(std::ostream & out = std::cout);

       public:
// -- EXAMPLE
// -- example data consists of two twodimensional Array A and B 
// -- representing the matrices A and B, the matrixsize n and
// -- - to save computation time - the values of LocalN and
// -- GlobalN because they depend only on n.   

//	MELEMTYPE ***A;
//	MELEMTYPE ***B;
	MELEMTYPE A[300][300];
	MELEMTYPE B[300][300];
	int n;
	float globaln,localn;

};

#endif