mixing/star inequality separator
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:
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) |
#define SEPA_NAME "mixing" |
Definition at line 99 of file sepa_mixing.c.
#define SEPA_DESC "mixing inequality separator" |
Definition at line 100 of file sepa_mixing.c.
#define DEFAULT_MAXROUNDS -1 |
maximal number of mixing separation rounds per node (-1: unlimited)
Definition at line 101 of file sepa_mixing.c.
#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.
#define SEPA_PRIORITY -50 |
Definition at line 103 of file sepa_mixing.c.
#define SEPA_FREQ 10 |
Definition at line 104 of file sepa_mixing.c.
#define SEPA_MAXBOUNDDIST 1.0 |
Definition at line 105 of file sepa_mixing.c.
#define SEPA_USESSUBSCIP FALSE |
does the separator use a secondary SCIP instance?
Definition at line 106 of file sepa_mixing.c.
#define SEPA_DELAY FALSE |
should separation method be delayed, if other separators found cuts?
Definition at line 107 of file sepa_mixing.c.
#define DEFAULT_USELOCALBOUNDS FALSE |
should local bounds be used?
Definition at line 109 of file sepa_mixing.c.
Referenced by SCIPincludeSepaMixing().
#define DEFAULT_ISCUTSONINTS FALSE |
should general/implicit integer variables be used to generate cuts?
Definition at line 110 of file sepa_mixing.c.
Referenced by SCIPincludeSepaMixing().
#define DEFAULT_MAXNUNSUCCESSFUL 10 |
maximal number of consecutive unsuccessful iterations
Definition at line 111 of file sepa_mixing.c.
Referenced by SCIPincludeSepaMixing().
|
static |
adds the given cut
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 assert(), cutoff, FALSE, NULL, SCIP_Bool, SCIP_CALL, SCIP_LONGINT_FORMAT, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPcreateEmptyRowSepa(), SCIPdebugMsg, SCIPflushRowExtensions(), SCIPgetCutEfficacy(), SCIPgetNLPs(), SCIPgetVars(), SCIPinfinity(), SCIPisCutEfficacious(), SCIPprintRow(), SCIPreleaseRow(), SCIProwChgRank(), SCIPsnprintf(), sol, TRUE, and vars.
Referenced by separateCuts().
|
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.:
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(), assert(), cutoff, FALSE, i, NULL, nvars, 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(), sepadata, sol, TRUE, var, and vars.
Referenced by SCIP_DECL_SEPAEXECLP(), and SCIP_DECL_SEPAEXECSOL().
|
static |
copy method for separator plugins (called when SCIP copies plugins)
Definition at line 721 of file sepa_mixing.c.
References assert(), NULL, SCIP_CALL, SCIP_OKAY, SCIPincludeSepaMixing(), SCIPsepaGetName(), and SEPA_NAME.
|
static |
destructor of separator to free user data (called when SCIP is exiting)
Definition at line 735 of file sepa_mixing.c.
References assert(), NULL, SCIP_OKAY, SCIPfreeBlockMemory, SCIPsepaGetData(), SCIPsepaGetName(), SCIPsepaSetData(), SEPA_NAME, and sepadata.
|
static |
LP solution separation method of separator
Definition at line 757 of file sepa_mixing.c.
References assert(), cutoff, depth, nbinvars, ncalls, NULL, nvars, result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPdebugMsg, SCIPgetVarsData(), SCIPsepaGetData(), SCIPsepaGetNCallsAtNode(), sepadata, and separateCuts().
|
static |
arbitrary primal solution separation method of separator
Definition at line 806 of file sepa_mixing.c.
References assert(), cutoff, depth, nbinvars, ncalls, NULL, nvars, result, SCIP_Bool, SCIP_CALL, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_SEPARATED, SCIPdebugMsg, SCIPgetNBinVars(), SCIPgetNVars(), SCIPsepaGetData(), SCIPsepaGetNCallsAtNode(), sepadata, separateCuts(), and sol.