39 #define HEUR_NAME "repair" 40 #define HEUR_DESC "tries to repair a primal infeasible solution" 41 #define HEUR_DISPCHAR '!' 42 #define HEUR_PRIORITY 0 44 #define HEUR_FREQOFS 0 45 #define HEUR_MAXDEPTH -1 46 #define HEUR_TIMING SCIP_HEURTIMING_AFTERNODE 47 #define HEUR_USESSUBSCIP TRUE 48 #define DEFAULT_MINFIXINGRATE 0.3 50 #define DEFAULT_NODESOFS 500 51 #define DEFAULT_MAXNODES 5000 52 #define DEFAULT_MINNODES 50 53 #define DEFAULT_NODESQUOT 0.1 55 #define DEFAULT_FILENAME "-" 56 #define DEFAULT_ROUNDIT TRUE 60 #define DEFAULT_USEOBJFACTOR FALSE 63 #define DEFAULT_USEVARFIX TRUE 64 #define DEFAULT_USESLACKVARS FALSE 65 #define DEFAULT_ALPHA 2.0 156 for (i = 0; i < nvars; ++i)
169 else if(
SCIPisGT(scip, 0.0, upperbound) )
181 *factor = upperbound - lprelaxobj;
184 *factor = 1.0 / *factor;
188 objoffset = -lprelaxobj * (*factor);
206 assert(
NULL != scip);
209 if( 0 > sgn * coefficient )
266 assert(
NULL != scip);
267 assert(
NULL != potential);
268 assert(
NULL != slack);
270 assert(
NULL != inftycounter);
271 assert(
NULL != heurdata);
273 alpha = heurdata->alpha;
294 infeasible, fixed) );
295 assert(!*infeasible && *fixed);
296 heurdata->nvarfixed++;
300 assert(
NULL != rows);
303 for( i = 0; i < nrows; ++i )
307 assert(rowindex >= 0);
324 potential[rowindex] -= contribution;
328 inftycounter[rowindex]--;
331 assert(0 <= inftycounter[rowindex]);
332 if( 0 == inftycounter[rowindex] &&
REALABS(potential[rowindex]) < alpha *
REALABS(slack[rowindex]) )
339 if( 0 == slack[rowindex] )
344 if( 0 > slack[rowindex])
351 potential[rowindex] += contribution;
355 inftycounter[rowindex]++;
363 infeasible, fixed) );
364 assert(!*infeasible && *fixed);
365 heurdata->nvarfixed++;
390 assert(
NULL != success);
399 nfracvars = nbinvars + nintvars;
400 for( i = 0; i < nfracvars; ++i)
411 roundedvalue =
SCIPceil(scip, value - 1.0);
415 roundedvalue =
SCIPfloor(scip, value + 1.0);
423 SCIPdebugMsg(scip,
"Repair: All variables are integral.\n");
448 assert(scip !=
NULL);
449 assert(subscip !=
NULL);
450 assert(subvars !=
NULL);
451 assert(subsol !=
NULL);
472 #ifdef SCIP_STATISTICS 503 int* nviolatedrows =
NULL;
504 int* permutation =
NULL;
505 int* inftycounter =
NULL;
526 sol = heurdata->infsol;
545 if( heurdata->useslackvars )
556 SCIPdebugMsg(scip,
"\n\n Calling objective factor calculation \n\n");
557 if( heurdata->useobjfactor )
568 for( i = 0; i < nvars; ++i )
583 #ifdef SCIP_STATISTIC 584 heurdata->norigvars++;
593 nviolatedrows[i] = 0;
596 if( heurdata->useslackvars &&
SCIPisFeasLT(scip, value, lborig) )
599 varslack = lborig - value;
608 if( heurdata->useslackvars &&
SCIPisFeasGT(scip, value, uborig) )
611 varslack = uborig - value;
619 if( heurdata->useobjfactor )
647 if( heurdata->useslackvars )
660 if( heurdata->useobjfactor )
673 if( heurdata->useslackvars )
685 #ifdef SCIP_STATISTIC 686 heurdata->nviolatedvars++;
691 #ifdef SCIP_STATISTIC 694 heurdata->nviolatedvars++;
713 for (i = 0; i < nrows; ++i)
725 #ifdef SCIP_STATISTIC 747 slacks[i] = lhs - rowsolact;
748 #ifdef SCIP_STATISTIC 749 heurdata->nviolatedcons++;
754 slacks[i] = rhs - rowsolact;
755 #ifdef SCIP_STATISTIC 756 heurdata->nviolatedcons++;
765 for( j = 0; j < nnonz; ++j )
783 consvars[j] = subvars[pos];
790 potential[i] += contribution;
799 nviolatedrows[pos]++;
806 nnonz, consvars, vals, lhs, rhs) );
808 if( heurdata->useslackvars )
833 if( heurdata->usevarfix )
836 for( i = 0; i < nvars; ++i )
846 heurdata->nvarfixed = 0;
847 for( i = 0; i < nvars; ++i )
852 SCIP_CALL(
tryFixVar(scip, subscip, sol, potential, slacks, vars[permutation[i]], subvars[permutation[i]], inftycounter, heurdata, &infeasible, &fixed) );
868 if( heurdata->useslackvars )
874 SCIPdebugMsg(scip,
"Initial repair solution was not accepted.\n");
878 #ifdef SCIP_STATISTIC 879 if( heurdata->useslackvars )
926 SCIPwarningMessage(scip,
"Error while solving subproblem in REPAIR heuristic; sub-SCIP terminated with code <%d>\n", retcode);
936 #ifdef SCIP_STATISTIC 959 #ifdef SCIP_STATISTIC 972 for( i = 0; i < nvars; ++i )
1007 assert(heurdata !=
NULL);
1025 heurdata->subiters = -1;
1026 heurdata->subnodes = -1;
1029 heurdata->nvarfixed = 0;
1030 heurdata->relvarfixed = -1;
1032 #ifdef SCIP_STATISTIC 1033 heurdata->subpresoltime = 0;
1035 heurdata->nviolatedvars = 0;
1036 heurdata->norigvars = 0;
1037 heurdata->relviolatedvars = 0;
1038 heurdata->nviolatedcons = 0;
1039 heurdata->norcons = 0;
1040 heurdata->relviolatedcons = 0;
1047 heurdata->usednodes = 0;
1057 #ifdef SCIP_STATISTIC 1074 violateds = heurdata->nviolatedvars+heurdata->nviolatedcons;
1075 ninvars = heurdata->nviolatedvars;
1076 ninvcons = heurdata->nviolatedcons;
1077 nvars = heurdata->norigvars;
1078 ncons = heurdata->norcons;
1079 iterations = heurdata->subiters;
1080 nodes = heurdata->subnodes;
1081 time = heurdata->subpresoltime;
1082 runs = heurdata->runs;
1093 heurdata->relviolatedvars =
MAX((
SCIP_Real)heurdata->norigvars, 1.0);
1094 heurdata->relviolatedvars = heurdata->nviolatedvars/heurdata->relviolatedvars;
1095 heurdata->relviolatedcons =
MAX((
SCIP_Real)heurdata->norcons, 1.0);
1096 heurdata->relviolatedcons = heurdata->nviolatedcons/heurdata->relviolatedcons;
1098 heurdata->relvarfixed =
MAX((
SCIP_Real)heurdata->norigvars, 1.0);
1099 heurdata->relvarfixed = heurdata->nvarfixed/heurdata->relvarfixed;
1100 relvars = heurdata->relviolatedvars;
1101 relcons = heurdata->relviolatedcons;
1102 relfixed = heurdata->relvarfixed;
1143 assert(result !=
NULL);
1147 if( 0 <
SCIPheurGetNCalls(heur) || !(heurdata->usevarfix || heurdata->useslackvars) )
1160 nnodes += heurdata->nodesofs;
1163 nnodes -= heurdata->usednodes;
1164 nnodes =
MIN(nnodes, heurdata->maxnodes);
1167 if( nnodes < heurdata->minnodes )
1212 SCIPwarningMessage(scip,
"cannot run repair, unknown return status <%d>\n", retcode);
1222 SCIPdebugMsg(scip,
"Given solution is not integral, repair terminates.\n");
1234 assert(
NULL != heurdata->infsol);
1235 assert(heurdata->usevarfix || heurdata->useslackvars);
1268 assert(heur !=
NULL);
1269 assert(heurdata !=
NULL);
1278 heurdata->filename =
NULL;
1281 "file name of a solution to be used as infeasible starting point, [-] if not available",
1286 "True : fractional variables which are not fractional in the given solution are rounded, " 1287 "FALSE : solving process of this heuristic is stopped. ",
1292 "should a scaled objective function for original variables be used in repair subproblem?",
1297 "should variable fixings be used in repair subproblem?",
1302 "should slack variables be used in repair subproblem?",
1309 "number of nodes added to the contingent of the total nodes",
1313 "maximum number of nodes to regard in the subproblem",
1317 "minimum number of nodes required to start the subproblem",
1321 "contingent of sub problem nodes in relation to the number of nodes of the original problem",
1326 "minimum percentage of integer variables that have to be fixed",
enum SCIP_Result SCIP_RESULT
SCIP_ROW ** SCIPgetLPRows(SCIP *scip)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
static SCIP_DECL_HEUREXIT(heurExitRepair)
SCIP_RETCODE SCIPchgVarLbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_RETCODE SCIPlinkLPSol(SCIP *scip, SCIP_SOL *sol)
SCIP_Real SCIPgetSolvingTime(SCIP *scip)
SCIP_Bool SCIPisFeasEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
SCIP_STAGE SCIPgetStage(SCIP *scip)
SCIP_RETCODE SCIPincludeHeurRepair(SCIP *scip)
SCIP_Longint SCIPgetNLPIterations(SCIP *scip)
static SCIP_RETCODE createNewSol(SCIP *scip, SCIP *subscip, SCIP_VAR **subvars, SCIP_HEUR *heur, SCIP_SOL *subsol, SCIP_Bool *success)
SCIP_RETCODE SCIPcreateConsBasicLinear(SCIP *scip, SCIP_CONS **cons, const char *name, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real lhs, SCIP_Real rhs)
SCIP_Bool SCIPisFeasLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Constraint handler for variable bound constraints .
static SCIP_Real getPotentialContributed(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real coefficient, int sgn)
SCIP_RETCODE SCIPaddOrigObjoffset(SCIP *scip, SCIP_Real addval)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPgetRealParam(SCIP *scip, const char *name, SCIP_Real *value)
SCIP_Longint SCIPheurGetNBestSolsFound(SCIP_HEUR *heur)
SCIP_RETCODE SCIPaddSolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool *stored)
SCIP_RETCODE SCIPcreateProb(SCIP *scip, const char *name, SCIP_DECL_PROBDELORIG((*probdelorig)), SCIP_DECL_PROBTRANS((*probtrans)), SCIP_DECL_PROBDELTRANS((*probdeltrans)), SCIP_DECL_PROBINITSOL((*probinitsol)), SCIP_DECL_PROBEXITSOL((*probexitsol)), SCIP_DECL_PROBCOPY((*probcopy)), SCIP_PROBDATA *probdata)
SCIP_Real * SCIPcolGetVals(SCIP_COL *col)
SCIP_RETCODE SCIPsetHeurExit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEUREXIT((*heurexit)))
int SCIProwGetNNonz(SCIP_ROW *row)
int SCIPgetNOrigVars(SCIP *scip)
#define DEFAULT_USEOBJFACTOR
const char * SCIProwGetName(SCIP_ROW *row)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
static SCIP_DECL_HEURINIT(heurInitRepair)
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
SCIP_RETCODE SCIPcutoffNode(SCIP *scip, SCIP_NODE *node)
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
enum SCIP_Retcode SCIP_RETCODE
SCIP_BRANCHRULE * SCIPfindBranchrule(SCIP *scip, const char *name)
int SCIPvarGetProbindex(SCIP_VAR *var)
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
static SCIP_RETCODE applyRepair(SCIP *scip, SCIP_HEUR *heur, SCIP_RESULT *result, SCIP_Longint nnodes)
struct SCIP_HeurData SCIP_HEURDATA
SCIP_RETCODE SCIPincludeHeurBasic(SCIP *scip, SCIP_HEUR **heur, const char *name, const char *desc, char dispchar, int priority, int freq, int freqofs, int maxdepth, SCIP_HEURTIMING timingmask, SCIP_Bool usessubscip, SCIP_DECL_HEUREXEC((*heurexec)), SCIP_HEURDATA *heurdata)
SCIP_RETCODE SCIPaddStringParam(SCIP *scip, const char *name, const char *desc, char **valueptr, SCIP_Bool isadvanced, const char *defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPconstructLP(SCIP *scip, SCIP_Bool *cutoff)
#define SCIPfreeBufferArray(scip, ptr)
SCIP_RETCODE SCIPcreate(SCIP **scip)
void SCIPheurSetData(SCIP_HEUR *heur, SCIP_HEURDATA *heurdata)
SCIP_RETCODE SCIPsetRealParam(SCIP *scip, const char *name, SCIP_Real value)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
SCIP_RETCODE SCIPchgVarUbGlobal(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound)
SCIP_RETCODE SCIPaddIntParam(SCIP *scip, const char *name, const char *desc, int *valueptr, SCIP_Bool isadvanced, int defaultvalue, int minvalue, int maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
static SCIP_RETCODE checkCands(SCIP *scip, SCIP_SOL *sol, SCIP_Bool roundit, SCIP_Bool *success)
SCIP_RETCODE SCIPcopyParamSettings(SCIP *sourcescip, SCIP *targetscip)
SCIP_Real SCIPgetPresolvingTime(SCIP *scip)
SCIP_RETCODE SCIPprintStatistics(SCIP *scip, FILE *file)
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
SCIP_RETCODE SCIPcreateOrigSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
const char * SCIPgetProbName(SCIP *scip)
SCIP_Bool SCIPisLPConstructed(SCIP *scip)
#define DEFAULT_MINFIXINGRATE
SCIP_RETCODE SCIPchgVarType(SCIP *scip, SCIP_VAR *var, SCIP_VARTYPE vartype, SCIP_Bool *infeasible)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPsolve(SCIP *scip)
#define SCIPallocMemory(scip, ptr)
SCIP_Bool SCIPisParamFixed(SCIP *scip, const char *name)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
SCIP_RETCODE SCIPsetHeurFree(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURFREE((*heurfree)))
SCIP_ROW ** SCIPcolGetRows(SCIP_COL *col)
#define DEFAULT_USEVARFIX
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
#define SCIPfreeBufferArrayNull(scip, ptr)
const char * SCIPvarGetName(SCIP_VAR *var)
#define DEFAULT_USESLACKVARS
int SCIPgetNLPRows(SCIP *scip)
SCIP_Real SCIPgetLowerbound(SCIP *scip)
SCIP_Longint SCIPgetNTotalNodes(SCIP *scip)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
SCIP_Longint SCIPheurGetNCalls(SCIP_HEUR *heur)
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
SCIP_Bool SCIPhasCurrentNodeLP(SCIP *scip)
#define SCIPallocBufferArray(scip, ptr, num)
SCIP_RETCODE SCIPsetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var, SCIP_Real val)
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
#define DEFAULT_NODESQUOT
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
SCIP_RETCODE SCIPsetObjlimit(SCIP *scip, SCIP_Real objlimit)
int SCIPvarGetNLocksUp(SCIP_VAR *var)
SCIP_RETCODE SCIPtrySolFree(SCIP *scip, SCIP_SOL **sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int value)
SCIP_RETCODE SCIPfreeSol(SCIP *scip, SCIP_SOL **sol)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
int SCIPgetNSols(SCIP *scip)
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
int SCIPgetNRuns(SCIP *scip)
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
SCIP_RETCODE SCIPcreateConsBasicVarbound(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *var, SCIP_VAR *vbdvar, SCIP_Real vbdcoef, SCIP_Real lhs, SCIP_Real rhs)
Constraint handler for linear constraints in their most general form, .
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPgetRowSolActivity(SCIP *scip, SCIP_ROW *row, SCIP_SOL *sol)
SCIP_RETCODE SCIPtrySol(SCIP *scip, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool completely, SCIP_Bool checkbounds, SCIP_Bool checkintegrality, SCIP_Bool checklprows, SCIP_Bool *stored)
static SCIP_DECL_HEURFREE(heurFreeRepair)
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
#define SCIPfreeMemory(scip, ptr)
SCIP_RETCODE SCIPreadSolFile(SCIP *scip, const char *filename, SCIP_SOL *sol, SCIP_Bool xml, SCIP_Bool *partial, SCIP_Bool *error)
int SCIPvarGetNLocksDown(SCIP_VAR *var)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
SCIP_Longint SCIPgetMemUsed(SCIP *scip)
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
static SCIP_RETCODE getObjectiveFactor(SCIP *scip, SCIP *subscip, SCIP_Real *factor, SCIP_Bool *success)
SCIP_RETCODE SCIPsetHeurInit(SCIP *scip, SCIP_HEUR *heur, SCIP_DECL_HEURINIT((*heurinit)))
SCIP_Longint SCIPgetMemExternEstim(SCIP *scip)
int SCIProwGetLPPos(SCIP_ROW *row)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_RETCODE SCIPsetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
enum SCIP_Vartype SCIP_VARTYPE
static SCIP_DECL_HEUREXEC(heurExecRepair)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPgetUpperbound(SCIP *scip)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_HEURDATA * SCIPheurGetData(SCIP_HEUR *heur)
SCIP_Longint SCIPgetNNodes(SCIP *scip)
int SCIPcolGetNLPNonz(SCIP_COL *col)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_RETCODE SCIPaddRealParam(SCIP *scip, const char *name, const char *desc, SCIP_Real *valueptr, SCIP_Bool isadvanced, SCIP_Real defaultvalue, SCIP_Real minvalue, SCIP_Real maxvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPsetSubscipsOff(SCIP *scip, SCIP_Bool quiet)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPsetLongintParam(SCIP *scip, const char *name, SCIP_Longint value)
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPcreateSol(SCIP *scip, SCIP_SOL **sol, SCIP_HEUR *heur)
static SCIP_RETCODE tryFixVar(SCIP *scip, SCIP *subscip, SCIP_SOL *sol, SCIP_Real *potential, SCIP_Real *slack, SCIP_VAR *var, SCIP_VAR *subvar, int *inftycounter, SCIP_HEURDATA *heurdata, SCIP_Bool *infeasible, SCIP_Bool *fixed)