Select Git revision
select-dataset.component.html
Code owners
Assign users and groups as approvers for specific file changes. Learn more.
relax_lagr.cpp 40.24 KiB
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/* */
/* This file is part of the program and library */
/* SCIP --- Solving Constraint Integer Programs */
/* */
/* Copyright (C) 2002-2020 Konrad-Zuse-Zentrum */
/* fuer Informationstechnik Berlin */
/* */
/* SCIP is distributed under the terms of the ZIB Academic License. */
/* */
/* You should have received a copy of the ZIB Academic License */
/* along with SCIP; see the file COPYING. If not visit scipopt.org. */
/* */
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/**@file relax_lagr.c
* @ingroup OTHER_CFILES
* @brief lagr relaxator
* @author Dawit Hailu
*/
/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
//I'm gonna write this, just to check if it will upload right or not :)
//what's up bro, this is just to check if i can pull it on git.
//it worked buddy. now time to push it
#include <assert.h>
#include <string.h>
#include <chrono>
#include <iostream>
#include <math.h>
#include "relax_lagr.h"
#include "scip/scipdefplugins.h"
#include "scip/scip.h"
#include "scip/cons_countsols.c"
#include "probdata_lagr.h"
#include "vardata_lagr.h"
#define RELAX_NAME "lagr"
#define RELAX_DESC "relaxator template"
#define RELAX_PRIORITY 0
#define RELAX_FREQ 0
/*
* Data structures
*/
/* TODO: fill in the necessary relaxator data */
/** relaxator data */
struct SCIP_RelaxData
{
SCIP_SOL* sol; /**current solution(working solution)*/
SCIP_VARDATA* vardata;
SCIP_CONSDATA* consdata;
SCIP_Real* bestsolvals;
SCIP_Real* feasiblesol;
SCIP_Real* upperbound;
};
struct SCIP_VarData{
SCIP_VAR* var;
SCIP_CONS** VarConss;
int nVarConss;
SCIP_CONS** VarSlotConss; /**<contains all slot constraints containing the variable */
int NVarInBadConss; /**<number of slot constraints the variable is occuring in*/
SCIP_Real varquotient;
int* consids;
int* varids;
};
/** destructor of relaxator to free user data (called when SCIP is exiting) */
static
SCIP_DECL_RELAXFREE(relaxFreelagr)
{ /*lint --e{715}*/
SCIPerrorMessage("start executing lagr\n");
SCIP_RELAXDATA* relaxdata;
relaxdata = SCIPrelaxGetData(relax);
SCIPfreeBlockMemory(scip, &relaxdata);
SCIPrelaxSetData(relax,NULL);
return SCIP_OKAY;
}
/** initialization method of relaxator (called after problem was transformed) */
int SCIPvardataGetNVarInBadConss(
SCIP_VARDATA* vardata /**< variable data */
)
{
return vardata->NVarInBadConss;
}
int* SCIPvardataGetvarids(
SCIP_VARDATA* vardata /**< variable data */
)
{
return vardata->varids;
}
static
SCIP_DECL_RELAXINIT(relaxInitlagr)
{ /*lint --e{715}*/
SCIP* relaxscip;
SCIP_HASHMAP* varmap;
SCIP_HASHMAP* consmap;
SCIP_CONS** conss;
SCIP_PROBDATA* probdata;
SCIP_VARDATA* vardata;
SCIP_Real relaxval;
SCIP_Bool valid;
int nconss;
int i;
int counter;
int id;
// *lowerbound = -SCIPinfinity(scip);
// *result = SCIP_DIDNOTRUN;
/* we can only run if none of the present constraints expect their variables to be binary or integer during transformation */
conss = SCIPgetConss(scip);
nconss = SCIPgetNConss(scip);
/* create the variable mapping hash map */ SCIP_CALL( SCIPcreate(&relaxscip) );
SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(relaxscip), SCIPgetNVars(scip)) );
valid = FALSE;
SCIP_CALL( SCIPcopy(scip, relaxscip, varmap, consmap, "relaxscip", FALSE, FALSE, FALSE, FALSE, &valid) );
/**************************************************************************************************************/
/*First, */
//*the probdata: where we get to identify the bad constraint we want to formulate(in our case, the slot conss) */
/***************************************************************************************************************/
int nvars = SCIPgetNVars(relaxscip);
SCIP_VAR** vars = SCIPgetVars(relaxscip);
SCIP_VAR** varbuffers;
int* badconss;
SCIPcreateprobdata(relaxscip,&probdata,SCIPgetConss(relaxscip),vars,&varbuffers,&badconss); /*will be used to identify the # of slot(bad) constraints*/
int nSlotConss = SCIPgetNSlotConss(probdata); //number of bad(slot) constraint
int allnconsvars = SCIPgetallnconsvars(probdata); //sum of all nconsvars, used for creating later on an array to collect the list of varids in each row
int* listnconsvars = SCIPlistnconsvars(probdata);
int* listconsvarids = SCIPlistconsvarids(probdata);
/* we then create the vardata function for each variable, to see at which constraint the variable is found*/
FILE* TimeCollector;
TimeCollector = fopen("time.txt","w");
SCIP_CLOCK* varslottime; //to help us record the time
SCIP_CALL( SCIPcreateClock(relaxscip, &varslottime) ); //* start time counting*
SCIP_CALL(SCIPstartClock(relaxscip,varslottime));
SCIP_CLOCK* totaliteration; //to help us record the time
SCIP_CALL( SCIPcreateClock(relaxscip, &totaliteration) ); //* start time counting*
int* consids;
SCIP_Real* weights;
SCIP_CALL(SCIPallocBufferArray(relaxscip,&weights,nvars));
SCIP_CALL(SCIPallocBufferArray(relaxscip,&consids,nSlotConss));
SCIP_Real maxobj=0;
for (int v = 0; v < nvars; v++)
{
SCIP_VAR* var = vars[v];
weights[v]=SCIPvarGetObj(var);
if(maxobj<weights[v]){maxobj=weights[v];}
}
for (int v = 0; v < nvars; v++)
{
int* varids;
int NVarInBadConss=0;
int nconsvars = 0;
SCIP_VAR* var = vars[v];
int varindex = SCIPvarGetIndex(var); /* (2) */
assert(varindex!= NULL);
for (int r = 0; r < nSlotConss; ++r)
{
id = badconss[r];
SCIP_CONS* cons = SCIPgetConss(relaxscip)[id];
// printf("%s \t",SCIPconsGetName(cons));
SCIP_CALL(SCIPgetConsNVars(relaxscip, cons, &nconsvars, &valid));
SCIP_CALL(SCIPgetConsVars(relaxscip, cons, varbuffers, nconsvars, &valid));
if (!valid){abort(); }
for (int j = 0; j < nconsvars; ++j) /* (8) */
{
SCIP_VAR* varx = varbuffers[j]; int varbufindex = SCIPvarGetIndex(varx);
assert(varbufindex != NULL);
// printf("%s\t \t%d",SCIPvarGetName(varx),varbufindex);
/** if var[i] is in cons[c], write conspointer in VarConss and increase nVarConsscounter */
if (varindex == varbufindex) /* (9) */
{
// VarSlotConss[NVarInBadConss] = cons;
consids[NVarInBadConss]=id;
NVarInBadConss++;
// printf(" %s \t,",SCIPconsGetName(cons));
}
}
}
SCIP_CALL(SCIPallocBufferArray(relaxscip, &varids, NVarInBadConss));
for(int t=0;t<NVarInBadConss;t++)
{
varids[t]=consids[t];
// printf("%d \t",varids[t]);
}
// // vardata=SCIPvarGetData(var);
SCIP_CALL(SCIPallocBlockMemory(scip , &vardata));
SCIP_CALL(SCIPduplicateBlockMemoryArray(scip, &(vardata->varids), varids, NVarInBadConss));
vardata->NVarInBadConss = NVarInBadConss; /**copy nVarConss to VarData */
vardata->varids = varids;
// /**set the variable data to the variable*/
SCIPvarSetData(var,vardata);
}
SCIP_CALL(SCIPstopClock(relaxscip,varslottime));
FILE* AfterPreProcessing;
AfterPreProcessing = fopen("AfterPreProcessing.txt","w+");
// SCIP_CALL(SCIPprintOrigProblem(relaxscip, AfterPreProcessing, "lp", FALSE));
SCIPinfoMessage(relaxscip, TimeCollector, "\n row and column identified in (sec) : %f\n", SCIPgetClockTime(relaxscip, varslottime));
for(int r=0;r<nSlotConss;r++)
{
id = badconss[r];
SCIP_CONS* cons = SCIPgetConss(relaxscip)[id];
SCIP_CALL(SCIPdelCons(relaxscip,cons));
}
/******************************************************************************************************************/
/*Next, we will do the initial iteration of finding the dual mulpliers of each slot conss, and their sum(dualsum) */
/* In the end, we will subtract this sum from the objective of the function. */
/* It's initial, because while we would search for more dual multipliers to solve the Lagrangian relaxation */
/******************************************************************************************************************/
SCIP_Real* dualmultipliers;
SCIP_CALL(SCIPallocBufferArray(relaxscip,&dualmultipliers,nSlotConss));
SCIP_Real* subgradients;
SCIP_CALL(SCIPallocBufferArray(relaxscip,&subgradients,nSlotConss));
//initialize subgradients;
SCIP_Real stepsize = 15;
SCIP_Real sumofduals=0;
for ( int r = 0; r < nSlotConss; ++r)
{
dualmultipliers[r] = 0;
sumofduals+=dualmultipliers[r]; //adds the negative of the minimum in each iteration
}
// /*******************************************************************************************************/
// /* The reformulation of the problem can be written as follows */
// //*>>>>>>>>>>>>>>>>>> min sum { (w[i]+sum{dual[j]})}x[i]-sum{dual[r]} <<<<<<<<<<<< */
// /*where i is nvars, j is NVarInBadConss, and r is nSlotConss for our case *******************************/
// /****************************************************************************************************************/
// /* The following function will add the following to the obj(weight) of the variable, */
// //* the obj(weight) of var + the sum of the dualmultipliers of bad constraints which contains this variable */
// /****************************************************************************************************************/
FILE* solutions;
solutions = fopen("sol.txt","wr");
FILE* dual;
dual= fopen("dual.txt","wr");
FILE* variableinfo;
variableinfo = fopen("var.txt","wr");
FILE* subgrad;
subgrad = fopen("subgrads.txt","wr");
FILE* varobjects;
varobjects=fopen("varobjs.txt","wr");
FILE* lower;
lower=fopen("lowerbounds.txt","wr");
FILE* iter;
iter=fopen("iter.txt","wr");
<<<<<<< HEAD
//fprintf(lower, "hi");
=======
fprintf(lower, "hi");
>>>>>>> 3d92d06a76cc6c4667871c4c3b4d0e3184fc9a3b
SCIP_Real* solvals;
SCIP_CALL(SCIPallocBufferArray(relaxscip,&solvals,nvars+2));
solvals[nvars+1]=0; //for last solutions
solvals[nvars]=0; //for best solution
<<<<<<< HEAD
int maxiter=1500;
=======
int maxiter=12;
>>>>>>> 3d92d06a76cc6c4667871c4c3b4d0e3184fc9a3b
int oscilatecounter=0;
int improvementcounter = 0;
SCIP_Real oscilator1=0;
SCIP_Real oscilator2=0;
SCIP_Real forcompare = -1000000000000000000;
SCIP_CALL(SCIPstartClock(relaxscip,totaliteration));
for(int iter=1;iter<=maxiter;iter++)
{
for(int v=0;v<nvars;v++)
{
SCIP_VAR* var = vars[v];
double sum =0;
vardata=SCIPvarGetData(var);
int* varids = SCIPvardataGetvarids(vardata);
assert(varids=!NULL);
int NVarInBadConss = SCIPvardataGetNVarInBadConss(vardata);
// if(NVarInBadConss==0){SCIPsetSolVal(relaxscip,) break;}
// else
// {
// SCIP_CALL(SCIPprintOrigProblem(relaxscip, AfterPreProcessing, "lp", FALSE));
// fprintf(varobjects,"%s \n",SCIPvarGetName(var));
for(int t=0;t<NVarInBadConss;t++)
{
sum += dualmultipliers[varids[t]];
// fprintf(varobjects,"{id = %d, dual = %f, sum = %f\t",varids[t], dualmultipliers[varids[t]],sum); }
// fprintf(varobjects,"}\n\n");
SCIP_CALL(SCIPaddVarObj(relaxscip,var,sum));
// }
}
SCIPinfoMessage(relaxscip, TimeCollector, "\n finished changing the variable's weight after (sec) : %f\n", SCIPgetClockTime(relaxscip, totaliteration));
SCIP_CALL(SCIPaddOrigObjoffset(relaxscip,-1*sumofduals));
<<<<<<< HEAD
//SCIP_CALL(SCIPprintOrigProblem(relaxscip, AfterPreProcessing, "lp", FALSE));
=======
SCIP_CALL(SCIPprintOrigProblem(relaxscip, AfterPreProcessing, "lp", FALSE));
>>>>>>> 3d92d06a76cc6c4667871c4c3b4d0e3184fc9a3b
SCIPsetMessagehdlrQuiet(relaxscip, TRUE);
// fclose(AfterPreProcessing);
SCIP_CALL( SCIPtransformProb(relaxscip) );
SCIP_CALL( SCIPsolve(relaxscip) );
relaxval = SCIPgetPrimalbound(relaxscip);
//printf("\ndualbound %f \n",SCIPgetDualbound(relaxscip));
fprintf(lower,"%f\n",SCIPgetPrimalbound(relaxscip));
SCIPdebugMessage("relaxation bound = %e status = %d\n", relaxval, SCIPgetStatus(relaxscip));
/*store the highest lower bound*/
if(solvals[nvars]<SCIPgetPrimalbound(relaxscip)){solvals[nvars]=SCIPgetPrimalbound(relaxscip);}
fprintf(variableinfo,"%f\n",solvals[nvars]);
/*make sure we're not oscilating by adding a counter, which checks the absolute value between the difference of the previous few steps and make sure it's not the same. */
oscilator2=abs(solvals[nvars+1]-SCIPgetPrimalbound(relaxscip));
if(oscilator1==oscilator2){oscilatecounter++;}
else{oscilator1=oscilator2; oscilatecounter==0;}
//if(oscilatecounter==5){printf("repetition"); break;}
//printf("dprev.sol=%f, current=%f, difference %f, coutner=%d, ",solvals[nvars+1],SCIPgetPrimalbound(relaxscip), oscilator2, oscilatecounter);
/*store the solution on the last entry of solvals, so we can compare it in the next round for repetitions*/
solvals[nvars+1]=SCIPgetPrimalbound(relaxscip);
/*breaking criteria for iterations*/
if(solvals[nvars]>forcompare){forcompare=solvals[nvars]; improvementcounter=0;}
else{improvementcounter++;}
//if(improvementcounter==10){break; fprintf(variableinfo,"%d\n",iter);}
printf("terminator %d",improvementcounter);
/*get the best solution*/
SCIP_SOL* bestsol = SCIPgetBestSol(relaxscip) ;
SCIP_SOL** sols = SCIPgetSols(relaxscip);
int nsols = SCIPgetNSols(relaxscip);
<<<<<<< HEAD
//fprintf(lower,"%d iteration \n",iter);
for(int n=0; n<nsols; n++)
{
//SCIP_CALL(SCIPprintSol(relaxscip,sols[n],lower,FALSE));
=======
fprintf(lower,"%d iteration \n",iter);
for(int n=0; n<nsols; n++)
{
SCIP_CALL(SCIPprintSol(relaxscip,sols[n],lower,FALSE));
>>>>>>> 3d92d06a76cc6c4667871c4c3b4d0e3184fc9a3b
}
/*text output*/
//SCIPinfoMessage(relaxscip, TimeCollector, "\n first iteration: problem solved after (sec) : %f\n", SCIPgetClockTime(relaxscip, totaliteration)); fprintf(solutions,"number of solutions %d, first iteration \t bound=%f, \t objsol=%f \n",nsols, SCIPgetPrimalbound(relaxscip),relaxval);
// SCIP_CALL(SCIPprintBestSol(relaxscip,solutions,FALSE));
/*store the solution in solvals so we can later export it to subgradient function*/
SCIP_Real lowerbound=0;
SCIPgetSolVals(relaxscip,bestsol,nvars,vars,solvals);
//SCIP_CALL(SCIPprintSol(relaxscip,bestsol,dual,FALSE));
SCIP_Real compare=0;
for (int v = 0; v<nvars; ++v)
{
compare += solvals[v]*weights[v];
}
//stepsize = (stepsize+iter)/double(iter+1);
// fprintf(solutions, "\niteration %d\n",iter);
// fprintf(dual, "\niteration %d\n",iter);
// fprintf(variableinfo, "\niteration %d\n",iter);
// fprintf(varobjects, "\niteration %d\n",iter);
SCIP_CALL(SCIPaddOrigObjoffset(relaxscip,sumofduals));
// SCIP_CALL( SCIPfreeTransform(relaxscip) );
// SCIP_CALL( SCIPtransformProb(relaxscip) );
counter = 0;
int checker = 0;
for(int r=0; r<nSlotConss;++r)
{
id = badconss[r];
double ax=-1;
for(int s=counter;s<(counter+listnconsvars[r]);++s)
{
// printf("%s->",SCIPvarGetName(vars[listconsvarids[s]]));
ax+=SCIPgetSolVal(relaxscip,bestsol,vars[listconsvarids[s]]);
// fprintf(subgrad,"%s\t,%f\t, sum %f",SCIPvarGetName(vars[listconsvarids[s]]),SCIPgetSolVal(relaxscip,bestsol,vars[listconsvarids[s]]),ax);
}
counter += listnconsvars[r];
if(ax>0){checker++;}
subgradients[r]=ax;
// fprintf(subgrad, "\n subgrad = %f \t",subgradients[r]);
}
/*breaking condition on finding a feasible solution*/
if(checker==0){printf("#*#*#*result found\n"); break;}
SCIP_CALL( SCIPfreeTransform(relaxscip) );
SCIP_CALL( SCIPtransformProb(relaxscip) );
for (int v = 0; v<nvars; ++v)
{
SCIP_VAR* var = vars[v];
SCIP_CALL(SCIPchgVarObj(relaxscip,var,weights[v]));
// fprintf(variableinfo,"(%s,%f,%f)->%f\n",SCIPvarGetName(var),solvals[v],SCIPvarGetObj(var), weights[v]);
lowerbound += solvals[v]*weights[v];
}
// fprintf(dual,"dualbound = %f, lowerbound=%f, norm of subgrad %f\t",SCIPgetPrimalbound(relaxscip),lowerbound, getnorm(subgradients,nSlotConss,stepsize));
// fprintf(lower,"%f\n",lowerbound);
<<<<<<< HEAD
SCIP_Real difference = 3000000-SCIPgetPrimalbound(relaxscip); if(improvementcounter<5){stepsize = 0.25*(difference)/(getnorm(subgradients,nSlotConss,stepsize)*getnorm(subgradients,nSlotConss,stepsize));}
else{stepsize = 0.1*(difference)/(getnorm(subgradients,nSlotConss,stepsize)*getnorm(subgradients,nSlotConss,stepsize));}
//fprintf(dual,"dualbound = %f, lowerbound=%f, norm of subgrad %f\t stepsize= %f \n" ,SCIPgetPrimalbound(relaxscip),lowerbound, getnorm(subgradients,nSlotConss,stepsize), stepsize);
=======
// stepsize = (SCIPgetPrimalbound(relaxscip)-lowerbound)/getnorm(subgradients,nSlotConss,stepsize);
fprintf(dual,"dualbound = %f, lowerbound=%f, norm of subgrad %f\t stepsize= %f \n" ,SCIPgetPrimalbound(relaxscip),lowerbound, getnorm(subgradients,nSlotConss,stepsize), stepsize);
>>>>>>> 3d92d06a76cc6c4667871c4c3b4d0e3184fc9a3b
SCIP_CALL( SCIPfreeTransform(relaxscip) );
//fprintf(solutions, "lowerbound = %f \n ", lowerbound);
//SCIPinfoMessage(relaxscip, TimeCollector, "\n subgradients found after (sec) : %f\n, lowerbound = %f \n", SCIPgetClockTime(relaxscip, varslottime),lowerbound);
//add back the sum of the duals we subtracted from the main obj function
int sum=0;
sumofduals = 0;
for(int r=0; r<nSlotConss;++r)
{
dualmultipliers[r] += subgradients[r]*stepsize;
if(dualmultipliers[r]<0){dualmultipliers[r]=0;}
sumofduals+=dualmultipliers[r];
<<<<<<< HEAD
//fprintf(dual," then dual = %f step size %f, subgradient %f \n",dualmultipliers[r], stepsize,subgradients[r]);
=======
fprintf(dual," then dual = %f step size %f, subgradient %f \n",dualmultipliers[r], stepsize,subgradients[r]);
>>>>>>> 3d92d06a76cc6c4667871c4c3b4d0e3184fc9a3b
}
// sumofduals=sum;
// fprintf(dual,"iteration %d, sumofduals=%f\n",iter, sumofduals);
SCIPinfoMessage(relaxscip, TimeCollector, "%f\n", SCIPgetClockTime(relaxscip, totaliteration));
// if(checker==0){printf("solution found in %d iterations\n",iter); break;}
}
SCIPfreeTransform(relaxscip);
fclose(variableinfo);
fclose(dual);
fclose(subgrad);
fclose(varobjects);
fclose(solutions);
fclose(lower);
/* free memory */
SCIPhashmapFree(&varmap);
SCIP_CALL( SCIPfree(&relaxscip) );
return SCIP_OKAY;
}
/** deinitialization method of relaxator (called before transformed problem is freed) */
#if 0
static
SCIP_DECL_RELAXEXIT(relaxExitlagr)
{ /*lint --e{715}*/
SCIPerrorMessage("method of lagr relaxator not implemented yet\n");
SCIPABORT(); /*lint --e{527}*/
return SCIP_OKAY;
}
#else
#define relaxExitlagr NULL
#endif
/** solving process initialization method of relaxator (called when branch and bound process is about to begin) */
#if 0
static
SCIP_DECL_RELAXINITSOL(relaxInitsollagr)
{ /*lint --e{715}*/
SCIPerrorMessage("method of lagr relaxator not implemented yet\n");
SCIPABORT(); /*lint --e{527}*/
return SCIP_OKAY;
}
#else
#define relaxInitsollagr NULL
#endif
/** solving process deinitialization method of relaxator (called before branch and bound process data is freed) */
#if 0
static
SCIP_DECL_RELAXEXITSOL(relaxExitsollagr)
{ /*lint --e{715}*/
printf("hellow\n");
return SCIP_OKAY;
}
#else
#define relaxExitsollagr NULL
#endif
/** execution method of relaxator */
static
SCIP_DECL_RELAXEXEC(relaxExeclagr)
{
SCIP* relaxscip;
SCIP_HASHMAP* varmap;
SCIP_HASHMAP* consmap;
SCIP_CONS** conss;
SCIP_PROBDATA* probdata;
SCIP_VARDATA* vardata;
SCIP_Real relaxval;
SCIP_Bool valid;
int nconss;
int i;
int counter;
int id;
*lowerbound = -SCIPinfinity(scip);
*result = SCIP_DIDNOTRUN;
/* we can only run if none of the present constraints expect their variables to be binary or integer during transformation */
conss = SCIPgetConss(scip);
nconss = SCIPgetNConss(scip);
/* create the variable mapping hash map */
SCIP_CALL( SCIPcreate(&relaxscip) );
SCIP_CALL( SCIPhashmapCreate(&varmap, SCIPblkmem(relaxscip), SCIPgetNVars(scip)) );
valid = FALSE;
SCIP_CALL( SCIPcopy(scip, relaxscip, varmap, consmap, "relaxscip", FALSE, FALSE, FALSE, FALSE, &valid) );
// /**************************************************************************************************************/
// /*First, */
// //*the probdata: where we get to identify the bad constraint we want to formulate(in our case, the slot conss) */
// /***************************************************************************************************************/
// int nvars = SCIPgetNVars(relaxscip);
// SCIP_VAR** vars = SCIPgetVars(relaxscip);
// SCIP_VAR** varbuffers; // int* badconss;
// SCIPcreateprobdata(relaxscip,&probdata,SCIPgetConss(relaxscip),vars,&varbuffers,&badconss); /*will be used to identify the # of slot(bad) constraints*/
// int nSlotConss = SCIPgetNSlotConss(probdata); //number of bad(slot) constraint
// int allnconsvars = SCIPgetallnconsvars(probdata); //sum of all nconsvars, used for creating later on an array to collect the list of varids in each row
// int* listnconsvars = SCIPlistnconsvars(probdata);
// int* listconsvarids = SCIPlistconsvarids(probdata);
// /* we then create the vardata function for each variable, to see at which constraint the variable is found*/
// FILE* TimeCollector;
// TimeCollector = fopen("time.txt","w");
// SCIP_CLOCK* varslottime; //to help us record the time
// SCIP_CALL( SCIPcreateClock(relaxscip, &varslottime) ); //* start time counting*
// SCIP_CALL(SCIPstartClock(relaxscip,varslottime));
// // int nconsvars=0;
// int* consids;
// SCIP_Real* weights;
// SCIP_CALL(SCIPallocBufferArray(relaxscip,&weights,nvars));
// SCIP_CALL(SCIPallocBufferArray(relaxscip,&consids,nSlotConss));
// for (int v = 0; v < nvars; v++)
// {
// SCIP_VAR* var = vars[v];
// weights[v]=SCIPvarGetObj(var);
// }
// for (int v = 0; v < nvars; v++)
// {
// int* varids;
// int NVarInBadConss=0;
// int nconsvars = 0;
// SCIP_VAR* var = vars[v];
// int varindex = SCIPvarGetIndex(var); /* (2) */
// assert(varindex!= NULL);
// // printf("%s****%d\n",SCIPvarGetName(var),varindex);
// for (int r = 0; r < nSlotConss; ++r)
// {
// id = badconss[r];
// SCIP_CONS* cons = SCIPgetConss(relaxscip)[id];
// // printf("%s \t",SCIPconsGetName(cons));
// SCIP_CALL(SCIPgetConsNVars(relaxscip, cons, &nconsvars, &valid));
// SCIP_CALL(SCIPgetConsVars(relaxscip, cons, varbuffers, nconsvars, &valid));
// if (!valid){
// abort(); }
// for (int j = 0; j < nconsvars; ++j) /* (8) */
// {
// SCIP_VAR* varx = varbuffers[j];
// int varbufindex = SCIPvarGetIndex(varx);
// assert(varbufindex != NULL);
// // printf("%s\t \t%d",SCIPvarGetName(varx),varbufindex);
// /** if var[i] is in cons[c], write conspointer in VarConss and increase nVarConsscounter */
// if (varindex == varbufindex) /* (9) */
// {
// // VarSlotConss[NVarInBadConss] = cons;
// consids[NVarInBadConss]=id;
// NVarInBadConss++;
// // printf(" %s \t,",SCIPconsGetName(cons));
// }
// }
// }
// SCIP_CALL(SCIPallocBufferArray(relaxscip, &varids, NVarInBadConss));
// for(int t=0;t<NVarInBadConss;t++)
// {
// varids[t]=consids[t];
// // printf("%d \t",varids[t]);
// }
// // vardata=SCIPvarGetData(var);
// SCIP_CALL(SCIPallocBlockMemory(scip , &vardata));
// SCIP_CALL(SCIPduplicateBlockMemoryArray(scip, &(vardata->varids), varids, NVarInBadConss));
// vardata->NVarInBadConss = NVarInBadConss; /**copy nVarConss to VarData */
// vardata->varids = varids;
// // /**set the variable data to the variable*/
// SCIPvarSetData(var,vardata);
// }
// // SCIP_CALL(SCIPstopClock(relaxscip,varslottime));
// FILE* AfterPreProcessing;
// AfterPreProcessing = fopen("AfterPreProcessing.txt","w+");
// // SCIP_CALL(SCIPprintOrigProblem(relaxscip, AfterPreProcessing, "lp", FALSE));
// SCIPinfoMessage(relaxscip, TimeCollector, "\n row and column identified in (sec) : %f\n", SCIPgetClockTime(relaxscip, varslottime));
// for(int r=0;r<nSlotConss;r++)
// {
// id = badconss[r];
// SCIP_CONS* cons = SCIPgetConss(relaxscip)[id];
// SCIP_CALL(SCIPdelCons(relaxscip,cons));
// }
// /******************************************************************************************************************/
// /*Next, we will do the initial iteration of finding the dual mulpliers of each slot conss, and their sum(dualsum) */
// /* In the end, we will subtract this sum from the objective of the function. */
// /* It's initial, because while we would search for more dual multipliers to solve the Lagrangian relaxation */
// /******************************************************************************************************************/
// SCIP_Real* dualmultipliers;
// SCIP_CALL(SCIPallocBufferArray(relaxscip,&dualmultipliers,nSlotConss));
// SCIP_Real* subgradients;
// SCIP_CALL(SCIPallocBufferArray(relaxscip,&subgradients,nSlotConss));
// //initialize subgradients;
// SCIP_Real stepsize = 1.00000;
// SCIP_Real sumofduals=0;
// for ( int r = 0; r < nSlotConss; ++r)
// {
// dualmultipliers[r] = 0;
// sumofduals+=dualmultipliers[r]; //adds the negative of the minimum in each iteration
// }
// /*******************************************************************************************************/
// /* The reformulation of the problem can be written as follows */
// //*>>>>>>>>>>>>>>>>>> min sum { (w[i]+sum{dual[j]})}x[i]-sum{dual[r]} <<<<<<<<<<<< */
// /*where i is nvars, j is NVarInBadConss, and r is nSlotConss for our case *******************************/
// /****************************************************************************************************************/
// /* The following function will add the following to the obj(weight) of the variable, */
// //* the obj(weight) of var + the sum of the dualmultipliers of bad constraints which contains this variable */
// /****************************************************************************************************************/
// FILE* solutions;
// solutions = fopen("sol.txt","wr");
// FILE* dual;
// dual= fopen("dual.txt","wr");
// FILE* variableinfo;
// variableinfo = fopen("var.txt","wr");
// FILE* subgrad; // subgrad = fopen("subgrads.txt","wr");
// FILE* varobjects;
// varobjects=fopen("varobjs.txt","wr");
// FILE* lower;
// lower=fopen("lowerbounds.txt","wr");
// FILE* iter;
// lower=fopen("iter.txt","wr");
// SCIP_Real* solvals;
// SCIP_CALL(SCIPallocBufferArray(relaxscip,&solvals,nvars+2));
// solvals[nvars+1]=0; //for last solutions
// solvals[nvars]=0; //for best solution
// int maxiter=125;
// int oscilatecounter=0;
// int improvementcounter = 0;
// SCIP_Real oscilator1=0;
// SCIP_Real oscilator2=0;
// SCIP_Real forcompare = 0.000;
// fprintf(lower,"%d\n",maxiter);
// for(int iter=1;iter<=maxiter;iter++)
// {
// for(int v=0;v<nvars;v++)
// {
// SCIP_VAR* var = vars[v];
// double sum =0;
// vardata=SCIPvarGetData(var);
// int* varids = SCIPvardataGetvarids(vardata);
// assert(varids=!NULL);
// int NVarInBadConss = SCIPvardataGetNVarInBadConss(vardata);
// if(NVarInBadConss==0){break;}
// else
// {
// SCIP_CALL(SCIPprintOrigProblem(relaxscip, AfterPreProcessing, "lp", FALSE));
// fprintf(varobjects,"%s \n",SCIPvarGetName(var));
// for(int t=0;t<NVarInBadConss;t++)
// {
// sum += dualmultipliers[varids[t]];
// fprintf(varobjects,"{id = %d, dual = %f, sum = %f\t",varids[t], dualmultipliers[varids[t]],sum);
// }
// fprintf(varobjects,"}\n\n");
// SCIP_CALL(SCIPaddVarObj(relaxscip,var,sum));
// }
// }
// SCIPinfoMessage(relaxscip, TimeCollector, "\n finished changing the variable's weight after (sec) : %f\n", SCIPgetClockTime(relaxscip, varslottime));
// SCIP_CALL(SCIPaddOrigObjoffset(relaxscip,-1*sumofduals));
// // SCIP_CALL(SCIPprintOrigProblem(relaxscip, AfterPreProcessing, "lp", FALSE));
// SCIPsetMessagehdlrQuiet(relaxscip, TRUE);
// // fclose(AfterPreProcessing);
// SCIP_CALL( SCIPtransformProb(relaxscip) );
// SCIP_CALL( SCIPsolve(relaxscip) );
// relaxval = SCIPgetPrimalbound(relaxscip);
// printf("\ndualbound %f \n",SCIPgetDualbound(relaxscip));
// fprintf(lower,"%f",SCIPgetPrimalbound(relaxscip));
// SCIPdebugMessage("relaxation bound = %e status = %d\n", relaxval, SCIPgetStatus(relaxscip));
// /*store the highest lower bound*/
// if(solvals[nvars]<SCIPgetPrimalbound(relaxscip)){solvals[nvars]=SCIPgetPrimalbound(relaxscip);fprintf(variableinfo,} // fprintf(variableinfo,"%f\n",solvals[nvars]);
// /*make sure we're not oscilating by adding a counter, which checks the absolute value between the difference of the previous few steps and make sure it's not the same. */
// oscilator2=abs(solvals[nvars+1]-SCIPgetPrimalbound(relaxscip));
// if(oscilator1==oscilator2){oscilatecounter++;}
// else(oscilator1=oscilator2);
// if(oscilatecounter==5){printf("repetition"); break;}
// printf("dprev.sol=%f, current=%f, difference %f, coutner=%d, ",solvals[nvars+1],SCIPgetPrimalbound(relaxscip), oscilator2, oscilatecounter);
// /*store the solution on the last entry of solvals, so we can compare it in the next round for repetitions*/
// solvals[nvars+1]=SCIPgetPrimalbound(relaxscip);
// /*breaking criteria for iterations*/
// if(solvals[nvars]>forcompare){forcompare=solvals[nvars];}
// else{improvementcounter++;}
// if(improvementcounter==5){break;}
// /*get the best solution*/
// SCIP_SOL* bestsol = SCIPgetBestSol(relaxscip) ;
// SCIP_SOL** sols = SCIPgetSols(relaxscip);
// int nsols = SCIPgetNSols(relaxscip);
// /*text output*/
// SCIPinfoMessage(relaxscip, TimeCollector, "\n first iteration: problem solved after (sec) : %f\n", SCIPgetClockTime(relaxscip, varslottime));
// fprintf(solutions,"number of solutions %d, first iteration \t bound=%f, \t objsol=%f \n",nsols, SCIPgetPrimalbound(relaxscip),relaxval);
// // SCIP_CALL(SCIPprintBestSol(relaxscip,solutions,FALSE));
// /*store the solution in solvals so we can later export it to subgradient function*/
// SCIP_Real lowerbound=0;
// SCIPgetSolVals(relaxscip,bestsol,nvars,vars,solvals);
// SCIP_CALL(SCIPprintSol(relaxscip,bestsol,dual,FALSE));
// SCIP_Real compare=0;
// for (int v = 0; v<nvars; ++v)
// {
// compare += solvals[v]*weights[v];
// }
// // stepsize = 15/double(iter+1);
// // fprintf(solutions, "\niteration %d\n",iter);
// // fprintf(dual, "\niteration %d\n",iter);
// // fprintf(variableinfo, "\niteration %d\n",iter);
// // fprintf(varobjects, "\niteration %d\n",iter);
// SCIP_CALL(SCIPaddOrigObjoffset(relaxscip,sumofduals));
// // SCIP_CALL( SCIPfreeTransform(relaxscip) );
// // SCIP_CALL( SCIPtransformProb(relaxscip) );
// counter = 0;
// int checker = 0;
// for(int r=0; r<nSlotConss;++r)
// {
// id = badconss[r];
// double ax=-1;
// for(int s=counter;s<(counter+listnconsvars[r]);++s)
// {
// // printf("%s->",SCIPvarGetName(vars[listconsvarids[s]]));
// ax+=SCIPgetSolVal(relaxscip,bestsol,vars[listconsvarids[s]]);
// // fprintf(subgrad,"%s\t,%f\t, sum %f",SCIPvarGetName(vars[listconsvarids[s]]),SCIPgetSolVal(relaxscip,bestsol,vars[listconsvarids[s]]),ax);
// }
// counter += listnconsvars[r];
// if(ax>0){checker++;} // subgradients[r]=ax;
// // fprintf(subgrad, "\n subgrad = %f \t",subgradients[r]);
// }
// /*breaking condition on finding a feasible solution*/
// if(checker==0){printf("#*#*#*result found\n"); break;}
// SCIP_CALL( SCIPfreeTransform(relaxscip) );
// SCIP_CALL( SCIPtransformProb(relaxscip) );
// for (int v = 0; v<nvars; ++v)
// {
// SCIP_VAR* var = vars[v];
// SCIP_CALL(SCIPchgVarObj(relaxscip,var,weights[v]));
// // fprintf(variableinfo,"(%s,%f,%f)->%f\n",SCIPvarGetName(var),solvals[v],SCIPvarGetObj(var), weights[v]);
// lowerbound += solvals[v]*weights[v];
// }
// // fprintf(dual,"dualbound = %f, lowerbound=%f, norm of subgrad %f\t",SCIPgetPrimalbound(relaxscip),lowerbound, getnorm(subgradients,nSlotConss,stepsize));
// // fprintf(lower,"%f\n",lowerbound);
// // stepsize = (SCIPgetPrimalbound(relaxscip)-lowerbound)/getnorm(subgradients,nSlotConss,stepsize);
// SCIP_CALL( SCIPfreeTransform(relaxscip) );
// fprintf(solutions, "lowerbound = %f \n ", lowerbound);
// SCIPinfoMessage(relaxscip, TimeCollector, "\n subgradients found after (sec) : %f\n, lowerbound = %f \n", SCIPgetClockTime(relaxscip, varslottime),lowerbound);
// //add back the sum of the duals we subtracted from the main obj function
// int sum=0;
// sumofduals = 0;
// for(int r=0; r<nSlotConss;++r)
// {
// dualmultipliers[r] += subgradients[r]*stepsize;
// if(dualmultipliers[r]<0){dualmultipliers[r]=0;}
// sum+=dualmultipliers[r];
// // fprintf(dual," then %f step size %f \n",dualmultipliers[r], stepsize);
// }
// sumofduals=sum;
// // fprintf(dual,"iteration %d, sumofduals=%f\n",iter, sumofduals);
// SCIPinfoMessage(relaxscip, TimeCollector, "\n new dual found after (sec) : %f\n", SCIPgetClockTime(relaxscip, varslottime));
// // if(checker==0){printf("solution found in %d iterations\n",iter); break;}
// }
// SCIPfreeTransform(relaxscip);
// fclose(variableinfo);
// fclose(dual);
// fclose(subgrad);
// fclose(varobjects);
// fclose(solutions);
// fclose(lower);
if( SCIPgetStatus(relaxscip) == SCIP_STATUS_OPTIMAL )
{
/* store relaxation solution in original SCIP if it improves the best relaxation solution thus far */
if( (! SCIPisRelaxSolValid(scip)) || SCIPisGT(scip, relaxval, SCIPgetRelaxSolObj(scip)) )
{
SCIPdebugMsg(scip, "Setting LP relaxation solution, which improved upon earlier solution\n");
SCIP_CALL( SCIPclearRelaxSolVals(scip, relax) );
for( i = 0; i < SCIPgetNVars(scip); ++i )
{
SCIP_VAR* relaxvar;
SCIP_Real solval;
relaxvar = (SCIP_VAR*)SCIPhashmapGetImage(varmap, SCIPgetVars(scip)[i]);
assert(relaxvar != NULL);
solval = SCIPgetSolVal(relaxscip, SCIPgetBestSol(relaxscip), relaxvar);
SCIP_CALL( SCIPsetRelaxSolVal(scip, relax, SCIPgetVars(scip)[i], solval) );
}
/* mark relaxation solution to be valid and inform SCIP that the relaxation included all LP rows */
SCIP_CALL( SCIPmarkRelaxSolValid(scip, relax, TRUE) );
}
SCIPdebugMsg(scip, "LP lower bound = %g\n", relaxval);
*lowerbound = relaxval;
*result = SCIP_SUCCESS;
}
else if( SCIPgetStatus(relaxscip) == SCIP_STATUS_INFEASIBLE )
{
SCIPdebugMsg(scip, "cutting off node\n");
*result = SCIP_CUTOFF;
}
/* free memory */
SCIPhashmapFree(&varmap);
SCIP_CALL( SCIPfree(&relaxscip) );
return SCIP_OKAY;
}
/*
* relaxator specific interface methods
*/
/** creates the lagr relaxator and includes it in SCIP */
SCIP_RETCODE SCIPincludeRelaxlagrangian(
SCIP* scip /**< SCIP data structure */
)
{
SCIP_RELAXDATA* relaxdata;
SCIP_RELAX* relax;
/* create lagr relaxator data */
SCIP_CALL(SCIPallocMemory(scip, &relaxdata));
relaxdata = NULL;
/* TODO: (optional) create relaxator specific data here */
relax = NULL;
/* include relaxator */
#if 0
/* use SCIPincludeRelax() if you want to set all callbacks explicitly and realize (by getting compiler errors) when
* new callbacks are added in future SCIP versions
*/
SCIP_CALL( SCIPincludeRelax(scip, RELAX_NAME, RELAX_DESC, RELAX_PRIORITY, RELAX_FREQ, RELAX_INCLUDESLP,
relaxCopylagr, relaxFreelagr, relaxInitlagr, relaxExitlagr, relaxInitsollagr, relaxExitsollagr, relaxExeclagr,
relaxdata) );
#else
/* use SCIPincludeRelaxBasic() 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( SCIPincludeRelaxBasic(scip, &relax, RELAX_NAME, RELAX_DESC, RELAX_PRIORITY, RELAX_FREQ,
relaxExeclagr, relaxdata) );
assert(relax != NULL);
/* set non fundamental callbacks via setter functions */
// SCIP_CALL( SCIPsetRelaxCopy(scip, relax, relaxCopylagr) );
SCIP_CALL( SCIPsetRelaxFree(scip, relax, relaxFreelagr) );
SCIP_CALL( SCIPsetRelaxInit(scip, relax, relaxInitlagr) );
SCIP_CALL( SCIPsetRelaxExit(scip, relax, relaxExitlagr) );
SCIP_CALL( SCIPsetRelaxInitsol(scip, relax, relaxInitsollagr) );
SCIP_CALL( SCIPsetRelaxExitsol(scip, relax, relaxExitsollagr) );
#endif
/* add lagr relaxator parameters */
/* TODO: (optional) add relaxator specific parameters with SCIPaddTypeParam() here */
return SCIP_OKAY;
}