Detailed Description
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:
- 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/implicit 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 |
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_LONGINT_FORMAT, 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 |
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 |
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 |
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 |
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 |
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().