# SCIP

Solving Constraint Integer Programs

sepa_mixing.c File Reference

## 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)

## ◆ SEPA_NAME

 #define SEPA_NAME   "mixing"

Definition at line 90 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 91 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 92 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 93 of file sepa_mixing.c.

Referenced by SCIPincludeSepaMixing().

## ◆ SEPA_PRIORITY

 #define SEPA_PRIORITY   -50

Definition at line 94 of file sepa_mixing.c.

Referenced by SCIPincludeSepaMixing().

## ◆ SEPA_FREQ

 #define SEPA_FREQ   10

Definition at line 95 of file sepa_mixing.c.

Referenced by SCIPincludeSepaMixing().

## ◆ SEPA_MAXBOUNDDIST

 #define SEPA_MAXBOUNDDIST   1.0

Definition at line 96 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 97 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 98 of file sepa_mixing.c.

Referenced by SCIPincludeSepaMixing().

## ◆ DEFAULT_USELOCALBOUNDS

 #define DEFAULT_USELOCALBOUNDS   FALSE

should local bounds be used?

Definition at line 100 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 101 of file sepa_mixing.c.

Referenced by SCIPincludeSepaMixing().

## ◆ DEFAULT_MAXNUNSUCCESSFUL

 #define DEFAULT_MAXNUNSUCCESSFUL   10

maximal number of consecutive unsuccessful iterations

Definition at line 102 of file sepa_mixing.c.

Referenced by SCIPincludeSepaMixing().

## Function Documentation

 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

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 121 of file sepa_mixing.c.

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 212 of file sepa_mixing.c.

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 712 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 726 of file sepa_mixing.c.

## ◆ SCIP_DECL_SEPAEXECLP()

 static SCIP_DECL_SEPAEXECLP ( sepaExeclpMixing )
static

LP solution separation method of separator

Definition at line 748 of file sepa_mixing.c.

## ◆ SCIP_DECL_SEPAEXECSOL()

 static SCIP_DECL_SEPAEXECSOL ( sepaExecSolMixing )
static

arbitrary primal solution separation method of separator

Definition at line 797 of file sepa_mixing.c.