69#define SEPA_NAME "disjunctive"
70#define SEPA_DESC "disjunctive cut separator"
71#define SEPA_PRIORITY 10
73#define SEPA_MAXBOUNDDIST 0.0
75#define SEPA_USESSUBSCIP FALSE
76#define SEPA_DELAY TRUE
78#define DEFAULT_MAXRANK 20
79#define DEFAULT_MAXRANKINTEGRAL -1
80#define DEFAULT_MAXWEIGHTRANGE 1e+03
81#define DEFAULT_STRENGTHEN TRUE
83#define DEFAULT_MAXDEPTH -1
84#define DEFAULT_MAXROUNDS 25
85#define DEFAULT_MAXROUNDSROOT 100
86#define DEFAULT_MAXINVCUTS 50
87#define DEFAULT_MAXINVCUTSROOT 250
88#define DEFAULT_MAXCONFSDELAY 100000
90#define MAKECONTINTEGRAL FALSE
98 SCIP_Real maxweightrange;
116 SCIP_Real* rowsmaxval,
117 SCIP_Real maxweightrange,
122 SCIP_Real maxweight = 0.0;
132 for (
r = 0;
r < nrows; ++
r)
136 val =
REALABS(binvrow[
r] * rowsmaxval[
r]);
142 for (
r = 0;
r < nrows; ++
r)
147 val =
REALABS(binvrow[
r] * rowsmaxval[
r]);
149 if ( rank > maxrank &&
SCIPisGT(
scip, val * maxweightrange, maxweight) )
167 SCIP_Real* simplexcoefs,
185 for (
c = 0;
c < ncols; ++
c)
192 simplexcoefs[(*nonbasicnumber)++] = coef[
c];
196 for (
r = 0;
r < nrows; ++
r)
206 simplexcoefs[(*nonbasicnumber)++] = binvrow[
r];
226 SCIP_Bool strengthen,
231 SCIP_Real* simplexcoefs1,
232 SCIP_Real* simplexcoefs2,
235 SCIP_Bool* madeintegral
248 int nonbasicnumber = 0;
264 *madeintegral =
FALSE;
277 cutlhs = sgn * cutlhs1 * cutlhs2;
280 for (
c = 0;
c < ncols; ++
c)
298 mval = (cutlhs2 * simplexcoefs1[nonbasicnumber] - cutlhs1 * simplexcoefs2[nonbasicnumber]) / (cutlhs2 * bound1 + cutlhs1 * bound2);
302 cutcoefs[ind] =
MIN(sgn * cutlhs2 * (simplexcoefs1[nonbasicnumber] - mvalfloor * bound1), sgn * cutlhs1 * (simplexcoefs2[nonbasicnumber] + mvalceil * bound2));
303 assert(
SCIPisFeasLE(
scip, cutcoefs[ind],
MAX(sgn * cutlhs2 * simplexcoefs1[nonbasicnumber], sgn * cutlhs1 * simplexcoefs2[nonbasicnumber])) );
306 cutcoefs[ind] =
MAX(sgn * cutlhs2 * simplexcoefs1[nonbasicnumber], sgn * cutlhs1 * simplexcoefs2[nonbasicnumber]);
308 cutlhs += cutcoefs[ind] * lb;
322 mval = (cutlhs2 * simplexcoefs1[nonbasicnumber] - cutlhs1 * simplexcoefs2[nonbasicnumber]) / (cutlhs2 * bound1 + cutlhs1 * bound2);
326 cutcoefs[ind] =
MAX(sgn * cutlhs2 * (simplexcoefs1[nonbasicnumber] + mvalfloor * bound1), sgn * cutlhs1 * (simplexcoefs2[nonbasicnumber] - mvalceil * bound2));
327 assert(
SCIPisFeasLE(
scip, -cutcoefs[ind], -
MIN(sgn * cutlhs2 * simplexcoefs1[nonbasicnumber], sgn * cutlhs1 * simplexcoefs2[nonbasicnumber])) );
330 cutcoefs[ind] =
MIN(sgn * cutlhs2 * simplexcoefs1[nonbasicnumber], sgn * cutlhs1 * simplexcoefs2[nonbasicnumber]);
332 cutlhs += cutcoefs[ind] * ub;
343 for (
r = 0;
r < nrows; ++
r)
360 cutcoef =
MAX(sgn * cutlhs2 * simplexcoefs1[nonbasicnumber], sgn * cutlhs1 * simplexcoefs2[nonbasicnumber]);
361 cutlhs -= cutcoef * rhsrow;
369 cutcoef =
MIN(sgn * cutlhs2 * simplexcoefs1[nonbasicnumber], sgn * cutlhs1 * simplexcoefs2[nonbasicnumber]);
370 cutlhs -= cutcoef * lhsrow;
378 for (
c = 0;
c < rownnonz; ++
c)
389 cutcoefs[ind] -= cutcoef * rowvals[
c];
401 for (
c = 0;
c < ncols; ++
c)
417 SCIP_Longint maxdnom;
502 SCIP_Real* cutcoefs =
NULL;
503 SCIP_Real* simplexcoefs1 =
NULL;
504 SCIP_Real* simplexcoefs2 =
NULL;
505 SCIP_Real* coef =
NULL;
506 SCIP_Real* binvrow =
NULL;
507 SCIP_Real* rowsmaxval =
NULL;
508 SCIP_Real* violationarray =
NULL;
509 int* fixings1 =
NULL;
510 int* fixings2 =
NULL;
511 int* basisind =
NULL;
512 int* basisrow =
NULL;
514 int* edgearray =
NULL;
555 if ( ncols == 0 || nrows == 0 )
567 if ( conshdlr ==
NULL )
589 if( conflictgraph ==
NULL )
602 sepadata->lastncutsfound = ncutsfound;
609 for (j = 0; j < ncols; ++j)
616 for (j = 0; j < nrows; ++j)
638 for (j = 0; j < nsos1vars; ++j)
653 for (
i = 0;
i < nsucc; ++
i)
663 fixings1[nrelevantedges] = j;
664 fixings2[nrelevantedges] = succind;
665 edgearray[nrelevantedges] = nrelevantedges;
673 if ( nrelevantedges > 0)
688 maxcuts =
MIN(
sepadata->maxinvcutsroot, nrelevantedges);
690 maxcuts =
MIN(
sepadata->maxinvcuts, nrelevantedges);
709 for (j = 0; j < nrows; ++j)
730 for (
i = 0;
i < nnonz; ++
i)
741 rowsmaxval[j] =
MAX(max, 1.0);
745 for (j = 0; j < ncols; ++j)
753 for (
i = 0;
i < maxcuts; ++
i)
755 SCIP_Bool madeintegral;
769 edgenumber = edgearray[
i];
786 if ( varrank[ind] < 0 )
788 cutrank =
MAX(cutrank, varrank[ind]);
812 if ( varrank[ind] < 0 )
814 cutrank =
MAX(cutrank, varrank[ind]);
824 SCIP_CALL(
generateDisjCutSOS1(
scip, sepa,
depth, rows, nrows, cols, ncols, ndisjcuts,
MAKECONTINTEGRAL,
sepadata->strengthen, cutlhs1, cutlhs2, bound1, bound2, simplexcoefs1, simplexcoefs2, cutcoefs, &row, &madeintegral) );
832 if ( ( madeintegral && (
sepadata->maxrankintegral == -1 || cutrank <= sepadata->maxrankintegral ) )
833 || ( ! madeintegral && (
sepadata->maxrank == -1 || cutrank <= sepadata->maxrank ) ) )
839 SCIP_Bool infeasible;
917 "strengthen cut if integer variables are present.",
921 "node depth of separating bipartite disjunctive cuts (-1: no limit)",
925 "maximal number of separation rounds per iteration in a branching node (-1: no limit)",
929 "maximal number of separation rounds in the root node (-1: no limit)",
933 "maximal number of cuts investigated per iteration in a branching node",
937 "maximal number of cuts investigated per iteration in the root node",
941 "delay separation if number of conflict graph edges is larger than predefined value (-1: no limit)",
945 "maximal rank of a disj. cut that could not be scaled to integral coefficients (-1: unlimited)",
949 "maximal rank of a disj. cut that could be scaled to integral coefficients (-1: unlimited)",
953 "maximal valid range max(|weights|)/min(|weights|) of row weights",
constraint handler for SOS type 1 constraints
#define SCIP_LONGINT_FORMAT
SCIP_DIGRAPH * SCIPgetConflictgraphSOS1(SCIP_CONSHDLR *conshdlr)
int SCIPgetNSOS1Vars(SCIP_CONSHDLR *conshdlr)
SCIP_VAR * SCIPnodeGetVarSOS1(SCIP_DIGRAPH *conflictgraph, int node)
int SCIPdigraphGetNSuccessors(SCIP_DIGRAPH *digraph, int node)
int SCIPdigraphGetNArcs(SCIP_DIGRAPH *digraph)
int * SCIPdigraphGetSuccessors(SCIP_DIGRAPH *digraph, int node)
SCIP_Bool SCIPisStopped(SCIP *scip)
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 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 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)
int SCIPcolGetLPPos(SCIP_COL *col)
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
SCIP_Bool SCIPcolIsIntegral(SCIP_COL *col)
SCIP_Real SCIPcolGetLb(SCIP_COL *col)
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
SCIP_Real SCIPcolGetUb(SCIP_COL *col)
SCIP_BASESTAT SCIPcolGetBasisStatus(SCIP_COL *col)
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
SCIP_RETCODE SCIPgetLPBasisInd(SCIP *scip, int *basisind)
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
SCIP_RETCODE SCIPgetLPBInvARow(SCIP *scip, int r, SCIP_Real *binvrow, SCIP_Real *coefs, int *inds, int *ninds)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
SCIP_RETCODE SCIPgetLPBInvRow(SCIP *scip, int r, SCIP_Real *coefs, int *inds, int *ninds)
#define SCIPallocBufferArray(scip, ptr, num)
#define SCIPfreeBlockMemory(scip, ptr)
#define SCIPfreeBufferArrayNull(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
int SCIProwGetNNonz(SCIP_ROW *row)
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
SCIP_Real SCIPgetRowLPActivity(SCIP *scip, SCIP_ROW *row)
SCIP_Real SCIProwGetRhs(SCIP_ROW *row)
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPmakeRowIntegral(SCIP *scip, SCIP_ROW *row, SCIP_Real mindelta, SCIP_Real maxdelta, SCIP_Longint maxdnom, SCIP_Real maxscale, SCIP_Bool usecontvars, SCIP_Bool *success)
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
SCIP_RETCODE SCIPcreateEmptyRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_SEPA *sepa, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
int SCIProwGetRank(SCIP_ROW *row)
void SCIProwChgRank(SCIP_ROW *row, int rank)
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
SCIP_BASESTAT SCIProwGetBasisStatus(SCIP_ROW *row)
SCIP_RETCODE SCIPincludeSepaBasic(SCIP *scip, SCIP_SEPA **sepa, const char *name, const char *desc, int priority, int freq, SCIP_Real maxbounddist, SCIP_Bool usessubscip, SCIP_Bool delay, SCIP_DECL_SEPAEXECLP((*sepaexeclp)), SCIP_DECL_SEPAEXECSOL((*sepaexecsol)), SCIP_SEPADATA *sepadata)
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa,)
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
SCIP_Bool SCIPsepaWasLPDelayed(SCIP_SEPA *sepa)
SCIP_RETCODE SCIPsetSepaInitsol(SCIP *scip, SCIP_SEPA *sepa,)
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa,)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
int SCIPgetNCutsFound(SCIP *scip)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPfloor(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Real SCIPepsilon(SCIP *scip)
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
SCIP_RETCODE SCIPincludeSepaDisjunctive(SCIP *scip)
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
int SCIPsnprintf(char *t, int len, const char *s,...)
assert(minobj< SCIPgetCutoffbound(scip))
memory allocation routines
public methods for managing constraints
public methods for LP management
public methods for message output
public data structures and miscellaneous methods
methods for sorting joint arrays of various types
public methods for separators
public methods for problem variables
public methods for constraint handler plugins and constraints
public methods for cuts and aggregation rows
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for separator plugins
public methods for solutions
public methods for querying solving statistics
public methods for the branch-and-bound tree
#define DEFAULT_MAXINVCUTS
#define DEFAULT_MAXWEIGHTRANGE
#define DEFAULT_MAXINVCUTSROOT
#define DEFAULT_STRENGTHEN
#define DEFAULT_MAXRANKINTEGRAL
#define DEFAULT_MAXROUNDSROOT
#define DEFAULT_MAXCONFSDELAY
SCIPsepaSetData(sepa, NULL)
static SCIP_RETCODE getSimplexCoefficients(SCIP *scip, SCIP_ROW **rows, int nrows, SCIP_COL **cols, int ncols, SCIP_Real *coef, SCIP_Real *binvrow, SCIP_Real *simplexcoefs, int *nonbasicnumber)
#define SEPA_MAXBOUNDDIST
#define DEFAULT_MAXROUNDS
static SCIP_RETCODE generateDisjCutSOS1(SCIP *scip, SCIP_SEPA *sepa, int depth, SCIP_ROW **rows, int nrows, SCIP_COL **cols, int ncols, int ndisjcuts, SCIP_Bool scale, SCIP_Bool strengthen, SCIP_Real cutlhs1, SCIP_Real cutlhs2, SCIP_Real bound1, SCIP_Real bound2, SCIP_Real *simplexcoefs1, SCIP_Real *simplexcoefs2, SCIP_Real *cutcoefs, SCIP_ROW **row, SCIP_Bool *madeintegral)
static int getVarRank(SCIP *scip, SCIP_Real *binvrow, SCIP_Real *rowsmaxval, SCIP_Real maxweightrange, SCIP_ROW **rows, int nrows)
disjunctive cut separator
enum SCIP_Retcode SCIP_RETCODE
struct SCIP_SepaData SCIP_SEPADATA
#define SCIP_DECL_SEPAEXECLP(x)
#define SCIP_DECL_SEPAFREE(x)
#define SCIP_DECL_SEPAEXITSOL(x)
#define SCIP_DECL_SEPACOPY(x)