70#define PRESOL_NAME "dualinfer"
71#define PRESOL_DESC "exploit dual information for fixings and side changes"
72#define PRESOL_PRIORITY (-3000)
73#define PRESOL_MAXROUNDS 0
74#define PRESOL_TIMING SCIP_PRESOLTIMING_EXHAUSTIVE
76#define DEFAULT_TWOCOLUMN_COMBINE TRUE
77#define DEFAULT_MAXLOOPS_DUALBNDSTR 12
78#define DEFAULT_MAXCONSIDEREDNONZEROS 100
79#define DEFAULT_MAXRETRIEVEFAILS 1000
80#define DEFAULT_MAXCOMBINEFAILS 1000
81#define DEFAULT_MAXHASHFAC 10
82#define DEFAULT_MAXPAIRFAC 1
83#define DEFAULT_MAXROWSUPPORT 3
93 SCIP_Bool usetwocolcombine;
99 int maxconsiderednonzeros;
154 a = (uint64_t)(
long)
colpair->col1idx;
155 b = (uint64_t)(
long)
colpair->col2idx;
156 return (
void*)((
a << 32) |
b);
168 return (
int)(
hash>>1);
191 (*hashlist)[(*pos)] =
hash;
192 (*colidxlist)[(*pos)] =
colidx;
477#ifdef SCIP_MORE_DEBUG
483#ifdef SCIP_MORE_DEBUG
489#ifdef SCIP_MORE_DEBUG
508#ifdef SCIP_MORE_DEBUG
579#ifdef SCIP_MORE_DEBUG
591#ifdef SCIP_MORE_DEBUG
600#ifdef SCIP_MORE_DEBUG
627#ifdef SCIP_MORE_DEBUG
651#ifdef SCIP_MORE_DEBUG
656#ifdef SCIP_MORE_DEBUG
662#ifdef SCIP_MORE_DEBUG
681#ifdef SCIP_MORE_DEBUG
1044 else if( val < 0.0 )
1110 else if( val < 0.0 )
1170 else if( val < 0.0 )
1280 assert(0 <= row && row < nrows);
1294 for(
i = 0;
i < ncols;
i++)
1309 for(
i = 0;
i < nrows;
i++ )
1355 constraints[
i] =
NULL;
1357 for(
i = 0;
i < ncols;
i++)
1466 if(constraints[
i] !=
NULL)
1628 for(
i = 0;
i < ncols;
i++ )
1640 for(
i = 0;
i < ncols;
i++ )
1679 for(
i = 0;
i < nrows;
i++ )
1696 if(
nimplubvars >= 2 && presoldata->usetwocolcombine )
1759#ifdef SCIP_MORE_DEBUG
1793#ifdef SCIP_MORE_DEBUG
1837#ifdef SCIP_MORE_DEBUG
1895#ifdef SCIP_MORE_DEBUG
1979#ifdef SCIP_MORE_DEBUG
1981 for(
i = 0;
i < nrows;
i++ )
2045#ifdef SCIP_MORE_DEBUG
2047 for(
i = 0;
i < nrows;
i++ )
2059 for(
i = 0;
i < ncols;
i++ )
2065 for(
i = 0;
i < ncols;
i++ )
2083 (*npossiblefixings)++;
2093 (*npossiblefixings)++;
2098 for(
i = 0;
i < nrows;
i++ )
2107 (*npossiblesidechanges)++;
2119 (*npossiblesidechanges)++;
2125 (*npossiblesidechanges)++;
2186 SCIP_Bool initialized;
2188 SCIP_Bool infeasible;
2217 SCIPdebugMsg(
scip,
"DualInfer not executed because condition of existing dual solution is not fulfilled.\n");
2226 naddconss, ndelconss, nchgcoefs, nchgbds, nfixedvars) );
2262 for(
i = ncols - 1;
i >= 0; --
i )
2323 for(
i = 0;
i < nrows;
i++ )
2402 SCIPdebugMsg(
scip,
"### fixed vars [cont: %d, int: %d, bin: %d], changed sides [%d]\n",
2434 "presolving/dualinfer/twocolcombine",
2435 "use convex combination of columns for determining dual bounds",
2439 "presolving/dualinfer/maxdualbndloops",
2440 "maximal number of dual bound strengthening loops",
2444 "presolving/dualinfer/maxconsiderednonzeros",
2445 "maximal number of considered non-zeros within one column (-1: no limit)",
2449 "presolving/dualinfer/maxretrievefails",
2450 "maximal number of consecutive useless hashtable retrieves",
2454 "presolving/dualinfer/maxcombinefails",
2455 "maximal number of consecutive useless column combines",
2459 "presolving/dualinfer/maxhashfac",
2460 "Maximum number of hashlist entries as multiple of number of columns in the problem (-1: no limit)",
2464 "presolving/dualinfer/maxpairfac",
2465 "Maximum number of processed column pairs as multiple of the number of columns in the problem (-1: no limit)",
2469 "presolving/dualinfer/maxrowsupport",
2470 "Maximum number of row's non-zeros for changing inequality to equality",
Constraint handler for linear constraints in their most general form, .
static SCIP_RETCODE determineBestBounds(SCIP *scip, SCIP_VAR *var, SCIP_SOL *sol, SCIP_Real boundswitch, int usevbds, SCIP_Bool allowlocal, SCIP_Bool fixintegralrhs, SCIP_Bool ignoresol, int *boundsfortrans, SCIP_BOUNDTYPE *boundtypesfortrans, SCIP_Real *bestlb, SCIP_Real *bestub, int *bestlbtype, int *bestubtype, SCIP_BOUNDTYPE *selectedbound, SCIP_Bool *freevariable)
SCIP_Real SCIPgetRhsLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPchgRhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real rhs)
SCIP_Real SCIPgetLhsLinear(SCIP *scip, SCIP_CONS *cons)
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_RETCODE SCIPchgLhsLinear(SCIP *scip, SCIP_CONS *cons, SCIP_Real lhs)
SCIP_RETCODE SCIPfree(SCIP **scip)
SCIP_RETCODE SCIPcreate(SCIP **scip)
SCIP_STATUS SCIPgetStatus(SCIP *scip)
SCIP_RETCODE SCIPaddVar(SCIP *scip, SCIP_VAR *var)
int SCIPgetNImplVars(SCIP *scip)
int SCIPgetNContVars(SCIP *scip)
SCIP_RETCODE SCIPwriteOrigProblem(SCIP *scip, const char *filename, const char *extension, SCIP_Bool genericnames)
SCIP_RETCODE SCIPaddCons(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPsetObjsense(SCIP *scip, SCIP_OBJSENSE objsense)
SCIP_RETCODE SCIPcreateProbBasic(SCIP *scip, const char *name)
void SCIPhashsetFree(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem)
SCIP_Bool SCIPhashsetExists(SCIP_HASHSET *hashset, void *element)
SCIP_RETCODE SCIPhashsetInsert(SCIP_HASHSET *hashset, BMS_BLKMEM *blkmem, void *element)
SCIP_RETCODE SCIPhashsetCreate(SCIP_HASHSET **hashset, BMS_BLKMEM *blkmem, int size)
#define SCIPhashTwo(a, b)
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
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)
SCIP_RETCODE SCIPsetIntParam(SCIP *scip, const char *name, int 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 SCIPsetBoolParam(SCIP *scip, const char *name, SCIP_Bool value)
SCIP_RETCODE SCIPincludePresolDualinfer(SCIP *scip)
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
SCIP_RETCODE SCIPreleaseCons(SCIP *scip, SCIP_CONS **cons)
SCIP_Real SCIPgetPseudoObjval(SCIP *scip)
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
int SCIPcalcMemGrowSize(SCIP *scip, int num)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
#define SCIPreallocBlockMemoryArray(scip, ptr, oldnum, newnum)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_RETCODE SCIPsetPresolFree(SCIP *scip, SCIP_PRESOL *presol,)
void SCIPpresolSetData(SCIP_PRESOL *presol, SCIP_PRESOLDATA *presoldata)
SCIP_PRESOLDATA * SCIPpresolGetData(SCIP_PRESOL *presol)
SCIP_RETCODE SCIPsetPresolCopy(SCIP *scip, SCIP_PRESOL *presol,)
SCIP_RETCODE SCIPincludePresolBasic(SCIP *scip, SCIP_PRESOL **presolptr, const char *name, const char *desc, int priority, int maxrounds, SCIP_PRESOLTIMING timing, SCIP_DECL_PRESOLEXEC((*presolexec)), SCIP_PRESOLDATA *presoldata)
const char * SCIPpresolGetName(SCIP_PRESOL *presol)
SCIP_RETCODE SCIPcheckSolOrig(SCIP *scip, SCIP_SOL *sol, SCIP_Bool *feasible, SCIP_Bool printreason, SCIP_Bool completely)
SCIP_SOL * SCIPgetBestSol(SCIP *scip)
SCIP_Real SCIPgetSolOrigObj(SCIP *scip, SCIP_SOL *sol)
SCIP_RETCODE SCIPfreeTransform(SCIP *scip)
SCIP_RETCODE SCIPsolve(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
const char * SCIPvarGetName(SCIP_VAR *var)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
SCIP_RETCODE SCIPcreateVarBasic(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype)
SCIP_RETCODE SCIPchgVarObj(SCIP *scip, SCIP_VAR *var, SCIP_Real newobj)
SCIP_Bool SCIPallowWeakDualReds(SCIP *scip)
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
void SCIPsortIntReal(int *intarray, SCIP_Real *realarray, int len)
void SCIPsortRealInt(SCIP_Real *realarray, int *intarray, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
assert(minobj< SCIPgetCutoffbound(scip))
static SCIP_RETCODE solveLP(SCIP *scip, SCIP_DIVESET *diveset, SCIP_Longint maxnlpiterations, SCIP_DIVECONTEXT divecontext, SCIP_Bool *lperror, SCIP_Bool *cutoff)
SCIP_Bool SCIPmatrixUplockConflict(SCIP_MATRIX *matrix, int col)
int * SCIPmatrixGetColIdxPtr(SCIP_MATRIX *matrix, int col)
int SCIPmatrixGetRowNNonzs(SCIP_MATRIX *matrix, int row)
int SCIPmatrixGetColNNonzs(SCIP_MATRIX *matrix, int col)
SCIP_Bool SCIPmatrixIsRowRhsInfinity(SCIP_MATRIX *matrix, int row)
SCIP_Real SCIPmatrixGetRowLhs(SCIP_MATRIX *matrix, int row)
SCIP_Real * SCIPmatrixGetRowValPtr(SCIP_MATRIX *matrix, int row)
SCIP_Bool SCIPmatrixDownlockConflict(SCIP_MATRIX *matrix, int col)
SCIP_Real SCIPmatrixGetRowRhs(SCIP_MATRIX *matrix, int row)
SCIP_Real * SCIPmatrixGetColValPtr(SCIP_MATRIX *matrix, int col)
SCIP_RETCODE SCIPmatrixCreate(SCIP *scip, SCIP_MATRIX **matrixptr, SCIP_Bool onlyifcomplete, SCIP_Bool *initialized, SCIP_Bool *complete, SCIP_Bool *infeasible, int *naddconss, int *ndelconss, int *nchgcoefs, int *nchgbds, int *nfixedvars)
int SCIPmatrixGetNColumns(SCIP_MATRIX *matrix)
SCIP_CONS * SCIPmatrixGetCons(SCIP_MATRIX *matrix, int row)
void SCIPmatrixFree(SCIP *scip, SCIP_MATRIX **matrix)
SCIP_VAR * SCIPmatrixGetVar(SCIP_MATRIX *matrix, int col)
int * SCIPmatrixGetRowIdxPtr(SCIP_MATRIX *matrix, int row)
int SCIPmatrixGetNRows(SCIP_MATRIX *matrix)
memory allocation routines
#define BMSclearMemoryArray(ptr, num)
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
enum Fixingdirection FIXINGDIRECTION
#define DEFAULT_TWOCOLUMN_COMBINE
static void calcMaxColActivity(SCIP *scip, SCIP_MATRIX *matrix, int col, SCIP_Real *lbdual, SCIP_Real *ubdual, SCIP_Real *maxcolact, int *maxcolactinf)
static void * encodeColPair(COLPAIR *colpair)
static void calcMinColActResidual(SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, SCIP_Real *lbdual, SCIP_Real *ubdual, const SCIP_Real *mincolact, const int *mincolactinf, SCIP_Real *mincolresact)
#define DEFAULT_MAXCONSIDEREDNONZEROS
static void getImpliedBounds(SCIP *scip, SCIP_MATRIX *matrix, int col, SCIP_Real *lbs, SCIP_Real *ubs, SCIP_Bool *ubimplied, SCIP_Bool *lbimplied)
static void calcMinColActivity(SCIP *scip, SCIP_MATRIX *matrix, int col, SCIP_Real *lbdual, SCIP_Real *ubdual, SCIP_Real *mincolact, int *mincolactinf)
static int hashIndexPair(int idx1, int idx2)
enum Fixingdirection FIXINGDIRECTION
static void getVarBoundsOfRow(SCIP *scip, SCIP_MATRIX *matrix, int col, int row, SCIP_Real val, SCIP_Real *lbs, SCIP_Real *ubs, SCIP_Real *rowub, SCIP_Bool *ubfound, SCIP_Real *rowlb, SCIP_Bool *lbfound)
static SCIP_RETCODE combineCols(SCIP *scip, int *row1idxptr, int *row2idxptr, SCIP_Real *row1valptr, SCIP_Real *row2valptr, SCIP_Real b1, SCIP_Real b2, int row1len, int row2len, int ncols, SCIP_Bool swaprow1, SCIP_Bool swaprow2, SCIP_Real *lbs, SCIP_Real *ubs, SCIP_Bool *success)
static SCIP_Real getMinColActWithoutRow(SCIP *scip, SCIP_MATRIX *matrix, int col, int withoutrow, SCIP_Real *lbdual, SCIP_Real *ubdual)
static void updateDualBounds(SCIP *scip, SCIP_MATRIX *matrix, SCIP_Real objval, SCIP_Real val, int row, SCIP_Real mincolresact, SCIP_Real *lbdual, SCIP_Real *ubdual, int *boundchanges, SCIP_Bool *ubinfchange, SCIP_Bool *lbinfchange)
static void findNextBlock(const int *list, int len, int *start, int *end)
static SCIP_RETCODE dualBoundStrengthening(SCIP *scip, SCIP_MATRIX *matrix, SCIP_PRESOLDATA *presoldata, FIXINGDIRECTION *varstofix, int *npossiblefixings, SIDECHANGE *sidestochange, int *npossiblesidechanges)
#define DEFAULT_MAXHASHFAC
enum SideChange SIDECHANGE
static void getMinMaxActivityResiduals(SCIP *scip, SCIP_MATRIX *matrix, int withoutcol, int row, SCIP_Real *lbs, SCIP_Real *ubs, SCIP_Real *minresactivity, SCIP_Real *maxresactivity, SCIP_Bool *isminsettoinfinity, SCIP_Bool *ismaxsettoinfinity)
#define DEFAULT_MAXCOMBINEFAILS
#define DEFAULT_MAXRETRIEVEFAILS
#define DEFAULT_MAXLOOPS_DUALBNDSTR
#define DEFAULT_MAXPAIRFAC
static void infinityCountUpdate(SCIP *scip, SCIP_MATRIX *matrix, int row, SCIP_Real *lbdual, SCIP_Real *ubdual, const SCIP_Bool *isubimplied, SCIP_Real *mincolact, int *mincolactinf, SCIP_Bool ubinfchange, SCIP_Bool lbinfchange)
#define DEFAULT_MAXROWSUPPORT
static SCIP_RETCODE addEntry(SCIP *scip, int *pos, int *listsize, int **hashlist, int **colidxlist, int hash, int colidx)
public methods for managing constraints
public methods for matrix
public methods for message output
public methods for presolvers
public methods for problem variables
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for presolving plugins
public methods for global and local (sub)problems
public methods for the probing mode
public methods for SCIP variables
SCIP_RETCODE SCIPincludeDefaultPlugins(SCIP *scip)
#define SCIP_DECL_PRESOLCOPY(x)
struct SCIP_PresolData SCIP_PRESOLDATA
#define SCIP_DECL_PRESOLFREE(x)
#define SCIP_DECL_PRESOLEXEC(x)
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARTYPE_CONTINUOUS