Scippy

SCIP

Solving Constraint Integer Programs

cons_indicator.c File Reference

Detailed Description

constraint handler for indicator constraints

Author
Marc Pfetsch

An indicator constraint is given by a binary variable \(y\) and an inequality \(ax \leq b\). It states that if \(y = 1\) then \(ax \leq b\) holds.

This constraint is handled by adding a slack variable \(s:\; ax - s \leq b\) with \(s \geq 0\). The constraint is enforced by fixing \(s\) to 0 if \(y = 1\).

Note
The constraint only implements an implication not an equivalence, i.e., it does not ensure that \(y = 1\) if \(ax \leq b\) or equivalently if \(s = 0\) holds.

This constraint is equivalent to a linear constraint \(ax - s \leq b\) and an SOS1 constraint on \(y\) and \(s\) (at most one should be nonzero). In the indicator context we can, however, separate more inequalities.

The name indicator apparently comes from CPLEX.

Separation Methods

We now explain the handling of indicator constraints in more detail. The indicator constraint handler adds an inequality for each indicator constraint. We assume that this system (with added slack variables) is \( Ax - s \leq b \), where \( x \) are the original variables and \( s \) are the slack variables added by the indicator constraint. Variables \( y \) are the binary variables corresponding to the indicator constraints.

Note
In the implementation, we assume that bounds on the original variables \(x\) cannot be influenced by the indicator constraint. If it should be possible to relax these constraints as well, then these constraints have to be added as indicator constraints.

We separate inequalities by using the so-called alternative polyhedron.

Separation via the Alternative Polyhedron

We now describe the separation method of the first method in more detail.

Consider the LP-relaxation of the current subproblem:

\[ \begin{array}{ll} min & c^T x + d^T z\\ & A x - s \leq b, \\ & D x + C z \leq f, \\ & l \leq x \leq u, \\ & u \leq z \leq v, \\ & 0 \leq s. \end{array} \]

As above \(Ax - s \leq b\) contains all inequalities corresponding to indicator constraints, while the system \(Dx + Cy \leq f\) contains all other inequalities (which are ignored in the following). Similarly, variables \(z\) not appearing in indicator constraints are ignored. Bounds for the variables \(x_j\) can be given, in particular, variables can be fixed. Note that \(s \leq 0\) renders the system infeasible.

To generate cuts, we construct the so-called alternative polyhedron:

\[ \begin{array}{ll} P = \{ (w,r,t) : & A^T w - r + t = 0,\\ & b^T w - l^T r + u^T t = -1,\\ & w, r, t \geq 0 \}. \end{array} \]

Here, \(r\) and \(t\) correspond to the lower and upper bounds on \(x\), respectively.

It turns out that the vertices of \(P\) correspond to minimal infeasible subsystems of \(A x \leq b\), \(l \leq x \leq u\). If \(I\) is the index set of such a system, it follows that not all \(s_i\) for \(i \in I\) can be 0, i.e., \(y_i\) can be 1. In other words, the following cut is valid:

\[ \sum_{i \in I} y_i \leq |I| - 1. \]

Separation heuristic

We separate the above inequalities by a heuristic described in

Branch-And-Cut for the Maximum Feasible Subsystem Problem,
Marc Pfetsch, SIAM Journal on Optimization 19, No.1, 21-38 (2008)

The first step in the separation heuristic is to apply the transformation \(\bar{y} = 1 - y\), which transforms the above inequality into the constraint

\[ \sum_{i \in I} \bar{y}_i \geq 1, \]

that is, it is a set covering constraint on the negated variables.

The basic idea is to use the current solution to the LP relaxation and use it as the objective, when optimizing of the alternative polyhedron. Since any vertex corresponds to such an inequality, we can check whether it is violated. To enlarge the chance that we find a violated inequality, we perform a fixing procedure, in which the variable corresponding to an arbitrary element of the last IIS \(I\) is fixed to zero, i.e., cannot be used in the next IISs. This is repeated until the corresponding alternative polyhedron is infeasible, i.e., we have obtained an IIS-cover. For more details see the paper above.

Preprocessing

Since each indicator constraint adds a linear constraint to the formulation, preprocessing of the linear constraints change the above approach as follows.

The system as present in the formulation is the following (ignoring variables that are not contained in indicator constraints and the objective function):

\[ \begin{array}{ll} & A x - s \leq b, \\ & l \leq x \leq u, \\ & s \leq 0. \end{array} \]

Note again that the requirement \(s \leq 0\) leads to an infeasible system. Consider now the preprocessing of the linear constraint (aggregation, bound strengthening, etc.) and assume that this changes the above system to the following:

\[ \begin{array}{ll} & \tilde{A} x - \tilde{B} s \leq \tilde{b}, \\ & \tilde{l} \leq x \leq \tilde{u}, \\ & s \leq 0. \\ \end{array} \]

Note that we forbid multi-aggregation of the \(s\) variables in order to be able to change their bounds in propagation/branching. The corresponding alternative system is the following:

\[ \begin{array}{ll} & \tilde{A}^T w - r + t = 0,\\ & - \tilde{B}^T w + v = 0,\\ & b^T w - l^T r + u^T t = -1,\\ & w, v, r, t \geq 0 \end{array} \qquad \Leftrightarrow \qquad \begin{array}{ll} & \tilde{A}^T w - r + t = 0,\\ & \tilde{B}^T w \geq 0,\\ & b^T w - l^T r + u^T t = -1,\\ & w, r, t \geq 0, \end{array} \]

where the second form arises by substituting \(v \geq 0\). A closer look at this system reveals that it is not larger than the original one:

  • (Multi-)Aggregation of variables \(x\) will remove these variables from the formulation, such that the corresponding column of \(\tilde{A}\) (row of \(\tilde{A}^T\)) will be zero.
  • The rows of \(\tilde{B}^T\) are not unit vectors, i.e., do not correspond to redundant nonnegativity constraints, only if the corresponding slack variables appear in an aggregation.

Taken together, these two observations yield the conclusion that the new system is roughly as large as the original one.

Note
Because of possible (multi-)aggregation it might happen that the linear constraint corresponding to an indicator constraint becomes redundant and is deleted. From this we cannot conclude that the indicator constraint is redundant as well (i.e. always fulfilled), because the corresponding slack variable is still present and its setting to 0 might influence other (linear) constraints. Thus, we have to rely on the dual presolving of the linear constraints to detect this case: If the linear constraint is really redundant, i.e., is always fulfilled, it is deleted and the slack variable can be fixed to 0. In this case, the indicator constraint can be deleted as well.

Definition in file cons_indicator.c.

#include <assert.h>
#include <string.h>
#include "scip/cons_indicator.h"
#include "scip/cons_linear.h"
#include "scip/cons_logicor.h"
#include "scip/cons_varbound.h"
#include "scip/cons_quadratic.h"
#include "scip/heur_trysol.h"
#include "scip/heur_indicator.h"
#include "scip/pub_misc.h"

Go to the source code of this file.

Macros

#define CONSHDLR_NAME   "indicator"
 
#define CONSHDLR_DESC   "indicator constraint handler"
 
#define CONSHDLR_SEPAPRIORITY   10
 
#define CONSHDLR_ENFOPRIORITY   -100
 
#define CONSHDLR_CHECKPRIORITY   -6000000
 
#define CONSHDLR_SEPAFREQ   10
 
#define CONSHDLR_PROPFREQ   1
 
#define CONSHDLR_EAGERFREQ   100
 
#define CONSHDLR_MAXPREROUNDS   -1
 
#define CONSHDLR_DELAYSEPA   FALSE
 
#define CONSHDLR_DELAYPROP   FALSE
 
#define CONSHDLR_NEEDSCONS   TRUE
 
#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_FAST
 
#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP
 
#define EVENTHDLR_BOUND_NAME   "indicatorbound"
 
#define EVENTHDLR_BOUND_DESC   "bound change event handler for indicator constraints"
 
#define EVENTHDLR_RESTART_NAME   "indicatorrestart"
 
#define EVENTHDLR_RESTART_DESC   "force restart if absolute gap is 1 or enough binary variables have been fixed"
 
#define CONFLICTHDLR_NAME   "indicatorconflict"
 
#define CONFLICTHDLR_DESC   "replace slack variables and generate logicor constraints"
 
#define CONFLICTHDLR_PRIORITY   200000
 
#define LINCONSUPGD_PRIORITY   +100000
 
#define DEFAULT_BRANCHINDICATORS   FALSE
 
#define DEFAULT_GENLOGICOR   FALSE
 
#define DEFAULT_ADDCOUPLING   TRUE
 
#define DEFAULT_MAXCOUPLINGVALUE   1e4
 
#define DEFAULT_ADDCOUPLINGCONS   FALSE
 
#define DEFAULT_SEPACOUPLINGCUTS   TRUE
 
#define DEFAULT_SEPACOUPLINGLOCAL   FALSE
 
#define DEFAULT_SEPACOUPLINGVALUE   1e4
 
#define DEFAULT_SEPAALTERNATIVELP   FALSE
 
#define DEFAULT_SEPAPERSPECTIVE   FALSE
 
#define DEFAULT_SEPAPERSPLOCAL   TRUE
 
#define DEFAULT_MAXSEPANONVIOLATED   3
 
#define DEFAULT_TRYSOLFROMCOVER   FALSE
 
#define DEFAULT_UPGRADELINEAR   FALSE
 
#define DEFAULT_USEOTHERCONSS   FALSE
 
#define DEFAULT_USEOBJECTIVECUT   FALSE
 
#define DEFAULT_UPDATEBOUNDS   FALSE
 
#define DEFAULT_MAXCONDITIONALTLP   0.0
 
#define DEFAULT_MAXSEPACUTS   100
 
#define DEFAULT_MAXSEPACUTSROOT   2000
 
#define DEFAULT_REMOVEINDICATORS   FALSE
 
#define DEFAULT_GENERATEBILINEAR   FALSE
 
#define DEFAULT_SCALESLACKVAR   FALSE
 
#define DEFAULT_NOLINCONSCONT   FALSE
 
#define DEFAULT_TRYSOLUTIONS   TRUE
 
#define DEFAULT_ENFORCECUTS   FALSE
 
#define DEFAULT_DUALREDUCTIONS   TRUE
 
#define DEFAULT_ADDOPPOSITE   FALSE
 
#define DEFAULT_CONFLICTSUPGRADE   FALSE
 
#define DEFAULT_FORCERESTART   FALSE
 
#define DEFAULT_RESTARTFRAC   0.9
 
#define OBJEPSILON   0.001
 
#define SEPAALTTHRESHOLD   10
 
#define MAXROUNDINGROUNDS   1
 
#define SCIP_CALL_PARAM(x)
 

Functions

static SCIP_DECL_EVENTEXEC (eventExecIndicatorBound)
 
static SCIP_DECL_EVENTEXEC (eventExecIndicatorRestart)
 
static SCIP_DECL_CONFLICTFREE (conflictFreeIndicator)
 
static SCIP_DECL_CONFLICTEXEC (conflictExecIndicator)
 
static SCIP_RETCODE checkTransferBoolParam (SCIP *scip, SCIP_PARAM *param, const char *name, SCIP_Bool newvalue, SCIP_Bool *value)
 
static SCIP_DECL_PARAMCHGD (paramChangedIndicator)
 
static SCIP_Real varGetObjDelta (SCIP_VAR *var)
 
static SCIP_RETCODE consdataEnsureAddLinConsSize (SCIP *scip, SCIP_CONSHDLR *conshdlr, int num)
 
static SCIP_RETCODE initAlternativeLP (SCIP *scip, SCIP_CONSHDLR *conshdlr)
 
static SCIP_RETCODE checkLPBoundsClean (SCIP *scip, SCIP_LPI *lp, int nconss, SCIP_CONS **conss)
 
static SCIP_RETCODE setAltLPObj (SCIP *scip, SCIP_LPI *lp, SCIP_SOL *sol, int nconss, SCIP_CONS **conss)
 
static SCIP_RETCODE setAltLPObjZero (SCIP *scip, SCIP_LPI *lp, int nconss, SCIP_CONS **conss)
 
static SCIP_RETCODE fixAltLPVariables (SCIP *scip, SCIP_LPI *lp, int nconss, SCIP_CONS **conss, SCIP_Bool *S)
 
static SCIP_RETCODE fixAltLPVariable (SCIP_LPI *lp, int ind)
 
static SCIP_RETCODE unfixAltLPVariable (SCIP_LPI *lp, int ind)
 
static SCIP_RETCODE unfixAltLPVariables (SCIP *scip, SCIP_LPI *lp, int nconss, SCIP_CONS **conss, SCIP_Bool *S)
 
static SCIP_RETCODE updateFirstRow (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata)
 
static SCIP_RETCODE updateFirstRowGlobal (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata)
 
static SCIP_RETCODE checkIISlocal (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_Real *vector, SCIP_Bool *isLocal)
 
static SCIP_RETCODE scaleFirstRow (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata)
 
static SCIP_RETCODE addAltLPColumn (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_VAR *slackvar, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real rhscoef, SCIP_Real objcoef, SCIP_Real sign, SCIP_Bool colfree, int *colindex)
 
static SCIP_RETCODE addAltLPConstraint (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *lincons, SCIP_VAR *slackvar, SCIP_Real objcoef, int *colindex)
 
static SCIP_RETCODE addAltLPRow (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_ROW *row, SCIP_Real objcoef, int *colindex)
 
static SCIP_RETCODE addObjcut (SCIP *scip, SCIP_CONSHDLR *conshdlr)
 
static SCIP_RETCODE deleteAltLPConstraint (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons)
 
static SCIP_RETCODE updateObjUpperbound (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata)
 
static SCIP_RETCODE checkAltLPInfeasible (SCIP *scip, SCIP_LPI *lp, SCIP_Real maxcondition, SCIP_Bool primal, SCIP_Bool *infeasible, SCIP_Bool *error)
 
static SCIP_RETCODE extendToCover (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_LPI *lp, SCIP_SOL *sol, SCIP_Bool removable, SCIP_Bool genlogicor, int nconss, SCIP_CONS **conss, SCIP_Bool *S, int *size, SCIP_Real *value, SCIP_Bool *error, SCIP_Bool *cutoff, int *nGen)
 
static SCIP_RETCODE consdataCreate (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSHDLRDATA *conshdlrdata, const char *consname, SCIP_CONSDATA **consdata, SCIP_EVENTHDLR *eventhdlrbound, SCIP_EVENTHDLR *eventhdlrrestart, SCIP_VAR *binvar, SCIP_VAR *slackvar, SCIP_CONS *lincons, SCIP_Bool linconsactive)
 
static SCIP_RETCODE createVarUbs (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS **conss, int nconss, int *ngen)
 
static SCIP_RETCODE presolRoundIndicator (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_Bool dualreductions, SCIP_Bool *cutoff, SCIP_Bool *success, int *ndelconss, int *nfixedvars)
 
static SCIP_RETCODE propIndicator (SCIP *scip, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_Bool dualreductions, SCIP_Bool addopposite, SCIP_Bool *cutoff, int *nGen)
 
static SCIP_RETCODE enforceCuts (SCIP *scip, SCIP_CONSHDLR *conshdlr, int nconss, SCIP_CONS **conss, SCIP_SOL *sol, SCIP_Bool genlogicor, SCIP_Bool *cutoff, int *nGen)
 
static SCIP_RETCODE enforceIndicators (SCIP *scip, SCIP_CONSHDLR *conshdlr, int nconss, SCIP_CONS **conss, SCIP_SOL *sol, SCIP_Bool genlogicor, SCIP_RESULT *result)
 
static SCIP_RETCODE separateIISRounding (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, int nconss, SCIP_CONS **conss, int maxsepacuts, SCIP_Bool *cutoff, int *nGen)
 
static SCIP_RETCODE separatePerspective (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, int nconss, SCIP_CONS **conss, int maxsepacuts, int *nGen)
 
static SCIP_RETCODE separateIndicators (SCIP *scip, SCIP_CONSHDLR *conshdlr, int nconss, int nusefulconss, SCIP_CONS **conss, SCIP_SOL *sol, SCIP_RESULT *result)
 
static void initConshdlrData (SCIP *scip, SCIP_CONSHDLRDATA *conshdlrdata)
 
static SCIP_DECL_LINCONSUPGD (linconsUpgdIndicator)
 
static SCIP_DECL_CONSHDLRCOPY (conshdlrCopyIndicator)
 
static SCIP_DECL_CONSINIT (consInitIndicator)
 
static SCIP_DECL_CONSEXIT (consExitIndicator)
 
static SCIP_DECL_CONSFREE (consFreeIndicator)
 
static SCIP_DECL_CONSINITSOL (consInitsolIndicator)
 
static SCIP_DECL_CONSEXITSOL (consExitsolIndicator)
 
static SCIP_DECL_CONSDELETE (consDeleteIndicator)
 
static SCIP_DECL_CONSTRANS (consTransIndicator)
 
static SCIP_DECL_CONSINITPRE (consInitpreIndicator)
 
static SCIP_DECL_CONSPRESOL (consPresolIndicator)
 
static SCIP_DECL_CONSINITLP (consInitlpIndicator)
 
static SCIP_DECL_CONSSEPALP (consSepalpIndicator)
 
static SCIP_DECL_CONSSEPASOL (consSepasolIndicator)
 
static SCIP_DECL_CONSENFOLP (consEnfolpIndicator)
 
static SCIP_DECL_CONSENFORELAX (consEnforelaxIndicator)
 
static SCIP_DECL_CONSENFOPS (consEnfopsIndicator)
 
static SCIP_DECL_CONSCHECK (consCheckIndicator)
 
static SCIP_DECL_CONSPROP (consPropIndicator)
 
static SCIP_DECL_CONSRESPROP (consRespropIndicator)
 
static SCIP_DECL_CONSLOCK (consLockIndicator)
 
static SCIP_DECL_CONSPRINT (consPrintIndicator)
 
static SCIP_DECL_CONSCOPY (consCopyIndicator)
 
static SCIP_DECL_CONSPARSE (consParseIndicator)
 
static SCIP_DECL_CONSENABLE (consEnableIndicator)
 
static SCIP_DECL_CONSDISABLE (consDisableIndicator)
 
static SCIP_DECL_CONSGETVARS (consGetVarsIndicator)
 
static SCIP_DECL_CONSGETNVARS (consGetNVarsIndicator)
 
static SCIP_DECL_CONSGETDIVEBDCHGS (consGetDiveBdChgsIndicator)
 
SCIP_RETCODE SCIPincludeConshdlrIndicator (SCIP *scip)
 
SCIP_RETCODE SCIPcreateConsIndicator (SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *binvar, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real rhs, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
 
SCIP_RETCODE SCIPcreateConsBasicIndicator (SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *binvar, int nvars, SCIP_VAR **vars, SCIP_Real *vals, SCIP_Real rhs)
 
SCIP_RETCODE SCIPcreateConsIndicatorLinCons (SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *binvar, SCIP_CONS *lincons, SCIP_VAR *slackvar, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
 
SCIP_RETCODE SCIPcreateConsBasicIndicatorLinCons (SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *binvar, SCIP_CONS *lincons, SCIP_VAR *slackvar)
 
SCIP_RETCODE SCIPaddVarIndicator (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
 
SCIP_CONSSCIPgetLinearConsIndicator (SCIP_CONS *cons)
 
SCIP_RETCODE SCIPsetLinearConsIndicator (SCIP *scip, SCIP_CONS *cons, SCIP_CONS *lincons)
 
SCIP_VARSCIPgetBinaryVarIndicator (SCIP_CONS *cons)
 
SCIP_RETCODE SCIPsetBinaryVarIndicator (SCIP *scip, SCIP_CONS *cons, SCIP_VAR *binvar)
 
SCIP_VARSCIPgetSlackVarIndicator (SCIP_CONS *cons)
 
SCIP_RETCODE SCIPsetSlackVarUb (SCIP *scip, SCIP_CONS *cons, SCIP_Real ub)
 
SCIP_Bool SCIPisViolatedIndicator (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol)
 
SCIP_RETCODE SCIPmakeIndicatorFeasible (SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool *changed)
 
SCIP_RETCODE SCIPmakeIndicatorsFeasible (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_SOL *sol, SCIP_Bool *changed)
 
SCIP_RETCODE SCIPaddLinearConsIndicator (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *lincons)
 
SCIP_RETCODE SCIPaddRowIndicator (SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_ROW *row)
 

Macro Definition Documentation

◆ CONSHDLR_NAME

◆ CONSHDLR_DESC

#define CONSHDLR_DESC   "indicator constraint handler"

Definition at line 209 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ CONSHDLR_SEPAPRIORITY

#define CONSHDLR_SEPAPRIORITY   10

priority of the constraint handler for separation

Definition at line 210 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ CONSHDLR_ENFOPRIORITY

#define CONSHDLR_ENFOPRIORITY   -100

priority of the constraint handler for constraint enforcing

Definition at line 211 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ CONSHDLR_CHECKPRIORITY

#define CONSHDLR_CHECKPRIORITY   -6000000

priority of the constraint handler for checking feasibility

Definition at line 212 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ CONSHDLR_SEPAFREQ

#define CONSHDLR_SEPAFREQ   10

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

Definition at line 213 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ CONSHDLR_PROPFREQ

#define CONSHDLR_PROPFREQ   1

frequency for propagating domains; zero means only preprocessing propagation

Definition at line 214 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ CONSHDLR_EAGERFREQ

#define CONSHDLR_EAGERFREQ   100

frequency for using all instead of only the useful constraints in separation, propagation and enforcement, -1 for no eager evaluations, 0 for first only

Definition at line 215 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ CONSHDLR_MAXPREROUNDS

#define CONSHDLR_MAXPREROUNDS   -1

maximal number of presolving rounds the constraint handler participates in (-1: no limit)

Definition at line 218 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ CONSHDLR_DELAYSEPA

#define CONSHDLR_DELAYSEPA   FALSE

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

Definition at line 219 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ CONSHDLR_DELAYPROP

#define CONSHDLR_DELAYPROP   FALSE

Should propagation method be delayed, if other propagators found reductions?

Definition at line 220 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ CONSHDLR_NEEDSCONS

#define CONSHDLR_NEEDSCONS   TRUE

Should the constraint handler be skipped, if no constraints are available?

Definition at line 221 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ CONSHDLR_PRESOLTIMING

#define CONSHDLR_PRESOLTIMING   SCIP_PRESOLTIMING_FAST

Definition at line 223 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ CONSHDLR_PROP_TIMING

#define CONSHDLR_PROP_TIMING   SCIP_PROPTIMING_BEFORELP

Definition at line 224 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ EVENTHDLR_BOUND_NAME

#define EVENTHDLR_BOUND_NAME   "indicatorbound"

Definition at line 228 of file cons_indicator.c.

Referenced by SCIP_DECL_EVENTEXEC(), and SCIPincludeConshdlrIndicator().

◆ EVENTHDLR_BOUND_DESC

#define EVENTHDLR_BOUND_DESC   "bound change event handler for indicator constraints"

Definition at line 229 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ EVENTHDLR_RESTART_NAME

#define EVENTHDLR_RESTART_NAME   "indicatorrestart"

Definition at line 231 of file cons_indicator.c.

Referenced by SCIP_DECL_EVENTEXEC(), and SCIPincludeConshdlrIndicator().

◆ EVENTHDLR_RESTART_DESC

#define EVENTHDLR_RESTART_DESC   "force restart if absolute gap is 1 or enough binary variables have been fixed"

Definition at line 232 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ CONFLICTHDLR_NAME

#define CONFLICTHDLR_NAME   "indicatorconflict"

◆ CONFLICTHDLR_DESC

#define CONFLICTHDLR_DESC   "replace slack variables and generate logicor constraints"

Definition at line 237 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ CONFLICTHDLR_PRIORITY

#define CONFLICTHDLR_PRIORITY   200000

Definition at line 238 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ LINCONSUPGD_PRIORITY

#define LINCONSUPGD_PRIORITY   +100000

priority of the constraint handler for upgrading of linear constraints

Definition at line 241 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_BRANCHINDICATORS

#define DEFAULT_BRANCHINDICATORS   FALSE

Branch on indicator constraints in enforcing?

Definition at line 244 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_GENLOGICOR

#define DEFAULT_GENLOGICOR   FALSE

Generate logicor constraints instead of cuts?

Definition at line 245 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_ADDCOUPLING

#define DEFAULT_ADDCOUPLING   TRUE

Add coupling constraints or rows if big-M is small enough?

Definition at line 246 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_MAXCOUPLINGVALUE

#define DEFAULT_MAXCOUPLINGVALUE   1e4

maximum coefficient for binary variable in coupling constraint

Definition at line 247 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_ADDCOUPLINGCONS

#define DEFAULT_ADDCOUPLINGCONS   FALSE

Add initial variable upper bound constraints, if 'addcoupling' is true?

Definition at line 248 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_SEPACOUPLINGCUTS

#define DEFAULT_SEPACOUPLINGCUTS   TRUE

Should the coupling inequalities be separated dynamically?

Definition at line 249 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_SEPACOUPLINGLOCAL

#define DEFAULT_SEPACOUPLINGLOCAL   FALSE

Allow to use local bounds in order to separate coupling inequalities?

Definition at line 250 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_SEPACOUPLINGVALUE

#define DEFAULT_SEPACOUPLINGVALUE   1e4

maximum coefficient for binary variable in separated coupling constraint

Definition at line 251 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_SEPAALTERNATIVELP

#define DEFAULT_SEPAALTERNATIVELP   FALSE

Separate using the alternative LP?

Definition at line 252 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_SEPAPERSPECTIVE

#define DEFAULT_SEPAPERSPECTIVE   FALSE

Separate cuts based on perspective formulation?

Definition at line 253 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_SEPAPERSPLOCAL

#define DEFAULT_SEPAPERSPLOCAL   TRUE

Allow to use local bounds in order to separate perspectice cuts?

Definition at line 254 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_MAXSEPANONVIOLATED

#define DEFAULT_MAXSEPANONVIOLATED   3

maximal number of separated non violated IISs, before separation is stopped

Definition at line 255 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_TRYSOLFROMCOVER

#define DEFAULT_TRYSOLFROMCOVER   FALSE

Try to construct a feasible solution from a cover?

Definition at line 256 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_UPGRADELINEAR

#define DEFAULT_UPGRADELINEAR   FALSE

Try to upgrade linear constraints to indicator constraints?

Definition at line 257 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_USEOTHERCONSS

#define DEFAULT_USEOTHERCONSS   FALSE

Collect other constraints to alternative LP?

Definition at line 258 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_USEOBJECTIVECUT

#define DEFAULT_USEOBJECTIVECUT   FALSE

Use objective cut with current best solution to alternative LP?

Definition at line 259 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_UPDATEBOUNDS

#define DEFAULT_UPDATEBOUNDS   FALSE

Update bounds of original variables for separation?

Definition at line 260 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_MAXCONDITIONALTLP

#define DEFAULT_MAXCONDITIONALTLP   0.0

max. estimated condition of the solution basis matrix of the alt. LP to be trustworthy (0.0 to disable check)

Definition at line 261 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_MAXSEPACUTS

#define DEFAULT_MAXSEPACUTS   100

maximal number of cuts separated per separation round

Definition at line 262 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_MAXSEPACUTSROOT

#define DEFAULT_MAXSEPACUTSROOT   2000

maximal number of cuts separated per separation round in the root node

Definition at line 263 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_REMOVEINDICATORS

#define DEFAULT_REMOVEINDICATORS   FALSE

Remove indicator constraint if corresponding variable bound constraint has been added?

Definition at line 264 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_GENERATEBILINEAR

#define DEFAULT_GENERATEBILINEAR   FALSE

Do not generate indicator constraint, but a bilinear constraint instead?

Definition at line 265 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_SCALESLACKVAR

#define DEFAULT_SCALESLACKVAR   FALSE

Scale slack variable coefficient at construction time?

Definition at line 266 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_NOLINCONSCONT

#define DEFAULT_NOLINCONSCONT   FALSE

Decompose problem (do not generate linear constraint if all variables are continuous)?

Definition at line 267 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_TRYSOLUTIONS

#define DEFAULT_TRYSOLUTIONS   TRUE

Try to make solutions feasible by setting indicator variables?

Definition at line 268 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_ENFORCECUTS

#define DEFAULT_ENFORCECUTS   FALSE

In enforcing try to generate cuts (only if sepaalternativelp is true)?

Definition at line 269 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_DUALREDUCTIONS

#define DEFAULT_DUALREDUCTIONS   TRUE

Should dual reduction steps be performed?

Definition at line 270 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_ADDOPPOSITE

#define DEFAULT_ADDOPPOSITE   FALSE

Add opposite inequality in nodes in which the binary variable has been fixed to 0?

Definition at line 271 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_CONFLICTSUPGRADE

#define DEFAULT_CONFLICTSUPGRADE   FALSE

Try to upgrade bounddisjunction conflicts by replacing slack variables?

Definition at line 272 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_FORCERESTART

#define DEFAULT_FORCERESTART   FALSE

Force restart if absolute gap is 1 or enough binary variables have been fixed?

Definition at line 273 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ DEFAULT_RESTARTFRAC

#define DEFAULT_RESTARTFRAC   0.9

fraction of binary variables that need to be fixed before restart occurs (in forcerestart)

Definition at line 274 of file cons_indicator.c.

Referenced by SCIPincludeConshdlrIndicator().

◆ OBJEPSILON

#define OBJEPSILON   0.001

value to add to objective in alt. LP if the binary variable is 1 to get small IISs

Definition at line 278 of file cons_indicator.c.

Referenced by setAltLPObj(), and setAltLPObjZero().

◆ SEPAALTTHRESHOLD

#define SEPAALTTHRESHOLD   10

only separate IIS cuts if the number of separated coupling cuts is less than this value

Definition at line 279 of file cons_indicator.c.

Referenced by separateIndicators().

◆ MAXROUNDINGROUNDS

#define MAXROUNDINGROUNDS   1

maximal number of rounds that produced cuts in separation

Definition at line 280 of file cons_indicator.c.

Referenced by initConshdlrData().

◆ SCIP_CALL_PARAM

#define SCIP_CALL_PARAM (   x)
Value:
/*lint -e527 */ do \
{ \
SCIP_RETCODE _restat_; \
if ( (_restat_ = (x)) != SCIP_OKAY && (_restat_ != SCIP_PARAMETERUNKNOWN) ) \
{ \
SCIPerrorMessage("[%s:%d] Error <%d> in function call\n", __FILE__, __LINE__, _restat_); \
SCIPABORT(); \
return _restat_; \
} \
} \
while ( FALSE )
#define FALSE
Definition: def.h:64

Definition at line 382 of file cons_indicator.c.

Referenced by checkAltLPInfeasible(), extendToCover(), initAlternativeLP(), and SCIP_DECL_CONSCHECK().

Function Documentation

◆ SCIP_DECL_EVENTEXEC() [1/2]

static SCIP_DECL_EVENTEXEC ( eventExecIndicatorBound  )
static

◆ SCIP_DECL_EVENTEXEC() [2/2]

static SCIP_DECL_EVENTEXEC ( eventExecIndicatorRestart  )
static

exec the event handler for forcing a restart

There are two cases in which we perform a (user) restart:

  • If we have a max FS instance, i.e., the objective is 1 for indicator variables and 0 otherwise, we can force a restart if the gap is 1. In this case, the remaining work consists of proving infeasibility of the non-fixed indicators.
  • If a large fraction of the binary indicator variables have been globally fixed, it makes sense to force a restart.

Definition at line 486 of file cons_indicator.c.

References EVENTHDLR_RESTART_NAME, REALABS, SCIP_CALL, SCIP_DECL_CONFLICTFREE(), SCIP_EVENTTYPE_BESTSOLFOUND, SCIP_EVENTTYPE_GLBCHANGED, SCIP_EVENTTYPE_GUBCHANGED, SCIP_INVALIDDATA, SCIP_OKAY, SCIP_Real, SCIP_STAGE_SOLVING, SCIP_VARTYPE_BINARY, SCIP_VERBLEVEL_NORMAL, SCIPABORT, SCIPdebugMsg, SCIPdropEvent(), SCIPerrorMessage, SCIPeventGetNewbound(), SCIPeventGetOldbound(), SCIPeventGetType(), SCIPeventGetVar(), SCIPeventhdlrGetName(), SCIPfindBranchrule(), SCIPgetDualbound(), SCIPgetPrimalbound(), SCIPgetStage(), SCIPisEQ(), SCIPisGE(), SCIPisIntegral(), SCIPisParamFixed(), SCIPisZero(), SCIPrestartSolve(), SCIPsetIntParam(), SCIPvarGetName(), SCIPvarGetType(), SCIPverbMessage(), and TRUE.

◆ SCIP_DECL_CONFLICTFREE()

static SCIP_DECL_CONFLICTFREE ( conflictFreeIndicator  )
static

destructor of conflict handler to free conflict handler data (called when SCIP is exiting)

Definition at line 592 of file cons_indicator.c.

References CONFLICTHDLR_NAME, SCIP_DECL_CONFLICTEXEC(), SCIP_OKAY, SCIPconflicthdlrGetData(), SCIPconflicthdlrGetName(), and SCIPfreeBlockMemory.

Referenced by SCIP_DECL_EVENTEXEC().

◆ SCIP_DECL_CONFLICTEXEC()

◆ checkTransferBoolParam()

static SCIP_RETCODE checkTransferBoolParam ( SCIP scip,
SCIP_PARAM param,
const char *  name,
SCIP_Bool  newvalue,
SCIP_Bool value 
)
static

check whether we transfer a changed parameter to the given value

See also
paramChangedIndicator()
Parameters
scipSCIP data structure
paramparameter
nameparameter name to check
newvaluenew value
valueold and possibly changed value of parameter

Definition at line 785 of file cons_indicator.c.

References SCIP_CALL, SCIP_DECL_PARAMCHGD(), SCIP_OKAY, SCIP_PARAMTYPE_BOOL, SCIP_STAGE_PROBLEM, SCIPchgBoolParam(), SCIPgetStage(), SCIPparamGetName(), SCIPparamGetType(), and SCIPwarningMessage().

Referenced by SCIP_DECL_CONFLICTEXEC(), and SCIP_DECL_PARAMCHGD().

◆ SCIP_DECL_PARAMCHGD()

◆ varGetObjDelta()

static SCIP_Real varGetObjDelta ( SCIP_VAR var)
static

return objective contribution of variable

Special treatment of negated variables: return negative of objective of original variable. SCIPvarGetObj() would return 0 in these cases.

Parameters
varvariable

Definition at line 1247 of file cons_indicator.c.

References consdataEnsureAddLinConsSize(), SCIP_VARSTATUS_AGGREGATED, SCIPvarGetAggrScalar(), SCIPvarGetAggrVar(), SCIPvarGetNegatedVar(), SCIPvarGetObj(), SCIPvarGetStatus(), SCIPvarIsBinary(), and SCIPvarIsNegated().

Referenced by enforceCuts(), extendToCover(), presolRoundIndicator(), propIndicator(), SCIP_DECL_CONSINITSOL(), SCIP_DECL_PARAMCHGD(), SCIPmakeIndicatorFeasible(), and separateIISRounding().

◆ consdataEnsureAddLinConsSize()

static SCIP_RETCODE consdataEnsureAddLinConsSize ( SCIP scip,
SCIP_CONSHDLR conshdlr,
int  num 
)
static

ensures that the addlincons array can store at least num entries

Parameters
scipSCIP data structure
conshdlrconstraint handler
numminimum number of entries to store

Definition at line 1268 of file cons_indicator.c.

References CONSHDLR_NAME, initAlternativeLP(), SCIP_CALL, SCIP_OKAY, SCIPcalcMemGrowSize(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), and SCIPreallocBlockMemoryArray.

Referenced by SCIPaddLinearConsIndicator(), and varGetObjDelta().

◆ initAlternativeLP()

static SCIP_RETCODE initAlternativeLP ( SCIP scip,
SCIP_CONSHDLR conshdlr 
)
static

initialize alternative LP

The alternative system is organized as follows:

  • The first row corresponds to the right hand side of the original system.
  • The next nconss constraints correspond to the slack variables.
  • The rows after that correspond to the original variables.
Parameters
scipSCIP pointer
conshdlrconstraint handler

Definition at line 1308 of file cons_indicator.c.

References checkLPBoundsClean(), CONSHDLR_NAME, FALSE, SCIP_CALL, SCIP_CALL_PARAM, SCIP_LPPAR_FASTMIP, SCIP_LPPAR_FROMSCRATCH, SCIP_LPPAR_PRESOLVING, SCIP_LPPAR_SCALING, SCIP_OBJSEN_MINIMIZE, SCIP_OKAY, SCIP_Real, SCIPblkmem(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetMessagehdlr(), SCIPgetNVars(), SCIPhashmapCreate(), SCIPlpiAddRows(), SCIPlpiCreate(), SCIPlpiSetIntpar(), and TRUE.

Referenced by addAltLPColumn(), and consdataEnsureAddLinConsSize().

◆ checkLPBoundsClean()

static SCIP_RETCODE checkLPBoundsClean ( SCIP scip,
SCIP_LPI lp,
int  nconss,
SCIP_CONS **  conss 
)
static

check whether the bounds in given (alternative) LP are set correctly (for debugging)

Parameters
scipSCIP pointer
lpLP for which bounds should be checked
nconssnumber of constraints
conssconstraints

Definition at line 1358 of file cons_indicator.c.

References FALSE, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPABORT, SCIPallocBufferArray, SCIPconsGetData(), SCIPfreeBufferArray, SCIPisFeasZero(), SCIPlpiGetBounds(), SCIPlpiGetNCols(), SCIPlpiIsInfinity(), setAltLPObj(), and TRUE.

Referenced by enforceCuts(), initAlternativeLP(), SCIP_DECL_CONSCHECK(), and separateIISRounding().

◆ setAltLPObj()

static SCIP_RETCODE setAltLPObj ( SCIP scip,
SCIP_LPI lp,
SCIP_SOL sol,
int  nconss,
SCIP_CONS **  conss 
)
static

set the alternative system objective function

We assume that the objective function coefficients of the variables other than the binary indicators are always 0 and hence do not have to be changed.

We already use the tranformation \(y' = 1 - y\).

Parameters
scipSCIP pointer
lpalternative LP
solsolution to be dealt with
nconssnumber of constraints
conssindicator constraints

Definition at line 1436 of file cons_indicator.c.

References OBJEPSILON, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetData(), SCIPfreeBufferArray, SCIPgetSolVal(), SCIPisFeasEQ(), SCIPlpiChgObj(), and setAltLPObjZero().

Referenced by checkLPBoundsClean(), and separateIISRounding().

◆ setAltLPObjZero()

static SCIP_RETCODE setAltLPObjZero ( SCIP scip,
SCIP_LPI lp,
int  nconss,
SCIP_CONS **  conss 
)
static

set the alternative system objective function to some small value

Parameters
scipSCIP pointer
lpalternative LP
nconssnumber of constraints
conssindicator constraints

Definition at line 1489 of file cons_indicator.c.

References fixAltLPVariables(), OBJEPSILON, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetData(), SCIPfreeBufferArray, and SCIPlpiChgObj().

Referenced by enforceCuts(), SCIP_DECL_CONSCHECK(), and setAltLPObj().

◆ fixAltLPVariables()

static SCIP_RETCODE fixAltLPVariables ( SCIP scip,
SCIP_LPI lp,
int  nconss,
SCIP_CONS **  conss,
SCIP_Bool S 
)
static

fix variable given by S to 0

Parameters
scipSCIP pointer
lpalternative LP
nconssnumber of constraints
conssindicator constraints
Sbitset of variables

Definition at line 1537 of file cons_indicator.c.

References fixAltLPVariable(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetData(), SCIPfreeBufferArray, and SCIPlpiChgBounds().

Referenced by enforceCuts(), SCIP_DECL_CONSCHECK(), separateIISRounding(), and setAltLPObjZero().

◆ fixAltLPVariable()

static SCIP_RETCODE fixAltLPVariable ( SCIP_LPI lp,
int  ind 
)
static

fix variable ind to 0

Parameters
lpalternative LP
indvariable that should be fixed to 0

Definition at line 1596 of file cons_indicator.c.

References SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPlpiChgBounds(), and unfixAltLPVariable().

Referenced by deleteAltLPConstraint(), extendToCover(), fixAltLPVariables(), and SCIP_DECL_CONSDISABLE().

◆ unfixAltLPVariable()

static SCIP_RETCODE unfixAltLPVariable ( SCIP_LPI lp,
int  ind 
)
static

unfix variable ind to 0

Parameters
lpalternative LP
indvariable that should be fixed to 0

Definition at line 1613 of file cons_indicator.c.

References SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPlpiChgBounds(), SCIPlpiInfinity(), and unfixAltLPVariables().

Referenced by fixAltLPVariable(), and SCIP_DECL_CONSENABLE().

◆ unfixAltLPVariables()

static SCIP_RETCODE unfixAltLPVariables ( SCIP scip,
SCIP_LPI lp,
int  nconss,
SCIP_CONS **  conss,
SCIP_Bool S 
)
static

unfix variable given by S to 0

Parameters
scipSCIP pointer
lpalternative LP
nconssnumber of constraints
conssindicator constraints
Sbitset of variables

Definition at line 1629 of file cons_indicator.c.

References SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetData(), SCIPfreeBufferArray, SCIPlpiChgBounds(), SCIPlpiInfinity(), and updateFirstRow().

Referenced by enforceCuts(), SCIP_DECL_CONSCHECK(), separateIISRounding(), and unfixAltLPVariable().

◆ updateFirstRow()

static SCIP_RETCODE updateFirstRow ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata 
)
static

update bounds in first row to the current ones

Parameters
scipSCIP pointer
conshdlrdataconstraint handler

Definition at line 1688 of file cons_indicator.c.

References FALSE, SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPgetNVars(), SCIPgetVars(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPisEQ(), SCIPlpiChgCoef(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and updateFirstRowGlobal().

Referenced by separateIISRounding(), and unfixAltLPVariables().

◆ updateFirstRowGlobal()

static SCIP_RETCODE updateFirstRowGlobal ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata 
)
static

update bounds in first row to the global bounds

Parameters
scipSCIP pointer
conshdlrdataconstraint handler

Definition at line 1752 of file cons_indicator.c.

References checkIISlocal(), SCIP_CALL, SCIP_OKAY, SCIPdebugMsg, SCIPgetNVars(), SCIPgetVars(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPlpiChgCoef(), SCIPvarGetLbGlobal(), and SCIPvarGetUbGlobal().

Referenced by enforceCuts(), SCIP_DECL_CONSCHECK(), and updateFirstRow().

◆ checkIISlocal()

static SCIP_RETCODE checkIISlocal ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_Real vector,
SCIP_Bool isLocal 
)
static

check whether IIS defined by vector corresponds to a local cut

Parameters
scipSCIP pointer
conshdlrdataconstraint handler
vectorsolution to alternative LP defining IIS
isLocalwhether the IIS uses local bounds different from the global ones

Definition at line 1813 of file cons_indicator.c.

References FALSE, scaleFirstRow(), SCIP_CALL, SCIP_OKAY, SCIPgetNVars(), SCIPgetVars(), SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPisEQ(), SCIPisFeasZero(), SCIPlpiGetNCols(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), and TRUE.

Referenced by extendToCover(), and updateFirstRowGlobal().

◆ scaleFirstRow()

static SCIP_RETCODE scaleFirstRow ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata 
)
static

compute scaling for first row

If the coefficients in the first row are large, a right hand side of -1 might not be adequate. Here, we replace the right hand side by the sum of the coefficients divided by the number of nonzeros.

Parameters
scipSCIP pointer
conshdlrdataconstraint handler

Definition at line 1902 of file cons_indicator.c.

References addAltLPColumn(), REALABS, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPfreeBufferArray, SCIPlpiChgSides(), SCIPlpiGetNCols(), SCIPlpiGetRows(), and TRUE.

Referenced by checkIISlocal(), enforceCuts(), SCIP_DECL_CONSCHECK(), and separateIISRounding().

◆ addAltLPColumn()

static SCIP_RETCODE addAltLPColumn ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_VAR slackvar,
int  nvars,
SCIP_VAR **  vars,
SCIP_Real vals,
SCIP_Real  rhscoef,
SCIP_Real  objcoef,
SCIP_Real  sign,
SCIP_Bool  colfree,
int *  colindex 
)
static

add column to alternative LP

See the description at the top of the file for more information.

Parameters
scipSCIP pointer
conshdlrconstraint handler
conshdlrdatadata of constraint handler
slackvarslack variable or NULL
nvarsnumber of variables in column
varsvariables for column
valsvalues for column
rhscoefcoefficient for first row
objcoefobjective in alternative LP
signsign (+1,-1) for column
colfreewhether column should be free, e.g., for equations
colindexindex of new column (return value)

Definition at line 1956 of file cons_indicator.c.

References addAltLPConstraint(), FALSE, initAlternativeLP(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPdebugMsg, SCIPfreeBufferArray, SCIPhashmapExists(), SCIPhashmapGetImage(), SCIPhashmapInsert(), SCIPhashmapSetImage(), SCIPisEQ(), SCIPisFeasZero(), SCIPisInfinity(), SCIPisZero(), SCIPlpiAddCols(), SCIPlpiAddRows(), SCIPlpiGetNCols(), SCIPlpiGetNRows(), SCIPlpiInfinity(), SCIPlpiWriteLP(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetUbGlobal(), sign(), and TRUE.

Referenced by addAltLPConstraint(), addAltLPRow(), addObjcut(), and scaleFirstRow().

◆ addAltLPConstraint()

static SCIP_RETCODE addAltLPConstraint ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_CONS lincons,
SCIP_VAR slackvar,
SCIP_Real  objcoef,
int *  colindex 
)
static

add column corresponding to constraint to alternative LP

See the description at the top of the file for more information.

Parameters
scipSCIP pointer
conshdlrconstraint handler
linconslinear constraint
slackvarslack variable or NULL
objcoefobjective coefficient
colindexindex of new column

Definition at line 2227 of file cons_indicator.c.

References addAltLPColumn(), addAltLPRow(), CONSHDLR_NAME, FALSE, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIP_VARSTATUS_AGGREGATED, SCIP_VARSTATUS_MULTAGGR, SCIPallocBufferArray, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsActive(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetLhsLinear(), SCIPgetNVarsLinear(), SCIPgetProbvarSum(), SCIPgetRhsLinear(), SCIPgetValsLinear(), SCIPgetVarsLinear(), SCIPinfinity(), SCIPisEQ(), SCIPisInfinity(), SCIPisZero(), SCIPvarGetStatus(), and TRUE.

Referenced by addAltLPColumn(), consdataCreate(), and SCIP_DECL_CONSINITSOL().

◆ addAltLPRow()

static SCIP_RETCODE addAltLPRow ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_ROW row,
SCIP_Real  objcoef,
int *  colindex 
)
static

add column corresponding to row to alternative LP

See the description at the top of the file for more information.

Parameters
scipSCIP pointer
conshdlrconstraint handler
rowrow to add
objcoefobjective coefficient
colindexindex of new column

Definition at line 2328 of file cons_indicator.c.

References addAltLPColumn(), addObjcut(), CONSHDLR_NAME, FALSE, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPcolGetVar(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPfreeBufferArray, SCIPisEQ(), SCIPisInfinity(), SCIProwGetCols(), SCIProwGetConstant(), SCIProwGetLhs(), SCIProwGetNNonz(), SCIProwGetRhs(), SCIProwGetVals(), SCIProwIsLocal(), and TRUE.

Referenced by addAltLPConstraint(), and SCIPaddRowIndicator().

◆ addObjcut()

static SCIP_RETCODE addObjcut ( SCIP scip,
SCIP_CONSHDLR conshdlr 
)
static

try to add objective cut as column to alternative LP

Parameters
scipSCIP pointer
conshdlrconstraint handler

Definition at line 2401 of file cons_indicator.c.

References addAltLPColumn(), CONSHDLR_NAME, deleteAltLPConstraint(), FALSE, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetVarsData(), SCIPisInfinity(), SCIPisZero(), and SCIPvarGetObj().

Referenced by addAltLPRow(), and updateObjUpperbound().

◆ deleteAltLPConstraint()

static SCIP_RETCODE deleteAltLPConstraint ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_CONS cons 
)
static

delete column corresponding to constraint in alternative LP

We currently just fix the corresponding variable to 0.

Parameters
scipSCIP pointer
conshdlrconstraint handler
consindicator constraint

Definition at line 2471 of file cons_indicator.c.

References CONSHDLR_NAME, FALSE, fixAltLPVariable(), SCIP_CALL, SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, and updateObjUpperbound().

Referenced by addObjcut(), and SCIP_DECL_CONSDELETE().

◆ updateObjUpperbound()

static SCIP_RETCODE updateObjUpperbound ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_CONSHDLRDATA conshdlrdata 
)
static

update upper bound in alternative LP

Parameters
scipSCIP pointer
conshdlrconstraint handler
conshdlrdataconstraint handler data

Definition at line 2510 of file cons_indicator.c.

References addObjcut(), checkAltLPInfeasible(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPcutoffbounddelta(), SCIPdebugMsg, SCIPfeasCeil(), SCIPgetUpperbound(), SCIPisEQ(), SCIPisInfinity(), SCIPisLT(), SCIPisObjIntegral(), SCIPlpiChgCoef(), SCIPlpiGetCoef(), and SCIPlpiWriteLP().

Referenced by deleteAltLPConstraint(), enforceCuts(), and separateIISRounding().

◆ checkAltLPInfeasible()

static SCIP_RETCODE checkAltLPInfeasible ( SCIP scip,
SCIP_LPI lp,
SCIP_Real  maxcondition,
SCIP_Bool  primal,
SCIP_Bool infeasible,
SCIP_Bool error 
)
static

check whether the given LP is infeasible

If primal is false we assume that the problem is dual feasible, e.g., the problem was only changed by fixing bounds!

This is the workhorse for all methods that have to solve the alternative LP. We try in several ways to recover from possible stability problems.

Precondition
It is assumed that all parameters for the alternative LP are set.
Parameters
scipSCIP pointer
lpLP
maxconditionmaximal allowed condition of LP solution basis matrix
primalwhether we are using the primal or dual simplex
infeasibleoutput: whether the LP is infeasible
erroroutput: whether an error occurred

Definition at line 2586 of file cons_indicator.c.

References extendToCover(), FALSE, SCIP_CALL, SCIP_CALL_PARAM, SCIP_INVALID, SCIP_LPERROR, SCIP_LPPAR_FROMSCRATCH, SCIP_LPPAR_PRESOLVING, SCIP_LPPAR_SCALING, SCIP_LPSOLQUALITY_ESTIMCONDITION, SCIP_OKAY, SCIP_Real, SCIPdebugMsg, SCIPlpiExistsPrimalRay(), SCIPlpiGetInternalStatus(), SCIPlpiGetRealSolQuality(), SCIPlpiIsOptimal(), SCIPlpiIsPrimalInfeasible(), SCIPlpiIsPrimalUnbounded(), SCIPlpiIsStable(), SCIPlpiSetIntpar(), SCIPlpiSolveDual(), SCIPlpiSolvePrimal(), SCIPwarningMessage(), and TRUE.

Referenced by extendToCover(), SCIP_DECL_CONSCHECK(), and updateObjUpperbound().

◆ extendToCover()

static SCIP_RETCODE extendToCover ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_LPI lp,
SCIP_SOL sol,
SCIP_Bool  removable,
SCIP_Bool  genlogicor,
int  nconss,
SCIP_CONS **  conss,
SCIP_Bool S,
int *  size,
SCIP_Real value,
SCIP_Bool error,
SCIP_Bool cutoff,
int *  nGen 
)
static

tries to extend a given set of variables to a cover

At each step we include a variable which covers a new IIS. The corresponding IIS inequalities are added to the LP, if this not already happened.

Precondition
It is assumed that all parameters for the alternative LP are set and that the variables corresponding to S are fixed. Furthermore xVal_ should contain the current LP solution.
Parameters
scipSCIP pointer
conshdlrconstraint handler
conshdlrdataconstraint handler data
lpLP
solsolution to be separated
removablewhether cuts should be removable
genlogicorshould logicor constraints be generated?
nconssnumber of constraints
conssindicator constraints
Sbitset of variables
sizesize of S
valueobjective value of S
erroroutput: whether an error occurred
cutoffwhether we detected a cutoff by an infeasible inequality
nGennumber of generated cuts

Definition at line 2733 of file cons_indicator.c.

References checkAltLPInfeasible(), checkIISlocal(), consdataCreate(), FALSE, fixAltLPVariable(), SCIP_Bool, SCIP_CALL, SCIP_CALL_PARAM, SCIP_LPPAR_FROMSCRATCH, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_PLUGINNOTFOUND, SCIP_Real, SCIPABORT, SCIPaddCons(), SCIPaddPoolCut(), SCIPaddRow(), SCIPaddVarToRow(), SCIPallocBufferArray, SCIPcacheRowExtensions(), SCIPconsGetData(), SCIPcreateConsLogicor(), SCIPcreateEmptyRowCons(), SCIPdebugMsg, SCIPerrorMessage, SCIPfindHeur(), SCIPflushRowExtensions(), SCIPfreeBufferArray, SCIPgetNBinVars(), SCIPgetNegatedVar(), SCIPgetNIntVars(), SCIPgetRowSolFeasibility(), SCIPgetSolVal(), SCIPheurPassIndicator(), SCIPinfinity(), SCIPinfoMessage(), SCIPisEfficacious(), SCIPisFeasNegative(), SCIPisFeasZero(), SCIPlpiGetNCols(), SCIPlpiGetSol(), SCIPlpiSetIntpar(), SCIPprintCons(), SCIPprintRow(), SCIPreleaseCons(), SCIPreleaseRow(), SCIPsnprintf(), sqrt(), TRUE, and varGetObjDelta().

Referenced by checkAltLPInfeasible(), enforceCuts(), and separateIISRounding().

◆ consdataCreate()

static SCIP_RETCODE consdataCreate ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_CONSHDLRDATA conshdlrdata,
const char *  consname,
SCIP_CONSDATA **  consdata,
SCIP_EVENTHDLR eventhdlrbound,
SCIP_EVENTHDLR eventhdlrrestart,
SCIP_VAR binvar,
SCIP_VAR slackvar,
SCIP_CONS lincons,
SCIP_Bool  linconsactive 
)
static

creates and initializes consdata

Parameters
scipSCIP data structure
conshdlrconstraint handler
conshdlrdataconstraint handler data
consnamename of constraint (or NULL)
consdatapointer to linear constraint data
eventhdlrboundevent handler for bound change events
eventhdlrrestartevent handler for handling restarts
binvarbinary variable (or NULL)
slackvarslack variable
linconslinear constraint (or NULL)
linconsactivewhether the linear constraint is active

Definition at line 3060 of file cons_indicator.c.

References addAltLPConstraint(), createVarUbs(), FALSE, SCIP_CALL, SCIP_ERROR, SCIP_EVENTTYPE_BOUNDCHANGED, SCIP_EVENTTYPE_GBDCHANGED, SCIP_OKAY, SCIP_STAGE_INITSOLVE, SCIP_VARTYPE_BINARY, SCIPallocBlockMemory, SCIPcaptureCons(), SCIPcaptureVar(), SCIPcatchVarEvent(), SCIPdebugMsg, SCIPerrorMessage, SCIPgetStage(), SCIPgetTransformedVar(), SCIPinfoMessage(), SCIPisFeasPositive(), SCIPisTransformed(), SCIPprintCons(), SCIPvarGetLbLocal(), SCIPvarGetName(), and SCIPvarGetType().

Referenced by extendToCover(), SCIP_DECL_CONSTRANS(), SCIPcreateConsIndicator(), and SCIPcreateConsIndicatorLinCons().

◆ createVarUbs()

static SCIP_RETCODE createVarUbs ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_CONS **  conss,
int  nconss,
int *  ngen 
)
static

create variable upper bounds for constraints

Parameters
scipSCIP pointer
conshdlrdataconstraint handler data
conssconstraints
nconssnumber of constraints
ngennumber of successful operations

Definition at line 3178 of file cons_indicator.c.

References FALSE, presolRoundIndicator(), SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPconsAddUpgradeLocks(), SCIPconsGetData(), SCIPconsGetName(), SCIPconsGetNUpgradeLocks(), SCIPconsIsActive(), SCIPconsIsModifiable(), SCIPcreateConsVarbound(), SCIPdebugMsg, SCIPdelCons(), SCIPinfinity(), SCIPisNegative(), SCIPreleaseCons(), SCIPsnprintf(), SCIPvarGetUbGlobal(), and TRUE.

Referenced by consdataCreate(), and SCIP_DECL_CONSPRESOL().

◆ presolRoundIndicator()

static SCIP_RETCODE presolRoundIndicator ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata,
SCIP_CONS cons,
SCIP_CONSDATA consdata,
SCIP_Bool  dualreductions,
SCIP_Bool cutoff,
SCIP_Bool success,
int *  ndelconss,
int *  nfixedvars 
)
static

◆ propIndicator()

static SCIP_RETCODE propIndicator ( SCIP scip,
SCIP_CONS cons,
SCIP_CONSDATA consdata,
SCIP_Bool  dualreductions,
SCIP_Bool  addopposite,
SCIP_Bool cutoff,
int *  nGen 
)
static

propagate indicator constraint

Parameters
scipSCIP pointer
consconstraint
consdataconstraint data
dualreductionsshould dual reductions be performed?
addoppositeadd opposite inequalities if binary var = 0?
cutoffwhether a cutoff happened
nGennumber of domain changes

Definition at line 3579 of file cons_indicator.c.

References enforceCuts(), FALSE, REALABS, SCIP_Bool, SCIP_CALL, SCIP_CONFTYPE_PROPAGATION, SCIP_MAXSTRLEN, SCIP_OKAY, SCIP_Real, SCIP_STAGE_SOLVING, SCIP_VARSTATUS_MULTAGGR, SCIPaddConflictBinvar(), SCIPaddConflictLb(), SCIPaddCons(), SCIPallocBufferArray, SCIPanalyzeConflictCons(), SCIPconsAddUpgradeLocks(), SCIPconsGetName(), SCIPconsGetNUpgradeLocks(), SCIPconsIsActive(), SCIPconsIsModifiable(), SCIPcreateConsLinear(), SCIPdebugMsg, SCIPdebugPrintCons, SCIPdelConsLocal(), SCIPfreeBufferArray, SCIPgetDepth(), SCIPgetNVarsLinear(), SCIPgetRhsLinear(), SCIPgetStage(), SCIPgetValsLinear(), SCIPgetVarsLinear(), SCIPincConsAge(), SCIPinferVarLbCons(), SCIPinferVarUbCons(), SCIPinfinity(), SCIPinitConflictAnalysis(), SCIPinProbing(), SCIPinRepropagation(), SCIPisConflictAnalysisApplicable(), SCIPisEQ(), SCIPisFeasGE(), SCIPisFeasPositive(), SCIPisFeasZero(), SCIPisInfinity(), SCIPisIntegral(), SCIPisPositive(), SCIPisZero(), SCIPreleaseCons(), SCIPresetConsAge(), SCIPsnprintf(), SCIPvarGetLbLocal(), SCIPvarGetName(), SCIPvarGetNLocksDown(), SCIPvarGetNLocksUp(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), SCIPvarIsIntegral(), TRUE, and varGetObjDelta().

Referenced by enforceIndicators(), presolRoundIndicator(), and SCIP_DECL_CONSPROP().

◆ enforceCuts()

static SCIP_RETCODE enforceCuts ( SCIP scip,
SCIP_CONSHDLR conshdlr,
int  nconss,
SCIP_CONS **  conss,
SCIP_SOL sol,
SCIP_Bool  genlogicor,
SCIP_Bool cutoff,
int *  nGen 
)
static

enforcement method that produces cuts if possible

This is a variant of the enforcement method that generates cuts/constraints via the alternative LP, if possible.

Parameters
scipSCIP pointer
conshdlrconstraint handler
nconssnumber of constraints
conssindicator constraints
solsolution to be enforced
genlogicorwhether logicor constraint should be generated
cutoffwhether we detected a cutoff by an infeasible inequality
nGennumber of cuts generated

Definition at line 3871 of file cons_indicator.c.

References checkLPBoundsClean(), enforceIndicators(), extendToCover(), FALSE, fixAltLPVariables(), scaleFirstRow(), SCIP_Bool, SCIP_CALL, SCIP_LPERROR, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetData(), SCIPconshdlrGetData(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetSolVal(), SCIPisFeasIntegral(), SCIPisFeasZero(), setAltLPObjZero(), TRUE, unfixAltLPVariables(), updateFirstRowGlobal(), updateObjUpperbound(), and varGetObjDelta().

Referenced by enforceIndicators(), and propIndicator().

◆ enforceIndicators()

static SCIP_RETCODE enforceIndicators ( SCIP scip,
SCIP_CONSHDLR conshdlr,
int  nconss,
SCIP_CONS **  conss,
SCIP_SOL sol,
SCIP_Bool  genlogicor,
SCIP_RESULT result 
)
static

enforcement method

We check whether the current solution is feasible, i.e., if binvar = 1 implies that slackvar = 0. If not, we branch as follows:

In one branch we fix binvar = 1 and slackvar = 0. In the other branch we fix binvar = 0 and leave slackvar unchanged.

Parameters
scipSCIP pointer
conshdlrconstraint handler
nconssnumber of constraints
conssindicator constraints
solsolution to be enforced (NULL for LP solution)
genlogicorwhether logicor constraint should be generated
resultresult

Definition at line 3981 of file cons_indicator.c.

References branchCons(), enforceCuts(), FALSE, propIndicator(), SCIP_Bool, SCIP_BRANCHED, SCIP_CALL, SCIP_CONSADDED, SCIP_CUTOFF, SCIP_FEASIBLE, SCIP_INFEASIBLE, SCIP_OKAY, SCIP_Real, SCIP_REDUCEDDOM, SCIP_SEPARATED, SCIP_VARSTATUS_MULTAGGR, SCIPallowDualReds(), SCIPcalcChildEstimate(), SCIPchgVarLbNode(), SCIPchgVarUbNode(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPcreateChild(), SCIPdebugMsg, SCIPgetSolVal(), SCIPinfoMessage(), SCIPisFeasNegative(), SCIPisFeasZero(), SCIPprintCons(), SCIPresetConsAge(), SCIPvarGetLbLocal(), SCIPvarGetStatus(), SCIPvarGetUbLocal(), SCIPwriteTransProblem(), separateIISRounding(), and TRUE.

Referenced by enforceCuts(), SCIP_DECL_CONSENFOLP(), SCIP_DECL_CONSENFOPS(), and SCIP_DECL_CONSENFORELAX().

◆ separateIISRounding()

static SCIP_RETCODE separateIISRounding ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_SOL sol,
int  nconss,
SCIP_CONS **  conss,
int  maxsepacuts,
SCIP_Bool cutoff,
int *  nGen 
)
static

separate IIS-cuts via rounding

Parameters
scipSCIP pointer
conshdlrconstraint handler
solsolution to be separated
nconssnumber of constraints
conssindicator constraints
maxsepacutsmaximal number of cuts to be generated
cutoffwhether we detected a cutoff by an infeasible inequality
nGennumber of domain changes

Definition at line 4170 of file cons_indicator.c.

References checkLPBoundsClean(), extendToCover(), FALSE, fixAltLPVariables(), scaleFirstRow(), SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetData(), SCIPconshdlrGetData(), SCIPdebug, SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetVarSol(), SCIPhashmapExists(), SCIPisFeasEQ(), SCIPisFeasLT(), SCIPisFeasZero(), SCIPvarGetNegatedVar(), separatePerspective(), setAltLPObj(), TRUE, unfixAltLPVariables(), updateFirstRow(), updateObjUpperbound(), and varGetObjDelta().

Referenced by enforceIndicators(), and separateIndicators().

◆ separatePerspective()

static SCIP_RETCODE separatePerspective ( SCIP scip,
SCIP_CONSHDLR conshdlr,
SCIP_SOL sol,
int  nconss,
SCIP_CONS **  conss,
int  maxsepacuts,
int *  nGen 
)
static

separate cuts based on perspective formulation

Hijazi, Bonami, and Ouorou (2014) introduced the following cuts: We consider an indicator constraint

\[ y = 1 \rightarrow \alpha^T x \leq \beta \]

and assume finite bounds \(\ell \leq x \leq u\). Then for \(I \subseteq \{1, \dots, n\}\) define

\[ \Sigma(I,x,y) = \sum_{i \notin I} \alpha_i x_i + y \Big(\sum_{i \in I, \alpha_i < 0} \alpha_i u_i + \sum_{i \in I, \alpha_i > 0} \alpha_i \ell_i + \sum_{i \notin I, \alpha_i < 0} \alpha_i \ell_i + \sum_{i \notin I, \alpha_i > 0} \alpha_i u_i - \beta\Big). \]

Then the cuts

\[ \Sigma(I,x,y) \leq \sum_{i \notin I, \alpha_i < 0} \alpha_i \ell_i + \sum_{i \notin I, \alpha_i > 0} \alpha_i u_i \]

are valid for the disjunction

\[ \{y = 0,\; \ell \leq x \leq u\} \cup \{y = 1,\; \ell \leq x \leq u,\; \alpha^T x \leq \beta\}. \]

These cuts can easily be separated for a given point \((x^*, y^*)\) by checking for each \(i \in \{1, \dots, n\}\) whether

\[ y^*(\alpha_i\, u_i\, [\alpha_i < 0] + \alpha_i\, \ell_i\, [\alpha_i > 0]) > \alpha_i x_i^* + y^* )\alpha_i \ell_i [\alpha_i < 0] + \alpha_i u_i [\alpha_i > 0]), \]

where \([C] = 1\) if condition \(C\) is satisfied, otherwise it is 0. If the above inequality holds, \(i\) is included in \(I\), otherwise not.

Parameters
scipSCIP pointer
conshdlrconstraint handler
solsolution to be separated
nconssnumber of constraints
conssindicator constraints
maxsepacutsmaximal number of cuts to be generated
nGennumber of generated cuts

Definition at line 4382 of file cons_indicator.c.

References FALSE, SCIP_Bool, SCIP_CALL, SCIP_OKAY, SCIP_Real, SCIPaddRow(), SCIPaddVarsToRow(), SCIPallocBufferArray, SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconshdlrGetData(), SCIPconsIsActive(), SCIPcreateEmptyRowCons(), SCIPdebugMsg, SCIPfreeBufferArray, SCIPgetLhsLinear(), SCIPgetNVars(), SCIPgetNVarsLinear(), SCIPgetRhsLinear(), SCIPgetSolVal(), SCIPgetValsLinear(), SCIPgetVarsLinear(), SCIPinfinity(), SCIPisEfficacious(), SCIPisGT(), SCIPisInfinity(), SCIPisNegative(), SCIPisPositive(), SCIPprintRow(), SCIPreleaseRow(), SCIPresetConsAge(), SCIPsnprintf(), SCIPvarGetLbGlobal(), SCIPvarGetLbLocal(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), separateIndicators(), and TRUE.

Referenced by separateIISRounding(), and separateIndicators().

◆ separateIndicators()

static SCIP_RETCODE separateIndicators ( SCIP scip,
SCIP_CONSHDLR conshdlr,
int  nconss,
int  nusefulconss,
SCIP_CONS **  conss,
SCIP_SOL sol,
SCIP_RESULT result 
)
static

separation method

We first check whether coupling inequalities can be separated (if required). If not enough of these could be generated, we check whether IIS inequalities can be separated.

Parameters
scipSCIP pointer
conshdlrconstraint handler
nconssnumber of constraints
nusefulconssnumber of useful constraints
conssindicator constraints
solsolution to be separated
resultresult

Definition at line 4583 of file cons_indicator.c.

References FALSE, initConshdlrData(), SCIP_Bool, SCIP_CALL, SCIP_CONSADDED, SCIP_CUTOFF, SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIP_SEPARATED, SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPcreateEmptyRowCons(), SCIPdebugMsg, SCIPflushRowExtensions(), SCIPgetDepth(), SCIPgetSolVal(), SCIPinfinity(), SCIPisEfficacious(), SCIPisFeasNegative(), SCIPprintRow(), SCIPreleaseRow(), SCIPresetConsAge(), SCIPsnprintf(), SCIPvarGetUbGlobal(), SCIPvarGetUbLocal(), SEPAALTTHRESHOLD, separateIISRounding(), separatePerspective(), and TRUE.

Referenced by SCIP_DECL_CONSSEPALP(), SCIP_DECL_CONSSEPASOL(), and separatePerspective().

◆ initConshdlrData()

static void initConshdlrData ( SCIP scip,
SCIP_CONSHDLRDATA conshdlrdata 
)
static

initializes the constraint handler data

Parameters
scipSCIP pointer
conshdlrdataconstraint handler data

Definition at line 4752 of file cons_indicator.c.

References FALSE, MAXROUNDINGROUNDS, SCIP_DECL_LINCONSUPGD(), SCIPinfinity(), and TRUE.

Referenced by SCIP_DECL_CONSINIT(), SCIPincludeConshdlrIndicator(), and separateIndicators().

◆ SCIP_DECL_LINCONSUPGD()

static SCIP_DECL_LINCONSUPGD ( linconsUpgdIndicator  )
static

tries to upgrade a linear constraint into an indicator constraint

For some linear constraint of the form \(a^T x + \alpha\, y \geq \beta\) with \(y \in \{0,1\}\), we can upgrade it to an indicator constraint if for the residual value \(a^T x \geq \gamma\), we have \(\alpha + \gamma \geq \beta\): in this case, the constraint is always satisfied if \(y = 1\).

Similarly, for a linear constraint in the form \(a^T x + \alpha\, y \leq \beta\) with \(y \in \{0,1\}\), we can upgrade it to an indicator constraint if for the residual value \(a^T x \leq \gamma\), we have \(\alpha + \gamma \leq \beta\).

Definition at line 4803 of file cons_indicator.c.

References FALSE, REALABS, SCIP_Bool, SCIP_CALL, SCIP_DECL_CONSHDLRCOPY(), SCIP_OKAY, SCIP_Real, SCIPallocBufferArray, SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsChecked(), SCIPconsIsDynamic(), SCIPconsIsEnforced(), SCIPconsIsInitial(), SCIPconsIsLocal(), SCIPconsIsModifiable(), SCIPconsIsPropagated(), SCIPconsIsRemovable(), SCIPconsIsSeparated(), SCIPconsIsStickingAtNode(), SCIPcreateConsIndicator(), SCIPdebugMsg, SCIPfindConshdlr(), SCIPfreeBufferArray, SCIPgetLinearConsIndicator(), SCIPgetNegatedVar(), SCIPinfinity(), SCIPinfoMessage(), SCIPisEQ(), SCIPisGE(), SCIPisInfinity(), SCIPisLE(), SCIPisZero(), SCIPprintCons(), SCIPvarGetLbGlobal(), SCIPvarGetUbGlobal(), SCIPvarIsBinary(), and TRUE.

Referenced by initConshdlrData().

◆ SCIP_DECL_CONSHDLRCOPY()

static SCIP_DECL_CONSHDLRCOPY ( conshdlrCopyIndicator  )
static

copy method for constraint handler plugins (called when SCIP copies plugins)

Definition at line 5029 of file cons_indicator.c.

References CONSHDLR_NAME, SCIP_CALL, SCIP_DECL_CONSINIT(), SCIP_OKAY, SCIPconshdlrGetName(), SCIPincludeConshdlrIndicator(), and TRUE.

Referenced by SCIP_DECL_LINCONSUPGD().

◆ SCIP_DECL_CONSINIT()

static SCIP_DECL_CONSINIT ( consInitIndicator  )
static

initialization method of constraint handler (called after problem was transformed)

Definition at line 5047 of file cons_indicator.c.

References CONSHDLR_NAME, initConshdlrData(), SCIP_DECL_CONSEXIT(), SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), and SCIPfindHeur().

Referenced by SCIP_DECL_CONSHDLRCOPY().

◆ SCIP_DECL_CONSEXIT()

static SCIP_DECL_CONSEXIT ( consExitIndicator  )
static

deinitialization method of constraint handler (called before transformed problem is freed)

Definition at line 5072 of file cons_indicator.c.

References CONSHDLR_NAME, SCIP_DECL_CONSFREE(), SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPfreeBlockMemoryArrayNull, and SCIPhashmapFree().

Referenced by SCIP_DECL_CONSINIT().

◆ SCIP_DECL_CONSFREE()

static SCIP_DECL_CONSFREE ( consFreeIndicator  )
static

destructor of constraint handler to free constraint handler data (called when SCIP is exiting)

Definition at line 5096 of file cons_indicator.c.

References CONSHDLR_NAME, SCIP_DECL_CONSINITSOL(), SCIP_OKAY, SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPfreeBlockMemory, and SCIPfreeBlockMemoryArrayNull.

Referenced by SCIP_DECL_CONSEXIT().

◆ SCIP_DECL_CONSINITSOL()

static SCIP_DECL_CONSINITSOL ( consInitsolIndicator  )
static

◆ SCIP_DECL_CONSEXITSOL()

static SCIP_DECL_CONSEXITSOL ( consExitsolIndicator  )
static

solving process deinitialization method of constraint handler (called before branch and bound process data is freed)

Definition at line 5445 of file cons_indicator.c.

References CONSHDLR_NAME, SCIP_CALL, SCIP_DECL_CONSDELETE(), SCIP_OKAY, SCIPconsGetData(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPgetMessagehdlr(), SCIPhashmapFree(), SCIPhashmapPrintStatistics(), SCIPinfoMessage(), and SCIPlpiFree().

Referenced by SCIP_DECL_CONSINITSOL().

◆ SCIP_DECL_CONSDELETE()

◆ SCIP_DECL_CONSTRANS()

◆ SCIP_DECL_CONSINITPRE()

static SCIP_DECL_CONSINITPRE ( consInitpreIndicator  )
static

◆ SCIP_DECL_CONSPRESOL()

static SCIP_DECL_CONSPRESOL ( consPresolIndicator  )
static

presolving method of constraint handler

For an indicator constraint with binary variable \(y\) and slack variable \(s\) the coupling inequality \(s \le M (1-y)\) (equivalently: \(s + M y \le M\)) is inserted, where \(M\) is an upper bound on the value of \(s\). If \(M\) is too large the inequality is not inserted. Depending on the parameter addcouplingcons we add a variable upper bound or a row (in consInitlpIndicator()).

Warning
We can never delete linear constraints, because we need them to get the right values for the slack variables!

Definition at line 5727 of file cons_indicator.c.

References CONSHDLR_NAME, createVarUbs(), FALSE, presolRoundIndicator(), SCIP_Bool, SCIP_BOUNDTYPE_UPPER, SCIP_CALL, SCIP_CUTOFF, SCIP_DECL_CONSINITLP(), SCIP_DIDNOTFIND, SCIP_DIDNOTRUN, SCIP_OKAY, SCIP_Real, SCIP_SUCCESS, SCIP_VARTYPE_CONTINUOUS, SCIP_VARTYPE_IMPLINT, SCIPaddVarImplication(), SCIPallowDualReds(), SCIPchgVarType(), SCIPconsGetData(), SCIPconsGetHdlr(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPconsIsModifiable(), SCIPconsIsTransformed(), SCIPdebug, SCIPdebugMsg, SCIPgetNVarsLinear(), SCIPgetValsLinear(), SCIPgetVarsLinear(), SCIPisInfinity(), SCIPisIntegral(), SCIPvarGetLbGlobal(), SCIPvarGetName(), SCIPvarGetType(), SCIPvarGetUbGlobal(), SCIPvarIsIntegral(), and TRUE.

Referenced by SCIP_DECL_CONSINITPRE().

◆ SCIP_DECL_CONSINITLP()

static SCIP_DECL_CONSINITLP ( consInitlpIndicator  )
static

LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved)

For an indicator constraint with binary variable \(y\) and slack variable \(s\) the coupling inequality \(s \le M (1-y)\) (equivalently: \(s + M y \le M\)) is inserted, where \(M\) is an upper bound on the value of \(s\). If \(M\) is too large the inequality is not inserted.

Definition at line 5909 of file cons_indicator.c.

References CONSHDLR_NAME, FALSE, SCIP_CALL, SCIP_DECL_CONSSEPALP(), SCIP_OKAY, SCIP_Real, SCIPaddCons(), SCIPaddRow(), SCIPaddVarToRow(), SCIPcacheRowExtensions(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPcreateConsVarbound(), SCIPcreateEmptyRowCons(), SCIPdebugMsg, SCIPflushRowExtensions(), SCIPinfinity(), SCIPisNegative(), SCIPprintRow(), SCIPreleaseCons(), SCIPreleaseRow(), SCIPsnprintf(), SCIPvarGetUbGlobal(), and TRUE.

Referenced by SCIP_DECL_CONSPRESOL().

◆ SCIP_DECL_CONSSEPALP()

static SCIP_DECL_CONSSEPALP ( consSepalpIndicator  )
static

separation method of constraint handler for LP solutions

Definition at line 6005 of file cons_indicator.c.

References CONSHDLR_NAME, SCIP_CALL, SCIP_DECL_CONSSEPASOL(), SCIP_OKAY, SCIPconshdlrGetName(), and separateIndicators().

Referenced by SCIP_DECL_CONSINITLP().

◆ SCIP_DECL_CONSSEPASOL()

static SCIP_DECL_CONSSEPASOL ( consSepasolIndicator  )
static

separation method of constraint handler for arbitrary primal solutions

Definition at line 6022 of file cons_indicator.c.

References CONSHDLR_NAME, SCIP_CALL, SCIP_DECL_CONSENFOLP(), SCIP_OKAY, SCIPconshdlrGetName(), and separateIndicators().

Referenced by SCIP_DECL_CONSSEPALP().

◆ SCIP_DECL_CONSENFOLP()

static SCIP_DECL_CONSENFOLP ( consEnfolpIndicator  )
static

constraint enforcing method of constraint handler for LP solutions

Definition at line 6039 of file cons_indicator.c.

References CONSHDLR_NAME, enforceIndicators(), SCIP_CALL, SCIP_DECL_CONSENFORELAX(), SCIP_FEASIBLE, SCIP_OKAY, SCIPconshdlrGetData(), and SCIPconshdlrGetName().

Referenced by SCIP_DECL_CONSSEPASOL().

◆ SCIP_DECL_CONSENFORELAX()

static SCIP_DECL_CONSENFORELAX ( consEnforelaxIndicator  )
static

constraint enforcing method of constraint handler for relaxation solutions

Definition at line 6067 of file cons_indicator.c.

References CONSHDLR_NAME, enforceIndicators(), SCIP_CALL, SCIP_DECL_CONSENFOPS(), SCIP_FEASIBLE, SCIP_OKAY, SCIPconshdlrGetData(), and SCIPconshdlrGetName().

Referenced by SCIP_DECL_CONSENFOLP().

◆ SCIP_DECL_CONSENFOPS()

static SCIP_DECL_CONSENFOPS ( consEnfopsIndicator  )
static

constraint enforcing method of constraint handler for pseudo solutions

Definition at line 6095 of file cons_indicator.c.

References CONSHDLR_NAME, enforceIndicators(), SCIP_CALL, SCIP_DECL_CONSCHECK(), SCIP_DIDNOTRUN, SCIP_FEASIBLE, SCIP_OKAY, SCIPconshdlrGetName(), and TRUE.

Referenced by SCIP_DECL_CONSENFORELAX().

◆ SCIP_DECL_CONSCHECK()

◆ SCIP_DECL_CONSPROP()

static SCIP_DECL_CONSPROP ( consPropIndicator  )
static

◆ SCIP_DECL_CONSRESPROP()

static SCIP_DECL_CONSRESPROP ( consRespropIndicator  )
static

propagation conflict resolving method of constraint handler

We check which bound changes were the reason for infeasibility. We use that inferinfo is 0 if the binary variable has bounds that fix it to be nonzero (these bounds are the reason). Likewise inferinfo is 1 if the slack variable has bounds that fix it to be nonzero.

Definition at line 6389 of file cons_indicator.c.

References CONSHDLR_NAME, FALSE, SCIP_CALL, SCIP_DECL_CONSLOCK(), SCIP_DIDNOTFIND, SCIP_OKAY, SCIP_SUCCESS, SCIPaddConflictLb(), SCIPaddConflictUb(), SCIPallowDualReds(), SCIPallowObjProp(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetVarLbAtIndex(), SCIPgetVarUbAtIndex(), SCIPisFeasZero(), and SCIPisPositive().

Referenced by SCIP_DECL_CONSPROP().

◆ SCIP_DECL_CONSLOCK()

static SCIP_DECL_CONSLOCK ( consLockIndicator  )
static

variable rounding lock method of constraint handler

The up-rounding of the binary and slack variable may violate the constraint. If the linear constraint is not active, we lock all variables in the depending constraint - otherwise they will be fixed by dual presolving methods.

Definition at line 6445 of file cons_indicator.c.

References CONSHDLR_NAME, REALABS, SCIP_Bool, SCIP_CALL, SCIP_DECL_CONSPRINT(), SCIP_OKAY, SCIP_Real, SCIPaddVarLocks(), SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetName(), SCIPdebugMsg, SCIPgetLhsLinear(), SCIPgetNVarsLinear(), SCIPgetRhsLinear(), SCIPgetValsLinear(), SCIPgetVarsLinear(), SCIPisInfinity(), SCIPisPositive(), and SCIPisZero().

Referenced by SCIP_DECL_CONSRESPROP().

◆ SCIP_DECL_CONSPRINT()

static SCIP_DECL_CONSPRINT ( consPrintIndicator  )
static

◆ SCIP_DECL_CONSCOPY()

◆ SCIP_DECL_CONSPARSE()

static SCIP_DECL_CONSPARSE ( consParseIndicator  )
static

◆ SCIP_DECL_CONSENABLE()

static SCIP_DECL_CONSENABLE ( consEnableIndicator  )
static

constraint enabling notification method of constraint handler

Definition at line 6777 of file cons_indicator.c.

References CONSHDLR_NAME, SCIP_CALL, SCIP_DECL_CONSDISABLE(), SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), SCIPdebugMsg, and unfixAltLPVariable().

Referenced by SCIP_DECL_CONSPARSE().

◆ SCIP_DECL_CONSDISABLE()

static SCIP_DECL_CONSDISABLE ( consDisableIndicator  )
static

constraint disabling notification method of constraint handler

Definition at line 6813 of file cons_indicator.c.

References CONSHDLR_NAME, fixAltLPVariable(), SCIP_CALL, SCIP_DECL_CONSGETVARS(), SCIP_OKAY, SCIPconsGetData(), SCIPconsGetName(), SCIPconshdlrGetData(), SCIPconshdlrGetName(), and SCIPdebugMsg.

Referenced by SCIP_DECL_CONSENABLE().

◆ SCIP_DECL_CONSGETVARS()

static SCIP_DECL_CONSGETVARS ( consGetVarsIndicator  )
static

constraint method of constraint handler which returns the variables (if possible)

Definition at line 6849 of file cons_indicator.c.

References SCIP_CALL, SCIP_DECL_CONSGETNVARS(), SCIP_INVALIDDATA, SCIP_OKAY, SCIPconsGetData(), SCIPconsIsDeleted(), SCIPgetConsVars(), and TRUE.

Referenced by SCIP_DECL_CONSDISABLE().

◆ SCIP_DECL_CONSGETNVARS()

static SCIP_DECL_CONSGETNVARS ( consGetNVarsIndicator  )
static

constraint method of constraint handler which returns the number of variables (if possible)

Definition at line 6896 of file cons_indicator.c.

References SCIP_CALL, SCIP_DECL_CONSGETDIVEBDCHGS(), SCIP_OKAY, SCIPconsGetData(), SCIPconsIsDeleted(), SCIPgetConsNVars(), and TRUE.

Referenced by SCIP_DECL_CONSGETVARS().

◆ SCIP_DECL_CONSGETDIVEBDCHGS()