Detailed Description

mixing/star inequality separator

Author: Weikun Chen; Marc Pfetsch

This separator generates cuts based on the mixing set

\[ X = \{ (x,y) \in \{0,1\}^{N \cup M} \times \mathbb{R} \, : \, y \geq a_i x_i, \, \textrm{for} \, i \in N, \, y \leq u - a_i x_i, \, \textrm{for} \, i \in M, \, 0 \leq y \leq u \}, \]

where \(0 \leq a_i \leq u\) for all \(i\). This information can be obtained directly from the variable bounds data structure. The separator will generate three classes of cuts.

VLB: Let \(T\) be a subset of \(N\), wlog, \(T = \{1,\ldots,r\}\) with \(a_1 \leq a_2 \leq \ldots \leq a_r\). Let \(a_0 = 0\). The mixing/star VLB cut is of the form \( y \geq \sum_{i=1}^r (a_i - a_{i-1})x_i \).

VUB: Let \(T\) be a subset of \(M\), wlog, \(T = \{1,\ldots,r\}\) with \(a_1 \leq a_2 \leq \ldots \leq a_r\). Let \(a_0 = 0\). The mixing/star VUB cut is of the form \( y \leq u - \sum_{i=1}^r (a_i - a_{i-1})x_i \).

CONFLICT: Consider \(i \in N\) and \(j \in M\) with \(a_i + a_j > u\). The conflict cut is \(x_i + x_j \leq 1\).

A small example is described in the following to see the generated cuts.

\[ Y = \{ (x,y) \in \{0,1\}^{4} \times \mathbb{R} \, : \, y \geq 2x_1, \, y \geq 3x_2, \, y \leq 4 - x_3, \, y \leq 4 - 2 x_4, \, 0 \leq y \leq 4 \}. \]

In this small example, the mixing/star cuts \(y \geq 2x_1 + x_2\) (VLB) and \(y \leq 4 - x_3 - x_4\) (VUB) will be considered to be generated. Besides the mixing cuts, we also consider the conflict cut \(x_1 + x_3 \leq 1\) (CONFLICT).

For an overview see: Atamturk, A., Nemhauser, G.L. and Savelsbergh, M.W.,
The mixed vertex packing problem.
Mathematical Programming, 89(1), 35-53, 2000.

Some remarks:

Besides the mixing inequality, we also add the conflict inequality.
Currently, the performance is bad on the neos-565672 instance. The reason is that, after adding the separator, SCIP spends a lot of time at the stage of cutting plane generation.
We do not consider sparsity of the cuts as we aim to find a most violated cut.
Besides the most violated cut we consider, we also add an additional variable to make the cut be the strongest one, even the additional variable does not contribute any to the violation.

Definition in file sepa_mixing.c.

#include "blockmemshell/memory.h"
#include "scip/pub_implics.h"
#include "scip/pub_lp.h"
#include "scip/pub_message.h"
#include "scip/pub_misc.h"
#include "scip/pub_sepa.h"
#include "scip/pub_var.h"
#include "scip/scip_branch.h"
#include "scip/scip_cut.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_prob.h"
#include "scip/scip_sepa.h"
#include "scip/scip_sol.h"
#include "scip/scip_solvingstats.h"
#include "scip/scip_var.h"
#include "scip/sepa_mixing.h"
#include "scip/scip_tree.h"
#include <string.h>

Go to the source code of this file.

Macros
#define	SEPA_NAME "mixing"

#define	SEPA_DESC "mixing inequality separator"

#define	DEFAULT_MAXROUNDS -1

#define	DEFAULT_MAXROUNDSROOT -1

#define	SEPA_PRIORITY -50

#define	SEPA_FREQ 10

#define	SEPA_MAXBOUNDDIST 1.0

#define	SEPA_USESSUBSCIP FALSE

#define	SEPA_DELAY FALSE

#define	DEFAULT_USELOCALBOUNDS FALSE

#define	DEFAULT_ISCUTSONINTS FALSE

#define	DEFAULT_MAXNUNSUCCESSFUL 10

Functions
static SCIP_RETCODE	addCut (SCIP scip, SCIP_SEPA sepa, SCIP_SOL sol, SCIP_Real cutcoefs, int cutinds, int cutnnz, SCIP_Real cutrhs, SCIP_Bool cutislocal, SCIP_Bool cutoff, int *ncuts)

static SCIP_RETCODE	separateCuts (SCIP scip, SCIP_SEPA sepa, SCIP_SOL sol, SCIP_Bool cutoff, int *ncuts)

static	SCIP_DECL_SEPACOPY (sepaCopyMixing)

static	SCIP_DECL_SEPAFREE (sepaFreeMixing)

static	SCIP_DECL_SEPAEXECLP (sepaExeclpMixing)

static	SCIP_DECL_SEPAEXECSOL (sepaExecSolMixing)

SCIP_RETCODE	SCIPincludeSepaMixing (SCIP *scip)

Macro Definition Documentation

◆ SEPA_NAME

#define SEPA_NAME "mixing"

Definition at line 99 of file sepa_mixing.c.

Referenced by SCIP_DECL_SEPACOPY(), SCIP_DECL_SEPAFREE(), and SCIPincludeSepaMixing().

◆ SEPA_DESC

#define SEPA_DESC "mixing inequality separator"

Definition at line 100 of file sepa_mixing.c.

Referenced by SCIPincludeSepaMixing().

◆ DEFAULT_MAXROUNDS

#define DEFAULT_MAXROUNDS -1

maximal number of mixing separation rounds per node (-1: unlimited)

Definition at line 101 of file sepa_mixing.c.

Referenced by SCIPincludeSepaMixing().

◆ DEFAULT_MAXROUNDSROOT

#define DEFAULT_MAXROUNDSROOT -1

maximal number of mixing separation rounds in the root node (-1: unlimited)

Definition at line 102 of file sepa_mixing.c.

Referenced by SCIPincludeSepaMixing().

◆ SEPA_PRIORITY

#define SEPA_PRIORITY -50

Definition at line 103 of file sepa_mixing.c.

Referenced by SCIPincludeSepaMixing().

◆ SEPA_FREQ

#define SEPA_FREQ 10

Definition at line 104 of file sepa_mixing.c.

Referenced by SCIPincludeSepaMixing().

◆ SEPA_MAXBOUNDDIST

#define SEPA_MAXBOUNDDIST 1.0

Definition at line 105 of file sepa_mixing.c.

Referenced by SCIPincludeSepaMixing().

◆ SEPA_USESSUBSCIP

#define SEPA_USESSUBSCIP FALSE

does the separator use a secondary SCIP instance?

Definition at line 106 of file sepa_mixing.c.

Referenced by SCIPincludeSepaMixing().

◆ SEPA_DELAY

#define SEPA_DELAY FALSE

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

Definition at line 107 of file sepa_mixing.c.

Referenced by SCIPincludeSepaMixing().

◆ DEFAULT_USELOCALBOUNDS

#define DEFAULT_USELOCALBOUNDS FALSE

should local bounds be used?

Definition at line 109 of file sepa_mixing.c.

Referenced by SCIPincludeSepaMixing().

◆ DEFAULT_ISCUTSONINTS

#define DEFAULT_ISCUTSONINTS FALSE

should general/implied integer variables be used to generate cuts?

Definition at line 110 of file sepa_mixing.c.

Referenced by SCIPincludeSepaMixing().

◆ DEFAULT_MAXNUNSUCCESSFUL

#define DEFAULT_MAXNUNSUCCESSFUL 10

maximal number of consecutive unsuccessful iterations

Definition at line 111 of file sepa_mixing.c.

Referenced by SCIPincludeSepaMixing().

Function Documentation

◆ addCut()

static SCIP_RETCODE addCut	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SOL *	sol,
		SCIP_Real *	cutcoefs,
		int *	cutinds,
		int	cutnnz,
		SCIP_Real	cutrhs,
		SCIP_Bool	cutislocal,
		SCIP_Bool *	cutoff,
		int *	ncuts
	)

static

adds the given cut

Parameters

scip	SCIP data structure
sepa	separator
sol	the solution that should be separated, or NULL for LP solution
cutcoefs	coefficients of active variables in cut
cutinds	problem indices of variables in cut
cutnnz	number of non-zeros in cut
cutrhs	right hand side of cut
cutislocal	Is the cut only locally valid?
cutoff	pointer to store whether a cutoff has been detected
ncuts	pointer to update number of cuts added

Definition at line 130 of file sepa_mixing.c.

References FALSE, NULL, SCIP_CALL, SCIP_MAXSTRLEN, SCIP_OKAY, SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcreateEmptyRowSepa(), SCIPdebugMsg, SCIPflushRowExtensions(), SCIPgetCutEfficacy(), SCIPgetNLPs(), SCIPgetVars(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPprintRow(), SCIPreleaseRow(), SCIProwChgRank(), SCIPsnprintf(), and TRUE.

Referenced by separateCuts().

◆ separateCuts()

static SCIP_RETCODE separateCuts	(	SCIP *	scip,
		SCIP_SEPA *	sepa,
		SCIP_SOL *	sol,
		SCIP_Bool *	cutoff,
		int *	ncuts
	)

static

searches and adds mixing cuts that are violated by the given solution value array

This function implements a separation heuristic that runs in linear time in comparison to the quadratic exact algorithm in Atamturk et al.:

Lower and upper bounds are considered separately. Then possible conflict cuts.
Variable lower/upper bounds data are collected, i.e., the corresponding binary variables and coefficients.
These lists are sorted non-increasingly according to the solution values.
Then binary variables are added in turn as long as their coefficients increase in order to make the coefficients nonnegative. This clearly makes the cuts heuristic, since it is order dependent, but also sparser.
The procedure stops as soon as it reaches 0 solution values.
If the cut is efficious it is added.

Parameters

scip	SCIP data structure
sepa	separator
sol	the solution that should be separated, or NULL for LP solution
cutoff	whether a cutoff has been detected
ncuts	pointer to store the number of generated cuts

Definition at line 221 of file sepa_mixing.c.

References addCut(), FALSE, NULL, REALABS, SCIP_Bool, SCIP_CALL, SCIP_INVALID, SCIP_OKAY, SCIP_Real, SCIP_VARTYPE_BINARY, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPgetNBinVars(), SCIPgetNImplVars(), SCIPgetNIntVars(), SCIPgetNVars(), SCIPgetSolVal(), SCIPgetVars(), SCIPisEfficacious(), SCIPisFeasEQ(), SCIPisFeasGE(), SCIPisFeasGT(), SCIPisFeasLE(), SCIPisFeasZero(), SCIPisGT(), SCIPisLE(), SCIPisLT(), SCIPsepaGetData(), SCIPsortDownRealRealIntInt(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetNVlbs(), SCIPvarGetNVubs(), SCIPvarGetProbindex(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SCIPvarGetVlbCoefs(), SCIPvarGetVlbConstants(), SCIPvarGetVlbVars(), SCIPvarGetVubCoefs(), SCIPvarGetVubConstants(), SCIPvarGetVubVars(), SCIPvarIsBinary(), and TRUE.

Referenced by SCIP_DECL_SEPAEXECLP(), and SCIP_DECL_SEPAEXECSOL().

◆ SCIP_DECL_SEPACOPY()

static SCIP_DECL_SEPACOPY ( sepaCopyMixing )

static

copy method for separator plugins (called when SCIP copies plugins)

Definition at line 721 of file sepa_mixing.c.

References NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeSepaMixing(), SCIPsepaGetName(), and SEPA_NAME.

◆ SCIP_DECL_SEPAFREE()

static SCIP_DECL_SEPAFREE ( sepaFreeMixing )

static

destructor of separator to free user data (called when SCIP is exiting)

Definition at line 735 of file sepa_mixing.c.

References NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaSetData(), and SEPA_NAME.

◆ SCIP_DECL_SEPAEXECLP()

static SCIP_DECL_SEPAEXECLP ( sepaExeclpMixing )

static

LP solution separation method of separator

Definition at line 757 of file sepa_mixing.c.

References NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPdebugMsg, SCIPgetVarsData(), SCIPsepaGetData(), SCIPsepaGetNCallsAtNode(), and separateCuts().

◆ SCIP_DECL_SEPAEXECSOL()

static SCIP_DECL_SEPAEXECSOL ( sepaExecSolMixing )

static

arbitrary primal solution separation method of separator

Definition at line 806 of file sepa_mixing.c.

References NULL, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPdebugMsg, SCIPgetNBinVars(), SCIPgetNVars(), SCIPsepaGetData(), SCIPsepaGetNCallsAtNode(), and separateCuts().

SCIP

Detailed Description

Macros

Functions

Macro Definition Documentation

◆ SEPA_NAME

◆ SEPA_DESC

◆ DEFAULT_MAXROUNDS

◆ DEFAULT_MAXROUNDSROOT

◆ SEPA_PRIORITY

◆ SEPA_FREQ

◆ SEPA_MAXBOUNDDIST

◆ SEPA_USESSUBSCIP

◆ SEPA_DELAY

◆ DEFAULT_USELOCALBOUNDS

◆ DEFAULT_ISCUTSONINTS

◆ DEFAULT_MAXNUNSUCCESSFUL

Function Documentation

◆ addCut()

◆ separateCuts()

◆ SCIP_DECL_SEPACOPY()

◆ SCIP_DECL_SEPAFREE()

◆ SCIP_DECL_SEPAEXECLP()

◆ SCIP_DECL_SEPAEXECSOL()