Detailed Description

disjunctive cut separator

Author: Tobias Fischer; Marc Pfetsch

We separate disjunctive cuts for two term disjunctions of the form \(x_1 = 0 \vee x_2 = 0\). They can be generated directly from the simplex tableau. For further information, we refer to
"A complementarity-based partitioning and disjunctive cut algorithm for mathematical programming problems with equilibrium constraints"
Júdice, J.J., Sherali, H.D., Ribeiro, I.M., Faustino, A.M., Journal of Global Optimization 36(1), 89–114 (2006)

Cut coefficients belonging to integer variables can be strengthened by the 'monoidal cut strengthening' procedure, see
"Strengthening cuts for mixed integer programs"
Egon Balas, Robert G. Jeroslow, European Journal of Operational Research, Volume 4, Issue 4, 1980, Pages 224-234

Definition in file sepa_disjunctive.c.

#include "blockmemshell/memory.h"
#include "scip/cons_sos1.h"
#include "scip/pub_cons.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_misc_sort.h"
#include "scip/pub_sepa.h"
#include "scip/pub_var.h"
#include "scip/scip_cons.h"
#include "scip/scip_cut.h"
#include "scip/scip_general.h"
#include "scip/scip_lp.h"
#include "scip/scip_mem.h"
#include "scip/scip_message.h"
#include "scip/scip_numerics.h"
#include "scip/scip_param.h"
#include "scip/scip_sepa.h"
#include "scip/scip_sol.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_tree.h"
#include "scip/sepa_disjunctive.h"
#include <string.h>

Go to the source code of this file.

Macros
#define	SEPA_NAME "disjunctive"

#define	SEPA_DESC "disjunctive cut separator"

#define	SEPA_PRIORITY 10

#define	SEPA_FREQ 0

#define	SEPA_MAXBOUNDDIST 0.0

#define	SEPA_USESSUBSCIP FALSE

#define	SEPA_DELAY TRUE

#define	DEFAULT_MAXRANK 20

#define	DEFAULT_MAXRANKINTEGRAL -1

#define	DEFAULT_MAXWEIGHTRANGE 1e+03

#define	DEFAULT_STRENGTHEN TRUE

#define	DEFAULT_MAXDEPTH -1

#define	DEFAULT_MAXROUNDS 25

#define	DEFAULT_MAXROUNDSROOT 100

#define	DEFAULT_MAXINVCUTS 50

#define	DEFAULT_MAXINVCUTSROOT 250

#define	DEFAULT_MAXCONFSDELAY 100000

#define	MAKECONTINTEGRAL FALSE

Functions
static int	getVarRank (SCIP scip, SCIP_Real binvrow, SCIP_Real rowsmaxval, SCIP_Real maxweightrange, SCIP_ROW *rows, int nrows)

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)

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	SCIP_DECL_SEPACOPY (sepaCopyDisjunctive)

static	SCIP_DECL_SEPAFREE (sepaFreeDisjunctive)

static	SCIP_DECL_SEPAEXITSOL (sepaInitsolDisjunctive)

static	SCIP_DECL_SEPAEXECLP (sepaExeclpDisjunctive)

SCIP_RETCODE	SCIPincludeSepaDisjunctive (SCIP *scip)

Macro Definition Documentation

◆ SEPA_NAME

#define SEPA_NAME "disjunctive"

Definition at line 60 of file sepa_disjunctive.c.

Referenced by SCIP_DECL_SEPACOPY(), SCIP_DECL_SEPAEXECLP(), SCIP_DECL_SEPAFREE(), and SCIPincludeSepaDisjunctive().

◆ SEPA_DESC

#define SEPA_DESC "disjunctive cut separator"

Definition at line 61 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

◆ SEPA_PRIORITY

#define SEPA_PRIORITY 10

priority for separation

Definition at line 62 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

◆ SEPA_FREQ

#define SEPA_FREQ 0

frequency for separating cuts; zero means to separate only in the root node

Definition at line 63 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST 0.0

maximal relative distance from the current node's dual bound to primal bound compared to best node's dual bound for applying separation.

Definition at line 64 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

◆ SEPA_USESSUBSCIP

#define SEPA_USESSUBSCIP FALSE

does the separator use a secondary SCIP instance?

Definition at line 67 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

◆ SEPA_DELAY

#define SEPA_DELAY TRUE

should separation method be delayed, if other separators found cuts?

Definition at line 68 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

◆ DEFAULT_MAXRANK

#define DEFAULT_MAXRANK 20

maximal rank of a cut that could not be scaled to integral coefficients (-1: unlimited)

Definition at line 70 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

◆ DEFAULT_MAXRANKINTEGRAL

#define DEFAULT_MAXRANKINTEGRAL -1

maximal rank of a cut that could be scaled to integral coefficients (-1: unlimited)

Definition at line 71 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

◆ DEFAULT_MAXWEIGHTRANGE

#define DEFAULT_MAXWEIGHTRANGE 1e+03

maximal valid range max(|weights|)/min(|weights|) of row weights

Definition at line 72 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

◆ DEFAULT_STRENGTHEN

#define DEFAULT_STRENGTHEN TRUE

strengthen cut if integer variables are present

Definition at line 73 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

◆ DEFAULT_MAXDEPTH

#define DEFAULT_MAXDEPTH -1

node depth of separating cuts (-1: no limit)

Definition at line 75 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

◆ DEFAULT_MAXROUNDS

#define DEFAULT_MAXROUNDS 25

maximal number of separation rounds in a branching node (-1: no limit)

Definition at line 76 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

◆ DEFAULT_MAXROUNDSROOT

#define DEFAULT_MAXROUNDSROOT 100

maximal number of separation rounds in the root node (-1: no limit)

Definition at line 77 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

◆ DEFAULT_MAXINVCUTS

#define DEFAULT_MAXINVCUTS 50

maximal number of cuts investigated per iteration in a branching node

Definition at line 78 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

◆ DEFAULT_MAXINVCUTSROOT

#define DEFAULT_MAXINVCUTSROOT 250

maximal number of cuts investigated per iteration in the root node

Definition at line 79 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

◆ DEFAULT_MAXCONFSDELAY

#define DEFAULT_MAXCONFSDELAY 100000

delay separation if number of conflict graph edges is larger than predefined value (-1: no limit)

Definition at line 80 of file sepa_disjunctive.c.

Referenced by SCIPincludeSepaDisjunctive().

◆ MAKECONTINTEGRAL

#define MAKECONTINTEGRAL FALSE

convert continuous variable to integral variables in SCIPmakeRowIntegral()

Definition at line 82 of file sepa_disjunctive.c.

Referenced by SCIP_DECL_SEPAEXECLP().

Function Documentation

◆ getVarRank()

static int getVarRank	(	SCIP *	scip,
		SCIP_Real *	binvrow,
		SCIP_Real *	rowsmaxval,
		SCIP_Real	maxweightrange,
		SCIP_ROW **	rows,
		int	nrows
	)

static

gets rank of variable corresponding to row of \(B^{-1}\)

Parameters

scip	SCIP pointer
binvrow	row of \(B^{-1}\)
rowsmaxval	maximal row multiplicator from nonbasic matrix A_N
maxweightrange	maximal valid range max(\|weights\|)/min(\|weights\|) of row weights
rows	rows of LP relaxation of scip
nrows	number of rows

Definition at line 105 of file sepa_disjunctive.c.

References getSimplexCoefficients(), NULL, r, REALABS, SCIP_Real, SCIPisGT(), and SCIProwGetRank().

Referenced by SCIP_DECL_SEPAEXECLP().

◆ getSimplexCoefficients()

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
	)

static

gets the nonbasic coefficients of a simplex row

Parameters

scip	SCIP pointer
rows	LP rows
nrows	number LP rows
cols	LP columns
ncols	number of LP columns
coef	row of \(B^{-1} \cdot A\)
binvrow	row of \(B^{-1}\)
simplexcoefs	pointer to store the nonbasic simplex-coefficients
nonbasicnumber	pointer to store the number of nonbasic simplex-coefficients

Definition at line 151 of file sepa_disjunctive.c.

References generateDisjCutSOS1(), NULL, r, SCIP_BASESTAT_LOWER, SCIP_BASESTAT_UPPER, SCIP_OKAY, SCIPcolGetBasisStatus(), SCIPgetRowLPActivity(), SCIPisFeasZero(), SCIProwGetBasisStatus(), SCIProwGetLhs(), and SCIProwGetRhs().

Referenced by getVarRank(), and SCIP_DECL_SEPAEXECLP().

◆ generateDisjCutSOS1()

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

computes a disjunctive cut inequality based on two simplex tableau rows

Parameters

scip	SCIP pointer
sepa	separator
depth	current depth
rows	LP rows
nrows	number of LP rows
cols	LP columns
ncols	number of LP columns
ndisjcuts	number of disjunctive cuts found so far
scale	should cut be scaled
strengthen	should cut be strengthened if integer variables are present
cutlhs1	left hand side of the first simplex row
cutlhs2	left hand side of the second simplex row
bound1	bound of first simplex row
bound2	bound of second simplex row
simplexcoefs1	simplex coefficients of first row
simplexcoefs2	simplex coefficients of second row
cutcoefs	pointer to store cut coefficients (length: nscipvars)
row	pointer to store disjunctive cut inequality
madeintegral	pointer to store whether cut has been scaled to integral values