/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
 /*                                                                           */
 /*                  This file is part of the program and library             */
 /*         SCIP --- Solving Constraint Integer Programs                      */
 /*                                                                           */
#include "stdafx.h"


/* standard library includes */
#include <stdio.h>

/* scip includes */
#include "objscip/objscip.h"
#include "objscip/objscipdefplugins.h"

#include <assert.h>

#include "Branching.h"

#include "scip/branch_relpscost.h"
#include <vector>

using namespace std;
using namespace scip;

#include <iostream>
#include <string>


#define BRANCHRULE_NAME            "multinode"
#define BRANCHRULE_DESC            "multinode branching creates a child for every variable of a setpartitioning constraint"
#define BRANCHRULE_PRIORITY        10000000
#define BRANCHRULE_MAXDEPTH        -1
#define BRANCHRULE_MAXBOUNDDIST    1.0

/*
 * Local methods
 */

static Branching* pThis = NULL;

Branching::Branching(
	SCIP*                   scip,							/**< SCIP pointer */
	Pricer*			_objPricer,						/**< pricer pointer */
	double					_eps
) :
	ObjBranchrule(scip, "branch rule", "branch rule", 1, -1, 1.0),
	objPricer(_objPricer),
	eps(_eps)

{
	startCustomerId = -1;
	endCustomerId = -1;
	branchCandidate = 0;
	pThis = this;
}





/* put your local methods here, and declare them static */

/** get the branching candidate variables for arc branching */
bool Branching::findArcBranchCand(
	SCIP*					scip							/**< SCIP data structure */
)
{
	setStartCustomerId(-1);
	setEndCustomerId(-1);

	// Calculate arc values
	vector<vector<double>> edgeValues(getNumberOfNodes());
	for (int i = 0; i < getNumberOfNodes(); i++)
	{
		edgeValues[i].resize(getNumberOfNodes());
	}
	vector<Variable>* vars = getPricer()->getVariables();
	for (int i = 0; i < vars->size(); i++)
	{
		for (int j = 0; j < (*vars)[i].getOrder().size() - 1; j++)
		{
			if (getPricer()->edgeContained((*vars)[i].getOrder()[j],(*vars)[i].getOrder()[j + 1])) 
			{
				edgeValues[(*vars)[i].getOrder()[j]][(*vars)[i].getOrder()[j + 1]] += SCIPvarGetLPSol((*vars)[i].getVariable());
			}

		}
	}

	double minGap = 0.5;
	for (int i = 0; i < getNumberOfNodes(); i++)
	{

		for (int j = 0; j < getNumberOfNodes(); j++)
		{
			if (i != j)
			{
				if (!(edgeValues[i][j] <getEps() || edgeValues[i][j] >(1 - getEps())))
				{
					double tempGap = 0;
					edgeValues[i][j] - 0.5 > 0 ? tempGap = edgeValues[i][j] - 0.5 : tempGap = 0.5 - edgeValues[i][j];
					if (minGap > tempGap)
					{
						minGap = tempGap;
						setStartCustomerId(i);
						setEndCustomerId(j);
					}
				}
			}

		}
	}
	if (getStartCustomerId() != -1 && getEndCustomerId() != -1) {
		return true;
	}
	else {
		cout << "no arc Branching con" << endl;
		return false;
	}

	return false;
}

void cloneAdditionalBranchingConsStruct(BranchingConstraints* original, BranchingConstraints* clone) {
	for (vector<ArcBranchingConstraints>::iterator it = original->getArcBranchingConstraints()->begin(); it != original->getArcBranchingConstraints()->end(); it++) {
		clone->getArcBranchingConstraints()->push_back(*it);
	}
}

/** branch on an Arc */

SCIP_RETCODE Branching::branchArc(
	SCIP*               scip				/**< SCIP data structure */
)
{
	int currNode = (int)SCIPnodeGetNumber(SCIPgetCurrentNode(scip));
	BranchingConstraints* bC(0);
	for (int i = 0; i < getPricer()->getBranchingConstraintsAtANode()->size(); i++)
	{
		if (currNode == (*getPricer()->getBranchingConstraintsAtANode())[i].getNodeNumber())
		{
			bC = &(*(getPricer()->getBranchingConstraintsAtANode()))[i];
			break;
		}
	}

	// Find all variables that have start and end customer
	vector<Variable> variables;

	int iDStartCustomer = getStartCustomerId();
	int iDEndCustomer = getEndCustomerId();
	vector<Variable>* vars = getPricer()->getVariables();

	//	priority = SCIPcalcNodeselPriority(scip, binvars[row][k], SCIP_BRANCHDIR_UPWARDS, 1.0);
//	estimate = SCIPcalcChildEstimate(scip, binvars[row][k], 1.0);

	SCIP_Node* nodeU;
	SCIP_Node* nodeL;


	int parentId = (int)SCIPnodeGetNumber(SCIPgetCurrentNode(scip));
	// Create upper & lower child
	double prio = 1.0;
	
	SCIP_CALL(SCIPcreateChild(scip, &nodeU, prio, 1.0));
	int childUId = (int)SCIPnodeGetNumber(nodeU);

	SCIP_CALL(SCIPcreateChild(scip, &nodeL, prio, 1.0));
	int childLId = (int)SCIPnodeGetNumber(nodeL);


	vector<BranchingConstraints>* branchingCons = getBranchingCons();
	BranchingConstraints additionalBranchingConsUpper(childUId);
	cloneAdditionalBranchingConsStruct(bC, &additionalBranchingConsUpper);

	BranchingConstraints additionalBranchingConsLower(childLId);
	cloneAdditionalBranchingConsStruct(bC, &additionalBranchingConsLower);

	if ((*getPricer()->getUpperArcBranchingCons())[iDStartCustomer][iDEndCustomer].getIdStartCustomer() == -1 &&
		(*getPricer()->getLowerArcBranchingCons())[iDStartCustomer][iDEndCustomer].getIdStartCustomer() == -1
		)
	{
		for (int i = 0; i < vars->size(); i++)
		{
			if ((*vars)[i].getOrder().size() != 1)
			{
				for (int j = 0; j < (*vars)[i].getOrder().size() - 1; j++)
				{
					if ((*vars)[i].getOrder()[j] == iDStartCustomer && (*vars)[i].getOrder()[j + 1] == iDEndCustomer)
					{
						variables.push_back((*vars)[i]);
						break;
					}
				}
			}
		}

		SCIP_CONS* conU;
		char con_name[255];

		//	(void)SCIPsnprintf(con_name, 255, "u"+ getCustomerId());
		(void)SCIPsnprintf(con_name, 255, "arc_u_%d_%d", iDStartCustomer, iDEndCustomer);


		SCIP_CALL(SCIPcreateConsBasicSetcover(scip, &conU, con_name, 0, NULL));
		// declare constraint modifiable for adding variables during pricing 
		SCIP_CALL(SCIPsetConsModifiable(scip, conU, TRUE));
		SCIP_CALL(SCIPsetConsLocal(scip, conU, TRUE));

		for (int i = 0; i < variables.size(); i++)
		{
			SCIP_CALL(SCIPaddCoefSetppc(scip,conU,variables[i].getVariable()));
		}

		SCIPaddConsNode(scip, nodeU, conU, NULL);
		ArcBranchingConstraints arcBranchingConUpper(iDStartCustomer, iDEndCustomer, true, conU);
		additionalBranchingConsUpper.getArcBranchingConstraints()->push_back(arcBranchingConUpper);
		getPricer()->setUpperArcBranchingCon(arcBranchingConUpper);
		getPricer()->addBranchingConstraintsAtANode(&additionalBranchingConsUpper);
		SCIP_CONS* conL;
		(void)SCIPsnprintf(con_name, 255, "arc_l_%d_%d", iDStartCustomer, iDEndCustomer);

		SCIP_CALL(SCIPcreateConsLinear(scip, &conL, con_name,
			0,						/* n vars*/
			0,						/* vars */
			0,						/* vals */
			0.0,					/* lhs */
			SCIPinfinity(scip),		/* rhs */
			true,                   /* initial */
			true,					/* separate */
			true,                   /* enforce */
			true,                   /* check */
			true,                   /* propagate */
			true,					/* local */
			true,                   /* modifiable */
			false,                  /* dynamic */
			false,                  /* removable */
			false));               /* stickingatnode ??? */

		for (int i = 0; i < variables.size(); i++)
		{
			SCIP_CALL(SCIPaddCoefLinear(scip, conL, variables[i].getVariable(), -1.0));
		}

		SCIPaddConsNode(scip, nodeL, conL, NULL);


		ArcBranchingConstraints arcBranchingConLower(iDStartCustomer, iDEndCustomer, false, conL);
		additionalBranchingConsLower.getArcBranchingConstraints()->push_back(arcBranchingConLower);
		getPricer()->setLowerArcBranchingCon(arcBranchingConLower);
		getPricer()->addBranchingConstraintsAtANode(&additionalBranchingConsLower);
	}
	else
	{

		SCIPaddConsNode(scip, nodeU, (*getPricer()->getUpperArcBranchingCons())[iDStartCustomer][iDEndCustomer].getCon(), NULL);
		additionalBranchingConsUpper.getArcBranchingConstraints()->push_back((*getPricer()->getUpperArcBranchingCons())[iDStartCustomer][iDEndCustomer]);
		getPricer()->addBranchingConstraintsAtANode(&additionalBranchingConsUpper);

		SCIPaddConsNode(scip, nodeL, (*getPricer()->getLowerArcBranchingCons())[iDStartCustomer][iDEndCustomer].getCon(), NULL);
		additionalBranchingConsLower.getArcBranchingConstraints()->push_back((*getPricer()->getLowerArcBranchingCons())[iDStartCustomer][iDEndCustomer]);
		getPricer()->addBranchingConstraintsAtANode(&additionalBranchingConsLower);
	}

	branchingCons->push_back(additionalBranchingConsUpper);
	branchingCons->push_back(additionalBranchingConsLower);

	return SCIP_OKAY;
}
/*
 * Callback methods of branching rule
 */



 /** copy method for branchrule plugins (called when SCIP copies plugins) */
SCIP_DECL_BRANCHCOPY(Branching::scip_copy)
{  /*lint --e{715}*/
	SCIPerrorMessage("method of xyz branching rule not implemented yet\n");
	SCIPABORT(); /*lint --e{527}*/

	return SCIP_OKAY;
}

/** destructor of branching rule to free user data (called when SCIP is exiting) */
SCIP_DECL_BRANCHFREE(Branching::scip_free)
{  /*lint --e{715}*/
	SCIPerrorMessage("method of xyz branching rule not implemented yet\n");
	SCIPABORT(); /*lint --e{527}*/

	return SCIP_OKAY;
}

/** initialization method of branching rule (called after problem was transformed) */
SCIP_DECL_BRANCHINIT(Branching::scip_init)
{  /*lint --e{715}*/
	SCIPerrorMessage("method of xyz branching rule not implemented yet\n");
	SCIPABORT(); /*lint --e{527}*/

	return SCIP_OKAY;
}

/** deinitialization method of branching rule (called before transformed problem is freed) */
SCIP_DECL_BRANCHEXIT(Branching::scip_exit)
{  /*lint --e{715}*/
	SCIPerrorMessage("method of xyz branching rule not implemented yet\n");
	SCIPABORT(); /*lint --e{527}*/

	return SCIP_OKAY;
}


/** solving process initialization method of branching rule (called when branch and bound process is about to begin) */
SCIP_DECL_BRANCHINITSOL(Branching::scip_initsol)
{  /*lint --e{715}*/
	SCIPerrorMessage("method of xyz branching rule not implemented yet\n");
	SCIPABORT(); /*lint --e{527}*/

	return SCIP_OKAY;
}

/** solving process deinitialization method of branching rule (called before branch and bound process data is freed) */
SCIP_DECL_BRANCHEXITSOL(Branching::scip_exitsol)
{  /*lint --e{715}*/
	SCIPerrorMessage("method of xyz branching rule not implemented yet\n");
	SCIPABORT(); /*lint --e{527}*/

	return SCIP_OKAY;
}

/** branching execution method for external candidates */
SCIP_DECL_BRANCHEXECEXT(Branching::scip_execext)
{  /*lint --e{715}*/
	SCIPerrorMessage("method of xyz branching rule not implemented yet\n");
	SCIPABORT(); /*lint --e{527}*/

	return SCIP_OKAY;
}

/** branching execution method for not completely fixed pseudo solutions */
SCIP_DECL_BRANCHEXECPS(Branching::scip_execps)
{  /*lint --e{715}*/
	SCIPerrorMessage("method of xyz branching rule not implemented yet\n");
	SCIPABORT(); /*lint --e{527}*/

	return SCIP_OKAY;
}

/** branching execution method for fractional LP solutions */
SCIP_DECL_BRANCHEXECLP(Branching::scip_execlp)
{


	findArcBranchCand(scip);


	branchArc(scip);


	return SCIP_OKAY;
}

/** branching execution method for fractional LP solutions */
SCIP_DECL_BRANCHEXECLP(scip_execlp)
{


	if (pThis->findArcBranchCand(scip)) {
		pThis->branchArc(scip);
		*result = SCIP_BRANCHED;
		return SCIP_OKAY;
	}
	else
	{
		cout << "No node or arc branching candidate";
		exit(1);
		*result = SCIP_DIDNOTRUN;
		// IMPLEMENT BRANCH METHOD
	}

	return SCIP_OKAY;
}



/*
 * branching rule specific interface methods
 */

 /** creates the mutlinode branching rule and includes it in SCIP */
SCIP_RETCODE SCIPincludeBranchruleMyBranchRule2(SCIP * scip)
{
	SCIP_BRANCHRULEDATA* branchruledata;
	SCIP_BRANCHRULE* branchrule = NULL;

	branchruledata = NULL;

	/* include branching rule */
	/* use SCIPincludeBranchruleBasic() plus setter functions if you want to set callbacks one-by-one
	 * and your code should compile independent of new callbacks being added in future SCIP versions
	 */
	SCIP_CALL(SCIPincludeBranchruleBasic(scip, &branchrule, "BranchRule", "Meine Branch rule", 100000,
		-1, 1.0, branchruledata));

	/* set non fundamental callbacks via setter functions */
//	SCIP_CALL(SCIPsetBranchruleCopy(scip, branchrule, scip_copy));
//	SCIP_CALL(SCIPsetBranchruleFree(scip, branchrule, branchFreeXyz));
//	SCIP_CALL(SCIPsetBranchruleInit(scip, branchrule, branchInitXyz));
//	SCIP_CALL(SCIPsetBranchruleExit(scip, branchrule, branchExitXyz));
//	SCIP_CALL(SCIPsetBranchruleInitsol(scip, branchrule, branchInitsolXyz));
//	SCIP_CALL(SCIPsetBranchruleExitsol(scip, branchrule, branchExitsolXyz));
	SCIPsetBranchruleExecLp(scip, branchrule, scip_execlp);
	//	SCIP_CALL(SCIPsetBranchruleExecExt(scip, branchrule, scip_execext));


	assert(branchrule != NULL);

	return SCIP_OKAY;
}

SCIP_RETCODE Branching::SCIPincludeBranchruleMyBranchRule(SCIP * scip)
{
	SCIPincludeBranchruleMyBranchRule2(scip);
	return SCIP_OKAY;
}