41 #define SEPA_NAME "disjunctive" 42 #define SEPA_DESC "disjunctive cut separator" 43 #define SEPA_PRIORITY 10 45 #define SEPA_MAXBOUNDDIST 0.0 47 #define SEPA_USESSUBSCIP FALSE 48 #define SEPA_DELAY TRUE 50 #define DEFAULT_MAXRANK 20 51 #define DEFAULT_MAXRANKINTEGRAL -1 52 #define DEFAULT_MAXWEIGHTRANGE 1e+03 53 #define DEFAULT_STRENGTHEN TRUE 55 #define DEFAULT_MAXDEPTH -1 56 #define DEFAULT_MAXROUNDS 25 57 #define DEFAULT_MAXROUNDSROOT 100 58 #define DEFAULT_MAXINVCUTS 50 59 #define DEFAULT_MAXINVCUTSROOT 250 60 #define DEFAULT_MAXCONFSDELAY 100000 62 #define MAKECONTINTEGRAL FALSE 98 assert( scip != NULL );
99 assert( binvrow != NULL || nrows == 0 );
100 assert( rowsmaxval != NULL || nrows == 0 );
101 assert( rows != NULL || nrows == 0 );
104 for (r = 0; r < nrows; ++r)
108 val =
REALABS(binvrow[r] * rowsmaxval[r]);
109 if (
SCIPisGT(scip, val, maxweight) )
114 for (r = 0; r < nrows; ++r)
119 val =
REALABS(binvrow[r] * rowsmaxval[r]);
121 if ( rank > maxrank &&
SCIPisGT(scip, val * maxweightrange, maxweight) )
146 assert( scip != NULL );
147 assert( rows != NULL );
148 assert( nonbasicnumber != NULL );
149 assert( simplexcoefs != NULL );
150 assert( cols != NULL );
157 for (c = 0; c < ncols; ++c)
162 assert( col != NULL );
164 simplexcoefs[(*nonbasicnumber)++] = coef[c];
168 for (r = 0; r < nrows; ++r)
172 assert( row != NULL );
178 simplexcoefs[(*nonbasicnumber)++] = binvrow[r];
219 int nonbasicnumber = 0;
225 assert( scip != NULL );
226 assert( row != NULL );
227 assert( rows != NULL );
228 assert( cols != NULL );
229 assert( simplexcoefs1 != NULL );
230 assert( simplexcoefs2 != NULL );
231 assert( cutcoefs != NULL );
232 assert( sepa != NULL );
233 assert( madeintegral != NULL );
235 *madeintegral =
FALSE;
248 cutlhs = sgn * cutlhs1 * cutlhs2;
251 for (c = 0; c < ncols; ++c)
254 assert( col != NULL );
269 mval = (cutlhs2 * simplexcoefs1[nonbasicnumber] - cutlhs1 * simplexcoefs2[nonbasicnumber]) / (cutlhs2 * bound1 + cutlhs1 * bound2);
273 cutcoefs[ind] = MIN(sgn * cutlhs2 * (simplexcoefs1[nonbasicnumber] - mvalfloor * bound1), sgn * cutlhs1 * (simplexcoefs2[nonbasicnumber] + mvalceil * bound2));
274 assert(
SCIPisFeasLE(scip, cutcoefs[ind],
MAX(sgn * cutlhs2 * simplexcoefs1[nonbasicnumber], sgn * cutlhs1 * simplexcoefs2[nonbasicnumber])) );
277 cutcoefs[ind] =
MAX(sgn * cutlhs2 * simplexcoefs1[nonbasicnumber], sgn * cutlhs1 * simplexcoefs2[nonbasicnumber]);
279 cutlhs += cutcoefs[ind] * lb;
293 mval = (cutlhs2 * simplexcoefs1[nonbasicnumber] - cutlhs1 * simplexcoefs2[nonbasicnumber]) / (cutlhs2 * bound1 + cutlhs1 * bound2);
297 cutcoefs[ind] =
MAX(sgn * cutlhs2 * (simplexcoefs1[nonbasicnumber] + mvalfloor * bound1), sgn * cutlhs1 * (simplexcoefs2[nonbasicnumber] - mvalceil * bound2));
298 assert(
SCIPisFeasLE(scip, -cutcoefs[ind], -MIN(sgn * cutlhs2 * simplexcoefs1[nonbasicnumber], sgn * cutlhs1 * simplexcoefs2[nonbasicnumber])) );
301 cutcoefs[ind] = MIN(sgn * cutlhs2 * simplexcoefs1[nonbasicnumber], sgn * cutlhs1 * simplexcoefs2[nonbasicnumber]);
303 cutlhs += cutcoefs[ind] * ub;
314 for (r = 0; r < nrows; ++r)
331 cutcoef =
MAX(sgn * cutlhs2 * simplexcoefs1[nonbasicnumber], sgn * cutlhs1 * simplexcoefs2[nonbasicnumber]);
332 cutlhs -= cutcoef * rhsrow;
340 cutcoef = MIN(sgn * cutlhs2 * simplexcoefs1[nonbasicnumber], sgn * cutlhs1 * simplexcoefs2[nonbasicnumber]);
341 cutlhs -= cutcoef * lhsrow;
349 for (c = 0; c < rownnonz; ++c)
360 cutcoefs[ind] -= cutcoef * rowvals[c];
373 for (c = 0; c < ncols; ++c)
419 assert( scip != NULL );
420 assert( sepa != NULL );
440 assert( sepadata != NULL );
457 assert(sepadata != NULL);
481 int* fixings1 = NULL;
482 int* fixings2 = NULL;
483 int* basisind = NULL;
484 int* basisrow = NULL;
486 int* edgearray = NULL;
501 assert( sepa != NULL );
503 assert( scip != NULL );
504 assert( result != NULL );
528 if ( ncols == 0 || nrows == 0 )
531 assert( cols != NULL );
532 assert( rows != NULL );
536 assert( sepadata != NULL );
539 conshdlr = sepadata->conshdlr;
540 if ( conshdlr == NULL )
550 if ( ( sepadata->maxdepth >= 0 && sepadata->maxdepth < depth )
551 || ( depth == 0 && sepadata->maxinvcutsroot == 0 )
552 || ( depth > 0 && sepadata->maxinvcuts == 0 ) )
557 if ( (depth == 0 && sepadata->maxroundsroot >= 0 && ncalls >= sepadata->maxroundsroot)
558 || (depth > 0 && sepadata->maxrounds >= 0 && ncalls >= sepadata->maxrounds) )
566 if ( sepadata->maxconfsdelay >= 0 && nedges >= sepadata->maxconfsdelay )
573 sepadata->lastncutsfound = ncutsfound;
580 for (j = 0; j < ncols; ++j)
587 for (j = 0; j < nrows; ++j)
609 for (j = 0; j < nsos1vars; ++j)
624 for (i = 0; i < nsucc; ++i)
634 fixings1[nrelevantedges] = j;
635 fixings2[nrelevantedges] = succind;
636 edgearray[nrelevantedges] = nrelevantedges;
644 if ( nrelevantedges > 0)
659 maxcuts = MIN(sepadata->maxinvcutsroot, nrelevantedges);
661 maxcuts = MIN(sepadata->maxinvcuts, nrelevantedges);
662 assert( maxcuts > 0 );
680 for (j = 0; j < nrows; ++j)
696 assert( row != NULL );
701 for (i = 0; i < nnonz; ++i)
712 rowsmaxval[j] =
MAX(max, 1.0);
716 for (j = 0; j < ncols; ++j)
724 for (i = 0; i < maxcuts; ++i)
740 edgenumber = edgearray[i];
757 if ( varrank[ind] < 0 )
758 varrank[ind] =
getVarRank(scip, binvrow, rowsmaxval, sepadata->maxweightrange, rows, nrows);
759 cutrank =
MAX(cutrank, varrank[ind]);
784 if ( varrank[ind] < 0 )
785 varrank[ind] =
getVarRank(scip, binvrow, rowsmaxval, sepadata->maxweightrange, rows, nrows);
786 cutrank =
MAX(cutrank, varrank[ind]);
796 SCIP_CALL(
generateDisjCutSOS1(scip, sepa, rows, nrows, cols, ncols, ndisjcuts,
MAKECONTINTEGRAL, sepadata->strengthen, cutlhs1, cutlhs2, bound1, bound2, simplexcoefs1, simplexcoefs2, cutcoefs, &row, &madeintegral) );
804 if ( ( madeintegral && ( sepadata->maxrankintegral == -1 || cutrank <= sepadata->maxrankintegral ) )
805 || ( ! madeintegral && ( sepadata->maxrank == -1 || cutrank <= sepadata->maxrank ) ) )
844 SCIPdebugMsg(scip,
"Number of found disjunctive cuts: %d.\n", ndisjcuts);
873 sepadata->conshdlr = NULL;
874 sepadata->lastncutsfound = 0;
880 assert( sepa != NULL );
889 "strengthen cut if integer variables are present.",
893 "node depth of separating bipartite disjunctive cuts (-1: no limit)",
897 "maximal number of separation rounds per iteration in a branching node (-1: no limit)",
901 "maximal number of separation rounds in the root node (-1: no limit)",
905 "maximal number of cuts investigated per iteration in a branching node",
909 "maximal number of cuts investigated per iteration in the root node",
913 "delay separation if number of conflict graph edges is larger than predefined value (-1: no limit)",
917 "maximal rank of a disj. cut that could not be scaled to integral coefficients (-1: unlimited)",
921 "maximal rank of a disj. cut that could be scaled to integral coefficients (-1: unlimited)",
925 "maximal valid range max(|weights|)/min(|weights|) of row weights",
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPgetLPBInvRow(SCIP *scip, int r, SCIP_Real *coefs, int *inds, int *ninds)
#define DEFAULT_MAXINVCUTS
static SCIP_DECL_SEPAEXECLP(sepaExeclpDisjunctive)
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
static SCIP_DECL_SEPAEXITSOL(sepaInitsolDisjunctive)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
#define DEFAULT_MAXINVCUTSROOT
SCIP_BASESTAT SCIPcolGetBasisStatus(SCIP_COL *col)
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
int SCIProwGetNNonz(SCIP_ROW *row)
int * SCIPdigraphGetSuccessors(SCIP_DIGRAPH *digraph, int node)
SCIP_Real SCIProwGetLhs(SCIP_ROW *row)
SCIP_Bool SCIPcolIsIntegral(SCIP_COL *col)
SCIP_Real SCIPcolGetUb(SCIP_COL *col)
SCIP_BASESTAT SCIProwGetBasisStatus(SCIP_ROW *row)
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPgetNSOS1Vars(SCIP_CONSHDLR *conshdlr)
int SCIPsnprintf(char *t, int len, const char *s,...)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
enum SCIP_Retcode SCIP_RETCODE
#define DEFAULT_MAXWEIGHTRANGE
#define SCIPfreeBlockMemory(scip, ptr)
disjunctive cut separator
void SCIPsortDownRealInt(SCIP_Real *realarray, int *intarray, int len)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_RETCODE SCIPgetLPColsData(SCIP *scip, SCIP_COL ***cols, int *ncols)
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
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_Real SCIPepsilon(SCIP *scip)
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
SCIP_Bool SCIProwIsInLP(SCIP_ROW *row)
#define SEPA_MAXBOUNDDIST
SCIP_Bool SCIPisLPSolBasic(SCIP *scip)
SCIP_Bool SCIPisCutEfficacious(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut)
SCIP_Real SCIPcolGetPrimsol(SCIP_COL *col)
int SCIPgetNCutsFound(SCIP *scip)
#define SCIPfreeBufferArrayNull(scip, ptr)
int SCIPsepaGetNCallsAtNode(SCIP_SEPA *sepa)
SCIP_Real SCIPcolGetLb(SCIP_COL *col)
static SCIP_DECL_SEPAFREE(sepaFreeDisjunctive)
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
SCIP_RETCODE SCIPincludeSepaDisjunctive(SCIP *scip)
SCIP_RETCODE SCIPsetSepaInitsol(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAINITSOL((*sepainitsol)))
#define DEFAULT_MAXCONFSDELAY
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)
SCIP_Real SCIPgetRowLPActivity(SCIP *scip, SCIP_ROW *row)
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
SCIP_DIGRAPH * SCIPgetConflictgraphSOS1(SCIP_CONSHDLR *conshdlr)
SCIP_COL ** SCIProwGetCols(SCIP_ROW *row)
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
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_Bool SCIPsepaWasLPDelayed(SCIP_SEPA *sepa)
#define SCIPallocBufferArray(scip, ptr, num)
SCIP_RETCODE SCIPgetLPBInvARow(SCIP *scip, int r, SCIP_Real *binvrow, SCIP_Real *coefs, int *inds, int *ninds)
SCIP_Real * SCIProwGetVals(SCIP_ROW *row)
static SCIP_DECL_SEPACOPY(sepaCopyDisjunctive)
int SCIPdigraphGetNSuccessors(SCIP_DIGRAPH *digraph, int node)
SCIP_LPSOLSTAT SCIPgetLPSolstat(SCIP *scip)
int SCIPgetDepth(SCIP *scip)
int SCIPdigraphGetNArcs(SCIP_DIGRAPH *digraph)
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)
static int getVarRank(SCIP *scip, SCIP_Real *binvrow, SCIP_Real *rowsmaxval, SCIP_Real maxweightrange, SCIP_ROW **rows, int nrows)
SCIP_VAR * SCIPnodeGetVarSOS1(SCIP_DIGRAPH *conflictgraph, int node)
#define DEFAULT_MAXROUNDS
#define DEFAULT_STRENGTHEN
SCIP_COL * SCIPvarGetCol(SCIP_VAR *var)
SCIP_RETCODE SCIPgetLPBasisInd(SCIP *scip, int *basisind)
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)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
int SCIProwGetRank(SCIP_ROW *row)
SCIP_Real SCIProwGetConstant(SCIP_ROW *row)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_VAR * SCIPcolGetVar(SCIP_COL *col)
#define DEFAULT_MAXROUNDSROOT
void SCIProwChgRank(SCIP_ROW *row, int rank)
static SCIP_RETCODE generateDisjCutSOS1(SCIP *scip, SCIP_SEPA *sepa, 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)
SCIP_Bool SCIPisFeasPositive(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisStopped(SCIP *scip)
constraint handler for SOS type 1 constraints
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
#define DEFAULT_MAXRANKINTEGRAL
SCIP_Real SCIPsumepsilon(SCIP *scip)
SCIP_RETCODE SCIPgetLPRowsData(SCIP *scip, SCIP_ROW ***rows, int *nrows)
SCIP_Real SCIPceil(SCIP *scip, SCIP_Real val)
SCIP_Longint SCIPgetNLPs(SCIP *scip)
int SCIPcolGetLPPos(SCIP_COL *col)
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_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_Real SCIPfloor(SCIP *scip, SCIP_Real val)
struct SCIP_SepaData SCIP_SEPADATA
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_Bool SCIPvarIsActive(SCIP_VAR *var)