Scippy

SCIP

Solving Constraint Integer Programs

cons_indicator.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2020 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scipopt.org. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file cons_indicator.c
17  * @ingroup DEFPLUGINS_CONS
18  * @brief constraint handler for indicator constraints
19  * @author Marc Pfetsch
20  *
21  * An indicator constraint is given by a binary variable \f$y\f$ and an inequality \f$ax \leq
22  * b\f$. It states that if \f$y = 1\f$ then \f$ax \leq b\f$ holds.
23  *
24  * This constraint is handled by adding a slack variable \f$s:\; ax - s \leq b\f$ with \f$s \geq
25  * 0\f$. The constraint is enforced by fixing \f$s\f$ to 0 if \f$y = 1\f$.
26  *
27  * @note The constraint only implements an implication not an equivalence, i.e., it does not ensure
28  * that \f$y = 1\f$ if \f$ax \leq b\f$ or equivalently if \f$s = 0\f$ holds.
29  *
30  * This constraint is equivalent to a linear constraint \f$ax - s \leq b\f$ and an SOS1 constraint on
31  * \f$y\f$ and \f$s\f$ (at most one should be nonzero). In the indicator context we can, however,
32  * separate more inequalities.
33  *
34  * The name indicator apparently comes from CPLEX.
35  *
36  *
37  * @section SEPARATION Separation Methods
38  *
39  * We now explain the handling of indicator constraints in more detail. The indicator constraint
40  * handler adds an inequality for each indicator constraint. We assume that this system (with added
41  * slack variables) is \f$ Ax - s \leq b \f$, where \f$ x \f$ are the original variables and \f$ s
42  * \f$ are the slack variables added by the indicator constraint. Variables \f$ y \f$ are the binary
43  * variables corresponding to the indicator constraints.
44  *
45  * @note In the implementation, we assume that bounds on the original variables \f$x\f$ cannot be
46  * influenced by the indicator constraint. If it should be possible to relax these constraints as
47  * well, then these constraints have to be added as indicator constraints.
48  *
49  * We separate inequalities by using the so-called alternative polyhedron.
50  *
51  *
52  * @section ALTERNATIVEPOLYHEDRON Separation via the Alternative Polyhedron
53  *
54  * We now describe the separation method of the first method in more detail.
55  *
56  * Consider the LP-relaxation of the current subproblem:
57  * \f[
58  * \begin{array}{ll}
59  * min & c^T x + d^T z\\
60  * & A x - s \leq b, \\
61  * & D x + C z \leq f, \\
62  * & l \leq x \leq u, \\
63  * & u \leq z \leq v, \\
64  * & 0 \leq s.
65  * \end{array}
66  * \f]
67  * As above \f$Ax - s \leq b\f$ contains all inequalities corresponding to indicator constraints,
68  * while the system \f$Dx + Cy \leq f\f$ contains all other inequalities (which are ignored in the
69  * following). Similarly, variables \f$z\f$ not appearing in indicator constraints are
70  * ignored. Bounds for the variables \f$x_j\f$ can be given, in particular, variables can be
71  * fixed. Note that \f$s \leq 0\f$ renders the system infeasible.
72  *
73  * To generate cuts, we construct the so-called @a alternative @a polyhedron:
74  * \f[
75  * \begin{array}{ll}
76  * P = \{ (w,r,t) : & A^T w - r + t = 0,\\
77  * & b^T w - l^T r + u^T t = -1,\\
78  * & w, r, t \geq 0 \}.
79  * \end{array}
80  * \f]
81  * Here, \f$r\f$ and \f$t\f$ correspond to the lower and upper bounds on \f$x\f$, respectively.
82  *
83  * It turns out that the vertices of \f$P\f$ correspond to minimal infeasible subsystems of \f$A x
84  * \leq b\f$, \f$l \leq x \leq u\f$. If \f$I\f$ is the index set of such a system, it follows that not all \f$s_i\f$ for
85  * \f$i \in I\f$ can be 0, i.e., \f$y_i\f$ can be 1. In other words, the following cut is valid:
86  * \f[
87  * \sum_{i \in I} y_i \leq |I| - 1.
88  * \f]
89  *
90  *
91  * @subsection DETAIL Separation heuristic
92  *
93  * We separate the above inequalities by a heuristic described in
94  *
95  * Branch-And-Cut for the Maximum Feasible Subsystem Problem,@n
96  * Marc Pfetsch, SIAM Journal on Optimization 19, No.1, 21-38 (2008)
97  *
98  * The first step in the separation heuristic is to apply the transformation \f$\bar{y} = 1 - y\f$, which
99  * transforms the above inequality into the constraint
100  * \f[
101  * \sum_{i \in I} \bar{y}_i \geq 1,
102  * \f]
103  * that is, it is a set covering constraint on the negated variables.
104  *
105  * The basic idea is to use the current solution to the LP relaxation and use it as the objective,
106  * when optimizing of the alternative polyhedron. Since any vertex corresponds to such an
107  * inequality, we can check whether it is violated. To enlarge the chance that we find a @em
108  * violated inequality, we perform a fixing procedure, in which the variable corresponding to an
109  * arbitrary element of the last IIS \f$I\f$ is fixed to zero, i.e., cannot be used in the next
110  * IISs. This is repeated until the corresponding alternative polyhedron is infeasible, i.e., we
111  * have obtained an IIS-cover. For more details see the paper above.
112  *
113  *
114  * @subsection PREPROC Preprocessing
115  *
116  * Since each indicator constraint adds a linear constraint to the formulation, preprocessing of the
117  * linear constraints change the above approach as follows.
118  *
119  * The system as present in the formulation is the following (ignoring variables that are not
120  * contained in indicator constraints and the objective function):
121  * \f[
122  * \begin{array}{ll}
123  * & A x - s \leq b, \\
124  * & l \leq x \leq u, \\
125  * & s \leq 0.
126  * \end{array}
127  * \f]
128  * Note again that the requirement \f$s \leq 0\f$ leads to an infeasible system. Consider now the
129  * preprocessing of the linear constraint (aggregation, bound strengthening, etc.) and assume that
130  * this changes the above system to the following:
131  * \f[
132  * \begin{array}{ll}
133  * & \tilde{A} x - \tilde{B} s \leq \tilde{b}, \\
134  * & \tilde{l} \leq x \leq \tilde{u}, \\
135  * & s \leq 0. \\
136  * \end{array}
137  * \f]
138  * Note that we forbid multi-aggregation of the \f$s\f$ variables in order to be able to change their
139  * bounds in propagation/branching. The corresponding alternative system is the following:
140  * \f[
141  * \begin{array}{ll}
142  * & \tilde{A}^T w - r + t = 0,\\
143  * & - \tilde{B}^T w + v = 0,\\
144  * & b^T w - l^T r + u^T t = -1,\\
145  * & w, v, r, t \geq 0
146  * \end{array}
147  * \qquad \Leftrightarrow \qquad
148  * \begin{array}{ll}
149  * & \tilde{A}^T w - r + t = 0,\\
150  * & \tilde{B}^T w \geq 0,\\
151  * & b^T w - l^T r + u^T t = -1,\\
152  * & w, r, t \geq 0,
153  * \end{array}
154  * \f]
155  * where the second form arises by substituting \f$v \geq 0\f$. A closer look at this system reveals
156  * that it is not larger than the original one:
157  *
158  * - (Multi-)Aggregation of variables \f$x\f$ will remove these variables from the formulation, such that
159  * the corresponding column of \f$\tilde{A}\f$ (row of \f$\tilde{A}^T\f$) will be zero.
160  *
161  * - The rows of \f$\tilde{B}^T\f$ are not unit vectors, i.e., do not correspond to redundant
162  * nonnegativity constraints, only if the corresponding slack variables appear in an aggregation.
163  *
164  * Taken together, these two observations yield the conclusion that the new system is roughly as
165  * large as the original one.
166  *
167  * @note Because of possible (multi-)aggregation it might happen that the linear constraint
168  * corresponding to an indicator constraint becomes redundant and is deleted. From this we cannot
169  * conclude that the indicator constraint is redundant as well (i.e. always fulfilled), because the
170  * corresponding slack variable is still present and its setting to 0 might influence other
171  * (linear) constraints. Thus, we have to rely on the dual presolving of the linear constraints to
172  * detect this case: If the linear constraint is really redundant, i.e., is always fulfilled, it is
173  * deleted and the slack variable can be fixed to 0. In this case, the indicator constraint can be
174  * deleted as well.
175  *
176  * @todo Accept arbitrary ranged linear constraints as input (in particular: equations). Internally
177  * create two indicator constraints or correct alternative polyhedron accordingly (need to split the
178  * variables there, but not in original problem).
179  *
180  * @todo Treat variable upper bounds in a special way: Do not create the artificial slack variable,
181  * but directly enforce the propagations etc.
182  *
183  * @todo Turn off separation if the alternative polyhedron is infeasible and updateBounds is false.
184  *
185  * @todo Improve parsing of indicator constraint in CIP-format. Currently, we have to rely on a particular name, i.e.,
186  * the slack variable has to start with "indslack" and end with the name of the corresponding linear constraint.
187  *
188  * @todo Check whether one can further use the fact that the slack variable is aggregated.
189  */
190 
191 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
192 
193 #include "blockmemshell/memory.h"
194 #include "lpi/lpi.h"
195 #include "lpi/type_lpi.h"
196 #include "nlpi/type_expr.h"
197 #include "scip/cons_indicator.h"
198 #include "scip/cons_linear.h"
199 #include "scip/cons_logicor.h"
200 #include "scip/cons_quadratic.h"
201 #include "scip/cons_varbound.h"
202 #include "scip/heur_indicator.h"
203 #include "scip/heur_trysol.h"
204 #include "scip/pub_conflict.h"
205 #include "scip/pub_cons.h"
206 #include "scip/pub_event.h"
207 #include "scip/pub_lp.h"
208 #include "scip/pub_message.h"
209 #include "scip/pub_misc.h"
210 #include "scip/pub_paramset.h"
211 #include "scip/pub_var.h"
212 #include "scip/scip_branch.h"
213 #include "scip/scip_conflict.h"
214 #include "scip/scip_cons.h"
215 #include "scip/scip_copy.h"
216 #include "scip/scip_cut.h"
217 #include "scip/scip_event.h"
218 #include "scip/scip_general.h"
219 #include "scip/scip_heur.h"
220 #include "scip/scip_lp.h"
221 #include "scip/scip_mem.h"
222 #include "scip/scip_message.h"
223 #include "scip/scip_nlp.h"
224 #include "scip/scip_numerics.h"
225 #include "scip/scip_param.h"
226 #include "scip/scip_prob.h"
227 #include "scip/scip_probing.h"
228 #include "scip/scip_sol.h"
229 #include "scip/scip_solve.h"
230 #include "scip/scip_solvingstats.h"
231 #include "scip/scip_tree.h"
232 #include "scip/scip_var.h"
233 #include <string.h>
234 
235 /* #define SCIP_OUTPUT */
236 /* #define SCIP_ENABLE_IISCHECK */
237 
238 /* constraint handler properties */
239 #define CONSHDLR_NAME "indicator"
240 #define CONSHDLR_DESC "indicator constraint handler"
241 #define CONSHDLR_SEPAPRIORITY 10 /**< priority of the constraint handler for separation */
242 #define CONSHDLR_ENFOPRIORITY -100 /**< priority of the constraint handler for constraint enforcing */
243 #define CONSHDLR_CHECKPRIORITY -6000000 /**< priority of the constraint handler for checking feasibility */
244 #define CONSHDLR_SEPAFREQ 10 /**< frequency for separating cuts; zero means to separate only in the root node */
245 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
246 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
247  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
248 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
249 #define CONSHDLR_DELAYSEPA FALSE /**< Should separation method be delayed, if other separators found cuts? */
250 #define CONSHDLR_DELAYPROP FALSE /**< Should propagation method be delayed, if other propagators found reductions? */
251 #define CONSHDLR_NEEDSCONS TRUE /**< Should the constraint handler be skipped, if no constraints are available? */
253 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_FAST
254 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
256 
257 /* event handler properties */
258 #define EVENTHDLR_BOUND_NAME "indicatorbound"
259 #define EVENTHDLR_BOUND_DESC "bound change event handler for indicator constraints"
261 #define EVENTHDLR_RESTART_NAME "indicatorrestart"
262 #define EVENTHDLR_RESTART_DESC "force restart if absolute gap is 1 or enough binary variables have been fixed"
264 
265 /* conflict handler properties */
266 #define CONFLICTHDLR_NAME "indicatorconflict"
267 #define CONFLICTHDLR_DESC "replace slack variables and generate logicor constraints"
268 #define CONFLICTHDLR_PRIORITY 200000
270 /* upgrade properties */
271 #define LINCONSUPGD_PRIORITY +100000 /**< priority of the constraint handler for upgrading of linear constraints */
273 /* default values for parameters */
274 #define DEFAULT_BRANCHINDICATORS FALSE /**< Branch on indicator constraints in enforcing? */
275 #define DEFAULT_GENLOGICOR FALSE /**< Generate logicor constraints instead of cuts? */
276 #define DEFAULT_ADDCOUPLING TRUE /**< Add coupling constraints or rows if big-M is small enough? */
277 #define DEFAULT_MAXCOUPLINGVALUE 1e4 /**< maximum coefficient for binary variable in coupling constraint */
278 #define DEFAULT_ADDCOUPLINGCONS FALSE /**< Add initial variable upper bound constraints, if 'addcoupling' is true? */
279 #define DEFAULT_SEPACOUPLINGCUTS TRUE /**< Should the coupling inequalities be separated dynamically? */
280 #define DEFAULT_SEPACOUPLINGLOCAL FALSE /**< Allow to use local bounds in order to separate coupling inequalities? */
281 #define DEFAULT_SEPACOUPLINGVALUE 1e4 /**< maximum coefficient for binary variable in separated coupling constraint */
282 #define DEFAULT_SEPAALTERNATIVELP FALSE /**< Separate using the alternative LP? */
283 #define DEFAULT_SEPAPERSPECTIVE FALSE /**< Separate cuts based on perspective formulation? */
284 #define DEFAULT_SEPAPERSPLOCAL TRUE /**< Allow to use local bounds in order to separate perspectice cuts? */
285 #define DEFAULT_MAXSEPANONVIOLATED 3 /**< maximal number of separated non violated IISs, before separation is stopped */
286 #define DEFAULT_TRYSOLFROMCOVER FALSE /**< Try to construct a feasible solution from a cover? */
287 #define DEFAULT_UPGRADELINEAR FALSE /**< Try to upgrade linear constraints to indicator constraints? */
288 #define DEFAULT_USEOTHERCONSS FALSE /**< Collect other constraints to alternative LP? */
289 #define DEFAULT_USEOBJECTIVECUT FALSE /**< Use objective cut with current best solution to alternative LP? */
290 #define DEFAULT_UPDATEBOUNDS FALSE /**< Update bounds of original variables for separation? */
291 #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) */
292 #define DEFAULT_MAXSEPACUTS 100 /**< maximal number of cuts separated per separation round */
293 #define DEFAULT_MAXSEPACUTSROOT 2000 /**< maximal number of cuts separated per separation round in the root node */
294 #define DEFAULT_REMOVEINDICATORS FALSE /**< Remove indicator constraint if corresponding variable bound constraint has been added? */
295 #define DEFAULT_GENERATEBILINEAR FALSE /**< Do not generate indicator constraint, but a bilinear constraint instead? */
296 #define DEFAULT_SCALESLACKVAR FALSE /**< Scale slack variable coefficient at construction time? */
297 #define DEFAULT_NOLINCONSCONT FALSE /**< Decompose problem (do not generate linear constraint if all variables are continuous)? */
298 #define DEFAULT_TRYSOLUTIONS TRUE /**< Try to make solutions feasible by setting indicator variables? */
299 #define DEFAULT_ENFORCECUTS FALSE /**< In enforcing try to generate cuts (only if sepaalternativelp is true)? */
300 #define DEFAULT_DUALREDUCTIONS TRUE /**< Should dual reduction steps be performed? */
301 #define DEFAULT_ADDOPPOSITE FALSE /**< Add opposite inequality in nodes in which the binary variable has been fixed to 0? */
302 #define DEFAULT_CONFLICTSUPGRADE FALSE /**< Try to upgrade bounddisjunction conflicts by replacing slack variables? */
303 #define DEFAULT_FORCERESTART FALSE /**< Force restart if absolute gap is 1 or enough binary variables have been fixed? */
304 #define DEFAULT_RESTARTFRAC 0.9 /**< fraction of binary variables that need to be fixed before restart occurs (in forcerestart) */
306 
307 /* other values */
308 #define OBJEPSILON 0.001 /**< value to add to objective in alt. LP if the binary variable is 1 to get small IISs */
309 #define SEPAALTTHRESHOLD 10 /**< only separate IIS cuts if the number of separated coupling cuts is less than this value */
310 #define MAXROUNDINGROUNDS 1 /**< maximal number of rounds that produced cuts in separation */
312 
313 /** constraint data for indicator constraints */
314 struct SCIP_ConsData
315 {
316  SCIP_VAR* binvar; /**< binary variable for indicator constraint */
317  SCIP_VAR* slackvar; /**< slack variable of inequality of indicator constraint */
318  SCIP_CONS* lincons; /**< linear constraint corresponding to indicator constraint */
319  int nfixednonzero; /**< number of variables among binvar and slackvar fixed to be nonzero */
320  int colindex; /**< column index in alternative LP */
321  unsigned int linconsactive:1; /**< whether linear constraint and slack variable are active */
322  unsigned int implicationadded:1; /**< whether corresponding implication has been added */
323  unsigned int slacktypechecked:1; /**< whether it has been checked to convert the slack variable to be implicit integer */
324 };
325 
326 
327 /** indicator constraint handler data */
328 struct SCIP_ConshdlrData
329 {
330  SCIP_EVENTHDLR* eventhdlrbound; /**< event handler for bound change events */
331  SCIP_EVENTHDLR* eventhdlrrestart; /**< event handler for performing restarts */
332  SCIP_Bool removable; /**< whether the separated cuts should be removable */
333  SCIP_Bool scaled; /**< if first row of alt. LP has been scaled */
334  SCIP_Bool objindicatoronly; /**< whether the objective is nonzero only for indicator variables */
335  SCIP_Bool objothervarsonly; /**< whether the objective is nonzero only for non-indicator variables */
336  SCIP_Real minabsobj; /**< minimum absolute nonzero objective of indicator variables */
337  SCIP_LPI* altlp; /**< alternative LP for cut separation */
338  int nrows; /**< # rows in the alt. LP corr. to original variables in linear constraints and slacks */
339  int nlbbounds; /**< # lower bounds of original variables */
340  int nubbounds; /**< # upper bounds of original variables */
341  SCIP_HASHMAP* varhash; /**< hash map from variable to row index in alternative LP */
342  SCIP_HASHMAP* lbhash; /**< hash map from variable to index of lower bound column in alternative LP */
343  SCIP_HASHMAP* ubhash; /**< hash map from variable to index of upper bound column in alternative LP */
344  SCIP_HASHMAP* slackhash; /**< hash map from slack variable to row index in alternative LP */
345  SCIP_HASHMAP* binvarhash; /**< hash map from binary indicator variable to indicator constraint */
346  int nslackvars; /**< # slack variables */
347  int niiscutsgen; /**< number of IIS-cuts generated */
348  int nperspcutsgen; /**< number of cuts based on perspective formulation generated */
349  int objcutindex; /**< index of objective cut in alternative LP (-1 if not added) */
350  SCIP_Real objupperbound; /**< best upper bound on objective known */
351  SCIP_Real objaltlpbound; /**< upper objective bound stored in alternative LP (infinity if not added) */
352  int maxroundingrounds; /**< maximal number of rounds that produced cuts in separation */
353  SCIP_Real roundingminthres; /**< minimal value for rounding in separation */
354  SCIP_Real roundingmaxthres; /**< maximal value for rounding in separation */
355  SCIP_Real roundingoffset; /**< offset for rounding in separation */
356  SCIP_Bool branchindicators; /**< Branch on indicator constraints in enforcing? */
357  SCIP_Bool genlogicor; /**< Generate logicor constraints instead of cuts? */
358  SCIP_Bool addcoupling; /**< whether the coupling inequalities should be added at the beginning */
359  SCIP_Bool addcouplingcons; /**< Add initial variable upper bound constraints, if 'addcoupling' is true? */
360  SCIP_Bool sepacouplingcuts; /**< Should the coupling inequalities be separated dynamically? */
361  SCIP_Bool sepacouplinglocal; /**< Allow to use local bounds in order to separate coupling inequalities? */
362  SCIP_Bool sepaperspective; /**< Separate cuts based on perspective formulation? */
363  SCIP_Bool sepapersplocal; /**< Allow to use local bounds in order to separate perspectice cuts? */
364  SCIP_Bool removeindicators; /**< Remove indicator constraint if corresponding variable bound constraint has been added? */
365  SCIP_Bool updatebounds; /**< whether the bounds of the original variables should be changed for separation */
366  SCIP_Bool trysolutions; /**< Try to make solutions feasible by setting indicator variables? */
367  SCIP_Bool enforcecuts; /**< in enforcing try to generate cuts (only if sepaalternativelp is true) */
368  SCIP_Bool dualreductions; /**< Should dual reduction steps be performed? */
369  SCIP_Bool addopposite; /**< Add opposite inequality in nodes in which the binary variable has been fixed to 0? */
370  SCIP_Bool generatebilinear; /**< Do not generate indicator constraint, but a bilinear constraint instead? */
371  SCIP_Bool scaleslackvar; /**< Scale slack variable coefficient at construction time? */
372  SCIP_Bool conflictsupgrade; /**< Try to upgrade bounddisjunction conflicts by replacing slack variables? */
373  SCIP_Bool performedrestart; /**< whether a restart has been performed already */
374  int maxsepacuts; /**< maximal number of cuts separated per separation round */
375  int maxsepacutsroot; /**< maximal number of cuts separated per separation round in root node */
376  int maxsepanonviolated; /**< maximal number of separated non violated IISs, before separation is stopped */
377  int nbinvarszero; /**< binary variables globally fixed to zero */
378  int ninitconss; /**< initial number of indicator constraints (needed in event handlers) */
379  SCIP_Real maxcouplingvalue; /**< maximum coefficient for binary variable in initial coupling constraint */
380  SCIP_Real sepacouplingvalue; /**< maximum coefficient for binary variable in separated coupling constraint */
381  SCIP_Real maxconditionaltlp; /**< maximum estimated condition number of the alternative LP to trust its solution */
382  SCIP_Real restartfrac; /**< fraction of binary variables that need to be fixed before restart occurs (in forcerestart) */
383  SCIP_HEUR* heurtrysol; /**< trysol heuristic */
384  SCIP_Bool addedcouplingcons; /**< whether the coupling constraints have been added already */
385  SCIP_CONS** addlincons; /**< additional linear constraints that should be added to the alternative LP */
386  int naddlincons; /**< number of additional constraints */
387  int maxaddlincons; /**< maximal number of additional constraints */
388  SCIP_Bool useotherconss; /**< Collect other constraints to alternative LP? */
389  SCIP_Bool useobjectivecut; /**< Use objective cut with current best solution to alternative LP? */
390  SCIP_Bool trysolfromcover; /**< Try to construct a feasible solution from a cover? */
391  SCIP_Bool upgradelinear; /**< Try to upgrade linear constraints to indicator constraints? */
392  char normtype; /**< norm type for cut computation */
393  /* parameters that should not be changed after problem stage: */
394  SCIP_Bool sepaalternativelp; /**< Separate using the alternative LP? */
395  SCIP_Bool sepaalternativelp_; /**< used to store the sepaalternativelp parameter */
396  SCIP_Bool nolinconscont; /**< decompose problem - do not generate linear constraint if all variables are continuous */
397  SCIP_Bool nolinconscont_; /**< used to store the nolinconscont parameter */
398  SCIP_Bool forcerestart; /**< Force restart if absolute gap is 1 or enough binary variables have been fixed? */
399  SCIP_Bool forcerestart_; /**< used to store the forcerestart parameter */
400 };
401 
402 
403 /** indicator conflict handler data */
404 struct SCIP_ConflicthdlrData
405 {
406  SCIP_CONSHDLR* conshdlr; /**< indicator constraint handler */
407  SCIP_CONSHDLRDATA* conshdlrdata; /**< indicator constraint handler data */
408 };
409 
410 
411 /* macro for parameters */
412 #define SCIP_CALL_PARAM(x) /*lint -e527 */ do \
413 { \
414  SCIP_RETCODE _restat_; \
415  if ( (_restat_ = (x)) != SCIP_OKAY && (_restat_ != SCIP_PARAMETERUNKNOWN) ) \
416  { \
417  SCIPerrorMessage("[%s:%d] Error <%d> in function call\n", __FILE__, __LINE__, _restat_); \
418  SCIPABORT(); \
419  return _restat_; \
420  } \
421 } \
422 while ( FALSE )
423 
424 
425 /* ---------------- Callback methods of event handlers ---------------- */
426 
427 /** execute the event handler for getting variable bound changes
428  *
429  * We update the number of variables fixed to be nonzero.
430  */
431 static
432 SCIP_DECL_EVENTEXEC(eventExecIndicatorBound)
433 {
434  SCIP_EVENTTYPE eventtype;
435  SCIP_CONSDATA* consdata;
436  SCIP_Real oldbound;
437  SCIP_Real newbound;
438 
439  assert( eventhdlr != NULL );
440  assert( eventdata != NULL );
441  assert( strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_BOUND_NAME) == 0 );
442  assert( event != NULL );
443 
444  consdata = (SCIP_CONSDATA*)eventdata;
445  assert( consdata != NULL );
446  assert( 0 <= consdata->nfixednonzero && consdata->nfixednonzero <= 2 );
447  assert( consdata->linconsactive );
448 
449  oldbound = SCIPeventGetOldbound(event);
450  newbound = SCIPeventGetNewbound(event);
451 
452  eventtype = SCIPeventGetType(event);
453  switch ( eventtype )
454  {
456  /* if variable is now fixed to be positive */
457  if ( ! SCIPisFeasPositive(scip, oldbound) && SCIPisFeasPositive(scip, newbound) )
458  ++(consdata->nfixednonzero);
459 #ifdef SCIP_MORE_DEBUG
460  SCIPdebugMsg(scip, "Changed lower bound of variable <%s> from %g to %g (nfixednonzero: %d).\n",
461  SCIPvarGetName(SCIPeventGetVar(event)), oldbound, newbound, consdata->nfixednonzero);
462 #endif
463  break;
464 
466  /* if variable is now fixed to be negative */
467  if ( ! SCIPisFeasNegative(scip, oldbound) && SCIPisFeasNegative(scip, newbound) )
468  ++(consdata->nfixednonzero);
469 #ifdef SCIP_MORE_DEBUG
470  SCIPdebugMsg(scip, "Changed upper bound of variable <%s> from %g to %g (nfixednonzero: %d).\n",
471  SCIPvarGetName(SCIPeventGetVar(event)), oldbound, newbound, consdata->nfixednonzero);
472 #endif
473  break;
474 
476  /* if variable is not fixed to be positive anymore */
477  if ( SCIPisFeasPositive(scip, oldbound) && ! SCIPisFeasPositive(scip, newbound) )
478  --(consdata->nfixednonzero);
479 #ifdef SCIP_MORE_DEBUG
480  SCIPdebugMsg(scip, "Changed lower bound of variable <%s> from %g to %g (nfixednonzero: %d).\n",
481  SCIPvarGetName(SCIPeventGetVar(event)), oldbound, newbound, consdata->nfixednonzero);
482 #endif
483  break;
484 
486  /* if variable is not fixed to be negative anymore */
487  if ( SCIPisFeasNegative(scip, oldbound) && ! SCIPisFeasNegative(scip, newbound) )
488  --(consdata->nfixednonzero);
489 #ifdef SCIP_MORE_DEBUG
490  SCIPdebugMsg(scip, "Changed upper bound of variable <%s> from %g to %g (nfixednonzero: %d).\n",
491  SCIPvarGetName(SCIPeventGetVar(event)), oldbound, newbound, consdata->nfixednonzero);
492 #endif
493  break;
494 
495  default:
496  SCIPerrorMessage("Invalid event type.\n");
497  SCIPABORT();
498  return SCIP_INVALIDDATA; /*lint !e527*/
499  }
500  assert( 0 <= consdata->nfixednonzero && consdata->nfixednonzero <= 2 );
501 
502  return SCIP_OKAY;
503 }
504 
505 
506 /** exec the event handler for forcing a restart
507  *
508  * There are two cases in which we perform a (user) restart:
509  * - If we have a max FS instance, i.e., the objective is 1 for indicator variables and 0 otherwise,
510  * we can force a restart if the gap is 1. In this case, the remaining work consists of proving
511  * infeasibility of the non-fixed indicators.
512  * - If a large fraction of the binary indicator variables have been globally fixed, it makes sense
513  * to force a restart.
514  */
515 static
516 SCIP_DECL_EVENTEXEC(eventExecIndicatorRestart)
517 {
518  SCIP_CONSHDLRDATA* conshdlrdata;
519  SCIP_EVENTTYPE eventtype;
520 
521  assert( scip != NULL );
522  assert( eventhdlr != NULL );
523  assert( eventdata != NULL );
524  assert( strcmp(SCIPeventhdlrGetName(eventhdlr), EVENTHDLR_RESTART_NAME) == 0 );
525  assert( event != NULL );
526 
527  conshdlrdata = (SCIP_CONSHDLRDATA*)eventdata;
528  assert( conshdlrdata != NULL );
529  assert( conshdlrdata->forcerestart );
530 
531  eventtype = SCIPeventGetType(event);
532  switch ( eventtype )
533  {
536  {
537 #ifndef NDEBUG
538  SCIP_Real oldbound;
539  SCIP_Real newbound;
540 
542  oldbound = SCIPeventGetOldbound(event);
543  newbound = SCIPeventGetNewbound(event);
544  assert( SCIPisIntegral(scip, oldbound) );
545  assert( SCIPisIntegral(scip, newbound) );
546  assert( ! SCIPisEQ(scip, oldbound, newbound) );
547  assert( SCIPisZero(scip, oldbound) || SCIPisEQ(scip, oldbound, 1.0) );
548  assert( SCIPisZero(scip, newbound) || SCIPisEQ(scip, newbound, 1.0) );
549 #endif
550 
551  /* do not treat this case if we have performed a restart already */
552  if ( conshdlrdata->performedrestart )
553  return SCIP_OKAY;
554 
555  /* variable is now fixed */
556  ++(conshdlrdata->nbinvarszero);
557  SCIPdebugMsg(scip, "Fixed variable <%s> (nbinvarszero: %d, total: %d).\n",
558  SCIPvarGetName(SCIPeventGetVar(event)), conshdlrdata->nbinvarszero, conshdlrdata->ninitconss);
559 
561  break;
562 
563  /* if enough variables have been fixed */
564  if ( conshdlrdata->nbinvarszero > (int) ((SCIP_Real) conshdlrdata->ninitconss * conshdlrdata->restartfrac) )
565  {
567  "Forcing restart, since %d binary variables among %d have been fixed.\n", conshdlrdata->nbinvarszero, conshdlrdata->ninitconss);
569 
570  /* drop event */
571  if ( conshdlrdata->objindicatoronly )
572  {
573  SCIP_CALL( SCIPdropEvent(scip, SCIP_EVENTTYPE_BESTSOLFOUND, eventhdlr, (SCIP_EVENTDATA*) conshdlrdata, -1) );
574  }
575  conshdlrdata->performedrestart = TRUE;
576  }
577  break;
578  }
579 
581  assert( SCIPisIntegral(scip, conshdlrdata->minabsobj) );
582  assert( SCIPisGE(scip, conshdlrdata->minabsobj, 1.0 ) );
583 
585  break;
586 
587  if ( ! conshdlrdata->objindicatoronly )
588  break;
589 
590  /* if the absolute gap is equal to minabsobj */
591  if ( SCIPisEQ(scip, REALABS(SCIPgetPrimalbound(scip) - SCIPgetDualbound(scip)), conshdlrdata->minabsobj) )
592  {
593  SCIPverbMessage(scip, SCIP_VERBLEVEL_NORMAL, NULL, "Forcing restart, since the absolute gap is %f.\n", conshdlrdata->minabsobj);
595 
596  /* use inference branching, since the objective is not meaningful */
597  if ( SCIPfindBranchrule(scip, "inference") != NULL && !SCIPisParamFixed(scip, "branching/inference/priority") )
598  {
599  SCIP_CALL( SCIPsetIntParam(scip, "branching/inference/priority", INT_MAX/4) );
600  }
601 
602  /* drop event */
603  SCIP_CALL( SCIPdropEvent(scip, SCIP_EVENTTYPE_BESTSOLFOUND, eventhdlr, (SCIP_EVENTDATA*) conshdlrdata, -1) );
604  conshdlrdata->performedrestart = TRUE;
605  }
606  break;
607 
608  default:
609  SCIPerrorMessage("invalid event type.\n");
610  SCIPABORT();
611  return SCIP_INVALIDDATA; /*lint !e527*/
612  }
613 
614  return SCIP_OKAY;
615 }
616 
617 
618 /* ------------------------ conflict handler ---------------------------------*/
619 
620 /** destructor of conflict handler to free conflict handler data (called when SCIP is exiting) */
621 static
622 SCIP_DECL_CONFLICTFREE(conflictFreeIndicator)
623 {
624  SCIP_CONFLICTHDLRDATA* conflicthdlrdata;
625 
626  assert( scip != NULL );
627  assert( conflicthdlr != NULL );
628  assert( strcmp(SCIPconflicthdlrGetName(conflicthdlr), CONFLICTHDLR_NAME) == 0 );
629 
630  conflicthdlrdata = SCIPconflicthdlrGetData(conflicthdlr);
631  SCIPfreeBlockMemory(scip, &conflicthdlrdata);
632 
633  return SCIP_OKAY;
634 }
635 
636 
637 /** conflict processing method of conflict handler (called when conflict was found)
638  *
639  * In this conflict handler we try to replace slack variables by binary indicator variables and
640  * generate a logicor constraint if possible.
641  *
642  * @todo Extend to integral case.
643  */
644 static
645 SCIP_DECL_CONFLICTEXEC(conflictExecIndicator)
646 { /*lint --e{715}*/
647  SCIP_CONFLICTHDLRDATA* conflicthdlrdata;
648  SCIP_Bool haveslack;
649  SCIP_VAR* var;
650  int i;
651 
652  assert( conflicthdlr != NULL );
653  assert( strcmp(SCIPconflicthdlrGetName(conflicthdlr), CONFLICTHDLR_NAME) == 0 );
654  assert( bdchginfos != NULL || nbdchginfos == 0 );
655  assert( result != NULL );
656 
657  /* don't process already resolved conflicts */
658  if ( resolved )
659  {
660  *result = SCIP_DIDNOTRUN;
661  return SCIP_OKAY;
662  }
663 
664  SCIPdebugMsg(scip, "Indicator conflict handler.\n");
665 
666  conflicthdlrdata = SCIPconflicthdlrGetData(conflicthdlr);
667  assert( conflicthdlrdata != NULL );
668 
669  /* possibly skip conflict handler */
670  if ( ! ((SCIP_CONFLICTHDLRDATA*) conflicthdlrdata)->conshdlrdata->conflictsupgrade )
671  return SCIP_OKAY;
672 
673  *result = SCIP_DIDNOTFIND;
674 
675  /* check whether there seems to be one slack variable and all other variables are binary */
676  haveslack = FALSE;
677  for (i = 0; i < nbdchginfos; ++i)
678  {
679  assert( bdchginfos != NULL ); /* for flexelint */
680  assert( bdchginfos[i] != NULL );
681 
682  var = SCIPbdchginfoGetVar(bdchginfos[i]);
683 
684  /* quick check for slack variable that is implicitly integral or continuous */
686  {
687  /* check string */
688  if ( strstr(SCIPvarGetName(var), "indslack") != NULL )
689  {
690  /* make sure that the slack variable occurs with its lower bound */
692  break;
693 
694  /* make sure that the lower bound is 0 */
695  if ( ! SCIPisFeasZero(scip, SCIPbdchginfoGetNewbound(bdchginfos[i])) )
696  break;
697 
698  haveslack = TRUE;
699  continue;
700  }
701  }
702 
703  /* we only treat binary variables (other than slack variables) */
704  if ( ! SCIPvarIsBinary(var) )
705  break;
706  }
707 
708  /* if we have found at least one slack variable and all other variables are binary */
709  if ( haveslack && i == nbdchginfos )
710  {
711  SCIP_CONS** conss;
712  SCIP_VAR** vars;
713  int nconss;
714  int j;
715 
716  SCIPdebugMsg(scip, "Found conflict involving slack variables that can be remodelled.\n");
717 
718  assert( conflicthdlrdata->conshdlr != NULL );
719  assert( strcmp(SCIPconshdlrGetName(conflicthdlrdata->conshdlr), CONSHDLR_NAME) == 0 );
720 
721  nconss = SCIPconshdlrGetNConss(conflicthdlrdata->conshdlr);
722  conss = SCIPconshdlrGetConss(conflicthdlrdata->conshdlr);
723 
724  /* create array of variables in conflict constraint */
725  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nbdchginfos) );
726  for (i = 0; i < nbdchginfos; ++i)
727  {
728  assert( bdchginfos != NULL ); /* for flexelint */
729  assert( bdchginfos[i] != NULL );
730 
731  var = SCIPbdchginfoGetVar(bdchginfos[i]);
732 
733  SCIPdebugMsg(scip, " <%s> %s %g\n", SCIPvarGetName(var), SCIPbdchginfoGetBoundtype(bdchginfos[i]) == SCIP_BOUNDTYPE_LOWER ? ">=" : "<=",
734  SCIPbdchginfoGetNewbound(bdchginfos[i]));
735 
736  /* quick check for slack variable that is implicitly integral or continuous */
737  if ( (SCIPvarGetType(var) == SCIP_VARTYPE_IMPLINT || SCIPvarGetType(var) == SCIP_VARTYPE_CONTINUOUS) && strstr(SCIPvarGetName(var), "indslack") != NULL )
738  {
739  SCIP_VAR* slackvar;
740 
741  /* search for slack variable */
742  for (j = 0; j < nconss; ++j)
743  {
744  assert( conss[j] != NULL );
745  slackvar = SCIPgetSlackVarIndicator(conss[j]);
746  assert( slackvar != NULL );
747 
748  /* check whether we found the variable */
749  if ( slackvar == var )
750  {
751  /* replace slack variable by binary variable */
752  var = SCIPgetBinaryVarIndicator(conss[j]);
753  break;
754  }
755  }
756 
757  /* check whether we found the slack variable */
758  if ( j >= nconss )
759  {
760  SCIPdebugMsg(scip, "Could not find slack variable <%s>.\n", SCIPvarGetName(var));
761  break;
762  }
763  }
764  else
765  {
766  /* if the variable is fixed to one in the conflict set, we have to use its negation */
767  if ( SCIPbdchginfoGetNewbound(bdchginfos[i]) > 0.5 )
768  {
769  SCIP_CALL( SCIPgetNegatedVar(scip, var, &var) );
770  }
771  }
772 
773  vars[i] = var;
774  }
775 
776  /* whether all slack variables have been found */
777  if ( i == nbdchginfos )
778  {
779  SCIP_CONS* cons;
780  char consname[SCIP_MAXSTRLEN];
781 
782  SCIPdebugMsg(scip, "Generated logicor conflict constraint.\n");
783 
784  /* create a logicor constraint out of the conflict set */
785  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "cf%d_%" SCIP_LONGINT_FORMAT, SCIPgetNRuns(scip), SCIPgetNConflictConssApplied(scip));
786  SCIP_CALL( SCIPcreateConsLogicor(scip, &cons, consname, nbdchginfos, vars,
787  FALSE, separate, FALSE, FALSE, TRUE, local, FALSE, dynamic, removable, FALSE) );
788 
789 #ifdef SCIP_OUTPUT
790  SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
791  SCIPinfoMessage(scip, NULL, ";\n");
792 #endif
793 
794  /* add constraint to SCIP */
795  SCIP_CALL( SCIPaddConflict(scip, node, cons, validnode, conftype, cutoffinvolved) );
796 
797  *result = SCIP_CONSADDED;
798  }
799 
800  /* free temporary memory */
801  SCIPfreeBufferArray(scip, &vars);
802  }
803 
804  return SCIP_OKAY;
805 }
806 
807 
808 /* ------------------------ parameter handling ---------------------------------*/
809 
810 /** check whether we transfer a changed parameter to the given value
811  *
812  * @see paramChangedIndicator()
813  */
814 static
816  SCIP* scip, /**< SCIP data structure */
817  SCIP_PARAM* param, /**< parameter */
818  const char* name, /**< parameter name to check */
819  SCIP_Bool newvalue, /**< new value */
820  SCIP_Bool* value /**< old and possibly changed value of parameter */
821  )
822 {
823  const char* paramname;
824 
825  assert( scip != NULL );
826  assert( param != NULL );
827  assert( name != NULL );
828  assert( value != NULL );
829 
830  if ( SCIPparamGetType(param) != SCIP_PARAMTYPE_BOOL )
831  return SCIP_OKAY;
832 
833  if ( *value == newvalue )
834  return SCIP_OKAY;
835 
836  paramname = SCIPparamGetName(param);
837  assert( paramname != NULL );
838 
839  /* check whether the change parameter corresponds to our name to check */
840  if ( strcmp(paramname, name) == 0 )
841  {
842  /* check stage and possibly ignore parameter change */
843  if ( SCIPgetStage(scip) > SCIP_STAGE_PROBLEM )
844  {
845  SCIPwarningMessage(scip, "Cannot change parameter <%s> stage %d - reset to old value %s.\n", name, SCIPgetStage(scip), *value ? "true" : "false");
846  /* Note that the following command will create a recursive call, but then *value == newvalue above. */
847  SCIP_CALL( SCIPchgBoolParam(scip, param, *value) );
848  }
849  else
850  {
851  /* otherwise copy value */
852  *value = newvalue;
853  }
854  }
855 
856  return SCIP_OKAY;
857 }
858 
859 
860 /** called after a parameter has been changed */
861 static
862 SCIP_DECL_PARAMCHGD(paramChangedIndicator)
863 {
864  SCIP_CONSHDLR* conshdlr;
865  SCIP_CONSHDLRDATA* conshdlrdata;
866 
867  assert( scip != NULL );
868  assert( param != NULL );
869 
870  /* get indicator constraint handler */
871  conshdlr = SCIPfindConshdlr(scip, "indicator");
872  assert( conshdlr != NULL );
873 
874  /* get constraint handler data */
875  conshdlrdata = SCIPconshdlrGetData(conshdlr);
876  assert( conshdlrdata != NULL );
877 
878  SCIP_CALL( checkTransferBoolParam(scip, param, "constraints/indicator/sepaalternativelp", conshdlrdata->sepaalternativelp_, &conshdlrdata->sepaalternativelp) );
879  SCIP_CALL( checkTransferBoolParam(scip, param, "constraints/indicator/forcerestart", conshdlrdata->forcerestart_, &conshdlrdata->forcerestart) );
880  SCIP_CALL( checkTransferBoolParam(scip, param, "constraints/indicator/nolinconscont", conshdlrdata->nolinconscont_, &conshdlrdata->nolinconscont) );
881 
882  return SCIP_OKAY;
883 }
884 
885 
886 /* ------------------------ debugging routines ---------------------------------*/
887 
888 #ifdef SCIP_ENABLE_IISCHECK
889 /** Check that indicator constraints corresponding to nonnegative entries in @a vector are infeasible in original problem
890  *
891  * @note This function will probably fail if the has been presolved by the cons_linear presolver. To make it complete
892  * we would have to substitute active variables.
893  */
894 static
895 SCIP_RETCODE checkIIS(
896  SCIP* scip, /**< SCIP pointer */
897  int nconss, /**< number of constraints */
898  SCIP_CONS** conss, /**< indicator constraints */
899  SCIP_Real* vector /**< vector */
900  )
901 {
902  SCIP_CONSHDLRDATA* conshdlrdata;
903  SCIP_CONSHDLR* conshdlr;
904  SCIP_HASHMAP* varhash; /* hash map from variable to column index in auxiliary LP */
905  SCIP_LPI* lp;
906  int nvars = 0;
907  int c;
908 
909  assert( scip != NULL );
910  assert( vector != NULL );
911 
912  SCIPdebugMsg(scip, "Checking IIS ...\n");
913 
914  /* now check indicator constraints */
915  conshdlr = SCIPfindConshdlr(scip, "indicator");
916  assert( conshdlr != NULL );
917 
918  conshdlrdata = SCIPconshdlrGetData(conshdlr);
919  assert( conshdlrdata != NULL );
920 
921  conss = SCIPconshdlrGetConss(conshdlr);
922  nconss = SCIPconshdlrGetNConss(conshdlr);
923 
924  /* create LP */
926 
927  /* set up hash map */
928  SCIP_CALL( SCIPhashmapCreate(&varhash, SCIPblkmem(scip), SCIPgetNVars(scip)) );
929 
930  /* loop through indicator constraints */
931  for (c = 0; c < nconss; ++c)
932  {
933  SCIP_CONSDATA* consdata;
934  consdata = SCIPconsGetData(conss[c]);
935  assert( consdata != NULL );
936 
937  /* check whether constraint should be included */
938  if ( consdata->colindex >= 0 && (! SCIPisFeasZero(scip, vector[consdata->colindex]) || ! SCIPconsIsEnabled(conss[c])) )
939  {
940  SCIP_CONS* lincons;
941  SCIP_VAR** linvars;
942  SCIP_Real* linvals;
943  SCIP_Real linrhs;
944  SCIP_Real linlhs;
945  SCIP_VAR* slackvar;
946  int nlinvars;
947  SCIP_Real sign = 1.0;
948  int matbeg;
949  int* matind;
950  SCIP_Real* matval;
951  SCIP_VAR** newvars;
952  int nnewvars;
953  SCIP_Real lhs;
954  SCIP_Real rhs;
955  int cnt;
956  int v;
957 
958  lincons = consdata->lincons;
959  assert( lincons != NULL );
960  assert( ! SCIPconsIsEnabled(conss[c]) || SCIPconsIsActive(lincons) );
961  assert( ! SCIPconsIsEnabled(conss[c]) || SCIPconsIsEnabled(lincons) );
962 
963  slackvar = consdata->slackvar;
964  assert( slackvar != NULL );
965 
966  /* if the slack variable is aggregated (multi-aggregation should not happen) */
967  assert( SCIPvarGetStatus(slackvar) != SCIP_VARSTATUS_MULTAGGR );
968  if ( SCIPvarGetStatus(slackvar) == SCIP_VARSTATUS_AGGREGATED )
969  {
970  SCIP_VAR* var;
971  SCIP_Real scalar = 1.0;
972  SCIP_Real constant = 0.0;
973 
974  var = slackvar;
975 
976  SCIP_CALL( SCIPgetProbvarSum(scip, &var, &scalar, &constant) );
977  assert( ! SCIPisZero(scip, scalar) );
978 
979  /* SCIPdebugMsg(scip, "slack variable aggregated (scalar: %f, constant: %f)\n", scalar, constant); */
980 
981  /* otherwise construct a linear constraint */
982  SCIP_CALL( SCIPallocBufferArray(scip, &linvars, 1) );
983  SCIP_CALL( SCIPallocBufferArray(scip, &linvals, 1) );
984  linvars[0] = var;
985  linvals[0] = scalar;
986  nlinvars = 1;
987  linlhs = -SCIPinfinity(scip);
988  linrhs = constant;
989  }
990  else
991  {
992  /* in this case, the linear constraint is directly usable */
993  linvars = SCIPgetVarsLinear(scip, lincons);
994  linvals = SCIPgetValsLinear(scip, lincons);
995  nlinvars = SCIPgetNVarsLinear(scip, lincons);
996  linlhs = SCIPgetLhsLinear(scip, lincons);
997  linrhs = SCIPgetRhsLinear(scip, lincons);
998  }
999 
1000  /* adapt rhs of linear constraint */
1001  assert( SCIPisInfinity(scip, -linlhs) || SCIPisInfinity(scip, linrhs) );
1002  if ( SCIPisInfinity(scip, linrhs) )
1003  {
1004  linrhs = -linlhs;
1005  assert( linrhs > -SCIPinfinity(scip) );
1006  sign = -1.0;
1007  }
1008 
1009  SCIP_CALL( SCIPallocBufferArray(scip, &matind, 4*nlinvars) );
1010  SCIP_CALL( SCIPallocBufferArray(scip, &matval, 4*nlinvars) );
1011  SCIP_CALL( SCIPallocBufferArray(scip, &newvars, nlinvars) );
1012 
1013  /* set up row */
1014  nnewvars = 0;
1015  for (v = 0; v < nlinvars; ++v)
1016  {
1017  SCIP_VAR* var;
1018  var = linvars[v];
1019  assert( var != NULL );
1020 
1021  /* skip slack variable */
1022  if ( var == slackvar )
1023  continue;
1024 
1025  /* if variable is new */
1026  if ( ! SCIPhashmapExists(varhash, var) )
1027  {
1028  /* add variable in map */
1029  SCIP_CALL( SCIPhashmapInsertInt(varhash, var, nvars) );
1030  assert( nvars == SCIPhashmapGetImageInt(varhash, var) );
1031  /* SCIPdebugMsg(scip, "Inserted variable <%s> into hashmap (%d).\n", SCIPvarGetName(var), nvars); */
1032  nvars++;
1033 
1034  /* store new variables */
1035  newvars[nnewvars++] = var;
1036  }
1037  assert( SCIPhashmapExists(varhash, var) );
1038  }
1039 
1040  /* add new columns */
1041  if ( nnewvars > 0 )
1042  {
1043  SCIP_Real* lb;
1044  SCIP_Real* ub;
1045  SCIP_Real* obj;
1046  char** colnames;
1047 
1048  SCIP_CALL( SCIPallocBufferArray(scip, &lb, nnewvars) );
1049  SCIP_CALL( SCIPallocBufferArray(scip, &ub, nnewvars) );
1050  SCIP_CALL( SCIPallocBufferArray(scip, &obj, nnewvars) );
1051  SCIP_CALL( SCIPallocBufferArray(scip, &colnames, nnewvars) );
1052 
1053  for (v = 0; v < nnewvars; ++v)
1054  {
1055  SCIP_VAR* var;
1056  var = newvars[v];
1057  obj[v] = 0.0;
1058  lb[v] = SCIPvarGetLbLocal(var);
1059  ub[v] = SCIPvarGetUbLocal(var);
1060  SCIP_CALL( SCIPallocBufferArray(scip, &(colnames[v]), SCIP_MAXSTRLEN) ); /*lint !e866*/
1061  (void) SCIPsnprintf(colnames[v], SCIP_MAXSTRLEN, "%s", SCIPvarGetName(var));
1062  }
1063 
1064  /* now add columns */
1065  SCIP_CALL( SCIPlpiAddCols(lp, nnewvars, obj, lb, ub, colnames, 0, NULL, NULL, NULL) );
1066 
1067  for (v = nnewvars - 1; v >= 0; --v)
1068  {
1069  SCIPfreeBufferArray(scip, &(colnames[v]));
1070  }
1071  SCIPfreeBufferArray(scip, &colnames);
1072  SCIPfreeBufferArray(scip, &obj);
1073  SCIPfreeBufferArray(scip, &ub);
1074  SCIPfreeBufferArray(scip, &lb);
1075  }
1076 
1077  /* set up row */
1078  cnt = 0;
1079  for (v = 0; v < nlinvars; ++v)
1080  {
1081  SCIP_VAR* var;
1082  var = linvars[v];
1083  assert( var != NULL );
1084 
1085  /* skip slack variable */
1086  if ( var == slackvar )
1087  continue;
1088 
1089  assert( SCIPhashmapExists(varhash, var) );
1090  matind[cnt] = SCIPhashmapGetImageInt(varhash, var);
1091  matval[cnt] = sign * linvals[v];
1092  ++cnt;
1093  }
1094 
1095  lhs = -SCIPlpiInfinity(lp);
1096  rhs = linrhs;
1097 
1098  /* add new row */
1099  matbeg = 0;
1100  SCIP_CALL( SCIPlpiAddRows(lp, 1, &lhs, &rhs, NULL, cnt, &matbeg, matind, matval) );
1101 
1102  SCIPfreeBufferArray(scip, &matind);
1103  SCIPfreeBufferArray(scip, &matval);
1104  SCIPfreeBufferArray(scip, &newvars);
1105 
1106  assert( slackvar != NULL );
1107  if ( SCIPvarGetStatus(slackvar) == SCIP_VARSTATUS_AGGREGATED )
1108  {
1109  SCIPfreeBufferArray(scip, &linvals);
1110  SCIPfreeBufferArray(scip, &linvars);
1111  }
1112  }
1113  }
1114 
1115  /* possibly handle additional linear constraints */
1116  if ( conshdlrdata->useotherconss )
1117  {
1118  /* get all linear constraints */
1119  conss = SCIPgetConss(scip);
1120  nconss = SCIPgetNConss(scip);
1121 
1122  /* loop through constraints */
1123  for (c = 0; c < nconss; ++c)
1124  {
1125  SCIP_CONS* cons;
1126  SCIP_VAR** linvars;
1127  SCIP_Real* linvals;
1128  SCIP_Real linrhs;
1129  SCIP_Real linlhs;
1130  SCIP_Real* matval;
1131  SCIP_VAR** newvars;
1132  int nnewvars = 0;
1133  int* matind;
1134  int nlinvars;
1135  int matbeg = 0;
1136  int cnt = 0;
1137  int v;
1138 
1139  cons = conss[c];
1140  assert( cons != NULL );
1141 
1142  /* avoid non-active, local constraints */
1143  if ( ! SCIPconsIsEnabled(cons) || ! SCIPconsIsActive(cons) || SCIPconsIsLocal(cons) )
1144  continue;
1145 
1146  /* check type of constraint (only take linear constraints) */
1147  if ( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), "linear") != 0 )
1148  continue;
1149 
1150  /* avoid adding linear constraints that correspond to indicator constraints */
1151  if ( strncmp(SCIPconsGetName(cons), "indlin", 6) == 0 )
1152  continue;
1153 
1154  /* get data of linear constraint */
1155  linvars = SCIPgetVarsLinear(scip, cons);
1156  linvals = SCIPgetValsLinear(scip, cons);
1157  nlinvars = SCIPgetNVarsLinear(scip, cons);
1158  linlhs = SCIPgetLhsLinear(scip, cons);
1159  linrhs = SCIPgetRhsLinear(scip, cons);
1160 
1161  /* reserve space */
1162  SCIP_CALL( SCIPallocBufferArray(scip, &matind, 4*nlinvars) );
1163  SCIP_CALL( SCIPallocBufferArray(scip, &matval, 4*nlinvars) );
1164  SCIP_CALL( SCIPallocBufferArray(scip, &newvars, nlinvars) );
1165 
1166  /* collect possibly new variables */
1167  for (v = 0; v < nlinvars; ++v)
1168  {
1169  SCIP_VAR* var;
1170  var = linvars[v];
1171  assert( var != NULL );
1172 
1173  /* if variable is new */
1174  if ( ! SCIPhashmapExists(varhash, var) )
1175  {
1176  /* add variable in map */
1177  SCIP_CALL( SCIPhashmapInsertInt(varhash, var, nvars) );
1178  assert( nvars == SCIPhashmapGetImageInt(varhash, var) );
1179  /* SCIPdebugMsg(scip, "Inserted variable <%s> into hashmap (%d).\n", SCIPvarGetName(var), nvars); */
1180  nvars++;
1181 
1182  /* store new variables */
1183  newvars[nnewvars++] = var;
1184  }
1185  assert( SCIPhashmapExists(varhash, var) );
1186  }
1187 
1188  /* add new columns */
1189  if ( nnewvars > 0 )
1190  {
1191  SCIP_Real* lb;
1192  SCIP_Real* ub;
1193  SCIP_Real* obj;
1194  char** colnames;
1195 
1196  SCIP_CALL( SCIPallocBufferArray(scip, &lb, nnewvars) );
1197  SCIP_CALL( SCIPallocBufferArray(scip, &ub, nnewvars) );
1198  SCIP_CALL( SCIPallocBufferArray(scip, &obj, nnewvars) );
1199  SCIP_CALL( SCIPallocBufferArray(scip, &colnames, nnewvars) );
1200 
1201  for (v = 0; v < nnewvars; ++v)
1202  {
1203  SCIP_VAR* var;
1204  var = newvars[v];
1205  obj[v] = 0.0;
1206  lb[v] = SCIPvarGetLbLocal(var);
1207  ub[v] = SCIPvarGetUbLocal(var);
1208  SCIP_CALL( SCIPallocBufferArray(scip, &(colnames[v]), SCIP_MAXSTRLEN) ); /*lint !e866*/
1209  (void) SCIPsnprintf(colnames[v], SCIP_MAXSTRLEN, "%s", SCIPvarGetName(var));
1210  }
1211 
1212  /* now add columns */
1213  SCIP_CALL( SCIPlpiAddCols(lp, nnewvars, obj, lb, ub, colnames, 0, NULL, NULL, NULL) );
1214 
1215  for (v = nnewvars - 1; v >= 0; --v)
1216  {
1217  SCIPfreeBufferArray(scip, &(colnames[v]));
1218  }
1219  SCIPfreeBufferArray(scip, &colnames);
1220  SCIPfreeBufferArray(scip, &obj);
1221  SCIPfreeBufferArray(scip, &ub);
1222  SCIPfreeBufferArray(scip, &lb);
1223  }
1224 
1225  /* set up row */
1226  for (v = 0; v < nlinvars; ++v)
1227  {
1228  SCIP_VAR* var;
1229  var = linvars[v];
1230  assert( var != NULL );
1231 
1232  assert( SCIPhashmapExists(varhash, var) );
1233  matind[cnt] = SCIPhashmapGetImageInt(varhash, var);
1234  matval[cnt] = linvals[v];
1235  ++cnt;
1236  }
1237 
1238  /* add new row */
1239  SCIP_CALL( SCIPlpiAddRows(lp, 1, &linlhs, &linrhs, NULL, cnt, &matbeg, matind, matval) );
1240 
1241  SCIPfreeBufferArray(scip, &matind);
1242  SCIPfreeBufferArray(scip, &matval);
1243  SCIPfreeBufferArray(scip, &newvars);
1244  }
1245  }
1246 
1247  /* solve LP and check status */
1249 
1250  if ( ! SCIPlpiIsPrimalInfeasible(lp) )
1251  {
1252  SCIPerrorMessage("Detected IIS is not infeasible in original problem!\n");
1253 
1254  SCIP_CALL( SCIPlpiWriteLP(lp, "check.lp") );
1255  SCIP_CALL( SCIPlpiWriteLP(conshdlrdata->altlp, "altdebug.lp") );
1256  SCIPABORT();
1257  return SCIP_ERROR; /*lint !e527*/
1258  }
1259  SCIPdebugMsg(scip, "Check successful!\n");
1260 
1261  SCIPhashmapFree(&varhash);
1262  SCIP_CALL( SCIPlpiFree(&lp) );
1263 
1264  return SCIP_OKAY;
1265 }
1266 #endif
1267 
1268 
1269 /* ------------------------ auxiliary operations -------------------------------*/
1270 
1271 /** return objective contribution of variable
1272  *
1273  * Special treatment of negated variables: return negative of objective of original
1274  * variable. SCIPvarGetObj() would return 0 in these cases.
1275  */
1276 static
1278  SCIP_VAR* var /**< variable */
1279  )
1280 {
1281  if ( SCIPvarIsBinary(var) && SCIPvarIsNegated(var) )
1282  {
1283  assert( SCIPvarGetNegatedVar(var) != NULL );
1284  return -SCIPvarGetObj(SCIPvarGetNegatedVar(var));
1285  }
1286  else if ( SCIPvarGetStatus(var) == SCIP_VARSTATUS_AGGREGATED )
1287  {
1288  assert( SCIPvarGetAggrVar(var) != NULL );
1290  }
1291 
1292  return SCIPvarGetObj(var);
1293 }
1294 
1295 
1296 /** ensures that the addlincons array can store at least num entries */
1297 static
1299  SCIP* scip, /**< SCIP data structure */
1300  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
1301  int num /**< minimum number of entries to store */
1302  )
1303 {
1304  SCIP_CONSHDLRDATA* conshdlrdata;
1305 
1306  assert( scip != NULL );
1307  assert( conshdlr != NULL );
1308  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1309 
1310  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1311  assert( conshdlrdata != NULL );
1312  assert( conshdlrdata->naddlincons <= conshdlrdata->maxaddlincons );
1313 
1314  if ( num > conshdlrdata->maxaddlincons )
1315  {
1316  int newsize;
1317 
1318  newsize = SCIPcalcMemGrowSize(scip, num);
1319  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &conshdlrdata->addlincons, conshdlrdata->maxaddlincons, newsize) );
1320  conshdlrdata->maxaddlincons = newsize;
1321  }
1322  assert( num <= conshdlrdata->maxaddlincons );
1323 
1324  return SCIP_OKAY;
1325 }
1326 
1327 
1328 /* ------------------------ operations on the alternative LP -------------------*/
1329 
1330 /** initialize alternative LP
1331  *
1332  * The alternative system is organized as follows:
1333  * - The first row corresponds to the right hand side of the original system.
1334  * - The next nconss constraints correspond to the slack variables.
1335  * - The rows after that correspond to the original variables.
1336  */
1337 static
1339  SCIP* scip, /**< SCIP pointer */
1340  SCIP_CONSHDLR* conshdlr /**< constraint handler */
1341  )
1342 {
1343  SCIP_CONSHDLRDATA* conshdlrdata;
1344  SCIP_Real lhs = -1.0;
1345  SCIP_Real rhs = -1.0;
1346 
1347  assert( scip != NULL );
1348  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1349 
1350  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1351  assert( conshdlrdata != NULL );
1352  assert( conshdlrdata->altlp == NULL );
1353  assert( conshdlrdata->varhash == NULL );
1354  assert( conshdlrdata->lbhash == NULL );
1355  assert( conshdlrdata->ubhash == NULL );
1356  assert( conshdlrdata->slackhash != NULL );
1357 
1358  /* create hash map of variables */
1359  SCIP_CALL( SCIPhashmapCreate(&conshdlrdata->varhash, SCIPblkmem(scip), SCIPgetNVars(scip)) );
1360  SCIP_CALL( SCIPhashmapCreate(&conshdlrdata->lbhash, SCIPblkmem(scip), SCIPgetNVars(scip)) );
1361  SCIP_CALL( SCIPhashmapCreate(&conshdlrdata->ubhash, SCIPblkmem(scip), SCIPgetNVars(scip)) );
1362 
1363  /* create alternative LP */
1364  SCIP_CALL( SCIPlpiCreate(&conshdlrdata->altlp, SCIPgetMessagehdlr(scip), "altlp", SCIP_OBJSEN_MINIMIZE) );
1365 
1366  /* add first row */
1367  SCIP_CALL( SCIPlpiAddRows(conshdlrdata->altlp, 1, &lhs, &rhs, NULL, 0, NULL, NULL, NULL) );
1368  conshdlrdata->nrows = 1;
1369 
1370  /* set parameters */
1372  SCIP_CALL_PARAM( SCIPlpiSetIntpar(conshdlrdata->altlp, SCIP_LPPAR_PRESOLVING, TRUE) );
1373  SCIP_CALL_PARAM( SCIPlpiSetIntpar(conshdlrdata->altlp, SCIP_LPPAR_SCALING, 1) );
1374  SCIP_CALL_PARAM( SCIPlpiSetIntpar(conshdlrdata->altlp, SCIP_LPPAR_FASTMIP, FALSE) );
1375 
1376  SCIPdebugMsg(scip, "Initialized alternative LP.\n");
1377 
1378  /* uncomment the following for debugging */
1379  /* SCIP_CALL_PARAM( SCIPlpiSetIntpar(conshdlrdata->altlp, SCIP_LPPAR_LPINFO, TRUE) ); */
1380 
1381  return SCIP_OKAY;
1382 }
1383 
1384 
1385 /** check whether the bounds in given (alternative) LP are set correctly (for debugging) */
1386 #ifndef NDEBUG
1387 static
1389  SCIP* scip, /**< SCIP pointer */
1390  SCIP_LPI* lp, /**< LP for which bounds should be checked */
1391  int nconss, /**< number of constraints */
1392  SCIP_CONS** conss /**< constraints */
1393  )
1394 {
1395  SCIP_Real* lb;
1396  SCIP_Real* ub;
1397  SCIP_Bool* covered;
1398  int nCols;
1399  int j;
1400 
1401  assert( scip != NULL );
1402  assert( lp != NULL );
1403 
1404  SCIP_CALL( SCIPlpiGetNCols(lp, &nCols) );
1405 
1406  SCIP_CALL( SCIPallocBufferArray(scip, &lb, nCols) );
1407  SCIP_CALL( SCIPallocBufferArray(scip, &ub, nCols) );
1408  SCIP_CALL( SCIPallocBufferArray(scip, &covered, nCols) );
1409 
1410  for (j = 0; j < nCols; ++j)
1411  covered[j] = FALSE;
1412 
1413  /* check columns used by constraints */
1414  SCIP_CALL( SCIPlpiGetBounds(lp, 0, nCols-1, lb, ub) );
1415  for (j = 0; j < nconss; ++j)
1416  {
1417  SCIP_CONSDATA* consdata;
1418  int ind;
1419 
1420  assert( conss[j] != NULL );
1421  consdata = SCIPconsGetData(conss[j]);
1422  assert( consdata != NULL );
1423  ind = consdata->colindex;
1424 
1425  if ( ind >= 0 )
1426  {
1427  assert( ind < nCols );
1428  covered[ind] = TRUE;
1429  if ( ! SCIPisFeasZero(scip, lb[ind]) || ! SCIPlpiIsInfinity(lp, ub[ind]) )
1430  {
1431  SCIPABORT();
1432  }
1433  }
1434  }
1435 
1436  /* check other columns */
1437  for (j = 0; j < nCols; ++j)
1438  {
1439  if (! covered[j] )
1440  {
1441  /* some columns can be fixed to 0, since they correspond to disabled constraints */
1442  if ( ( ! SCIPlpiIsInfinity(lp, -lb[j]) && ! SCIPisFeasZero(scip, lb[j])) || (! SCIPlpiIsInfinity(lp, ub[j]) && ! SCIPisFeasZero(scip, ub[j])) )
1443  {
1444  SCIPABORT();
1445  }
1446  }
1447  }
1448 
1449  SCIPfreeBufferArray(scip, &covered);
1450  SCIPfreeBufferArray(scip, &lb);
1451  SCIPfreeBufferArray(scip, &ub);
1452 
1453  return SCIP_OKAY;
1454 }
1455 #endif
1456 
1457 
1458 /** set the alternative system objective function
1459  *
1460  * We assume that the objective function coefficients of the variables other than the binary
1461  * indicators are always 0 and hence do not have to be changed.
1462  *
1463  * We already use the tranformation \f$y' = 1 - y\f$.
1464  */
1465 static
1467  SCIP* scip, /**< SCIP pointer */
1468  SCIP_LPI* lp, /**< alternative LP */
1469  SCIP_SOL* sol, /**< solution to be dealt with */
1470  int nconss, /**< number of constraints */
1471  SCIP_CONS** conss /**< indicator constraints */
1472  )
1473 {
1474  int j;
1475  SCIP_Real* obj = NULL;
1476  int* indices = NULL;
1477  int cnt = 0;
1478 
1479  assert( scip != NULL );
1480  assert( lp != NULL );
1481  assert( conss != NULL );
1482 
1483  SCIP_CALL( SCIPallocBufferArray(scip, &obj, nconss) );
1484  SCIP_CALL( SCIPallocBufferArray(scip, &indices, nconss) );
1485 
1486  for (j = 0; j < nconss; ++j)
1487  {
1488  SCIP_CONSDATA* consdata;
1489 
1490  assert( conss[j] != NULL );
1491  consdata = SCIPconsGetData(conss[j]);
1492  assert( consdata != NULL );
1493 
1494  if ( consdata->colindex >= 0 )
1495  {
1496  SCIP_Real val = SCIPgetSolVal(scip, sol, consdata->binvar);
1497  if ( SCIPisFeasEQ(scip, val, 1.0) )
1498  obj[cnt] = OBJEPSILON; /* set objective to some small number to get small IISs */
1499  else
1500  obj[cnt] = 1.0 - val;
1501  indices[cnt++] = consdata->colindex;
1502  }
1503  }
1504 
1505  if ( cnt > 0 )
1506  {
1507  SCIP_CALL( SCIPlpiChgObj(lp, cnt, indices, obj) );
1508  }
1509 
1510  SCIPfreeBufferArray(scip, &indices);
1511  SCIPfreeBufferArray(scip, &obj);
1512 
1513  return SCIP_OKAY;
1514 }
1515 
1516 
1517 /** set the alternative system objective function to some small value */
1518 static
1520  SCIP* scip, /**< SCIP pointer */
1521  SCIP_LPI* lp, /**< alternative LP */
1522  int nconss, /**< number of constraints */
1523  SCIP_CONS** conss /**< indicator constraints */
1524  )
1525 {
1526  int j;
1527  SCIP_Real* obj = NULL;
1528  int* indices = NULL;
1529  int cnt = 0;
1530 
1531  assert( scip != NULL );
1532  assert( lp != NULL );
1533  assert( conss != NULL );
1534 
1535  SCIP_CALL( SCIPallocBufferArray(scip, &obj, nconss) );
1536  SCIP_CALL( SCIPallocBufferArray(scip, &indices, nconss) );
1537 
1538  for (j = 0; j < nconss; ++j)
1539  {
1540  SCIP_CONSDATA* consdata;
1541 
1542  assert( conss[j] != NULL );
1543  consdata = SCIPconsGetData(conss[j]);
1544  assert( consdata != NULL );
1545 
1546  if ( consdata->colindex >= 0 )
1547  {
1548  obj[cnt] = OBJEPSILON;
1549  indices[cnt++] = consdata->colindex;
1550  }
1551  }
1552 
1553  if ( cnt > 0 )
1554  {
1555  SCIP_CALL( SCIPlpiChgObj(lp, cnt, indices, obj) );
1556  }
1557 
1558  SCIPfreeBufferArray(scip, &indices);
1559  SCIPfreeBufferArray(scip, &obj);
1560 
1561  return SCIP_OKAY;
1562 }
1563 
1564 
1565 /** fix variable given by @a S to 0 */
1566 static
1568  SCIP* scip, /**< SCIP pointer */
1569  SCIP_LPI* lp, /**< alternative LP */
1570  int nconss, /**< number of constraints */
1571  SCIP_CONS** conss, /**< indicator constraints */
1572  SCIP_Bool* S /**< bitset of variables */
1573  )
1574 {
1575  SCIP_Real* lb = NULL;
1576  SCIP_Real* ub = NULL;
1577  int* indices = NULL;
1578  int cnt = 0;
1579  int j;
1580 
1581  assert( scip != NULL );
1582  assert( lp != NULL );
1583  assert( conss != NULL );
1584 
1585  SCIP_CALL( SCIPallocBufferArray(scip, &lb, nconss) );
1586  SCIP_CALL( SCIPallocBufferArray(scip, &ub, nconss) );
1587  SCIP_CALL( SCIPallocBufferArray(scip, &indices, nconss) );
1588 
1589  /* collect bounds to be changed */
1590  for (j = 0; j < nconss; ++j)
1591  {
1592  SCIP_CONSDATA* consdata;
1593 
1594  assert( conss[j] != NULL );
1595  consdata = SCIPconsGetData(conss[j]);
1596  assert( consdata != NULL );
1597 
1598  if ( consdata->colindex >= 0 )
1599  {
1600  if ( S[j] )
1601  {
1602  indices[cnt] = consdata->colindex;
1603  lb[cnt] = 0.0;
1604  ub[cnt] = 0.0;
1605  ++cnt;
1606  }
1607  }
1608  }
1609 
1610  /* change bounds */
1611  if ( cnt > 0 )
1612  {
1613  SCIP_CALL( SCIPlpiChgBounds(lp, cnt, indices, lb, ub) );
1614  }
1615 
1616  SCIPfreeBufferArray(scip, &indices);
1617  SCIPfreeBufferArray(scip, &ub);
1618  SCIPfreeBufferArray(scip, &lb);
1619 
1620  return SCIP_OKAY;
1621 }
1622 
1623 
1624 /** fix variable @a ind to 0 */
1625 static
1627  SCIP_LPI* lp, /**< alternative LP */
1628  int ind /**< variable that should be fixed to 0 */
1629  )
1630 {
1631  SCIP_Real lb = 0.0;
1632  SCIP_Real ub = 0.0;
1633 
1634  /* change bounds */
1635  SCIP_CALL( SCIPlpiChgBounds(lp, 1, &ind, &lb, &ub) );
1636 
1637  return SCIP_OKAY;
1638 }
1639 
1640 
1641 /** unfix variable @a ind to 0 */
1642 static
1644  SCIP_LPI* lp, /**< alternative LP */
1645  int ind /**< variable that should be fixed to 0 */
1646  )
1647 {
1648  SCIP_Real lb = 0.0;
1649  SCIP_Real ub = SCIPlpiInfinity(lp);
1650 
1651  /* change bounds */
1652  SCIP_CALL( SCIPlpiChgBounds(lp, 1, &ind, &lb, &ub) );
1653 
1654  return SCIP_OKAY;
1655 }
1656 
1657 /** unfix variable given by @a S to 0 */
1658 static
1660  SCIP* scip, /**< SCIP pointer */
1661  SCIP_LPI* lp, /**< alternative LP */
1662  int nconss, /**< number of constraints */
1663  SCIP_CONS** conss, /**< indicator constraints */
1664  SCIP_Bool* S /**< bitset of variables */
1665  )
1666 {
1667  SCIP_Real* lb = NULL;
1668  SCIP_Real* ub = NULL;
1669  int* indices = NULL;
1670  int cnt = 0;
1671  int j;
1672 
1673  assert( scip != NULL );
1674  assert( lp != NULL );
1675  assert( conss != NULL );
1676 
1677  SCIP_CALL( SCIPallocBufferArray(scip, &lb, nconss) );
1678  SCIP_CALL( SCIPallocBufferArray(scip, &ub, nconss) );
1679  SCIP_CALL( SCIPallocBufferArray(scip, &indices, nconss) );
1680 
1681  /* collect bounds to be changed */
1682  for (j = 0; j < nconss; ++j)
1683  {
1684  if ( S[j] )
1685  {
1686  SCIP_CONSDATA* consdata;
1687 
1688  assert( conss[j] != NULL );
1689  consdata = SCIPconsGetData(conss[j]);
1690  assert( consdata != NULL );
1691 
1692  if ( consdata->colindex >= 0 )
1693  {
1694  indices[cnt] = consdata->colindex;
1695  lb[cnt] = 0.0;
1696  ub[cnt] = SCIPlpiInfinity(lp);
1697  ++cnt;
1698  }
1699  }
1700  }
1701 
1702  /* change bounds */
1703  if ( cnt > 0 )
1704  {
1705  SCIP_CALL( SCIPlpiChgBounds(lp, cnt, indices, lb, ub) );
1706  }
1707 
1708  SCIPfreeBufferArray(scip, &indices);
1709  SCIPfreeBufferArray(scip, &ub);
1710  SCIPfreeBufferArray(scip, &lb);
1711 
1712  return SCIP_OKAY;
1713 }
1714 
1715 
1716 /** update bounds in first row to the current ones */
1717 static
1719  SCIP* scip, /**< SCIP pointer */
1720  SCIP_CONSHDLRDATA* conshdlrdata /**< constraint handler */
1721  )
1722 {
1723  SCIP_HASHMAP* lbhash;
1724  SCIP_HASHMAP* ubhash;
1725  SCIP_VAR** vars;
1726  SCIP_LPI* altlp;
1727  int nvars;
1728  int cnt;
1729  int v;
1730 
1731  assert( scip != NULL );
1732  assert( conshdlrdata != NULL );
1733 
1734  altlp = conshdlrdata->altlp;
1735  lbhash = conshdlrdata->lbhash;
1736  ubhash = conshdlrdata->ubhash;
1737  assert( lbhash != NULL && ubhash != NULL );
1738 
1739  /* check all variables */
1740  vars = SCIPgetVars(scip);
1741  nvars = SCIPgetNVars(scip);
1742  cnt = 0;
1743 
1744  for (v = 0; v < nvars; ++v)
1745  {
1746  SCIP_VAR* var;
1747  var = vars[v];
1748  if ( SCIPhashmapExists(lbhash, var) )
1749  {
1750  int col;
1751 
1752  col = SCIPhashmapGetImageInt(lbhash, var);
1753  SCIP_CALL( SCIPlpiChgCoef(altlp, 0, col, -SCIPvarGetLbLocal(var)) );
1754  if ( ! SCIPisEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetLbGlobal(var)) )
1755  ++cnt;
1756  }
1757  if ( SCIPhashmapExists(ubhash, var) )
1758  {
1759  int col;
1760 
1761  col = SCIPhashmapGetImageInt(ubhash, var);
1762  SCIP_CALL( SCIPlpiChgCoef(altlp, 0, col, SCIPvarGetUbLocal(var)) );
1763  if ( ! SCIPisEQ(scip, SCIPvarGetUbLocal(var), SCIPvarGetUbGlobal(var)) )
1764  ++cnt;
1765  }
1766  }
1767  if ( cnt > 10 )
1768  {
1769  /* possible force a rescaling: */
1770  conshdlrdata->scaled = FALSE;
1771 
1772  /* SCIP_CALL( SCIPlpiWriteLP(altlp, "altChg.lp") ); */
1773  SCIPdebugMsg(scip, "Updated bounds of original variables: %d.\n", cnt);
1774  }
1775 
1776  return SCIP_OKAY;
1777 }
1778 
1779 
1780 /** update bounds in first row to the global bounds */
1781 static
1783  SCIP* scip, /**< SCIP pointer */
1784  SCIP_CONSHDLRDATA* conshdlrdata /**< constraint handler */
1785  )
1786 {
1787  SCIP_HASHMAP* lbhash;
1788  SCIP_HASHMAP* ubhash;
1789  SCIP_VAR** vars;
1790  SCIP_LPI* altlp;
1791  int nvars;
1792  int cnt;
1793  int v;
1794 
1795  assert( scip != NULL );
1796  assert( conshdlrdata != NULL );
1797 
1798  altlp = conshdlrdata->altlp;
1799  lbhash = conshdlrdata->lbhash;
1800  ubhash = conshdlrdata->ubhash;
1801  assert( lbhash != NULL && ubhash != NULL );
1802 
1803  /* check all variables */
1804  vars = SCIPgetVars(scip);
1805  nvars = SCIPgetNVars(scip);
1806  cnt = 0;
1807 
1808  for (v = 0; v < nvars; ++v)
1809  {
1810  SCIP_VAR* var;
1811  int col;
1812 
1813  var = vars[v];
1814  if ( SCIPhashmapExists(lbhash, var) )
1815  {
1816  col = SCIPhashmapGetImageInt(lbhash, var);
1817  SCIP_CALL( SCIPlpiChgCoef(altlp, 0, col, -SCIPvarGetLbGlobal(var)) );
1818  ++cnt;
1819  }
1820  if ( SCIPhashmapExists(ubhash, var) )
1821  {
1822  col = SCIPhashmapGetImageInt(ubhash, var);
1823  SCIP_CALL( SCIPlpiChgCoef(altlp, 0, col, SCIPvarGetUbGlobal(var)) );
1824  ++cnt;
1825  }
1826  }
1827 
1828  if ( cnt > 0 )
1829  {
1830  /* SCIP_CALL( SCIPlpiWriteLP(altlp, "altChg.lp") ); */
1831  SCIPdebugMsg(scip, "Updated bounds of original variables: %d.\n", cnt);
1832  }
1833 
1834  /* possible force a rescaling: */
1835  /* conshdlrdata->scaled = FALSE; */
1836 
1837  return SCIP_OKAY;
1838 }
1839 
1840 
1841 /** check whether IIS defined by @a vector corresponds to a local cut */
1842 static
1844  SCIP* scip, /**< SCIP pointer */
1845  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler */
1846  SCIP_Real* vector, /**< solution to alternative LP defining IIS */
1847  SCIP_Bool* isLocal /**< whether the IIS uses local bounds different from the global ones */
1848  )
1849 {
1850  SCIP_HASHMAP* lbhash;
1851  SCIP_HASHMAP* ubhash;
1852  SCIP_VAR** vars;
1853 #ifndef NDEBUG
1854  int nCols;
1855 #endif
1856  int nvars;
1857  int v;
1858 
1859  assert( scip != NULL );
1860  assert( conshdlrdata != NULL );
1861  assert( vector != NULL );
1862  assert( isLocal != NULL );
1863 
1864  *isLocal = FALSE;
1865 
1866 #ifndef NDEBUG
1867  SCIP_CALL( SCIPlpiGetNCols(conshdlrdata->altlp, &nCols) );
1868 #endif
1869 
1870  lbhash = conshdlrdata->lbhash;
1871  ubhash = conshdlrdata->ubhash;
1872  assert( lbhash != NULL && ubhash != NULL );
1873 
1874  /* get all variables */
1875  vars = SCIPgetVars(scip);
1876  nvars = SCIPgetNVars(scip);
1877 
1878  /* check all variables */
1879  for (v = 0; v < nvars; ++v)
1880  {
1881  SCIP_VAR* var;
1882  var = vars[v];
1883 
1884  /* if local bound is different from global bound */
1885  if ( ! SCIPisEQ(scip, SCIPvarGetLbLocal(var), SCIPvarGetLbGlobal(var)) )
1886  {
1887  /* check whether the variable corresponding to the lower bounds has been used */
1888  if ( SCIPhashmapExists(lbhash, var) )
1889  {
1890  int col;
1891 
1892  col = SCIPhashmapGetImageInt(lbhash, var);
1893  assert( 0 <= col && col < nCols );
1894  if ( ! SCIPisFeasZero(scip, vector[col]) )
1895  {
1896  *isLocal = TRUE;
1897  return SCIP_OKAY;
1898  }
1899  }
1900  }
1901 
1902  /* if local bound is different from global bound */
1903  if ( ! SCIPisEQ(scip, SCIPvarGetUbLocal(var), SCIPvarGetUbGlobal(var)) )
1904  {
1905  /* check whether the variable corresponding to the upper bounds has been used */
1906  if ( SCIPhashmapExists(ubhash, var) )
1907  {
1908  int col;
1909 
1910  col = SCIPhashmapGetImageInt(ubhash, var);
1911  assert( 0 <= col && col < nCols );
1912  if ( ! SCIPisFeasZero(scip, vector[col]) )
1913  {
1914  *isLocal = TRUE;
1915  return SCIP_OKAY;
1916  }
1917  }
1918  }
1919  }
1920 
1921  return SCIP_OKAY;
1922 }
1923 
1924 
1925 /** compute scaling for first row
1926  *
1927  * If the coefficients in the first row are large, a right hand side of -1 might not be
1928  * adequate. Here, we replace the right hand side by the sum of the coefficients divided by the
1929  * number of nonzeros.
1930  */
1931 static
1933  SCIP* scip, /**< SCIP pointer */
1934  SCIP_CONSHDLRDATA* conshdlrdata /**< constraint handler */
1935  )
1936 {
1937  assert( scip != NULL );
1938  assert( conshdlrdata != NULL );
1939 
1940  if ( ! conshdlrdata->scaled )
1941  {
1942  SCIP_Real* val;
1943  SCIP_LPI* altlp;
1944  int* ind;
1945  SCIP_Real sum = 0.0;
1946  int beg[1];
1947  int nCols;
1948  int cnt;
1949  int j;
1950 
1951  altlp = conshdlrdata->altlp;
1952  SCIP_CALL( SCIPlpiGetNCols(altlp, &nCols) );
1953  SCIP_CALL( SCIPallocBufferArray(scip, &ind, nCols) );
1954  SCIP_CALL( SCIPallocBufferArray(scip, &val, nCols) );
1955 
1956  SCIP_CALL( SCIPlpiGetRows(altlp, 0, 0, NULL, NULL, &cnt, beg, ind, val) );
1957 
1958  if ( cnt > 0 )
1959  {
1960  /* compute sum */
1961  for (j = 0; j < cnt; ++j)
1962  sum += REALABS(val[j]);
1963 
1964  /* set rhs */
1965  sum = - REALABS(sum) / ((double) cnt);
1966  j = 0;
1967  SCIP_CALL( SCIPlpiChgSides(altlp, 1, &j, &sum, &sum) );
1968  }
1969 
1970  SCIPfreeBufferArray(scip, &val);
1971  SCIPfreeBufferArray(scip, &ind);
1972 
1973  conshdlrdata->scaled = TRUE;
1974  }
1975 
1976  return SCIP_OKAY;
1977 }
1978 
1979 
1980 /** add column to alternative LP
1981  *
1982  * See the description at the top of the file for more information.
1983  */
1984 static
1986  SCIP* scip, /**< SCIP pointer */
1987  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
1988  SCIP_CONSHDLRDATA* conshdlrdata, /**< data of constraint handler */
1989  SCIP_VAR* slackvar, /**< slack variable or NULL */
1990  int nvars, /**< number of variables in column */
1991  SCIP_VAR** vars, /**< variables for column */
1992  SCIP_Real* vals, /**< values for column */
1993  SCIP_Real rhscoef, /**< coefficient for first row */
1994  SCIP_Real objcoef, /**< objective in alternative LP */
1995  SCIP_Real sign, /**< sign (+1,-1) for column */
1996  SCIP_Bool colfree, /**< whether column should be free, e.g., for equations */
1997  int* colindex /**< index of new column (return value) */
1998  )
1999 {
2000  SCIP_VAR** newvars;
2001  SCIP_Real val;
2002  SCIP_Real* matval;
2003  SCIP_Bool* newrowsslack;
2004  SCIP_Real* obj;
2005  SCIP_Real* lb;
2006  SCIP_Real* ub;
2007  int* matbeg;
2008  int* matind;
2009  int nnewvars = 0;
2010  int nnewcols = 0;
2011  int nnewrows = 0;
2012  int ncols = 0;
2013  int cnt = 0;
2014  int v;
2015 
2016  assert( scip != NULL );
2017  assert( conshdlrdata != NULL );
2018  assert( vars != NULL );
2019  assert( vals != NULL );
2020  assert( ! SCIPisInfinity(scip, rhscoef) && ! SCIPisInfinity(scip, -rhscoef) );
2021  assert( SCIPisEQ(scip, sign, 1.0) || SCIPisEQ(scip, sign, -1.0) );
2022  assert( colindex != NULL );
2023 
2024  *colindex = -1;
2025 
2026  if ( conshdlrdata->altlp == NULL )
2027  {
2028  SCIP_CALL( initAlternativeLP(scip, conshdlr) );
2029  }
2030  assert( conshdlrdata->altlp != NULL );
2031  assert( conshdlrdata->varhash != NULL );
2032  assert( conshdlrdata->lbhash != NULL );
2033  assert( conshdlrdata->ubhash != NULL );
2034  assert( conshdlrdata->slackhash != NULL );
2035 
2036 #ifndef NDEBUG
2037  {
2038  int nrows;
2039  SCIP_CALL( SCIPlpiGetNRows(conshdlrdata->altlp, &nrows) );
2040  assert( nrows == conshdlrdata->nrows );
2041  }
2042 #endif
2043 
2044  /* set up data for construction */
2045  SCIP_CALL( SCIPallocBufferArray(scip, &matbeg, nvars) );
2046  SCIP_CALL( SCIPallocBufferArray(scip, &matind, 4 * nvars) );
2047  SCIP_CALL( SCIPallocBufferArray(scip, &matval, 4 * nvars) );
2048  SCIP_CALL( SCIPallocBufferArray(scip, &obj, 2 * nvars) );
2049  SCIP_CALL( SCIPallocBufferArray(scip, &lb, 2 * nvars) );
2050  SCIP_CALL( SCIPallocBufferArray(scip, &ub, 2 * nvars) );
2051  SCIP_CALL( SCIPallocBufferArray(scip, &newvars, nvars) );
2052  SCIP_CALL( SCIPallocBufferArray(scip, &newrowsslack, 2 * nvars) );
2053 
2054  /* store index of column in constraint */
2055  /* coverity[var_deref_model] */
2056  SCIP_CALL( SCIPlpiGetNCols(conshdlrdata->altlp, &ncols) );
2057  *colindex = ncols;
2058 
2059  /* handle first row */
2060  if ( ! SCIPisFeasZero(scip, rhscoef) )
2061  {
2062  matind[cnt] = 0;
2063  matval[cnt++] = sign * rhscoef;
2064  }
2065 
2066  /* set up column (recognize new original variables) */
2067  for (v = 0; v < nvars; ++v)
2068  {
2069  SCIP_VAR* var;
2070 
2071  var = vars[v];
2072  assert( var != NULL );
2073 
2074  /* if variable is a slack variable */
2075  if ( SCIPhashmapExists(conshdlrdata->slackhash, var) )
2076  {
2077  /* to avoid trivial rows: only add row corresponding to slack variable if it appears outside its own constraint */
2078  if ( var != slackvar )
2079  {
2080  int ind;
2081 
2082  ind = SCIPhashmapGetImageInt(conshdlrdata->slackhash, var);
2083 
2084  if ( ind < INT_MAX )
2085  matind[cnt] = ind;
2086  else
2087  {
2088  /* correct number of variable already in map/array and remember to add a new row */
2089  SCIP_CALL( SCIPhashmapSetImageInt(conshdlrdata->slackhash, var, conshdlrdata->nrows) );
2090  assert( conshdlrdata->nrows == SCIPhashmapGetImageInt(conshdlrdata->slackhash, var) );
2091  SCIPdebugMsg(scip, "Inserted slack variable <%s> into hashmap (row: %d).\n", SCIPvarGetName(var), conshdlrdata->nrows);
2092  matind[cnt] = (conshdlrdata->nrows)++;
2093 
2094  /* store new variables */
2095  newrowsslack[nnewrows++] = TRUE;
2096  }
2097  assert( conshdlrdata->nrows >= SCIPhashmapGetImageInt(conshdlrdata->slackhash, var) );
2098  matval[cnt++] = sign * vals[v];
2099  }
2100  }
2101  else
2102  {
2103  /* if variable exists */
2104  if ( SCIPhashmapExists(conshdlrdata->varhash, var) )
2105  matind[cnt] = SCIPhashmapGetImageInt(conshdlrdata->varhash, var);
2106  else
2107  {
2108  /* add variable in map and array and remember to add a new row */
2109  SCIP_CALL( SCIPhashmapInsertInt(conshdlrdata->varhash, var, conshdlrdata->nrows) );
2110  assert( conshdlrdata->nrows == SCIPhashmapGetImageInt(conshdlrdata->varhash, var) );
2111  SCIPdebugMsg(scip, "Inserted variable <%s> into hashmap (row: %d).\n", SCIPvarGetName(var), conshdlrdata->nrows);
2112  matind[cnt] = (conshdlrdata->nrows)++;
2113 
2114  /* store new variables */
2115  newrowsslack[nnewrows++] = FALSE;
2116  newvars[nnewvars++] = var;
2117  }
2118  assert( SCIPhashmapExists(conshdlrdata->varhash, var) );
2119  matval[cnt++] = sign * vals[v];
2120  }
2121  }
2122 
2123  /* add new rows */
2124  if ( nnewrows > 0 )
2125  {
2126  SCIP_Real* lhs;
2127  SCIP_Real* rhs;
2128  int i;
2129 
2130  SCIP_CALL( SCIPallocBufferArray(scip, &lhs, nnewrows) );
2131  SCIP_CALL( SCIPallocBufferArray(scip, &rhs, nnewrows) );
2132  for (i = 0; i < nnewrows; ++i)
2133  {
2134  if ( newrowsslack[i] )
2135  lhs[i] = -SCIPlpiInfinity(conshdlrdata->altlp);
2136  else
2137  lhs[i] = 0.0;
2138  rhs[i] = 0.0;
2139  }
2140  /* add new rows */
2141  SCIP_CALL( SCIPlpiAddRows(conshdlrdata->altlp, nnewrows, lhs, rhs, NULL, 0, NULL, NULL, NULL) );
2142 
2143  SCIPfreeBufferArray(scip, &lhs);
2144  SCIPfreeBufferArray(scip, &rhs);
2145  }
2146 
2147  /* now add column */
2148  obj[0] = objcoef;
2149  if ( colfree )
2150  {
2151  /* create a free variable -> should only happen for additional linear constraints */
2152  assert( slackvar == NULL );
2153  lb[0] = -SCIPlpiInfinity(conshdlrdata->altlp);
2154  }
2155  else
2156  lb[0] = 0.0;
2157  ub[0] = SCIPlpiInfinity(conshdlrdata->altlp);
2158  matbeg[0] = 0;
2159 
2160  SCIP_CALL( SCIPlpiAddCols(conshdlrdata->altlp, 1, obj, lb, ub, NULL, cnt, matbeg, matind, matval) );
2161 
2162  /* add columns corresponding to bounds of original variables - no bounds needed for slack vars */
2163  cnt = 0;
2164  for (v = 0; v < nnewvars; ++v)
2165  {
2166  SCIP_VAR* var = newvars[v];
2167  assert( var != NULL );
2168 
2169  /* if the lower bound is finite */
2170  val = SCIPvarGetLbGlobal(var);
2171  if ( ! SCIPisInfinity(scip, -val) )
2172  {
2173  matbeg[nnewcols] = cnt;
2174  if ( ! SCIPisZero(scip, val) )
2175  {
2176  matind[cnt] = 0;
2177  matval[cnt++] = -val;
2178  }
2179  assert( SCIPhashmapExists(conshdlrdata->varhash, var) );
2180 
2181  matind[cnt] = SCIPhashmapGetImageInt(conshdlrdata->varhash, var);
2182  matval[cnt++] = -1.0;
2183  obj[nnewcols] = 0.0;
2184  lb[nnewcols] = 0.0;
2185  ub[nnewcols] = SCIPlpiInfinity(conshdlrdata->altlp);
2186  ++conshdlrdata->nlbbounds;
2187 
2188  SCIP_CALL( SCIPhashmapInsertInt(conshdlrdata->lbhash, var, ncols + 1 + nnewcols) );
2189  assert( SCIPhashmapExists(conshdlrdata->lbhash, var) );
2190  SCIPdebugMsg(scip, "Added column for lower bound (%f) of variable <%s> to alternative polyhedron (col: %d).\n",
2191  val, SCIPvarGetName(var), ncols + 1 + nnewcols);
2192  ++nnewcols;
2193  }
2194 
2195  /* if the upper bound is finite */
2196  val = SCIPvarGetUbGlobal(var);
2197  if ( ! SCIPisInfinity(scip, val) )
2198  {
2199  matbeg[nnewcols] = cnt;
2200  if ( ! SCIPisZero(scip, val) )
2201  {
2202  matind[cnt] = 0;
2203  matval[cnt++] = val;
2204  }
2205  assert( SCIPhashmapExists(conshdlrdata->varhash, var) );
2206 
2207  matind[cnt] = SCIPhashmapGetImageInt(conshdlrdata->varhash, var);
2208  matval[cnt++] = 1.0;
2209  obj[nnewcols] = 0.0;
2210  lb[nnewcols] = 0.0;
2211  ub[nnewcols] = SCIPlpiInfinity(conshdlrdata->altlp);
2212  ++conshdlrdata->nubbounds;
2213 
2214  SCIP_CALL( SCIPhashmapInsertInt(conshdlrdata->ubhash, var, ncols + 1 + nnewcols) );
2215  assert( SCIPhashmapExists(conshdlrdata->ubhash, var) );
2216  SCIPdebugMsg(scip, "Added column for upper bound (%f) of variable <%s> to alternative polyhedron (col: %d).\n",
2217  val, SCIPvarGetName(var), ncols + 1 + nnewcols);
2218  ++nnewcols;
2219  }
2220  }
2221 
2222  /* add columns if necessary */
2223  if ( nnewcols > 0 )
2224  {
2225  SCIP_CALL( SCIPlpiAddCols(conshdlrdata->altlp, nnewcols, obj, lb, ub, NULL, cnt, matbeg, matind, matval) );
2226  }
2227 
2228 #ifndef NDEBUG
2229  SCIP_CALL( SCIPlpiGetNCols(conshdlrdata->altlp, &cnt) );
2230  assert( cnt == ncols + nnewcols + 1 );
2231 #endif
2232 
2233  SCIPfreeBufferArray(scip, &ub);
2234  SCIPfreeBufferArray(scip, &lb);
2235  SCIPfreeBufferArray(scip, &obj);
2236  SCIPfreeBufferArray(scip, &matind);
2237  SCIPfreeBufferArray(scip, &matval);
2238  SCIPfreeBufferArray(scip, &matbeg);
2239  SCIPfreeBufferArray(scip, &newvars);
2240  SCIPfreeBufferArray(scip, &newrowsslack);
2241 
2242  conshdlrdata->scaled = FALSE;
2243 
2244 #ifdef SCIP_OUTPUT
2245  SCIP_CALL( SCIPlpiWriteLP(conshdlrdata->altlp, "alt.lp") );
2246 #endif
2247 
2248  return SCIP_OKAY;
2249 }
2250 
2251 
2252 /** add column corresponding to constraint to alternative LP
2253  *
2254  * See the description at the top of the file for more information.
2255  */
2256 static
2258  SCIP* scip, /**< SCIP pointer */
2259  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
2260  SCIP_CONS* lincons, /**< linear constraint */
2261  SCIP_VAR* slackvar, /**< slack variable or NULL */
2262  SCIP_Real objcoef, /**< objective coefficient */
2263  int* colindex /**< index of new column */
2264  )
2265 {
2266  SCIP_CONSHDLRDATA* conshdlrdata;
2267  SCIP_VAR** linvars;
2268  SCIP_Real* linvals;
2269  SCIP_Real linrhs;
2270  SCIP_Real linlhs;
2271  int nlinvars;
2272 
2273  assert( scip != NULL );
2274  assert( conshdlr != NULL );
2275  assert( lincons != NULL );
2276  assert( colindex != NULL );
2277  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2278 
2279  *colindex = -1;
2280 
2281  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2282  assert( conshdlrdata != NULL );
2283 
2284  /* if the slack variable is aggregated (multi-aggregation should not happen) */
2285  assert( slackvar == NULL || SCIPvarGetStatus(slackvar) != SCIP_VARSTATUS_MULTAGGR );
2286  if ( slackvar != NULL && SCIPvarGetStatus(slackvar) == SCIP_VARSTATUS_AGGREGATED )
2287  {
2288  SCIP_VAR* var;
2289  SCIP_Real scalar = 1.0;
2290  SCIP_Real constant = 0.0;
2291 
2292  var = slackvar;
2293 
2294  SCIP_CALL( SCIPgetProbvarSum(scip, &var, &scalar, &constant) );
2295 
2296  SCIPdebugMsg(scip, "Slack variable is aggregated (scalar: %f, constant: %f).\n", scalar, constant);
2297 
2298  /* if the slack variable is fixed */
2299  if ( SCIPisZero(scip, scalar) && ! SCIPconsIsActive(lincons) )
2300  return SCIP_OKAY;
2301 
2302  /* otherwise construct a linear constraint */
2303  SCIP_CALL( SCIPallocBufferArray(scip, &linvars, 1) );
2304  SCIP_CALL( SCIPallocBufferArray(scip, &linvals, 1) );
2305  linvars[0] = var;
2306  linvals[0] = scalar;
2307  nlinvars = 1;
2308  linlhs = -SCIPinfinity(scip);
2309  linrhs = constant;
2310  }
2311  else
2312  {
2313  /* exit if linear constraint is not active */
2314  if ( ! SCIPconsIsActive(lincons) && slackvar != NULL )
2315  return SCIP_OKAY;
2316 
2317  /* in this case, the linear constraint is directly usable */
2318  linvars = SCIPgetVarsLinear(scip, lincons);
2319  linvals = SCIPgetValsLinear(scip, lincons);
2320  nlinvars = SCIPgetNVarsLinear(scip, lincons);
2321  linlhs = SCIPgetLhsLinear(scip, lincons);
2322  linrhs = SCIPgetRhsLinear(scip, lincons);
2323  }
2324 
2325  /* create column */
2326  if ( SCIPisEQ(scip, linlhs, linrhs) )
2327  {
2328  /* create free variable for equations (should only happen for additional linear constraints) */
2329  SCIP_CALL( addAltLPColumn(scip, conshdlr, conshdlrdata, slackvar, nlinvars, linvars, linvals, linrhs, objcoef, 1.0, TRUE, colindex) );
2330  }
2331  else if ( ! SCIPisInfinity(scip, linrhs) )
2332  {
2333  /* create column for rhs */
2334  SCIP_CALL( addAltLPColumn(scip, conshdlr, conshdlrdata, slackvar, nlinvars, linvars, linvals, linrhs, objcoef, 1.0, FALSE, colindex) );
2335  }
2336  else
2337  {
2338  /* create column for lhs */
2339  assert( ! SCIPisInfinity(scip, -linlhs) );
2340  SCIP_CALL( addAltLPColumn(scip, conshdlr, conshdlrdata, slackvar, nlinvars, linvars, linvals, linlhs, objcoef, -1.0, FALSE, colindex) );
2341  }
2342 
2343  if ( slackvar != NULL && SCIPvarGetStatus(slackvar) == SCIP_VARSTATUS_AGGREGATED )
2344  {
2345  SCIPfreeBufferArray(scip, &linvals);
2346  SCIPfreeBufferArray(scip, &linvars);
2347  }
2348 
2349  return SCIP_OKAY;
2350 }
2351 
2352 
2353 /** add column corresponding to row to alternative LP
2354  *
2355  * See the description at the top of the file for more information.
2356  */
2357 static
2359  SCIP* scip, /**< SCIP pointer */
2360  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
2361  SCIP_ROW* row, /**< row to add */
2362  SCIP_Real objcoef, /**< objective coefficient */
2363  int* colindex /**< index of new column */
2364  )
2365 {
2366  SCIP_CONSHDLRDATA* conshdlrdata;
2367  SCIP_COL** rowcols;
2368  SCIP_Real* rowvals;
2369  SCIP_VAR** rowvars;
2370  SCIP_Real rowrhs;
2371  SCIP_Real rowlhs;
2372  int nrowcols;
2373  int j;
2374 
2375  assert( scip != NULL );
2376  assert( conshdlr != NULL );
2377  assert( row != NULL );
2378  assert( colindex != NULL );
2379  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2380 
2381  /* initialize data */
2382  *colindex = -1;
2383 
2384  /* exit if row is not global */
2385  if ( SCIProwIsLocal(row) )
2386  return SCIP_OKAY;
2387 
2388  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2389  assert( conshdlrdata != NULL );
2390 
2391  /* get row data */
2392  rowcols = SCIProwGetCols(row);
2393  rowvals = SCIProwGetVals(row);
2394  nrowcols = SCIProwGetNNonz(row);
2395  rowlhs = SCIProwGetLhs(row) - SCIProwGetConstant(row);
2396  rowrhs = SCIProwGetRhs(row) - SCIProwGetConstant(row);
2397 
2398  SCIP_CALL( SCIPallocBufferArray(scip, &rowvars, nrowcols) );
2399  for (j = 0; j < nrowcols; ++j)
2400  {
2401  rowvars[j] = SCIPcolGetVar(rowcols[j]);
2402  assert( rowvars[j] != NULL );
2403  }
2404 
2405  /* create column */
2406  if ( SCIPisEQ(scip, rowlhs, rowrhs) )
2407  {
2408  /* create free variable for equations (should only happen for additional linear constraints) */
2409  SCIP_CALL( addAltLPColumn(scip, conshdlr, conshdlrdata, NULL, nrowcols, rowvars, rowvals, rowrhs, objcoef, 1.0, TRUE, colindex) );
2410  }
2411  else if ( ! SCIPisInfinity(scip, rowrhs) )
2412  {
2413  /* create column for rhs */
2414  SCIP_CALL( addAltLPColumn(scip, conshdlr, conshdlrdata, NULL, nrowcols, rowvars, rowvals, rowrhs, objcoef, 1.0, FALSE, colindex) );
2415  }
2416  else
2417  {
2418  /* create column for lhs */
2419  assert( ! SCIPisInfinity(scip, -rowlhs) );
2420  SCIP_CALL( addAltLPColumn(scip, conshdlr, conshdlrdata, NULL, nrowcols, rowvars, rowvals, rowlhs, objcoef, -1.0, FALSE, colindex) );
2421  }
2422 
2423  SCIPfreeBufferArray(scip, &rowvars);
2424 
2425  return SCIP_OKAY;
2426 }
2427 
2428 
2429 /** try to add objective cut as column to alternative LP */
2430 static
2432  SCIP* scip, /**< SCIP pointer */
2433  SCIP_CONSHDLR* conshdlr /**< constraint handler */
2434  )
2435 {
2436  SCIP_CONSHDLRDATA* conshdlrdata;
2437  SCIP_VAR** objvars;
2438  SCIP_Real* objvals;
2439  SCIP_VAR** vars;
2440  int nobjvars = 0;
2441  int nvars;
2442  int v;
2443 
2444  assert( scip != NULL );
2445  assert( conshdlr != NULL );
2446  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2447 
2448  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2449  assert( conshdlrdata != NULL );
2450 
2451  /* skip procedure if already added */
2452  if ( conshdlrdata->objcutindex >= 0 )
2453  return SCIP_OKAY;
2454 
2455  /* check whether we can add objective cut: all indicator variables have zero objective */
2456  if ( ! conshdlrdata->objothervarsonly )
2457  return SCIP_OKAY;
2458 
2459  assert( ! SCIPisInfinity(scip, conshdlrdata->objupperbound) );
2460  SCIPdebugMsg(scip, "Add objective cut to alternative LP (obj. bound: %g).\n", conshdlrdata->objupperbound);
2461 
2462  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
2463  SCIP_CALL( SCIPallocBufferArray(scip, &objvars, nvars) );
2464  SCIP_CALL( SCIPallocBufferArray(scip, &objvals, nvars) );
2465 
2466  /* collect nonzeros */
2467  for (v = 0; v < nvars; ++v)
2468  {
2469  SCIP_VAR* var;
2470  SCIP_Real objval;
2471 
2472  var = vars[v];
2473  assert( var != NULL );
2474  objval = SCIPvarGetObj(var);
2475 
2476  /* skip variables with zero objective - this includes slack and indicator variables */
2477  if ( ! SCIPisZero(scip, objval) )
2478  {
2479  objvars[nobjvars] = var;
2480  objvals[nobjvars++] = objval;
2481  }
2482  }
2483 
2484  /* create column (with rhs = upperbound, objective 0, and scaling factor 1.0) */
2485  SCIP_CALL( addAltLPColumn(scip, conshdlr, conshdlrdata, NULL, nobjvars, objvars, objvals, conshdlrdata->objupperbound, 0.0, 1.0, FALSE, &conshdlrdata->objcutindex) );
2486  assert( conshdlrdata->objcutindex >= 0 );
2487  conshdlrdata->objaltlpbound = conshdlrdata->objupperbound;
2488 
2489  SCIPfreeBufferArray(scip, &objvals);
2490  SCIPfreeBufferArray(scip, &objvars);
2491 
2492  return SCIP_OKAY;
2493 }
2494 
2495 
2496 /** delete column corresponding to constraint in alternative LP
2497  *
2498  * We currently just fix the corresponding variable to 0.
2499  */
2500 static
2502  SCIP* scip, /**< SCIP pointer */
2503  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
2504  SCIP_CONS* cons /**< indicator constraint */
2505  )
2506 {
2507  SCIP_CONSHDLRDATA* conshdlrdata;
2508 
2509  assert( scip != NULL );
2510  assert( conshdlr != NULL );
2511  assert( cons != NULL );
2512  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2513 
2514  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2515  assert( conshdlrdata != NULL );
2516 
2517  if ( conshdlrdata->altlp != NULL )
2518  {
2519  SCIP_CONSDATA* consdata;
2520 
2521  consdata = SCIPconsGetData(cons);
2522  assert( consdata != NULL );
2523 
2524  if ( consdata->colindex >= 0 )
2525  {
2526  SCIP_CALL( fixAltLPVariable(conshdlrdata->altlp, consdata->colindex) );
2527  }
2528  consdata->colindex = -1;
2529 
2530  SCIPdebugMsg(scip, "Fixed variable for column %d (constraint: <%s>) from alternative LP to 0.\n", consdata->colindex, SCIPconsGetName(cons));
2531  }
2532  conshdlrdata->scaled = FALSE;
2533 
2534  return SCIP_OKAY;
2535 }
2536 
2537 
2538 /** update upper bound in alternative LP */
2539 static
2541  SCIP* scip, /**< SCIP pointer */
2542  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
2543  SCIP_CONSHDLRDATA* conshdlrdata /**< constraint handler data */
2544  )
2545 {
2546  SCIP_Real objbnd;
2547 
2548  assert( scip != NULL );
2549  assert( conshdlrdata != NULL );
2550 
2551  if ( ! conshdlrdata->useobjectivecut )
2552  return SCIP_OKAY;
2553 
2554  if ( conshdlrdata->altlp == NULL )
2555  return SCIP_OKAY;
2556 
2557  /* first check whether we can improve the upper bound */
2558  objbnd = SCIPgetUpperbound(scip);
2559  if ( ! SCIPisInfinity(scip, objbnd) )
2560  {
2561  if ( SCIPisObjIntegral(scip) )
2562  objbnd = SCIPfeasCeil(scip, objbnd) - (1.0 - SCIPcutoffbounddelta(scip));
2563  else
2564  objbnd -= SCIPcutoffbounddelta(scip);
2565 
2566  if ( SCIPisLT(scip, objbnd, conshdlrdata->objupperbound) )
2567  conshdlrdata->objupperbound = objbnd;
2568  }
2569 
2570  if ( SCIPisInfinity(scip, conshdlrdata->objupperbound) )
2571  return SCIP_OKAY;
2572 
2573  /* if we can improve on the bound stored in the alternative LP */
2574  if ( SCIPisLT(scip, conshdlrdata->objupperbound, conshdlrdata->objaltlpbound) )
2575  {
2576  SCIPdebugMsg(scip, "Update objective bound to %g.\n", conshdlrdata->objupperbound);
2577 
2578  /* possibly add column for objective cut */
2579  if ( conshdlrdata->objcutindex < 0 )
2580  {
2581  SCIP_CALL( addObjcut(scip, conshdlr) );
2582  }
2583  else
2584  {
2585 #ifndef NDEBUG
2586  SCIP_Real oldbnd;
2587  SCIP_CALL( SCIPlpiGetCoef(conshdlrdata->altlp, 0, conshdlrdata->objcutindex, &oldbnd) );
2588  assert( SCIPisEQ(scip, oldbnd, conshdlrdata->objaltlpbound) );
2589 #endif
2590 
2591  /* update bound */
2592  SCIP_CALL( SCIPlpiChgCoef(conshdlrdata->altlp, 0, conshdlrdata->objcutindex, conshdlrdata->objupperbound) );
2593  conshdlrdata->objaltlpbound = conshdlrdata->objupperbound;
2594 
2595 #ifdef SCIP_OUTPUT
2596  SCIP_CALL( SCIPlpiWriteLP(conshdlrdata->altlp, "alt.lp") );
2597 #endif
2598  }
2599  }
2600 
2601  return SCIP_OKAY;
2602 }
2603 
2604 
2605 /** check whether the given LP is infeasible
2606  *
2607  * If @a primal is false we assume that the problem is <em>dual feasible</em>, e.g., the problem
2608  * was only changed by fixing bounds!
2609  *
2610  * This is the workhorse for all methods that have to solve the alternative LP. We try in several
2611  * ways to recover from possible stability problems.
2612  *
2613  * @pre It is assumed that all parameters for the alternative LP are set.
2614  */
2615 static
2617  SCIP* scip, /**< SCIP pointer */
2618  SCIP_LPI* lp, /**< LP */
2619  SCIP_Real maxcondition, /**< maximal allowed condition of LP solution basis matrix */
2620  SCIP_Bool primal, /**< whether we are using the primal or dual simplex */
2621  SCIP_Bool* infeasible, /**< output: whether the LP is infeasible */
2622  SCIP_Bool* error /**< output: whether an error occurred */
2623  )
2624 {
2625  SCIP_RETCODE retcode;
2626  SCIP_Real condition;
2627 
2628  assert( scip != NULL );
2629  assert( lp != NULL );
2630  assert( infeasible != NULL );
2631  assert( error != NULL );
2632 
2633  *error = FALSE;
2634 
2635  /* solve LP */
2636  if ( primal )
2637  retcode = SCIPlpiSolvePrimal(lp); /* use primal simplex */
2638  else
2639  retcode = SCIPlpiSolveDual(lp); /* use dual simplex */
2640  if ( retcode == SCIP_LPERROR )
2641  {
2642  *error = TRUE;
2643  return SCIP_OKAY;
2644  }
2645  SCIP_CALL( retcode );
2646 
2647  /* resolve if LP is not stable */
2648  if ( ! SCIPlpiIsStable(lp) )
2649  {
2652  SCIPwarningMessage(scip, "Numerical problems, retrying ...\n");
2653 
2654  /* re-solve LP */
2655  if ( primal )
2656  retcode = SCIPlpiSolvePrimal(lp); /* use primal simplex */
2657  else
2658  retcode = SCIPlpiSolveDual(lp); /* use dual simplex */
2659 
2660  /* reset parameters */
2663 
2664  if ( retcode == SCIP_LPERROR )
2665  {
2666  *error = TRUE;
2667  return SCIP_OKAY;
2668  }
2669  SCIP_CALL( retcode );
2670  }
2671 
2672  /* check whether we want to ignore the result, because the condition number is too large */
2673  if ( maxcondition > 0.0 )
2674  {
2675  /* check estimated condition number of basis matrix */
2677  if ( condition != SCIP_INVALID && condition > maxcondition ) /*lint !e777*/
2678  {
2679  SCIPdebugMsg(scip, "Estimated condition number of basis matrix (%e) exceeds maximal allowance (%e).\n", condition, maxcondition);
2680 
2681  *error = TRUE;
2682 
2683  return SCIP_OKAY;
2684  }
2685  else if ( condition != SCIP_INVALID ) /*lint !e777*/
2686  {
2687  SCIPdebugMsg(scip, "Estimated condition number of basis matrix (%e) is below maximal allowance (%e).\n", condition, maxcondition);
2688  }
2689  else
2690  {
2691  SCIPdebugMsg(scip, "Estimated condition number of basis matrix not available.\n");
2692  }
2693  }
2694 
2695  /* check whether we are in the paradoxical situation that
2696  * - the primal is not infeasible
2697  * - the primal is not unbounded
2698  * - the LP is not optimal
2699  * - we have a primal ray
2700  *
2701  * If we ran the dual simplex algorithm, then we run again with the primal simplex
2702  */
2704  ! SCIPlpiIsOptimal(lp) && SCIPlpiExistsPrimalRay(lp) && ! primal )
2705  {
2706  SCIPwarningMessage(scip, "The dual simplex produced a primal ray. Retrying with primal ...\n");
2707 
2708  /* the following settings might be changed: */
2712 
2713  SCIP_CALL( SCIPlpiSolvePrimal(lp) ); /* use primal simplex */
2714 
2715  /* reset parameters */
2719  }
2720 
2721  /* examine LP solution status */
2722  if ( SCIPlpiIsPrimalInfeasible(lp) ) /* the LP is provably infeasible */
2723  {
2724  assert( ! SCIPlpiIsPrimalUnbounded(lp) ); /* can't be unbounded or optimal */
2725  assert( ! SCIPlpiIsOptimal(lp) ); /* if it is infeasible! */
2726 
2727  *infeasible = TRUE; /* LP is infeasible */
2728  return SCIP_OKAY;
2729  }
2730  else
2731  {
2732  /* By assumption the dual is feasible if the dual simplex is run, therefore
2733  * the status has to be primal unbounded or optimal. */
2734  if ( ! SCIPlpiIsPrimalUnbounded(lp) && ! SCIPlpiIsOptimal(lp) )
2735  {
2736  /* We have a status different from unbounded or optimal. This should not be the case ... */
2737  if (primal)
2738  SCIPwarningMessage(scip, "Primal simplex returned with unknown status: %d\n", SCIPlpiGetInternalStatus(lp));
2739  else
2740  SCIPwarningMessage(scip, "Dual simplex returned with unknown status: %d\n", SCIPlpiGetInternalStatus(lp));
2741 
2742  /* SCIP_CALL( SCIPlpiWriteLP(lp, "debug.lp") ); */
2743  *error = TRUE;
2744  return SCIP_OKAY;
2745  }
2746  }
2747 
2748  /* at this point we have a feasible solution */
2749  *infeasible = FALSE;
2750  return SCIP_OKAY;
2751 }
2752 
2753 
2754 /** tries to extend a given set of variables to a cover
2755  *
2756  * At each step we include a variable which covers a new IIS. The corresponding IIS inequalities are added to the LP,
2757  * if this not already happened.
2758  *
2759  * @pre It is assumed that all parameters for the alternative LP are set and that the variables
2760  * corresponding to @a S are fixed. Furthermore @c xVal_ should contain the current LP solution.
2761  */
2762 static
2764  SCIP* scip, /**< SCIP pointer */
2765  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
2766  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
2767  SCIP_LPI* lp, /**< LP */
2768  SCIP_SOL* sol, /**< solution to be separated */
2769  SCIP_Bool removable, /**< whether cuts should be removable */
2770  SCIP_Bool genlogicor, /**< should logicor constraints be generated? */
2771  int nconss, /**< number of constraints */
2772  SCIP_CONS** conss, /**< indicator constraints */
2773  SCIP_Bool* S, /**< bitset of variables */
2774  int* size, /**< size of S */
2775  SCIP_Real* value, /**< objective value of S */
2776  SCIP_Bool* error, /**< output: whether an error occurred */
2777  SCIP_Bool* cutoff, /**< whether we detected a cutoff by an infeasible inequality */
2778  int* nGen /**< number of generated cuts */
2779  )
2780 {
2781 #ifdef SCIP_DEBUG
2782  char name[SCIP_MAXSTRLEN];
2783 #endif
2784  SCIP_Real* primsol;
2785  int nnonviolated = 0;
2786  int step = 0;
2787  int nCols;
2788 
2789  assert( scip != NULL );
2790  assert( lp != NULL );
2791  assert( conss != NULL );
2792  assert( S != NULL );
2793  assert( size != NULL );
2794  assert( value != NULL );
2795  assert( error != NULL );
2796  assert( cutoff != NULL );
2797  assert( nGen != NULL );
2798 
2799  *error = FALSE;
2800  *cutoff = FALSE;
2801  *nGen = 0;
2802 
2803  SCIP_CALL( SCIPlpiGetNCols(lp, &nCols) );
2804  SCIP_CALL( SCIPallocBufferArray(scip, &primsol, nCols) );
2805  assert( nconss <= nCols );
2806 
2807  do
2808  {
2809  SCIP_Bool infeasible;
2810  SCIP_Real sum = 0.0;
2811  SCIP_Real candobj = -1.0;
2812  SCIP_Real candval = 2.0;
2813  SCIP_Real norm = 1.0;
2814  int sizeIIS = 0;
2815  int candidate = -1;
2816  int candindex = -1;
2817  int j;
2818 
2819  if ( step == 0 )
2820  {
2821  /* the first LP is solved without warm start, after that we use a warmstart. */
2823  SCIP_CALL( checkAltLPInfeasible(scip, lp, conshdlrdata->maxconditionaltlp, TRUE, &infeasible, error) );
2825  }
2826  else
2827  SCIP_CALL( checkAltLPInfeasible(scip, lp, conshdlrdata->maxconditionaltlp, FALSE, &infeasible, error) );
2828 
2829  if ( *error )
2830  break;
2831 
2832  /* if the alternative polyhedron is infeasible, we found a cover */
2833  if ( infeasible )
2834  {
2835  /* Note: checking for a primal solution is done in extendToCover(). */
2836  SCIPdebugMsg(scip, " size: %4d produced possible cover with indicator variable objective value %f.\n", *size, *value);
2837 
2838  /* we currently cannot call probing if there are cuts in the sepastore; @todo fix this */
2839  if ( conshdlrdata->trysolfromcover )
2840  {
2841  /* Check whether we want to try to construct a feasible solution: there should be no integer/binary variables
2842  * except the indicator variables. Thus, there should be no integral variables and the number of indicator
2843  * variables should be at least (actually equal to) the number of binary variables. */
2844  if ( SCIPgetNIntVars(scip) == 0 && nconss >= SCIPgetNBinVars(scip) )
2845  {
2846  SCIP_HEUR* heurindicator;
2847 
2848  heurindicator = SCIPfindHeur(scip, "indicator");
2849  if ( heurindicator == NULL )
2850  {
2851  SCIPerrorMessage("Could not find heuristic \"indicator\".\n");
2852  return SCIP_PLUGINNOTFOUND;
2853  }
2854 
2855  SCIP_CALL( SCIPheurPassIndicator(scip, heurindicator, nconss, conss, S, -*value) );
2856  SCIPdebugMsg(scip, "Passed feasible solution to indicator heuristic.\n");
2857  }
2858  }
2859  break;
2860  }
2861 
2862  /* get solution of alternative LP */
2863  SCIP_CALL( SCIPlpiGetSol(lp, NULL, primsol, NULL, NULL, NULL) );
2864 
2865  /* get value of cut and find candidate for variable to add */
2866  for (j = 0; j < nconss; ++j)
2867  {
2868  SCIP_CONSDATA* consdata;
2869  int ind;
2870 
2871  consdata = SCIPconsGetData(conss[j]);
2872  assert( consdata != NULL );
2873  ind = consdata->colindex;
2874 
2875  if ( ind >= 0 )
2876  {
2877  assert( ind < nCols );
2878 
2879  /* check support of the solution, i.e., the corresponding IIS */
2880  if ( ! SCIPisFeasZero(scip, primsol[ind]) )
2881  {
2882  SCIP_Real val;
2883 
2884  assert( ! S[j] );
2885  ++sizeIIS;
2886  val = SCIPgetSolVal(scip, sol, consdata->binvar);
2887  sum += val;
2888 
2889  /* take element with smallest relaxation value */
2890  if ( val < candval )
2891  {
2892  candidate = j;
2893  candindex = ind;
2894  candval = val;
2895  candobj = varGetObjDelta(consdata->binvar);
2896  }
2897  }
2898  }
2899  }
2900 
2901  /* check for error */
2902  if ( candidate < 0 )
2903  {
2904  /* Because of numerical problems it might happen that the solution primsol above is zero
2905  * within the tolerances. In this case we quit. */
2906  break;
2907  }
2908  assert( candidate >= 0 );
2909  assert( ! S[candidate] );
2910  assert( sizeIIS > 0 );
2911 
2912  /* get the type of norm to use for efficacy calculations */
2913  switch ( conshdlrdata->normtype )
2914  {
2915  case 'e':
2916  norm = sqrt((SCIP_Real) sizeIIS);
2917  break;
2918  case 'm':
2919  norm = 1.0;
2920  break;
2921  case 's':
2922  norm = (SCIP_Real) sizeIIS;
2923  break;
2924  case 'd':
2925  norm = 1.0;
2926  break;
2927  default:
2928  SCIPerrorMessage("Invalid efficacy norm parameter '%c'.\n", conshdlrdata->normtype);
2929  SCIPABORT();
2930  norm = 1.0; /*lint !e527*/
2931  }
2932 
2933  SCIPdebugMsg(scip, " size: %4d, add var. %4d (obj: %-6g, alt-LP sol: %-8.4f); IIS size: %4d, eff.: %g.\n",
2934  *size, candidate, candobj, primsol[SCIPconsGetData(conss[candidate])->colindex], sizeIIS, (sum - (SCIP_Real) (sizeIIS - 1))/norm);
2935 
2936  /* update new set S */
2937  S[candidate] = TRUE;
2938  ++(*size);
2939  *value += candobj;
2940 
2941  /* fix chosen variable to 0 */
2942  SCIP_CALL( fixAltLPVariable(lp, candindex) );
2943 
2944  /* if cut is violated, i.e., sum - sizeIIS + 1 > 0 */
2945  if ( SCIPisEfficacious(scip, (sum - (SCIP_Real) (sizeIIS - 1))/norm) )
2946  {
2947  SCIP_Bool isLocal = FALSE;
2948 
2949 #ifdef SCIP_ENABLE_IISCHECK
2950  /* check whether we really have an infeasible subsystem */
2951  SCIP_CALL( checkIIS(scip, nconss, conss, primsol) );
2952 #endif
2953 
2954  /* check whether IIS corresponds to a local cut */
2955  if ( conshdlrdata->updatebounds )
2956  {
2957  SCIP_CALL( checkIISlocal(scip, conshdlrdata, primsol, &isLocal) );
2958  }
2959 
2960  if ( genlogicor )
2961  {
2962  SCIP_CONS* cons;
2963  SCIP_VAR** vars;
2964  int cnt = 0;
2965 
2966  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nconss) );
2967 
2968  /* collect variables corresponding to support to cut */
2969  for (j = 0; j < nconss; ++j)
2970  {
2971  SCIP_CONSDATA* consdata;
2972  int ind;
2973 
2974  consdata = SCIPconsGetData(conss[j]);
2975  ind = consdata->colindex;
2976 
2977  if ( ind >= 0 )
2978  {
2979  assert( ind < nCols );
2980  assert( consdata->binvar != NULL );
2981 
2982  /* check support of the solution, i.e., the corresponding IIS */
2983  if ( ! SCIPisFeasZero(scip, primsol[ind]) )
2984  {
2985  SCIP_VAR* var;
2986  SCIP_CALL( SCIPgetNegatedVar(scip, consdata->binvar, &var) );
2987  vars[cnt++] = var;
2988  }
2989  }
2990  }
2991  assert( cnt == sizeIIS );
2992 
2993 #ifdef SCIP_DEBUG
2994  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "iis%d", conshdlrdata->niiscutsgen + *nGen);
2995  SCIP_CALL( SCIPcreateConsLogicor(scip, &cons, name, cnt, vars, FALSE, TRUE, TRUE, TRUE, TRUE, isLocal, FALSE, TRUE, removable, FALSE) );
2996 #else
2997  SCIP_CALL( SCIPcreateConsLogicor(scip, &cons, "", cnt, vars, FALSE, TRUE, TRUE, TRUE, TRUE, isLocal, FALSE, TRUE, removable, FALSE) );
2998 #endif
2999 
3000 #ifdef SCIP_OUTPUT
3001  SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
3002  SCIPinfoMessage(scip, NULL, ";\n");
3003 #endif
3004 
3005  SCIP_CALL( SCIPaddCons(scip, cons) );
3006  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
3007 
3008  SCIPfreeBufferArray(scip, &vars);
3009  ++(*nGen);
3010  }
3011  else
3012  {
3013  SCIP_ROW* row;
3014 
3015  /* create row */
3016 #ifdef SCIP_DEBUG
3017  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "iis%d", conshdlrdata->niiscutsgen + *nGen);
3018  SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, name, -SCIPinfinity(scip), (SCIP_Real) (sizeIIS - 1), isLocal, FALSE, removable) );
3019 #else
3020  SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, "", -SCIPinfinity(scip), (SCIP_Real) (sizeIIS - 1), isLocal, FALSE, removable) );
3021 #endif
3022  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
3023 
3024  /* add variables corresponding to support to cut */
3025  for (j = 0; j < nconss; ++j)
3026  {
3027  int ind;
3028  SCIP_CONSDATA* consdata;
3029 
3030  consdata = SCIPconsGetData(conss[j]);
3031  ind = consdata->colindex;
3032 
3033  if ( ind >= 0 )
3034  {
3035  assert( ind < nCols );
3036  assert( consdata->binvar != NULL );
3037 
3038  /* check support of the solution, i.e., the corresponding IIS */
3039  if ( ! SCIPisFeasZero(scip, primsol[ind]) )
3040  {
3041  SCIP_VAR* var = consdata->binvar;
3042  SCIP_CALL( SCIPaddVarToRow(scip, row, var, 1.0) );
3043  }
3044  }
3045  }
3046  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
3047 #ifdef SCIP_OUTPUT
3048  SCIP_CALL( SCIPprintRow(scip, row, NULL) );
3049 #endif
3050  SCIP_CALL( SCIPaddRow(scip, row, FALSE, cutoff) );
3051  if ( *cutoff )
3052  {
3053  SCIPfreeBufferArray(scip, &primsol);
3054  return SCIP_OKAY;
3055  }
3056 
3057  /* cut should be violated: */
3058  assert( SCIPisFeasNegative(scip, SCIPgetRowSolFeasibility(scip, row, sol)) );
3059 
3060  /* add cuts to pool if they are globally valid */
3061  if ( ! isLocal )
3062  SCIP_CALL( SCIPaddPoolCut(scip, row) );
3063  SCIP_CALL( SCIPreleaseRow(scip, &row));
3064  ++(*nGen);
3065  }
3066  nnonviolated = 0;
3067  }
3068  else
3069  ++nnonviolated;
3070  ++step;
3071 
3072  if ( nnonviolated > conshdlrdata->maxsepanonviolated )
3073  {
3074  SCIPdebugMsg(scip, "Stop separation after %d non violated IISs.\n", nnonviolated);
3075  break;
3076  }
3077  }
3078  while (step < nconss);
3079 
3080  SCIPfreeBufferArray(scip, &primsol);
3081 
3082  return SCIP_OKAY;
3083 }
3084 
3085 
3086 /* ---------------------------- constraint handler local methods ----------------------*/
3087 
3088 /** creates and initializes consdata */
3089 static
3091  SCIP* scip, /**< SCIP data structure */
3092  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
3093  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
3094  const char* consname, /**< name of constraint (or NULL) */
3095  SCIP_CONSDATA** consdata, /**< pointer to linear constraint data */
3096  SCIP_EVENTHDLR* eventhdlrbound, /**< event handler for bound change events */
3097  SCIP_EVENTHDLR* eventhdlrrestart, /**< event handler for handling restarts */
3098  SCIP_VAR* binvar, /**< binary variable (or NULL) */
3099  SCIP_VAR* slackvar, /**< slack variable */
3100  SCIP_CONS* lincons, /**< linear constraint (or NULL) */
3101  SCIP_Bool linconsactive /**< whether the linear constraint is active */
3102  )
3103 {
3104  assert( scip != NULL );
3105  assert( conshdlr != NULL );
3106  assert( conshdlrdata != NULL );
3107  assert( consdata != NULL );
3108  assert( slackvar != NULL );
3109  assert( eventhdlrbound != NULL );
3110  assert( eventhdlrrestart != NULL );
3111 
3112  /* create constraint data */
3113  SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
3114  (*consdata)->nfixednonzero = 0;
3115  (*consdata)->colindex = -1;
3116  (*consdata)->linconsactive = linconsactive;
3117  (*consdata)->binvar = binvar;
3118  (*consdata)->slackvar = slackvar;
3119  (*consdata)->lincons = lincons;
3120  (*consdata)->implicationadded = FALSE;
3121  (*consdata)->slacktypechecked = FALSE;
3122 
3123  /* if we are transformed, obtain transformed variables and catch events */
3124  if ( SCIPisTransformed(scip) )
3125  {
3126  SCIP_VAR* var;
3127 
3128  /* handle binary variable */
3129  if ( binvar != NULL )
3130  {
3131  SCIP_CALL( SCIPgetTransformedVar(scip, binvar, &var) );
3132  assert( var != NULL );
3133  (*consdata)->binvar = var;
3134 
3135  /* check type */
3136  if ( SCIPvarGetType(var) != SCIP_VARTYPE_BINARY )
3137  {
3138  SCIPerrorMessage("Indicator variable <%s> is not binary %d.\n", SCIPvarGetName(var), SCIPvarGetType(var));
3139  return SCIP_ERROR;
3140  }
3141 
3142  /* the indicator variable must not be multi-aggregated because the constraint handler propagation tries
3143  * to tighten its bounds, which is not allowed for multi-aggregated variables
3144  */
3145  SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, var) );
3146 
3147  /* catch local bound change events on binary variable */
3148  if ( linconsactive )
3149  {
3150  SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlrbound, (SCIP_EVENTDATA*)*consdata, NULL) );
3151  }
3152 
3153  /* catch global bound change events on binary variable */
3154  if ( conshdlrdata->forcerestart )
3155  {
3156  SCIPdebugMsg(scip, "Catching GBDCHANGED event for <%s>.\n", SCIPvarGetName(var));
3157  SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_GBDCHANGED, eventhdlrrestart, (SCIP_EVENTDATA*) conshdlrdata, NULL) );
3158  }
3159 
3160  /* if binary variable is fixed to be nonzero */
3161  if ( SCIPvarGetLbLocal(var) > 0.5 )
3162  ++((*consdata)->nfixednonzero);
3163  }
3164 
3165  /* handle slack variable */
3166  SCIP_CALL( SCIPgetTransformedVar(scip, slackvar, &var) );
3167  assert( var != NULL );
3168  (*consdata)->slackvar = var;
3169 
3170  /* catch bound change events on slack variable and adjust nfixednonzero */
3171  if ( linconsactive )
3172  {
3173  SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlrbound, (SCIP_EVENTDATA*)*consdata, NULL) );
3174 
3175  /* if slack variable is fixed to be nonzero */
3176  if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var)) )
3177  ++((*consdata)->nfixednonzero);
3178  }
3179 
3180  /* add corresponding column to alternative LP if the constraint is new */
3181  if ( conshdlrdata->sepaalternativelp && SCIPgetStage(scip) >= SCIP_STAGE_INITSOLVE && lincons != NULL )
3182  {
3183  assert( lincons != NULL );
3184  assert( consname != NULL );
3185 
3186  SCIP_CALL( addAltLPConstraint(scip, conshdlr, lincons, var, 1.0, &(*consdata)->colindex) );
3187 
3188  SCIPdebugMsg(scip, "Added column for <%s> to alternative LP with column index %d.\n", consname, (*consdata)->colindex);
3189 #ifdef SCIP_OUTPUT
3190  SCIP_CALL( SCIPprintCons(scip, lincons, NULL) );
3191  SCIPinfoMessage(scip, NULL, ";\n");
3192 #endif
3193  }
3194 
3195 #ifdef SCIP_DEBUG
3196  if ( (*consdata)->nfixednonzero > 0 )
3197  {
3198  SCIPdebugMsg(scip, "Constraint <%s> has %d variables fixed to be nonzero.\n", consname, (*consdata)->nfixednonzero);
3199  }
3200 #endif
3201  }
3202 
3203  return SCIP_OKAY;
3204 }
3205 
3206 
3207 /** create variable upper bounds for constraints */
3208 static
3210  SCIP* scip, /**< SCIP pointer */
3211  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
3212  SCIP_CONS** conss, /**< constraints */
3213  int nconss, /**< number of constraints */
3214  int* ngen /**< number of successful operations */
3215  )
3216 {
3217  char name[50];
3218  int c;
3219 
3220  assert( scip != NULL );
3221  assert( conshdlrdata != NULL );
3222  assert( ngen != NULL );
3223 
3224  *ngen = 0;
3225 
3226  /* check each constraint */
3227  for (c = 0; c < nconss; ++c)
3228  {
3229  SCIP_CONSDATA* consdata;
3230  SCIP_Real ub;
3231 
3232  consdata = SCIPconsGetData(conss[c]);
3233  assert( consdata != NULL );
3234 
3235  ub = SCIPvarGetUbGlobal(consdata->slackvar);
3236  assert( ! SCIPisNegative(scip, ub) );
3237 
3238  /* insert corresponding row if helpful and coefficient is not too large */
3239  if ( ub <= conshdlrdata->maxcouplingvalue )
3240  {
3241  SCIP_CONS* cons;
3242 
3243 #ifndef NDEBUG
3244  (void) SCIPsnprintf(name, 50, "couple%d", c);
3245 #else
3246  name[0] = '\0';
3247 #endif
3248 
3249  SCIPdebugMsg(scip, "Insert coupling varbound constraint for indicator constraint <%s> (coeff: %f).\n", SCIPconsGetName(conss[c]), ub);
3250 
3251  /* add variable upper bound:
3252  * - check constraint if we remove the indicator constraint afterwards
3253  * - constraint is dynamic if we do not remove indicator constraints
3254  * - constraint is removable if we do not remove indicator constraints
3255  */
3256  SCIP_CALL( SCIPcreateConsVarbound(scip, &cons, name, consdata->slackvar, consdata->binvar, ub, -SCIPinfinity(scip), ub,
3257  TRUE, TRUE, TRUE, conshdlrdata->removeindicators, TRUE, FALSE, FALSE,
3258  !conshdlrdata->removeindicators, !conshdlrdata->removeindicators, FALSE) );
3259 
3260  SCIP_CALL( SCIPaddCons(scip, cons) );
3261  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
3262 
3263  /* remove indicator constraint if required */
3264  if ( conshdlrdata->removeindicators )
3265  {
3266  SCIPdebugMsg(scip, "Removing indicator constraint <%s>.\n", SCIPconsGetName(conss[c]));
3267  assert( ! SCIPconsIsModifiable(conss[c]) );
3268 
3269  /* mark linear constraint to be upgrade-able */
3270  if ( SCIPconsIsActive(consdata->lincons) )
3271  {
3272  SCIPconsAddUpgradeLocks(consdata->lincons, -1);
3273  assert( SCIPconsGetNUpgradeLocks(consdata->lincons) == 0 );
3274  }
3275 
3276  SCIP_CALL( SCIPdelCons(scip, conss[c]) );
3277  }
3278 
3279  ++(*ngen);
3280  }
3281  }
3282 
3283  return SCIP_OKAY;
3284 }
3285 
3286 
3287 /** perform one presolving round */
3288 static
3290  SCIP* scip, /**< SCIP pointer */
3291  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
3292  SCIP_CONS* cons, /**< constraint */
3293  SCIP_CONSDATA* consdata, /**< constraint data */
3294  SCIP_Bool dualreductions, /**< should dual reductions be performed? */
3295  SCIP_Bool* cutoff, /**< whether a cutoff happened */
3296  SCIP_Bool* success, /**< whether we performed a successful reduction */
3297  int* ndelconss, /**< number of deleted constraints */
3298  int* nfixedvars /**< number of fixed variables */
3299  )
3300 {
3301  SCIP_Bool infeasible;
3302  SCIP_Bool fixed;
3303 
3304  assert( scip != NULL );
3305  assert( cons != NULL );
3306  assert( consdata != NULL );
3307  assert( cutoff != NULL );
3308  assert( success != NULL );
3309  assert( ndelconss != NULL );
3310  assert( nfixedvars != NULL );
3311  assert( consdata->binvar != NULL );
3312  assert( consdata->slackvar != NULL );
3313 
3314  *cutoff = FALSE;
3315  *success = FALSE;
3316 
3317  /* if the binary variable is fixed to nonzero */
3318  if ( SCIPvarGetLbLocal(consdata->binvar) > 0.5 )
3319  {
3320  SCIPdebugMsg(scip, "Presolving <%s>: Binary variable fixed to 1.\n", SCIPconsGetName(cons));
3321 
3322  /* if slack variable is fixed to nonzero, we are infeasible */
3323  if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(consdata->slackvar)) )
3324  {
3325  SCIPdebugMsg(scip, "The problem is infeasible: binary and slack variable are fixed to be nonzero.\n");
3326  *cutoff = TRUE;
3327  return SCIP_OKAY;
3328  }
3329 
3330  /* otherwise fix slack variable to 0 */
3331  SCIPdebugMsg(scip, "Fix slack variable to 0 and delete constraint.\n");
3332  SCIP_CALL( SCIPfixVar(scip, consdata->slackvar, 0.0, &infeasible, &fixed) );
3333  assert( ! infeasible );
3334  if ( fixed )
3335  ++(*nfixedvars);
3336 
3337  /* mark linear constraint to be update-able */
3338  if ( SCIPconsIsActive(consdata->lincons) )
3339  {
3340  SCIPconsAddUpgradeLocks(consdata->lincons, -1);
3341  assert( SCIPconsGetNUpgradeLocks(consdata->lincons) == 0 );
3342  }
3343 
3344  /* delete indicator constraint (leave linear constraint) */
3345  assert( ! SCIPconsIsModifiable(cons) );
3346  SCIP_CALL( SCIPdelCons(scip, cons) );
3347  ++(*ndelconss);
3348  *success = TRUE;
3349  return SCIP_OKAY;
3350  }
3351 
3352  /* if the binary variable is fixed to zero */
3353  if ( SCIPvarGetUbLocal(consdata->binvar) < 0.5 )
3354  {
3355  SCIPdebugMsg(scip, "Presolving <%s>: Binary variable fixed to 0, deleting indicator constraint.\n", SCIPconsGetName(cons));
3356 
3357  /* mark linear constraint to be update-able */
3358  if ( SCIPconsIsActive(consdata->lincons) )
3359  {
3360  SCIPconsAddUpgradeLocks(consdata->lincons, -1);
3361  assert( SCIPconsGetNUpgradeLocks(consdata->lincons) == 0 );
3362  }
3363 
3364  /* delete indicator constraint */
3365  assert( ! SCIPconsIsModifiable(cons) );
3366  SCIP_CALL( SCIPdelCons(scip, cons) );
3367  ++(*ndelconss);
3368  *success = TRUE;
3369  return SCIP_OKAY;
3370  }
3371 
3372  /* if the slack variable is fixed to nonzero */
3373  if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(consdata->slackvar)) )
3374  {
3375  SCIPdebugMsg(scip, "Presolving <%s>: Slack variable fixed to nonzero.\n", SCIPconsGetName(cons));
3376 
3377  /* if binary variable is fixed to nonzero, we are infeasible */
3378  if ( SCIPvarGetLbLocal(consdata->binvar) > 0.5 )
3379  {
3380  SCIPdebugMsg(scip, "The problem is infeasible: binary and slack variable are fixed to be nonzero.\n");
3381  *cutoff = TRUE;
3382  return SCIP_OKAY;
3383  }
3384 
3385  /* otherwise fix binary variable to 0 */
3386  SCIPdebugMsg(scip, "Fix binary variable to 0 and delete indicator constraint.\n");
3387  SCIP_CALL( SCIPfixVar(scip, consdata->binvar, 0.0, &infeasible, &fixed) );
3388  assert( ! infeasible );
3389  if ( fixed )
3390  ++(*nfixedvars);
3391 
3392  /* mark linear constraint to be update-able */
3393  if ( SCIPconsIsActive(consdata->lincons) )
3394  {
3395  SCIPconsAddUpgradeLocks(consdata->lincons, -1);
3396  assert( SCIPconsGetNUpgradeLocks(consdata->lincons) == 0 );
3397  }
3398 
3399  /* delete constraint */
3400  assert( ! SCIPconsIsModifiable(cons) );
3401  SCIP_CALL( SCIPdelCons(scip, cons) );
3402  ++(*ndelconss);
3403  *success = TRUE;
3404  return SCIP_OKAY;
3405  }
3406 
3407  /* if the slack variable is fixed to zero */
3408  if ( SCIPisFeasZero(scip, SCIPvarGetUbLocal(consdata->slackvar)) )
3409  {
3410  /* perform dual reductions - if required */
3411  if ( dualreductions )
3412  {
3413  SCIP_VAR* binvar;
3414  SCIP_Real obj;
3415 
3416  /* check objective of binary variable */
3417  binvar = consdata->binvar;
3418  obj = varGetObjDelta(binvar);
3419 
3420  /* if obj = 0, we prefer fixing the binary variable to 1 (if possible) */
3421  if ( obj <= 0.0 )
3422  {
3423  /* In this case we would like to fix the binary variable to 1, if it is not locked up
3424  except by this indicator constraint. If more than one indicator constraint is
3425  effected, we have to hope that they are all fulfilled - in this case the last
3426  constraint will fix the binary variable to 1. */
3427  if ( SCIPvarGetNLocksUpType(binvar, SCIP_LOCKTYPE_MODEL) <= 1 )
3428  {
3429  if ( SCIPvarGetUbGlobal(binvar) > 0.5 )
3430  {
3431  SCIPdebugMsg(scip, "Presolving <%s> - dual reduction: Slack variable fixed to 0, fix binary variable to 1.\n", SCIPconsGetName(cons));
3432  SCIP_CALL( SCIPfixVar(scip, binvar, 1.0, &infeasible, &fixed) );
3433  assert( ! infeasible );
3434  if ( fixed )
3435  ++(*nfixedvars);
3436  /* make sure that the other case does not occur */
3437  obj = -1.0;
3438  }
3439  }
3440  }
3441  if ( obj >= 0.0 )
3442  {
3443  /* In this case we would like to fix the binary variable to 0, if it is not locked down
3444  (should also have been performed by other dual reductions). */
3445  if ( SCIPvarGetNLocksDownType(binvar, SCIP_LOCKTYPE_MODEL) == 0 )
3446  {
3447  if ( SCIPvarGetLbGlobal(binvar) < 0.5 )
3448  {
3449  SCIPdebugMsg(scip, "Presolving <%s> - dual reduction: Slack variable fixed to 0, fix binary variable to 0.\n", SCIPconsGetName(cons));
3450  SCIP_CALL( SCIPfixVar(scip, binvar, 0.0, &infeasible, &fixed) );
3451  assert( ! infeasible );
3452  if ( fixed )
3453  ++(*nfixedvars);
3454  }
3455  }
3456  }
3457  }
3458 
3459  SCIPdebugMsg(scip, "Presolving <%s>: Slack variable fixed to zero, delete redundant indicator constraint.\n", SCIPconsGetName(cons));
3460 
3461  /* mark linear constraint to be upgrade-able */
3462  if ( SCIPconsIsActive(consdata->lincons) )
3463  {
3464  SCIPconsAddUpgradeLocks(consdata->lincons, -1);
3465  assert( SCIPconsGetNUpgradeLocks(consdata->lincons) == 0 );
3466  }
3467 
3468  /* delete constraint */
3469  assert( ! SCIPconsIsModifiable(cons) );
3470  SCIP_CALL( SCIPdelCons(scip, cons) );
3471  ++(*ndelconss);
3472  *success = TRUE;
3473  return SCIP_OKAY;
3474  }
3475 
3476  /* check whether indicator variable is aggregated */
3477  if ( SCIPvarGetStatus(consdata->binvar) == SCIP_VARSTATUS_AGGREGATED )
3478  {
3479  SCIP_Bool negated = FALSE;
3480  SCIP_VAR* var;
3481 
3482  /* possibly get representation of indicator variable by active variable */
3483  var = consdata->binvar;
3484  SCIP_CALL( SCIPvarGetProbvarBinary(&var, &negated) );
3485  assert( var == consdata->binvar || SCIPvarIsActive(var) || SCIPvarIsNegated(var) );
3486 
3487  /* we can replace the binary variable by the active variable if it is not negated */
3488  if ( var != consdata->binvar && ! negated )
3489  {
3490  SCIPdebugMsg(scip, "Indicator variable <%s> is aggregated and replaced by active/negated variable <%s>.\n", SCIPvarGetName(consdata->binvar), SCIPvarGetName(var) );
3491 
3492  /* we need to update the events and locks */
3493  assert( conshdlrdata->eventhdlrbound != NULL );
3494  SCIP_CALL( SCIPdropVarEvent(scip, consdata->binvar, SCIP_EVENTTYPE_BOUNDCHANGED, conshdlrdata->eventhdlrbound, (SCIP_EVENTDATA*) consdata, -1) );
3495  SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_BOUNDCHANGED, conshdlrdata->eventhdlrbound, (SCIP_EVENTDATA*) consdata, NULL) );
3496 
3497  /* We also need to update the events and locks if restart is forced, since global bound change events on binary
3498  * variables are also caught in this case. If it would not be updated and forcerestart = TRUE, then an event
3499  * might be dropped on a wrong variable. */
3500  if ( conshdlrdata->forcerestart )
3501  {
3502  assert( conshdlrdata->eventhdlrrestart != NULL );
3503  SCIP_CALL( SCIPdropVarEvent(scip, consdata->binvar, SCIP_EVENTTYPE_GBDCHANGED,
3504  conshdlrdata->eventhdlrrestart, (SCIP_EVENTDATA*) conshdlrdata, -1) );
3505  SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_GBDCHANGED, conshdlrdata->eventhdlrrestart,
3506  (SCIP_EVENTDATA*) conshdlrdata, NULL) );
3507  }
3508 
3509  SCIP_CALL( SCIPaddVarLocksType(scip, consdata->binvar, SCIP_LOCKTYPE_MODEL, 0, -1) );
3510  SCIP_CALL( SCIPaddVarLocksType(scip, var, SCIP_LOCKTYPE_MODEL, 0, 1) );
3511 
3512  /* change binvary variable */
3513  consdata->binvar = var;
3514  }
3515  }
3516  else if ( SCIPvarGetStatus(consdata->binvar) == SCIP_VARSTATUS_NEGATED )
3517  {
3518  SCIP_VAR* var;
3519 
3520  var = SCIPvarGetNegatedVar(consdata->binvar);
3521  assert( var != NULL );
3522 
3523  /* if the binary variable is the negated slack variable, we have 1 - s = 1 -> s = 0, i.e., the constraint is redundant */
3524  if ( var == consdata->slackvar )
3525  {
3526  /* delete constraint */
3527  assert( ! SCIPconsIsModifiable(cons) );
3528  SCIP_CALL( SCIPdelCons(scip, cons) );
3529  ++(*ndelconss);
3530  *success = TRUE;
3531  return SCIP_OKAY;
3532  }
3533  }
3534 
3535  /* check whether slack variable is aggregated */
3536  if ( SCIPvarGetStatus(consdata->slackvar) == SCIP_VARSTATUS_AGGREGATED || SCIPvarGetStatus(consdata->slackvar) == SCIP_VARSTATUS_NEGATED )
3537  {
3539  SCIP_Real bound;
3540  SCIP_VAR* var;
3541 
3542  /* possibly get representation of slack variable by active variable */
3543  var = consdata->slackvar;
3544  bound = SCIPvarGetLbGlobal(var);
3545 
3546  SCIP_CALL( SCIPvarGetProbvarBound(&var, &bound, &boundtype) );
3547  assert( var != consdata->slackvar );
3548 
3549  /* we can replace the slack variable by the active variable if it is also a >= variable */
3550  if ( var != consdata->binvar && boundtype == SCIP_BOUNDTYPE_LOWER && SCIPisEQ(scip, bound, 0.0) )
3551  {
3552  assert( SCIPvarIsActive(var) );
3553  SCIPdebugMsg(scip, "Slack variable <%s> is aggregated or negated and replaced by active variable <%s>.\n", SCIPvarGetName(consdata->slackvar), SCIPvarGetName(var) );
3554 
3555  /* we need to update the events, locks, and captures */
3556  assert( conshdlrdata->eventhdlrbound != NULL );
3557  SCIP_CALL( SCIPdropVarEvent(scip, consdata->slackvar, SCIP_EVENTTYPE_BOUNDCHANGED, conshdlrdata->eventhdlrbound, (SCIP_EVENTDATA*) consdata, -1) );
3558  SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_BOUNDCHANGED, conshdlrdata->eventhdlrbound, (SCIP_EVENTDATA*) consdata, NULL) );
3559 
3560  SCIP_CALL( SCIPunlockVarCons(scip, consdata->slackvar, cons, FALSE, TRUE) );
3561  SCIP_CALL( SCIPlockVarCons(scip, var, cons, FALSE, TRUE) );
3562 
3563  SCIP_CALL( SCIPreleaseVar(scip, &consdata->slackvar) );
3564  SCIP_CALL( SCIPcaptureVar(scip, var) );
3565 
3566  /* change slack variable */
3567  consdata->slackvar = var;
3568  }
3569  else if ( var == consdata->binvar )
3570  {
3571  /* check special case that aggregating variable is equal to the indicator variable */
3572  assert( SCIPisEQ(scip, bound, 0.0) || SCIPisEQ(scip, bound, 1.0) );
3573 
3574  /* if the lower bound is transformed to an upper bound, we have "y = 1 -> 1 - y = 0", i.e., the constraint is redundant */
3575  if ( boundtype == SCIP_BOUNDTYPE_UPPER )
3576  {
3577  SCIPdebugMsg(scip, "Slack variable <%s> is aggregated to negated indicator variable <%s> -> constraint redundant.\n",
3578  SCIPvarGetName(consdata->slackvar), SCIPvarGetName(consdata->binvar));
3579  assert( SCIPisEQ(scip, bound, 1.0) );
3580 
3581  /* delete constraint */
3582  assert( ! SCIPconsIsModifiable(cons) );
3583  SCIP_CALL( SCIPdelCons(scip, cons) );
3584  ++(*ndelconss);
3585  *success = TRUE;
3586  return SCIP_OKAY;
3587  }
3588  else
3589  {
3590  /* if the lower bound is transformed to a lower bound, we have "y = 1 -> y = 0", i.e., we can fix the binary variable to 0 */
3591  SCIPdebugMsg(scip, "Slack variable <%s> is aggregated to the indicator variable <%s> -> fix indicator variable to 0.\n",
3592  SCIPvarGetName(consdata->slackvar), SCIPvarGetName(consdata->binvar));
3593  assert( boundtype == SCIP_BOUNDTYPE_LOWER );
3594  assert( SCIPisEQ(scip, bound, 0.0) );
3595 
3596  SCIP_CALL( SCIPfixVar(scip, consdata->binvar, 0.0, &infeasible, &fixed) );
3597  assert( ! infeasible );
3598 
3599  if ( fixed )
3600  ++(*nfixedvars);
3601 
3602  SCIP_CALL( SCIPdelCons(scip, cons) );
3603 
3604  ++(*ndelconss);
3605  *success = TRUE;
3606 
3607  return SCIP_OKAY;
3608  }
3609  }
3610  }
3611 
3612  /* Note that because of possible multi-aggregation we cannot simply remove the indicator
3613  * constraint if the linear constraint is not active or disabled - see the note in @ref
3614  * PREPROC. */
3615 
3616  return SCIP_OKAY;
3617 }
3618 
3619 
3620 /** propagate indicator constraint */
3621 static
3623  SCIP* scip, /**< SCIP pointer */
3624  SCIP_CONS* cons, /**< constraint */
3625  SCIP_CONSDATA* consdata, /**< constraint data */
3626  SCIP_Bool dualreductions, /**< should dual reductions be performed? */
3627  SCIP_Bool addopposite, /**< add opposite inequalities if binary var = 0? */
3628  SCIP_Bool* cutoff, /**< whether a cutoff happened */
3629  int* nGen /**< number of domain changes */
3630  )
3631 {
3632  SCIP_Bool infeasible;
3633  SCIP_Bool tightened;
3634 
3635  assert( scip != NULL );
3636  assert( cons != NULL );
3637  assert( consdata != NULL );
3638  assert( cutoff != NULL );
3639  assert( nGen != NULL );
3640 
3641  *cutoff = FALSE;
3642  *nGen = 0;
3643 
3644  /* if the linear constraint has not been generated, we do nothing */
3645  if ( ! consdata->linconsactive )
3646  return SCIP_OKAY;
3647 
3648  assert( consdata->slackvar != NULL );
3649  assert( consdata->binvar != NULL );
3650  assert( SCIPisFeasGE(scip, SCIPvarGetLbLocal(consdata->slackvar), 0.0) );
3651 
3652  /* if both slackvar and binvar are fixed to be nonzero */
3653  if ( consdata->nfixednonzero > 1 )
3654  {
3655  SCIPdebugMsg(scip, "The node is infeasible, both the slack variable and the binary variable are fixed to be nonzero.\n");
3656  *cutoff = TRUE;
3657 
3658  SCIP_CALL( SCIPresetConsAge(scip, cons) );
3659  assert( SCIPvarGetLbLocal(consdata->binvar) > 0.5 );
3660  assert( SCIPisPositive(scip, SCIPvarGetLbLocal(consdata->slackvar)) );
3661 
3662  /* check if conflict analysis is turned on */
3663  if ( ! SCIPisConflictAnalysisApplicable(scip) )
3664  return SCIP_OKAY;
3665 
3666  /* conflict analysis can only be applied in solving stage */
3667  assert( SCIPgetStage(scip) == SCIP_STAGE_SOLVING || SCIPinProbing(scip) );
3668 
3669  /* perform conflict analysis */
3671 
3672  SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->binvar) );
3673  SCIP_CALL( SCIPaddConflictLb(scip, consdata->slackvar, NULL) );
3674  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
3675 
3676  return SCIP_OKAY;
3677  }
3678 
3679  /* if exactly one of the variables is fixed to be nonzero */
3680  if ( consdata->nfixednonzero == 1 )
3681  {
3682  /* increase age of constraint; age is reset to zero, if a conflict or a propagation was found */
3683  if ( ! SCIPinRepropagation(scip) )
3684  SCIP_CALL( SCIPincConsAge(scip, cons) );
3685 
3686  /* if binvar is fixed to be nonzero */
3687  if ( SCIPvarGetLbLocal(consdata->binvar) > 0.5 )
3688  {
3689  assert( SCIPvarGetStatus(consdata->slackvar) != SCIP_VARSTATUS_MULTAGGR );
3690 
3691  /* if slack variable is not already fixed to 0 */
3692  if ( ! SCIPisZero(scip, SCIPvarGetUbLocal(consdata->slackvar)) )
3693  {
3694  SCIPdebugMsg(scip, "Binary variable <%s> is fixed to be nonzero, fixing slack variable <%s> to 0.\n",
3695  SCIPvarGetName(consdata->binvar), SCIPvarGetName(consdata->slackvar));
3696 
3697  /* fix slack variable to 0 */
3698  SCIP_CALL( SCIPinferVarUbCons(scip, consdata->slackvar, 0.0, cons, 0, FALSE, &infeasible, &tightened) );
3699  assert( ! infeasible );
3700  if ( tightened )
3701  ++(*nGen);
3702  }
3703  }
3704 
3705  /* if slackvar is fixed to be nonzero */
3706  if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(consdata->slackvar)) )
3707  {
3708  /* if binary variable is not yet fixed to 0 */
3709  if ( SCIPvarGetUbLocal(consdata->binvar) > 0.5 )
3710  {
3711  SCIPdebugMsg(scip, "Slack variable <%s> is fixed to be nonzero, fixing binary variable <%s> to 0.\n",
3712  SCIPvarGetName(consdata->slackvar), SCIPvarGetName(consdata->binvar));
3713 
3714  /* fix binary variable to 0 */
3715  SCIP_CALL( SCIPinferVarUbCons(scip, consdata->binvar, 0.0, cons, 1, FALSE, &infeasible, &tightened) );
3716  assert( ! infeasible );
3717  if ( tightened )
3718  ++(*nGen);
3719  }
3720  }
3721 
3722  /* reset constraint age counter */
3723  if ( *nGen > 0 )
3724  SCIP_CALL( SCIPresetConsAge(scip, cons) );
3725 
3726  /* mark linear constraint to be update-able */
3727  if ( SCIPgetDepth(scip) == 0 && SCIPconsIsActive(consdata->lincons) )
3728  {
3729  SCIPconsAddUpgradeLocks(consdata->lincons, -1);
3730  assert( SCIPconsGetNUpgradeLocks(consdata->lincons) == 0 );
3731  }
3732 
3733  /* delete constraint locally */
3734  assert( ! SCIPconsIsModifiable(cons) );
3735  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
3736  }
3737  else
3738  {
3739  /* if the binary variable is fixed to zero */
3740  if ( SCIPvarGetUbLocal(consdata->binvar) < 0.5 )
3741  {
3742  if ( addopposite && consdata->linconsactive )
3743  {
3744  char name[SCIP_MAXSTRLEN];
3745  SCIP_CONS* reversecons;
3746  SCIP_VAR** linvars;
3747  SCIP_Real* linvals;
3748  SCIP_Bool allintegral = TRUE;
3749  SCIP_VAR* slackvar;
3750  SCIP_VAR** vars;
3751  SCIP_Real* vals;
3752  SCIP_Real lhs;
3753  SCIP_Real rhs;
3754  int nlinvars;
3755  int nvars = 0;
3756  int j;
3757 
3758  /* determine lhs/rhs (first exchange lhs/rhs) */
3759  lhs = SCIPgetRhsLinear(scip, consdata->lincons);
3760  if ( SCIPisInfinity(scip, lhs) )
3761  lhs = -SCIPinfinity(scip);
3762  rhs = SCIPgetLhsLinear(scip, consdata->lincons);
3763  if ( SCIPisInfinity(scip, -rhs) )
3764  rhs = SCIPinfinity(scip);
3765 
3766  assert( ! SCIPisInfinity(scip, lhs) );
3767  assert( ! SCIPisInfinity(scip, -rhs) );
3768 
3769  /* consider only finite lhs/rhs */
3770  if ( ! SCIPisInfinity(scip, -lhs) || ! SCIPisInfinity(scip, rhs) )
3771  {
3772  /* ignore equations (cannot add opposite constraint) */
3773  if ( ! SCIPisEQ(scip, lhs, rhs) )
3774  {
3775  assert( consdata->lincons != NULL );
3776  nlinvars = SCIPgetNVarsLinear(scip, consdata->lincons);
3777  linvars = SCIPgetVarsLinear(scip, consdata->lincons);
3778  linvals = SCIPgetValsLinear(scip, consdata->lincons);
3779  slackvar = consdata->slackvar;
3780  assert( slackvar != NULL );
3781 
3782  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nlinvars) );
3783  SCIP_CALL( SCIPallocBufferArray(scip, &vals, nlinvars) );
3784 
3785  /* copy data and check whether the linear constraint is integral */
3786  for (j = 0; j < nlinvars; ++j)
3787  {
3788  if ( linvars[j] != slackvar )
3789  {
3790  if (! SCIPvarIsIntegral(linvars[j]) || ! SCIPisIntegral(scip, linvals[j]) )
3791  allintegral = FALSE;
3792 
3793  vars[nvars] = linvars[j];
3794  vals[nvars++] = linvals[j];
3795  }
3796  }
3797  assert( nlinvars == nvars + 1 );
3798 
3799  /* possibly adjust lhs/rhs */
3800  if ( allintegral && ! SCIPisInfinity(scip, REALABS(lhs)) )
3801  lhs += 1.0;
3802 
3803  if ( allintegral && ! SCIPisInfinity(scip, REALABS(rhs)) )
3804  rhs -= 1.0;
3805 
3806  /* create reverse constraint */
3807  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "reverse_%s", SCIPconsGetName(consdata->lincons));
3808 
3809  /* constraint is initial, separated, not enforced, not checked, propagated, local, not modifiable, dynamic, removable */
3810  SCIP_CALL( SCIPcreateConsLinear(scip, &reversecons, name, nvars, vars, vals, lhs, rhs,
3811  TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE, TRUE, TRUE, FALSE) );
3812 
3813  SCIPdebugMsg(scip, "Binary variable <%s> fixed to 0. Adding opposite linear inequality.\n", SCIPvarGetName(consdata->binvar));
3814  SCIPdebugPrintCons(scip, reversecons, NULL);
3815 
3816  /* add constraint */
3817  SCIP_CALL( SCIPaddCons(scip, reversecons) );
3818  SCIP_CALL( SCIPreleaseCons(scip, &reversecons) );
3819 
3820  SCIPfreeBufferArray(scip, &vals);
3821  SCIPfreeBufferArray(scip, &vars);
3822  }
3823  }
3824  }
3825 
3826  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
3827  }
3828 
3829  /* if the slack variable is fixed to zero */
3830  if ( SCIPisFeasZero(scip, SCIPvarGetUbLocal(consdata->slackvar)) )
3831  {
3832  /* perform dual reduction - if required */
3833  if ( dualreductions )
3834  {
3835  SCIP_VAR* binvar;
3836  SCIP_Real obj;
3837 
3838  /* check objective of binary variable */
3839  binvar = consdata->binvar;
3840  obj = varGetObjDelta(binvar);
3841 
3842  /* if obj = 0, we prefer setting the binary variable to 1 (if possible) */
3843  if ( obj <= 0.0 )
3844  {
3845  /* In this case we would like to fix the binary variable to 1, if it is not locked up
3846  except by this indicator constraint. If more than one indicator constraint is
3847  affected, we have to hope that they are all fulfilled - in this case the last
3848  constraint will fix the binary variable to 1. */
3849  if ( SCIPvarGetNLocksUpType(binvar, SCIP_LOCKTYPE_MODEL) <= 1 )
3850  {
3851  if ( SCIPvarGetUbLocal(binvar) > 0.5 )
3852  {
3853  SCIPdebugMsg(scip, "Propagating <%s> - dual reduction: Slack variable fixed to 0, fix binary variable to 1.\n", SCIPconsGetName(cons));
3854  SCIP_CALL( SCIPinferVarLbCons(scip, binvar, 1.0, cons, 2, FALSE, &infeasible, &tightened) );
3855  assert( ! infeasible );
3856  if ( tightened )
3857  ++(*nGen);
3858  /* Make sure that the other case does not occur, since we are not sure whether SCIPinferVarLbCons() directly changes the bounds. */
3859  obj = -1.0;
3860  }
3861  }
3862  }
3863  if ( obj >= 0.0 )
3864  {
3865  /* In this case we would like to fix the binary variable to 0, if it is not locked down
3866  (should also have been performed by other dual reductions). */
3867  if ( SCIPvarGetNLocksDownType(binvar, SCIP_LOCKTYPE_MODEL) == 0 )
3868  {
3869  if ( SCIPvarGetLbLocal(binvar) < 0.5 )
3870  {
3871  SCIPdebugMsg(scip, "Propagating <%s> - dual reduction: Slack variable fixed to 0, fix binary variable to 0.\n", SCIPconsGetName(cons));
3872  SCIP_CALL( SCIPinferVarUbCons(scip, binvar, 0.0, cons, 2, FALSE, &infeasible, &tightened) );
3873  assert( ! infeasible );
3874  if ( tightened )
3875  ++(*nGen);
3876  }
3877  }
3878  }
3879  }
3880 
3881  SCIPdebugMsg(scip, "Slack variable fixed to zero, delete redundant indicator constraint <%s>.\n", SCIPconsGetName(cons));
3882 
3883  /* delete constraint */
3884  assert( ! SCIPconsIsModifiable(cons) );
3885 
3886  /* mark linear constraint to be update-able */
3887  if ( SCIPgetDepth(scip) == 0 && SCIPconsIsActive(consdata->lincons) )
3888  {
3889  SCIPconsAddUpgradeLocks(consdata->lincons, -1);
3890  assert( SCIPconsGetNUpgradeLocks(consdata->lincons) == 0 );
3891  }
3892 
3893  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
3894  SCIP_CALL( SCIPresetConsAge(scip, cons) );
3895  ++(*nGen);
3896  }
3897 
3898  /* Note that because of possible multi-aggregation we cannot simply remove the indicator
3899  * constraint if the linear constraint is not active or disabled - see the note in @ref
3900  * PREPROC and consPresolIndicator(). Moreover, it would drastically increase memory
3901  * consumption, because the linear constraints have to be stored in each node. */
3902  }
3903 
3904  return SCIP_OKAY;
3905 }
3906 
3907 
3908 /** enforcement method that produces cuts if possible
3909  *
3910  * This is a variant of the enforcement method that generates cuts/constraints via the alternative
3911  * LP, if possible.
3912  */
3913 static
3915  SCIP* scip, /**< SCIP pointer */
3916  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
3917  int nconss, /**< number of constraints */
3918  SCIP_CONS** conss, /**< indicator constraints */
3919  SCIP_SOL* sol, /**< solution to be enforced */
3920  SCIP_Bool genlogicor, /**< whether logicor constraint should be generated */
3921  SCIP_Bool* cutoff, /**< whether we detected a cutoff by an infeasible inequality */
3922  int* nGen /**< number of cuts generated */
3923  )
3924 {
3925  SCIP_CONSHDLRDATA* conshdlrdata;
3926  SCIP_LPI* lp;
3927  SCIP_Bool* S;
3928  SCIP_Real value = 0.0;
3929  SCIP_Bool error;
3930  int size = 0;
3931  int nCuts;
3932  int j;
3933 
3934  assert( scip != NULL );
3935  assert( conshdlr != NULL );
3936  assert( conss != NULL );
3937  assert( cutoff != NULL );
3938  assert( nGen != NULL );
3939 
3940  SCIPdebugMsg(scip, "Enforcing via cuts ...\n");
3941  *cutoff = FALSE;
3942  *nGen = 0;
3943 
3944  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3945  assert( conshdlrdata != NULL );
3946  lp = conshdlrdata->altlp;
3947  assert( lp != NULL );
3948 
3949 #ifndef NDEBUG
3950  SCIP_CALL( checkLPBoundsClean(scip, lp, nconss, conss) );
3951 #endif
3952 
3953  /* change coefficients of bounds in alternative LP */
3954  if ( conshdlrdata->updatebounds )
3955  SCIP_CALL( updateFirstRowGlobal(scip, conshdlrdata) );
3956 
3957  /* possibly update upper bound */
3958  SCIP_CALL( updateObjUpperbound(scip, conshdlr, conshdlrdata) );
3959 
3960  /* scale first row if necessary */
3961  SCIP_CALL( scaleFirstRow(scip, conshdlrdata) );
3962 
3963  /* set objective function to current solution */
3964  SCIP_CALL( setAltLPObjZero(scip, lp, nconss, conss) );
3965 
3966  SCIP_CALL( SCIPallocBufferArray(scip, &S, nconss) );
3967 
3968  /* set up variables fixed to 1 */
3969  for (j = 0; j < nconss; ++j)
3970  {
3971  SCIP_CONSDATA* consdata;
3972 
3973  assert( conss[j] != NULL );
3974  consdata = SCIPconsGetData(conss[j]);
3975  assert( consdata != NULL );
3976 
3977  assert( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, consdata->binvar)) );
3978  if ( SCIPisFeasZero(scip, SCIPgetSolVal(scip, sol, consdata->binvar)) )
3979  {
3980  ++size;
3981  value += varGetObjDelta(consdata->binvar);
3982  S[j] = TRUE;
3983  }
3984  else
3985  S[j] = FALSE;
3986  }
3987 
3988  /* fix the variables in S */
3989  SCIP_CALL( fixAltLPVariables(scip, lp, nconss, conss, S) );
3990 
3991  /* extend set S to a cover and generate cuts */
3992  error = FALSE;
3993  SCIP_CALL( extendToCover(scip, conshdlr, conshdlrdata, lp, sol, conshdlrdata->removable, genlogicor, nconss, conss, S, &size, &value, &error, cutoff, &nCuts) );
3994  *nGen = nCuts;
3995 
3996  /* return with an error if no cuts have been produced and and error occurred in extendToCover() */
3997  if ( nCuts == 0 && error )
3998  return SCIP_LPERROR;
3999 
4000  SCIPdebugMsg(scip, "Generated %d IIS-cuts.\n", nCuts);
4001 
4002  /* reset bounds */
4003  SCIP_CALL( unfixAltLPVariables(scip, lp, nconss, conss, S) );
4004 
4005 #ifndef NDEBUG
4006  SCIP_CALL( checkLPBoundsClean(scip, lp, nconss, conss) );
4007 #endif
4008 
4009  SCIPfreeBufferArray(scip, &S);
4010 
4011  return SCIP_OKAY;
4012 }
4013 
4014 
4015 /** enforcement method
4016  *
4017  * We check whether the current solution is feasible, i.e., if binvar = 1
4018  * implies that slackvar = 0. If not, we branch as follows:
4019  *
4020  * In one branch we fix binvar = 1 and slackvar = 0. In the other branch
4021  * we fix binvar = 0 and leave slackvar unchanged.
4022  */
4023 static
4025  SCIP* scip, /**< SCIP pointer */
4026  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
4027  int nconss, /**< number of constraints */
4028  SCIP_CONS** conss, /**< indicator constraints */
4029  SCIP_SOL* sol, /**< solution to be enforced (NULL for LP solution) */
4030  SCIP_Bool genlogicor, /**< whether logicor constraint should be generated */
4031  SCIP_RESULT* result /**< result */
4032  )
4033 {
4034  SCIP_CONSDATA* consdata;
4035  SCIP_CONSHDLRDATA* conshdlrdata;
4036  SCIP_NODE* node1;
4037  SCIP_NODE* node2;
4038  SCIP_VAR* slackvar;
4039  SCIP_VAR* binvar;
4041  SCIP_Real maxSlack = -1.0;
4042  SCIP_Bool someLinconsNotActive = FALSE;
4043  int c;
4044 
4045  assert( scip != NULL );
4046  assert( conshdlr != NULL );
4047  assert( conss != NULL );
4048  assert( result != NULL );
4049 
4050  *result = SCIP_FEASIBLE;
4051 
4052  SCIPdebugMsg(scip, "Enforcing indicator constraints for <%s> ...\n", SCIPconshdlrGetName(conshdlr) );
4053 
4054  /* get constraint handler data */
4055  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4056  assert( conshdlrdata != NULL );
4057 
4058 #ifdef SCIP_OUTPUT
4059  SCIP_CALL( SCIPwriteTransProblem(scip, "ind.cip", "cip", FALSE) );
4060 #endif
4061 
4062  /* check each constraint */
4063  for (c = 0; c < nconss; ++c)
4064  {
4065  SCIP_Bool cutoff;
4066  SCIP_Real valSlack;
4067  int cnt;
4068 
4069  assert( conss[c] != NULL );
4070  consdata = SCIPconsGetData(conss[c]);
4071  assert( consdata != NULL );
4072  assert( consdata->lincons != NULL );
4073 
4074  /* if the linear constraint has not been generated, we do nothing */
4075  if ( ! consdata->linconsactive )
4076  {
4077  someLinconsNotActive = TRUE;
4078  continue;
4079  }
4080 
4081  /* first perform propagation (it might happen that standard propagation is turned off) */
4082  SCIP_CALL( propIndicator(scip, conss[c], consdata,
4083  conshdlrdata->dualreductions && SCIPallowStrongDualReds(scip), conshdlrdata->addopposite,
4084  &cutoff, &cnt) );
4085  if ( cutoff )
4086  {
4087  SCIPdebugMsg(scip, "Propagation in enforcing <%s> detected cutoff.\n", SCIPconsGetName(conss[c]));
4088  *result = SCIP_CUTOFF;
4089  return SCIP_OKAY;
4090  }
4091  if ( cnt > 0 )
4092  {
4093  SCIPdebugMsg(scip, "Propagation in enforcing <%s> reduced domains: %d.\n", SCIPconsGetName(conss[c]), cnt);
4094  *result = SCIP_REDUCEDDOM;
4095  return SCIP_OKAY;
4096  }
4097 
4098  /* check whether constraint is infeasible */
4099  binvar = consdata->binvar;
4100  valSlack = SCIPgetSolVal(scip, sol, consdata->slackvar);
4101  assert( ! SCIPisFeasNegative(scip, valSlack) );
4102  if ( ! SCIPisFeasZero(scip, SCIPgetSolVal(scip, sol, binvar)) && ! SCIPisFeasZero(scip, valSlack) )
4103  {
4104  /* binary variable is not fixed - otherwise we would not be infeasible */
4105  assert( SCIPvarGetLbLocal(binvar) < 0.5 && SCIPvarGetUbLocal(binvar) > 0.5 );
4106 
4107  if ( valSlack > maxSlack )
4108  {
4109  maxSlack = valSlack;
4110  branchCons = conss[c];
4111 #ifdef SCIP_OUTPUT
4112  SCIPinfoMessage(scip, NULL, "Violated indicator constraint:\n");
4113  SCIP_CALL( SCIPprintCons(scip, conss[c], NULL) );
4114  SCIPinfoMessage(scip, NULL, ";\n");
4115  SCIPinfoMessage(scip, NULL, "Corresponding linear constraint:\n");
4116  SCIP_CALL( SCIPprintCons(scip, consdata->lincons, NULL) );
4117  SCIPinfoMessage(scip, NULL, ";\n");
4118 #endif
4119  }
4120  }
4121  }
4122 
4123  /* if some constraint has a linear constraint that is not active, we need to check feasibility via the alternative polyhedron */
4124  if ( (someLinconsNotActive || conshdlrdata->enforcecuts) && conshdlrdata->sepaalternativelp )
4125  {
4126  SCIP_Bool cutoff;
4127  int ngen;
4128 
4129  SCIP_CALL( enforceCuts(scip, conshdlr, nconss, conss, sol, genlogicor, &cutoff, &ngen) );
4130  if ( cutoff )
4131  {
4132  conshdlrdata->niiscutsgen += ngen;
4133  *result = SCIP_CUTOFF;
4134  return SCIP_OKAY;
4135  }
4136 
4137  if ( ngen > 0 )
4138  {
4139  conshdlrdata->niiscutsgen += ngen;
4140  if ( genlogicor )
4141  {
4142  SCIPdebugMsg(scip, "Generated %d constraints.\n", ngen);
4143  *result = SCIP_CONSADDED;
4144  }
4145  else
4146  {
4147  SCIPdebugMsg(scip, "Generated %d cuts.\n", ngen);
4148  *result = SCIP_SEPARATED;
4149  }
4150  return SCIP_OKAY;
4151  }
4152  SCIPdebugMsg(scip, "Enforcing produced no cuts.\n");
4153 
4154  assert( ! someLinconsNotActive || branchCons == NULL );
4155  }
4156 
4157  /* if all constraints are feasible */
4158  if ( branchCons == NULL )
4159  {
4160  SCIPdebugMsg(scip, "All indicator constraints are feasible.\n");
4161  return SCIP_OKAY;
4162  }
4163 
4164  /* skip branching if required */
4165  if ( ! conshdlrdata->branchindicators )
4166  {
4167  *result = SCIP_INFEASIBLE;
4168  return SCIP_OKAY;
4169  }
4170 
4171  /* otherwise create branches */
4172  SCIPdebugMsg(scip, "Branching on constraint <%s> (slack value: %f).\n", SCIPconsGetName(branchCons), maxSlack);
4173  consdata = SCIPconsGetData(branchCons);
4174  assert( consdata != NULL );
4175  binvar = consdata->binvar;
4176  slackvar = consdata->slackvar;
4177 
4178  /* node1: binvar = 1, slackvar = 0 */
4179  SCIP_CALL( SCIPcreateChild(scip, &node1, 0.0, SCIPcalcChildEstimate(scip, binvar, 1.0) ) );
4180 
4181  if ( SCIPvarGetLbLocal(binvar) < 0.5 )
4182  {
4183  SCIP_CALL( SCIPchgVarLbNode(scip, node1, binvar, 1.0) );
4184  }
4185 
4186  /* if slack-variable is multi-aggregated */
4187  assert( SCIPvarGetStatus(slackvar) != SCIP_VARSTATUS_MULTAGGR );
4188  if ( ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(slackvar)) )
4189  {
4190  SCIP_CALL( SCIPchgVarUbNode(scip, node1, slackvar, 0.0) );
4191  }
4192 
4193  /* node2: binvar = 0, no restriction on slackvar */
4194  SCIP_CALL( SCIPcreateChild(scip, &node2, 0.0, SCIPcalcChildEstimate(scip, binvar, 0.0) ) );
4195 
4196  if ( SCIPvarGetUbLocal(binvar) > 0.5 )
4197  {
4198  SCIP_CALL( SCIPchgVarUbNode(scip, node2, binvar, 0.0) );
4199  }
4200 
4201  SCIP_CALL( SCIPresetConsAge(scip, branchCons) );
4202  *result = SCIP_BRANCHED;
4203 
4204  return SCIP_OKAY;
4205 }
4206 
4207 
4208 /** separate IIS-cuts via rounding
4209  *
4210  * @todo Check whether the cover produced at the end is a feasible solution.
4211  */
4212 static
4214  SCIP* scip, /**< SCIP pointer */
4215  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
4216  SCIP_SOL* sol, /**< solution to be separated */
4217  int nconss, /**< number of constraints */
4218  SCIP_CONS** conss, /**< indicator constraints */
4219  int maxsepacuts, /**< maximal number of cuts to be generated */
4220  SCIP_Bool* cutoff, /**< whether we detected a cutoff by an infeasible inequality */
4221  int* nGen /**< number of domain changes */
4222  )
4223 { /*lint --e{850}*/
4224  SCIP_CONSHDLRDATA* conshdlrdata;
4225  SCIP_LPI* lp;
4226  int rounds;
4227  SCIP_Real threshold;
4228  SCIP_Bool* S;
4229  SCIP_Bool error;
4230  int oldsize = -1;
4231  SCIPdebug( int nGenOld = *nGen; )
4232 
4233  assert( scip != NULL );
4234  assert( conshdlr != NULL );
4235  assert( conss != NULL );
4236  assert( cutoff != NULL );
4237  assert( nGen != NULL );
4238 
4239  if ( *nGen >= maxsepacuts )
4240  return SCIP_OKAY;
4241 
4242  *cutoff = FALSE;
4243  rounds = 0;
4244 
4245  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4246  assert( conshdlrdata != NULL );
4247  lp = conshdlrdata->altlp;
4248  assert( lp != NULL );
4249 
4250  SCIPdebugMsg(scip, "Separating IIS-cuts by rounding ...\n");
4251 
4252 #ifndef NDEBUG
4253  SCIP_CALL( checkLPBoundsClean(scip, lp, nconss, conss) );
4254 #endif
4255 
4256  /* change coefficients of bounds in alternative LP */
4257  if ( conshdlrdata->updatebounds )
4258  {
4259  /* update to local bounds */
4260  SCIP_CALL( updateFirstRow(scip, conshdlrdata) );
4261  }
4262 
4263  /* possibly update upper bound */
4264  SCIP_CALL( updateObjUpperbound(scip, conshdlr, conshdlrdata) );
4265 
4266  /* scale first row if necessary */
4267  SCIP_CALL( scaleFirstRow(scip, conshdlrdata) );
4268 
4269  /* set objective function to current solution */
4270  SCIP_CALL( setAltLPObj(scip, lp, sol, nconss, conss) );
4271 
4272  SCIP_CALL( SCIPallocBufferArray(scip, &S, nconss) );
4273 
4274  /* loop through the possible thresholds */
4275  for (threshold = conshdlrdata->roundingmaxthres;
4276  rounds < conshdlrdata->maxroundingrounds && threshold >= conshdlrdata->roundingminthres && *nGen < maxsepacuts && ! (*cutoff);
4277  threshold -= conshdlrdata->roundingoffset )
4278  {
4279  SCIP_Real value = 0.0;
4280  int size = 0;
4281  int nCuts = 0;
4282  int j;
4283 #ifdef SCIP_DEBUG
4284  int nvarsone = 0;
4285  int nvarszero = 0;
4286  int nvarsfrac = 0;
4287 #endif
4288 
4289  SCIPdebugMsg(scip, "Threshold: %g.\n", threshold);
4290 
4291  /* choose variables that have a value < current threshold value */
4292  for (j = 0; j < nconss; ++j)
4293  {
4294  SCIP_CONSDATA* consdata;
4295  SCIP_Real binvarval;
4296  SCIP_VAR* binvarneg;
4297 
4298  assert( conss[j] != NULL );
4299  consdata = SCIPconsGetData(conss[j]);
4300  assert( consdata != NULL );
4301 
4302  binvarval = SCIPgetVarSol(scip, consdata->binvar);
4303 
4304 #ifdef SCIP_DEBUG
4305  if ( SCIPisFeasEQ(scip, binvarval, 1.0) )
4306  ++nvarsone;
4307  else if ( SCIPisFeasZero(scip, binvarval) )
4308  ++nvarszero;
4309  else
4310  ++nvarsfrac;
4311 #endif
4312 
4313  /* check whether complementary (negated) variable is present as well */
4314  binvarneg = SCIPvarGetNegatedVar(consdata->binvar);
4315  assert( binvarneg != NULL );
4316 
4317  /* negated variable is present as well */
4318  assert( conshdlrdata->binvarhash != NULL );
4319  if ( SCIPhashmapExists(conshdlrdata->binvarhash, (void*) binvarneg) )
4320  {
4321  SCIP_Real binvarnegval = SCIPgetVarSol(scip, binvarneg);
4322 
4323  /* take larger one */
4324  if ( binvarval > binvarnegval )
4325  S[j] = TRUE;
4326  else
4327  S[j] = FALSE;
4328  continue;
4329  }
4330 
4331  /* check for threshold */
4332  if ( SCIPisFeasLT(scip, SCIPgetVarSol(scip, consdata->binvar), threshold) )
4333  {
4334  S[j] = TRUE;
4335  value += varGetObjDelta(consdata->binvar);
4336  ++size;
4337  }
4338  else
4339  S[j] = FALSE;
4340  }
4341 
4342  if ( size == nconss )
4343  {
4344  SCIPdebugMsg(scip, "All variables in the set. Continue ...\n");
4345  continue;
4346  }
4347 
4348  /* skip computation if size has not changed (computation is likely the same) */
4349  if ( size == oldsize )
4350  {
4351  SCIPdebugMsg(scip, "Skipping computation: size support has not changed.\n");
4352  continue;
4353  }
4354  oldsize = size;
4355 
4356 #ifdef SCIP_DEBUG
4357  SCIPdebugMsg(scip, " Vars with value 1: %d 0: %d and fractional: %d.\n", nvarsone, nvarszero, nvarsfrac);
4358 #endif
4359 
4360  /* fix the variables in S */
4361  SCIP_CALL( fixAltLPVariables(scip, lp, nconss, conss, S) );
4362 
4363  /* extend set S to a cover and generate cuts */
4364  SCIP_CALL( extendToCover(scip, conshdlr, conshdlrdata, lp, sol, conshdlrdata->removable, conshdlrdata->genlogicor, nconss, conss, S, &size, &value, &error, cutoff, &nCuts) );
4365 
4366  /* we ignore errors in extendToCover */
4367  if ( nCuts > 0 )
4368  {
4369  *nGen += nCuts;
4370  ++rounds;
4371  }
4372  else
4373  {
4374  /* possibly update upper bound */
4375  SCIP_CALL( updateObjUpperbound(scip, conshdlr, conshdlrdata) );
4376  }
4377 
4378  /* reset bounds */
4379  SCIP_CALL( unfixAltLPVariables(scip, lp, nconss, conss, S) );
4380  }
4381  SCIPdebug( SCIPdebugMsg(scip, "Generated %d IISs.\n", *nGen - nGenOld); )
4382 
4383 #ifndef NDEBUG
4384  SCIP_CALL( checkLPBoundsClean(scip, lp, nconss, conss) );
4385 #endif
4386 
4387  SCIPfreeBufferArray(scip, &S);
4388 
4389  return SCIP_OKAY;
4390 }
4391 
4392 
4393 
4394 /** separate cuts based on perspective formulation
4395  *
4396  * Hijazi, Bonami, and Ouorou (2014) introduced the following cuts: We consider an indicator constraint
4397  * \f[
4398  * y = 1 \rightarrow \alpha^T x \leq \beta
4399  * \f]
4400  * and assume finite bounds \f$\ell \leq x \leq u\f$. Then for \f$I \subseteq \{1, \dots, n\}\f$ define
4401  * \f[
4402  * \Sigma(I,x,y) = \sum_{i \notin I} \alpha_i x_i +
4403  * y \Big(\sum_{i \in I, \alpha_i < 0} \alpha_i u_i + \sum_{i \in I, \alpha_i > 0} \alpha_i \ell_i +
4404  * \sum_{i \notin I, \alpha_i < 0} \alpha_i \ell_i + \sum_{i \notin I, \alpha_i > 0} \alpha_i u_i - \beta\Big).
4405  * \f]
4406  * Then the cuts
4407  * \f[
4408  * \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
4409  * \f]
4410  * are valid for the disjunction
4411  * \f[
4412  * \{y = 0,\; \ell \leq x \leq u\} \cup \{y = 1,\; \ell \leq x \leq u,\; \alpha^T x \leq \beta\}.
4413  * \f]
4414  * These cuts can easily be separated for a given point \f$(x^*, y^*)\f$ by checking for each \f$i \in \{1, \dots, n\}\f$ whether
4415  * \f[
4416  * y^*(\alpha_i\, u_i\, [\alpha_i < 0] + \alpha_i\, \ell_i\, [\alpha_i > 0]) >
4417  * \alpha_i x_i^* + y^* )\alpha_i \ell_i [\alpha_i < 0] + \alpha_i u_i [\alpha_i > 0]),
4418  * \f]
4419  * where \f$[C] = 1\f$ if condition \f$C\f$ is satisfied, otherwise it is 0.
4420  * If the above inequality holds, \f$i\f$ is included in \f$I\f$, otherwise not.
4421  */
4422 static
4424  SCIP* scip, /**< SCIP pointer */
4425  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
4426  SCIP_SOL* sol, /**< solution to be separated */
4427  int nconss, /**< number of constraints */
4428  SCIP_CONS** conss, /**< indicator constraints */
4429  int maxsepacuts, /**< maximal number of cuts to be generated */
4430  int* nGen /**< number of generated cuts */
4431  )
4432 { /*lint --e{850}*/
4433  SCIP_CONSHDLRDATA* conshdlrdata;
4434  SCIP_VAR** cutvars;
4435  SCIP_Real* cutvals;
4436  int nvars;
4437  int c;
4438 
4439  assert( scip != NULL );
4440  assert( conshdlr != NULL );
4441  assert( conss != NULL );
4442  assert( nGen != NULL );
4443 
4444  if ( *nGen >= maxsepacuts )
4445  return SCIP_OKAY;
4446 
4447  nvars = SCIPgetNVars(scip);
4448  SCIP_CALL( SCIPallocBufferArray(scip, &cutvars, nvars+1) );
4449  SCIP_CALL( SCIPallocBufferArray(scip, &cutvals, nvars+1) );
4450 
4451  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4452  assert( conshdlrdata != NULL );
4453 
4454  /* loop through constraints */
4455  for (c = 0; c < nconss; ++c)
4456  {
4457  SCIP_CONSDATA* consdata;
4458  SCIP_CONS* lincons;
4459  SCIP_VAR* slackvar;
4460  SCIP_VAR* binvar;
4461  SCIP_Real binval;
4462 
4463  assert( conss[c] != NULL );
4464  consdata = SCIPconsGetData(conss[c]);
4465  assert( consdata != NULL );
4466  slackvar = consdata->slackvar;
4467 
4468  lincons = consdata->lincons;
4469  assert( lincons != NULL );
4470 
4471  binvar = consdata->binvar;
4472  assert( binvar != NULL );
4473  binval = SCIPgetSolVal(scip, sol, binvar);
4474 
4475  if ( SCIPconsIsActive(lincons) )
4476  {
4477  SCIP_VAR** linvars;
4478  SCIP_Real* linvals;
4479  SCIP_Real linrhs;
4480  SCIP_Bool finitebound = TRUE;
4481  SCIP_Real cutrhs = 0.0;
4482  SCIP_Real cutval;
4483  SCIP_Real signfactor = 1.0;
4484  SCIP_Real ypart;
4485  SCIP_Bool islocal = FALSE;
4486  int nlinvars;
4487  int cnt = 0;
4488  int j;
4489 
4490  linvars = SCIPgetVarsLinear(scip, lincons);
4491  linvals = SCIPgetValsLinear(scip, lincons);
4492  nlinvars = SCIPgetNVarsLinear(scip, lincons);
4493 
4494  linrhs = SCIPgetRhsLinear(scip, lincons);
4495  if ( SCIPisInfinity(scip, linrhs) )
4496  {
4497  if ( ! SCIPisInfinity(scip, SCIPgetLhsLinear(scip, lincons)) )
4498  {
4499  linrhs = -SCIPgetLhsLinear(scip, lincons);
4500  signfactor = -1.0;
4501  }
4502  else
4503  continue;
4504  }
4505  ypart = -linrhs;
4506  cutval = binval * ypart;
4507 
4508  for (j = 0; j < nlinvars; ++j)
4509  {
4510  SCIP_Real linval;
4511  SCIP_Real lb;
4512  SCIP_Real ub;
4513  SCIP_Real din = 0.0;
4514  SCIP_Real dout = 0.0;
4515  SCIP_Real xpart;
4516  SCIP_Real xval;
4517 
4518  if ( linvars[j] == slackvar )
4519  continue;
4520 
4521  if ( conshdlrdata->sepapersplocal )
4522  {
4523  lb = SCIPvarGetLbLocal(linvars[j]);
4524  ub = SCIPvarGetUbLocal(linvars[j]);
4525 
4526  if ( lb > SCIPvarGetLbGlobal(linvars[j]) )
4527  islocal = TRUE;
4528  if ( ub < SCIPvarGetUbGlobal(linvars[j]) )
4529  islocal = TRUE;
4530  }
4531  else
4532  {
4533  lb = SCIPvarGetLbGlobal(linvars[j]);
4534  ub = SCIPvarGetUbGlobal(linvars[j]);
4535  }
4536 
4537  /* skip cases with unbounded variables */
4538  if ( SCIPisInfinity(scip, -lb) || SCIPisInfinity(scip, ub) )
4539  {
4540  finitebound = FALSE;
4541  break;
4542  }
4543 
4544  /* compute rest parts for i in the set (din) or not in the set (dout) */
4545  linval = signfactor * linvals[j];
4546  if ( SCIPisNegative(scip, linval) )
4547  {
4548  din += linval * ub;
4549  dout += linval * lb;
4550  }
4551  else if ( SCIPisPositive(scip, linval) )
4552  {
4553  din += linval * lb;
4554  dout += linval * ub;
4555  }
4556 
4557  xval = SCIPgetSolVal(scip, sol, linvars[j]);
4558  xpart = linval * xval;
4559 
4560  /* if din > dout, we want to include i in the set */
4561  if ( SCIPisGT(scip, binval * din, binval * dout + xpart) )
4562  {
4563  ypart += din;
4564  cutval += binval * din;
4565  }
4566  else
4567  {
4568  /* otherwise i is not in the set */
4569  ypart += dout;
4570 
4571  cutrhs += dout;
4572  cutval += binval * dout + xpart;
4573 
4574  cutvars[cnt] = linvars[j];
4575  cutvals[cnt++] = linval;
4576  }
4577  }
4578 
4579  if ( ! finitebound )
4580  continue;
4581 
4582  if ( SCIPisEfficacious(scip, cutval - cutrhs) )
4583  {
4584  SCIP_ROW* row;
4585  SCIP_Bool infeasible;
4586  char name[50];
4587 
4588  /* add y-variable */
4589  cutvars[cnt] = binvar;
4590  cutvals[cnt] = ypart;
4591  ++cnt;
4592 
4593  SCIPdebugMsg(scip, "Found cut of lhs value %f > %f.\n", cutval, cutrhs);
4594  (void) SCIPsnprintf(name, 50, "persp%d", conshdlrdata->nperspcutsgen + *nGen);
4595  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, conss[c], name, -SCIPinfinity(scip), cutrhs, islocal, FALSE, conshdlrdata->removable) );
4596  SCIP_CALL( SCIPaddVarsToRow(scip, row, cnt, cutvars, cutvals) );
4597 #ifdef SCIP_OUTPUT
4598  SCIP_CALL( SCIPprintRow(scip, row, NULL) );
4599 #endif
4600  SCIP_CALL( SCIPaddRow(scip, row, FALSE, &infeasible) );
4601  assert( ! infeasible );
4602  SCIP_CALL( SCIPreleaseRow(scip, &row));
4603  SCIP_CALL( SCIPresetConsAge(scip, conss[c]) );
4604  ++(*nGen);
4605  }
4606  }
4607  if ( *nGen >= maxsepacuts )
4608  break;
4609  }
4610 
4611  SCIPfreeBufferArray(scip, &cutvals);
4612  SCIPfreeBufferArray(scip, &cutvars);
4613 
4614  return SCIP_OKAY;
4615 }
4616 
4617 
4618 /** separation method
4619  *
4620  * We first check whether coupling inequalities can be separated (if required). If not enough of
4621  * these could be generated, we check whether IIS inequalities can be separated.
4622  */
4623 static
4625  SCIP* scip, /**< SCIP pointer */
4626  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
4627  int nconss, /**< number of constraints */
4628  int nusefulconss, /**< number of useful constraints */
4629  SCIP_CONS** conss, /**< indicator constraints */
4630  SCIP_SOL* sol, /**< solution to be separated */
4631  SCIP_RESULT* result /**< result */
4632  )
4633 {
4634  SCIP_CONSHDLRDATA* conshdlrdata;
4635  int maxsepacuts;
4636  int ncuts;
4637 
4638  assert( scip != NULL );
4639  assert( conshdlr != NULL );
4640  assert( conss != NULL );
4641  assert( result != NULL );
4642 
4643  *result = SCIP_DIDNOTRUN;
4644 
4645  if ( nconss == 0 )
4646  return SCIP_OKAY;
4647 
4648  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4649  assert( conshdlrdata != NULL );
4650  ncuts = 0;
4651 
4652  /* get the maximal number of cuts allowed in a separation round */
4653  if ( SCIPgetDepth(scip) == 0 )
4654  maxsepacuts = conshdlrdata->maxsepacutsroot;
4655  else
4656  maxsepacuts = conshdlrdata->maxsepacuts;
4657 
4658  /* first separate coupling inequalities (if required) */
4659  if ( conshdlrdata->sepacouplingcuts )
4660  {
4661  int c;
4662 
4663  *result = SCIP_DIDNOTFIND;
4664 
4665  /* check each constraint */
4666  for (c = 0; c < nusefulconss && ncuts < maxsepacuts; ++c)
4667  {
4668  SCIP_CONSDATA* consdata;
4669  SCIP_Bool islocal;
4670  SCIP_Real ub;
4671 
4672  assert( conss != NULL );
4673  assert( conss[c] != NULL );
4674  consdata = SCIPconsGetData(conss[c]);
4675  assert( consdata != NULL );
4676  assert( consdata->slackvar != NULL );
4677  assert( consdata->binvar != NULL );
4678 
4679  /* get upper bound for slack variable in linear constraint */
4680  islocal = FALSE;
4681  if ( conshdlrdata->sepacouplinglocal )
4682  {
4683  ub = SCIPvarGetUbLocal(consdata->slackvar);
4684  if ( ub < SCIPvarGetUbGlobal(consdata->slackvar) )
4685  islocal = TRUE;
4686  }
4687  else
4688  ub = SCIPvarGetUbGlobal(consdata->slackvar);
4689  assert( ! SCIPisFeasNegative(scip, ub) );
4690 
4691  /* only use coefficients that are not too large */
4692  if ( ub <= conshdlrdata->sepacouplingvalue )
4693  {
4694  SCIP_Real activity;
4695 
4696  activity = SCIPgetSolVal(scip, sol, consdata->slackvar) + ub * SCIPgetSolVal(scip, sol, consdata->binvar) - ub;
4697  if ( SCIPisEfficacious(scip, activity) )
4698  {
4699  SCIP_ROW* row;
4700  SCIP_Bool infeasible;
4701 #ifndef NDEBUG
4702  char name[50];
4703 
4704  (void) SCIPsnprintf(name, 50, "couple%d", c);
4705  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, conss[c], name, -SCIPinfinity(scip), ub, islocal, FALSE, conshdlrdata->removable) );
4706 #else
4707  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, conss[c], "", -SCIPinfinity(scip), ub, islocal, FALSE, conshdlrdata->removable) );
4708 #endif
4709  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
4710 
4711  SCIP_CALL( SCIPaddVarToRow(scip, row, consdata->slackvar, 1.0) );
4712  SCIP_CALL( SCIPaddVarToRow(scip, row, consdata->binvar, ub) );
4713  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
4714 
4715  SCIPdebugMsg(scip, "Separated coupling inequality for indicator constraint <%s> (coeff: %f).\n", SCIPconsGetName(conss[c]), ub);
4716 #ifdef SCIP_OUTPUT
4717  SCIP_CALL( SCIPprintRow(scip, row, NULL) );
4718 #endif
4719  SCIP_CALL( SCIPaddRow(scip, row, FALSE, &infeasible) );
4720  assert( ! infeasible );
4721  SCIP_CALL( SCIPreleaseRow(scip, &row));
4722 
4723  SCIP_CALL( SCIPresetConsAge(scip, conss[c]) );
4724  *result = SCIP_SEPARATED;
4725 
4726  ++ncuts;
4727  }
4728  }
4729  }
4730  SCIPdebugMsg(scip, "Number of separated coupling inequalities: %d.\n", ncuts);
4731  }
4732 
4733  /* separate cuts from the alternative lp (if required) */
4734  if ( conshdlrdata->sepaalternativelp && ncuts < SEPAALTTHRESHOLD )
4735  {
4736  SCIP_Bool cutoff;
4737  int noldcuts;
4738 
4739  SCIPdebugMsg(scip, "Separating inequalities for indicator constraints.\n");
4740 
4741  noldcuts = ncuts;
4742  if ( *result == SCIP_DIDNOTRUN )
4743  *result = SCIP_DIDNOTFIND;
4744 
4745  /* start separation */
4746  SCIP_CALL( separateIISRounding(scip, conshdlr, sol, nconss, conss, maxsepacuts, &cutoff, &ncuts) );
4747  SCIPdebugMsg(scip, "Separated %d cuts from indicator constraints.\n", ncuts - noldcuts);
4748 
4749  if ( cutoff )
4750  *result = SCIP_CUTOFF;
4751  else if ( ncuts > noldcuts )
4752  {
4753  conshdlrdata->niiscutsgen += ncuts;
4754 
4755  /* possibly overwrite result from separation above */
4756  if ( conshdlrdata->genlogicor )
4757  *result = SCIP_CONSADDED;
4758  else
4759  *result = SCIP_SEPARATED;
4760  }
4761  }
4762 
4763  /* separate cuts based on perspective formulation */
4764  if ( conshdlrdata->sepaperspective && ncuts < SEPAALTTHRESHOLD )
4765  {
4766  int noldcuts;
4767 
4768  SCIPdebugMsg(scip, "Separating inequalities based on perspective formulation.\n");
4769 
4770  noldcuts = ncuts;
4771  if ( *result == SCIP_DIDNOTRUN )
4772  *result = SCIP_DIDNOTFIND;
4773 
4774  /* start separation */
4775  SCIP_CALL( separatePerspective(scip, conshdlr, sol, nconss, conss, maxsepacuts, &ncuts) );
4776  SCIPdebugMsg(scip, "Separated %d cuts from perspective formulation.\n", ncuts - noldcuts);
4777 
4778  if ( ncuts > noldcuts )
4779  {
4780  conshdlrdata->nperspcutsgen += ncuts;
4781 
4782  /* possibly overwrite result from separation above */
4783  *result = SCIP_SEPARATED;
4784  }
4785  }
4786 
4787  return SCIP_OKAY;
4788 }
4789 
4790 
4791 /** initializes the constraint handler data */
4792 static
4793 void initConshdlrData(
4794  SCIP* scip, /**< SCIP pointer */
4795  SCIP_CONSHDLRDATA* conshdlrdata /**< constraint handler data */
4796  )
4797 {
4798  assert( conshdlrdata != NULL );
4799 
4800  conshdlrdata->removable = TRUE;
4801  conshdlrdata->scaled = FALSE;
4802  conshdlrdata->altlp = NULL;
4803  conshdlrdata->nrows = 0;
4804  conshdlrdata->varhash = NULL;
4805  conshdlrdata->slackhash = NULL;
4806  conshdlrdata->lbhash = NULL;
4807  conshdlrdata->ubhash = NULL;
4808  conshdlrdata->nlbbounds = 0;
4809  conshdlrdata->nubbounds = 0;
4810  conshdlrdata->nslackvars = 0;
4811  conshdlrdata->objcutindex = -1;
4812  conshdlrdata->objupperbound = SCIPinfinity(scip);
4813  conshdlrdata->objaltlpbound = SCIPinfinity(scip);
4814  conshdlrdata->roundingminthres = 0.1;
4815  conshdlrdata->roundingmaxthres = 0.6;
4816  conshdlrdata->maxroundingrounds = MAXROUNDINGROUNDS;
4817  conshdlrdata->roundingoffset = 0.1;
4818  conshdlrdata->addedcouplingcons = FALSE;
4819  conshdlrdata->ninitconss = 0;
4820  conshdlrdata->nbinvarszero = 0;
4821  conshdlrdata->performedrestart = FALSE;
4822  conshdlrdata->objindicatoronly = FALSE;
4823  conshdlrdata->objothervarsonly = FALSE;
4824  conshdlrdata->minabsobj = 0.0;
4825  conshdlrdata->normtype = 'e';
4826  conshdlrdata->niiscutsgen = 0;
4827  conshdlrdata->nperspcutsgen = 0;
4828 }
4829 
4830 
4831 /* ---------------------------- upgrading methods -----------------------------------*/
4832 
4833 /** tries to upgrade a linear constraint into an indicator constraint
4834  *
4835  * For some linear constraint of the form \f$a^T x + \alpha\, y \geq \beta\f$ with \f$y \in \{0,1\}\f$, we can upgrade
4836  * it to an indicator constraint if for the residual value \f$a^T x \geq \gamma\f$, we have \f$\alpha + \gamma \geq
4837  * \beta\f$: in this case, the constraint is always satisfied if \f$y = 1\f$.
4838  *
4839  * Similarly, for a linear constraint in the form \f$a^T x + \alpha\, y \leq \beta\f$ with \f$y \in \{0,1\}\f$, we can
4840  * upgrade it to an indicator constraint if for the residual value \f$a^T x \leq \gamma\f$, we have \f$\alpha + \gamma
4841  * \leq \beta\f$.
4842  */
4843 static
4844 SCIP_DECL_LINCONSUPGD(linconsUpgdIndicator)
4845 { /*lint --e{715}*/
4846  SCIP_CONSHDLRDATA* conshdlrdata;
4847  SCIP_CONSHDLR* conshdlr;
4848  SCIP_Real minactivity = 0.0;
4849  SCIP_Real maxactivity = 0.0;
4850  SCIP_Real maxabsval = -1.0;
4851  SCIP_Real secabsval = -1.0;
4852  int maxabsvalidx = -1;
4853  int j;
4854 
4855  assert( scip != NULL );
4856  assert( upgdcons != NULL );
4857  assert( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), "linear") == 0 );
4858  assert( ! SCIPconsIsModifiable(cons) );
4859 
4860  /* do not upgrade if there are at most 2 variables (2 variables should be upgraded to a varbound constraint) */
4861  if ( nvars <= 2 )
4862  return SCIP_OKAY;
4863 
4864  /* cannot currently ranged constraints, since we can only return one constraint (and we would need one for each side each) */
4865  if ( ! SCIPisInfinity(scip, -lhs) && ! SCIPisInfinity(scip, rhs) )
4866  return SCIP_OKAY;
4867 
4868  /* check whether upgrading is turned on */
4869  conshdlr = SCIPfindConshdlr(scip, "indicator");
4870  assert( conshdlr != NULL );
4871  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4872  assert( conshdlrdata != NULL );
4873 
4874  if ( ! conshdlrdata->upgradelinear )
4875  return SCIP_OKAY;
4876 
4877  /* calculate activities */
4878  for (j = 0; j < nvars; ++j)
4879  {
4880  SCIP_VAR* var;
4881  SCIP_Real val;
4882  SCIP_Real lb;
4883  SCIP_Real ub;
4884 
4885  val = vals[j];
4886  assert( ! SCIPisZero(scip, val) );
4887 
4888  var = vars[j];
4889  assert( var != NULL );
4890 
4891  /* store maximal (and second to largest) value of coefficients */
4892  if ( SCIPisGE(scip, REALABS(val), maxabsval) )
4893  {
4894  secabsval = maxabsval;
4895  maxabsval = REALABS(val);
4896  maxabsvalidx = j;
4897  }
4898 
4899  if ( val > 0 )
4900  {
4901  lb = SCIPvarGetLbGlobal(var);
4902  ub = SCIPvarGetUbGlobal(var);
4903  }
4904  else
4905  {
4906  ub = SCIPvarGetLbGlobal(var);
4907  lb = SCIPvarGetUbGlobal(var);
4908  }
4909 
4910  /* compute minimal activity */
4911  if ( SCIPisInfinity(scip, -lb) )
4912  minactivity = -SCIPinfinity(scip);
4913  else
4914  {
4915  if ( ! SCIPisInfinity(scip, -minactivity) )
4916  minactivity += val * lb;
4917  }
4918 
4919  /* compute maximal activity */
4920  if ( SCIPisInfinity(scip, ub) )
4921  maxactivity = SCIPinfinity(scip);
4922  else
4923  {
4924  if ( ! SCIPisInfinity(scip, maxactivity) )
4925  maxactivity += val * ub;
4926  }
4927  }
4928  assert( maxabsval >= 0.0 );
4929  assert( 0 <= maxabsvalidx && maxabsvalidx < nvars );
4930 
4931  /* exit if largest coefficient does not belong to binary variable */
4932  if ( ! SCIPvarIsBinary(vars[maxabsvalidx]) )
4933  return SCIP_OKAY;
4934 
4935  /* exit if the second largest coefficient is as large as largest */
4936  if ( SCIPisEQ(scip, secabsval, maxabsval) )
4937  return SCIP_OKAY;
4938 
4939  /* cannot upgrade if all activities are infinity */
4940  if ( SCIPisInfinity(scip, -minactivity) && SCIPisInfinity(scip, maxactivity) )
4941  return SCIP_OKAY;
4942 
4943  /* check each variable as indicator variable */
4944  for (j = 0; j < nvars; ++j)
4945  {
4946  SCIP_VAR** indconsvars;
4947  SCIP_Real* indconsvals;
4948  SCIP_Bool upgdlhs = FALSE;
4949  SCIP_Bool upgdrhs = FALSE;
4950  SCIP_Bool indneglhs = FALSE;
4951  SCIP_Bool indnegrhs = FALSE;
4952  SCIP_VAR* indvar;
4953  SCIP_Real indval;
4954  int l;
4955 
4956  indvar = vars[j];
4957  indval = vals[j];
4958  assert( ! SCIPisZero(scip, indval) );
4959 
4960  if ( ! SCIPvarIsBinary(indvar) )
4961  continue;
4962 
4963  /* check for upgrading of lhs */
4964  if ( ! SCIPisInfinity(scip, -minactivity) && ! SCIPisInfinity(scip, -lhs) )
4965  {
4966  /* upgrading is possible with binary variable */
4967  if ( SCIPisGE(scip, minactivity, lhs) )
4968  upgdlhs = TRUE;
4969 
4970  /* upgrading is possible with negated binary variable */
4971  if ( SCIPisGE(scip, minactivity + indval, lhs) )
4972  {
4973  upgdlhs = TRUE;
4974  indneglhs = TRUE;
4975  }
4976  }
4977 
4978  /* check for upgrading of rhs */
4979  if ( ! SCIPisInfinity(scip, maxactivity) && ! SCIPisInfinity(scip, rhs) )
4980  {
4981  /* upgrading is possible with binary variable */
4982  if ( SCIPisLE(scip, maxactivity, rhs) )
4983  {
4984  upgdrhs = TRUE;
4985  indnegrhs = TRUE;
4986  }
4987 
4988  /* upgrading is possible with negated binary variable */
4989  if ( SCIPisLE(scip, maxactivity - indval, rhs) )
4990  upgdrhs = TRUE;
4991  }
4992 
4993  /* upgrade constraint */
4994  if ( upgdlhs || upgdrhs )
4995  {
4996  SCIP_VAR* indvar2;
4997  SCIP_Real bnd;
4998  int cnt = 0;
4999 
5000  assert( ! upgdlhs || ! upgdrhs ); /* cannot treat ranged rows */
5001  SCIPdebugMsg(scip, "upgrading constraint <%s> to an indicator constraint.\n", SCIPconsGetName(cons));
5002 
5003  SCIP_CALL( SCIPallocBufferArray(scip, &indconsvars, nvars - 1) );
5004  SCIP_CALL( SCIPallocBufferArray(scip, &indconsvals, nvars - 1) );
5005 
5006  /* create constraint */
5007  for (l = 0; l < nvars; ++l)
5008  {
5009  if ( vars[l] == indvar )
5010  continue;
5011  indconsvars[cnt] = vars[l];
5012  if ( upgdlhs )
5013  indconsvals[cnt] = -vals[l];
5014  else
5015  indconsvals[cnt] = vals[l];
5016  ++cnt;
5017  }
5018 
5019  if ( indneglhs || indnegrhs )
5020  {
5021  SCIP_CALL( SCIPgetNegatedVar(scip, indvar, &indvar2) );
5022  }
5023  else
5024  indvar2 = indvar;
5025 
5026  if ( upgdlhs )
5027  {
5028  bnd = -lhs;
5029  if ( ! indneglhs )
5030  bnd -= indval;
5031  SCIP_CALL( SCIPcreateConsIndicator(scip, upgdcons, SCIPconsGetName(cons), indvar2, nvars-1, indconsvars, indconsvals, bnd,
5034  }
5035  else
5036  {
5037  bnd = rhs;
5038  if ( ! indnegrhs )
5039  bnd -= indval;
5040  SCIP_CALL( SCIPcreateConsIndicator(scip, upgdcons, SCIPconsGetName(cons), indvar2, nvars-1, indconsvars, indconsvals, bnd,
5043  }
5044 
5045 #ifdef SCIP_DEBUG
5046  SCIPinfoMessage(scip, NULL, "upgrade: \n");
5047  SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
5048  SCIPinfoMessage(scip, NULL, "\n");
5049  SCIP_CALL( SCIPprintCons(scip, *upgdcons, NULL) );
5050  SCIPinfoMessage(scip, NULL, "\n");
5052  SCIPinfoMessage(scip, NULL, " (minact: %f, maxact: %f)\n", minactivity, maxactivity);
5053 #endif
5054 
5055  SCIPfreeBufferArray(scip, &indconsvars);
5056  SCIPfreeBufferArray(scip, &indconsvals);
5057 
5058  return SCIP_OKAY;
5059  }
5060  }
5061 
5062  return SCIP_OKAY;
5063 }
5064 
5065 
5066 /* ---------------------------- constraint handler callback methods ----------------------*/
5067 
5068 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
5069 static
5070 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyIndicator)
5071 { /*lint --e{715}*/
5072  assert( scip != NULL );
5073  assert( conshdlr != NULL );
5074  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
5075  assert( valid != NULL );
5076 
5077  /* call inclusion method of constraint handler */
5079 
5080  *valid = TRUE;
5081 
5082  return SCIP_OKAY;
5083 }
5084 
5085 
5086 /** initialization method of constraint handler (called after problem was transformed) */
5087 static
5088 SCIP_DECL_CONSINIT(consInitIndicator)
5089 { /*lint --e{715}*/
5090  SCIP_CONSHDLRDATA* conshdlrdata;
5091 
5092  assert( scip != NULL );
5093  assert( conshdlr != NULL );
5094  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
5095 
5096  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5097  assert( conshdlrdata != NULL );
5098 
5099  initConshdlrData(scip, conshdlrdata);
5100 
5101  /* find trysol heuristic */
5102  if ( conshdlrdata->trysolutions && conshdlrdata->heurtrysol == NULL )
5103  {
5104  conshdlrdata->heurtrysol = SCIPfindHeur(scip, "trysol");
5105  }
5106 
5107  return SCIP_OKAY;
5108 }
5109 
5110 
5111 /** deinitialization method of constraint handler (called before transformed problem is freed) */
5112 static
5113 SCIP_DECL_CONSEXIT(consExitIndicator)
5114 { /*lint --e{715}*/
5115  SCIP_CONSHDLRDATA* conshdlrdata;
5116 
5117  assert( scip != NULL );
5118  assert( conshdlr != NULL );
5119  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
5120 
5121  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5122 
5123  if ( conshdlrdata->binvarhash != NULL )
5124  SCIPhashmapFree(&conshdlrdata->binvarhash);
5125 
5126  SCIPfreeBlockMemoryArrayNull(scip, &conshdlrdata->addlincons, conshdlrdata->maxaddlincons);
5127  conshdlrdata->maxaddlincons = 0;
5128  conshdlrdata->naddlincons = 0;
5129  conshdlrdata->nrows = 0;
5130 
5131  return SCIP_OKAY;
5132 }
5133 
5134 
5135 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
5136 static
5137 SCIP_DECL_CONSFREE(consFreeIndicator)
5139  SCIP_CONSHDLRDATA* conshdlrdata;
5140 
5141  assert( scip != NULL );
5142  assert( conshdlr != NULL );
5143  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
5144 
5145  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5146  assert( conshdlrdata != NULL );
5147  assert( conshdlrdata->altlp == NULL );
5148  assert( conshdlrdata->varhash == NULL );
5149  assert( conshdlrdata->lbhash == NULL );
5150  assert( conshdlrdata->ubhash == NULL );
5151  assert( conshdlrdata->slackhash == NULL );
5152 
5153  if ( conshdlrdata->maxaddlincons > 0 )
5154  {
5155  /* if problem was not yet transformed the array may need to be freed, because we did not call the EXIT callback */
5156  SCIPfreeBlockMemoryArrayNull(scip, &conshdlrdata->addlincons, conshdlrdata->maxaddlincons);
5157  }
5158  assert( conshdlrdata->addlincons == NULL );
5159  conshdlrdata->naddlincons = 0;
5160  conshdlrdata->maxaddlincons = 0;
5161 
5162  SCIPfreeBlockMemory(scip, &conshdlrdata);
5163 
5164  return SCIP_OKAY;
5165 }
5166 
5167 
5168 /** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */
5169 static
5170 SCIP_DECL_CONSINITSOL(consInitsolIndicator)
5172  SCIP_CONSHDLRDATA* conshdlrdata;
5173  int c;
5174 
5175  assert( scip != NULL );
5176  assert( conshdlr != NULL );
5177  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
5178 
5181  return SCIP_OKAY;
5182 
5183  SCIPdebugMsg(scip, "Initsol for indicator constraints.\n");
5184 
5185  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5186  assert( conshdlrdata != NULL );
5187  assert( conshdlrdata->slackhash == NULL );
5188 
5189  SCIP_CALL( SCIPgetCharParam(scip, "separating/efficacynorm", &conshdlrdata->normtype) );
5190 
5191  if ( conshdlrdata->sepaalternativelp )
5192  {
5193  /* generate hash for storing all slack variables (size is just a guess) */
5194  SCIP_CALL( SCIPhashmapCreate(&conshdlrdata->slackhash, SCIPblkmem(scip), SCIPgetNVars(scip)) );
5195  assert( conshdlrdata->slackhash != NULL );
5196 
5197  /* first initialize slack hash */
5198  for (c = 0; c < nconss; ++c)
5199  {
5200  SCIP_CONSDATA* consdata;
5201 
5202  assert( conss != NULL );
5203  assert( conss[c] != NULL );
5204  assert( SCIPconsIsTransformed(conss[c]) );
5205 
5206  consdata = SCIPconsGetData(conss[c]);
5207  assert( consdata != NULL );
5208 
5209  assert( consdata->slackvar != NULL );
5210 
5211  /* insert slack variable into hash */
5212  SCIP_CALL( SCIPhashmapInsertInt(conshdlrdata->slackhash, consdata->slackvar, INT_MAX) );
5213  assert( SCIPhashmapExists(conshdlrdata->slackhash, consdata->slackvar) );
5214  ++conshdlrdata->nslackvars;
5215  }
5216 
5217  if ( conshdlrdata->genlogicor )
5218  {
5219  SCIP_CONSHDLR* logicorconshdlr;
5220  int logicorsepafreq;
5221  int sepafreq;
5222 
5223  /* If we generate logicor constraints, make sure that we separate them with the same frequency */
5224  logicorconshdlr = SCIPfindConshdlr(scip, "logicor");
5225  if ( logicorconshdlr == NULL )
5226  {
5227  SCIPerrorMessage("Logicor constraint handler not included, cannot generate constraints.\n");
5228  return SCIP_ERROR;
5229  }
5230  logicorsepafreq = SCIPconshdlrGetSepaFreq(logicorconshdlr);
5231  sepafreq = SCIPconshdlrGetSepaFreq(conshdlr);
5232  if ( sepafreq != -1 && ((logicorsepafreq == 0 && sepafreq > 0) || sepafreq < logicorsepafreq) )
5233  {
5234  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "Set sepafreq of logicor constraint handler to %d.\n", sepafreq);
5235  SCIP_CALL( SCIPsetIntParam(scip, "constraints/logicor/sepafreq", sepafreq) );
5236  }
5237  }
5238  }
5239 
5240  /* check each constraint */
5241  conshdlrdata->objothervarsonly = TRUE;
5242  for (c = 0; c < nconss; ++c)
5243  {
5244  SCIP_CONSDATA* consdata;
5245 
5246  assert( conss != NULL );
5247  assert( conss[c] != NULL );
5248  assert( SCIPconsIsTransformed(conss[c]) );
5249 
5250  consdata = SCIPconsGetData(conss[c]);
5251  assert( consdata != NULL );
5252  assert( consdata->binvar != NULL );
5253  assert( consdata->slackvar != NULL );
5254 
5255  /* Presolving might replace a slack variable by an active variable. Thus, the objective of a slack variables might
5256  * be nonzero. However, we do not need to check slack variables here. */
5257  if ( ! SCIPisZero(scip, varGetObjDelta(consdata->binvar)) )
5258  conshdlrdata->objothervarsonly = FALSE;
5259 
5260  /* deactivate */
5261  if ( ! consdata->linconsactive )
5262  {
5263  SCIP_CALL( SCIPdisableCons(scip, consdata->lincons) );
5264  }
5265  else
5266  {
5267  /* add constraint to alternative LP if not already done */
5268  if ( conshdlrdata->sepaalternativelp && consdata->colindex < 0 )
5269  {
5270  SCIP_CALL( addAltLPConstraint(scip, conshdlr, consdata->lincons, consdata->slackvar, 1.0, &consdata->colindex) );
5271  SCIPdebugMsg(scip, "Added column for <%s> to alternative LP with column index %d.\n", SCIPconsGetName(conss[c]),consdata->colindex);
5272 #ifdef SCIP_OUTPUT
5273  SCIP_CALL( SCIPprintCons(scip, consdata->lincons, NULL) );
5274  SCIPinfoMessage(scip, NULL, ";\n");
5275 #endif
5276  }
5277  }
5278 
5279  /* add nlrow representation to NLP, if NLP had been constructed
5280  *
5281  * Note, that we did not tell SCIP in exitpre that we have something to add to the NLP, thus
5282  * indicators are only available in the NLP for MINLPs, but not for MIPs with indicators.
5283  */
5284  if ( SCIPisNLPConstructed(scip) && SCIPconsIsChecked(conss[c]) )
5285  {
5286  SCIP_NLROW* nlrow;
5287  SCIP_VAR* quadvars[2];
5288  SCIP_QUADELEM quadelem;
5289 
5290  /* create nonlinear row binary variable * slack variable = 0 */
5291  quadvars[0] = consdata->binvar;
5292  quadvars[1] = consdata->slackvar;
5293  quadelem.idx1 = 0;
5294  quadelem.idx2 = 1;
5295  quadelem.coef = 1.0;
5296 
5297  SCIP_CALL( SCIPcreateNlRow(scip, &nlrow, SCIPconsGetName(conss[c]), 0.0, 0, NULL, NULL, 2, quadvars, 1,
5298  &quadelem, NULL, 0.0, 0.0, SCIP_EXPRCURV_UNKNOWN) );
5299 
5300  /* add row to NLP and forget about it */
5301  SCIP_CALL( SCIPaddNlRow(scip, nlrow) );
5302  SCIP_CALL( SCIPreleaseNlRow(scip, &nlrow) );
5303  }
5304  }
5305 
5306  SCIPdebugMsg(scip, "Initialized %d indicator constraints.\n", nconss);
5307 
5308  /* check additional constraints */
5309  if ( conshdlrdata->sepaalternativelp )
5310  {
5311  SCIP_CONS* cons;
5312  int colindex;
5313  int cnt = 0;
5314 
5315  /* add stored linear constraints if they exist */
5316  if ( conshdlrdata->naddlincons > 0 )
5317  {
5318  for (c = 0; c < conshdlrdata->naddlincons; ++c)
5319  {
5320  cons = conshdlrdata->addlincons[c];
5321 
5322  /* get transformed constraint - since it is needed only here, we do not store the information */
5323  if ( ! SCIPconsIsTransformed(cons) )
5324  {
5325  SCIP_CALL( SCIPgetTransformedCons(scip, conshdlrdata->addlincons[c], &cons) );
5326 
5327  /* @todo check when exactly the transformed constraint does not exist - SCIPisActive() does not suffice */
5328  if ( cons == NULL )
5329  continue;
5330  }
5331  SCIP_CALL( addAltLPConstraint(scip, conshdlr, cons, NULL, 0.0, &colindex) );
5332  ++cnt;
5333 
5334 #ifdef SCIP_OUTPUT
5335  SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
5336  SCIPinfoMessage(scip, NULL, ";\n");
5337 #endif
5338  }
5339  SCIPdebugMsg(scip, "Added %d additional columns to alternative LP.\n", cnt);
5340  }
5341  else
5342  {
5343  /* if no stored linear constraints are available, possibly collect other linear constraints; we only use linear
5344  * constraints, since most other constraints involve integral variables, and in this context we will likely
5345  * benefit much more from continuous variables. */
5346  if ( conshdlrdata->useotherconss )
5347  {
5348  const char* conshdlrname;
5349  SCIP_CONS** allconss;
5350  int nallconss;
5351 
5352  nallconss = SCIPgetNConss(scip);
5353  allconss = SCIPgetConss(scip);
5354 
5355  /* loop through all constraints */
5356  for (c = 0; c < nallconss; ++c)
5357  {
5358  /* get constraint */
5359  cons = allconss[c];
5360  assert( cons != NULL );
5361  assert( SCIPconsIsTransformed(cons) );
5362 
5363  /* get constraint handler name */
5364  conshdlrname = SCIPconshdlrGetName(SCIPconsGetHdlr(cons));
5365 
5366  /* check type of constraint (only take linear constraints) */
5367  if ( strcmp(conshdlrname, "linear") == 0 )
5368  {
5369  /* avoid adding linear constraints that correspond to indicator constraints */
5370  if ( strncmp(SCIPconsGetName(cons), "indlin", 6) != 0 )
5371  {
5372  SCIP_CALL( addAltLPConstraint(scip, conshdlr, cons, NULL, 0.0, &colindex) );
5373  SCIPdebugMsg(scip, "Added column for linear constraint <%s> to alternative LP with column index %d.\n", SCIPconsGetName(cons), colindex);
5374  ++cnt;
5375  }
5376  }
5377  }
5378  SCIPdebugMsg(scip, "Added %d additional columns from linear constraints to alternative LP.\n", cnt);
5379  }
5380  }
5381  }
5382 
5383  /* initialize event handler if restart should be forced */
5384  if ( conshdlrdata->forcerestart )
5385  {
5386  SCIP_Bool* covered;
5387  SCIP_VAR** vars;
5388  int nvars;
5389  int j;
5390 
5391  assert( conshdlrdata->eventhdlrrestart != NULL );
5392 
5393  /* store number of initial constraints */
5394  conshdlrdata->ninitconss = SCIPconshdlrGetNActiveConss(conshdlr);
5395 
5396  /* reset number of fixed binary variables */
5397  conshdlrdata->nbinvarszero = 0;
5398 
5399  /* loop through variables */
5400  nvars = SCIPgetNVars(scip);
5401  vars = SCIPgetVars(scip);
5402 
5403  conshdlrdata->objindicatoronly = FALSE;
5404  conshdlrdata->minabsobj = SCIP_REAL_MAX;
5405 
5406  /* unmark all variables */
5407  SCIP_CALL( SCIPallocBufferArray(scip, &covered, nvars) );
5408  for (j = 0; j < nvars; ++j)
5409  covered[j] = FALSE;
5410 
5411  /* mark indicator variables */
5412  for (c = 0; c < nconss; ++c)
5413  {
5414  SCIP_CONSDATA* consdata;
5415  int probindex;
5416 
5417  assert( conss != NULL );
5418  assert( conss[c] != NULL );
5419 
5420  /* avoid non-active indicator constraints */
5421  if ( ! SCIPconsIsActive(conss[c]) )
5422  continue;
5423 
5424  consdata = SCIPconsGetData(conss[c]);
5425  assert( consdata != NULL );
5426  assert( consdata->binvar != NULL );
5427 
5428  if ( SCIPvarIsNegated(consdata->binvar) )
5429  {
5430  assert( SCIPvarGetNegatedVar(consdata->binvar) != NULL );
5431  probindex = SCIPvarGetProbindex(SCIPvarGetNegatedVar(consdata->binvar));
5432  }
5433  else
5434  probindex = SCIPvarGetProbindex(consdata->binvar);
5435 
5436  /* if presolving detected infeasibility it might be that the binary variables are not active */
5437  if ( probindex < 0 )
5438  continue;
5439 
5440  assert( 0 <= probindex && probindex < nvars );
5441  covered[probindex] = TRUE;
5442  }
5443 
5444  /* check all variables */
5445  for (j = 0; j < nvars; ++j)
5446  {
5447  SCIP_Real obj;
5448 
5449  obj = SCIPvarGetObj(vars[j]);
5450  if ( ! SCIPisZero(scip, obj) )
5451  {
5452  if ( ! covered[j] )
5453  break;
5454  if ( ! SCIPisIntegral(scip, obj) )
5455  break;
5456  if ( REALABS(obj) < conshdlrdata->minabsobj )
5457  conshdlrdata->minabsobj = REALABS(obj);
5458  }
5459  }
5460 
5461  /* if all variables have integral objective and only indicator variables have nonzero objective */
5462  if ( j >= nvars )
5463  {
5464  /* if there are variables with nonzero objective */
5465  if ( conshdlrdata->minabsobj < SCIP_REAL_MAX )
5466  {
5467  assert( SCIPisIntegral(scip, conshdlrdata->minabsobj) );
5468  assert( SCIPisGE(scip, conshdlrdata->minabsobj, 1.0) );
5469 
5470  conshdlrdata->objindicatoronly = TRUE;
5471 
5472  assert( conshdlrdata->eventhdlrrestart != NULL );
5473  SCIP_CALL( SCIPcatchEvent(scip, SCIP_EVENTTYPE_BESTSOLFOUND, conshdlrdata->eventhdlrrestart, (SCIP_EVENTDATA*) conshdlrdata, NULL) );
5474  }
5475  }
5476 
5477  SCIPfreeBufferArray(scip, &covered);
5478  }
5479 
5480  return SCIP_OKAY;
5481 }
5482 
5483 
5484 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
5485 static
5486 SCIP_DECL_CONSEXITSOL(consExitsolIndicator)
5487 { /*lint --e{715}*/
5488  SCIP_CONSHDLRDATA* conshdlrdata;
5489  int c;
5490 
5491  assert( scip != NULL );
5492  assert( conshdlr != NULL );
5493  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
5494 
5495  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5496  assert( conshdlrdata != NULL );
5497 
5498  if ( conshdlrdata->sepaalternativelp )
5499  {
5500  if ( conshdlrdata->slackhash != NULL )
5501  {
5502 #ifdef SCIP_DEBUG
5503  SCIPinfoMessage(scip, NULL, "\nStatistics for cons_indicator slack hash:\n");
5504  SCIPhashmapPrintStatistics(conshdlrdata->slackhash, SCIPgetMessagehdlr(scip));
5505 #endif
5506  SCIPhashmapFree(&conshdlrdata->slackhash);
5507  }
5508 
5509  if ( conshdlrdata->altlp != NULL )
5510  {
5511  assert( conshdlrdata->varhash != NULL );
5512  assert( conshdlrdata->lbhash != NULL );
5513  assert( conshdlrdata->ubhash != NULL );
5514 
5515 #ifdef SCIP_DEBUG
5516  SCIPinfoMessage(scip, NULL, "\nStatistics for cons_indicator var hash:\n");
5517  SCIPhashmapPrintStatistics(conshdlrdata->varhash, SCIPgetMessagehdlr(scip));
5518  SCIPinfoMessage(scip, NULL, "\nStatistics for cons_indicator lower bound hash:\n");
5519  SCIPhashmapPrintStatistics(conshdlrdata->lbhash, SCIPgetMessagehdlr(scip));
5520  SCIPinfoMessage(scip, NULL, "\nStatistics for cons_indicator upper bound hash:\n");
5521  SCIPhashmapPrintStatistics(conshdlrdata->ubhash, SCIPgetMessagehdlr(scip));
5522 #endif
5523 
5524  SCIPhashmapFree(&conshdlrdata->varhash);
5525  SCIPhashmapFree(&conshdlrdata->lbhash);
5526  SCIPhashmapFree(&conshdlrdata->ubhash);
5527 
5528  SCIP_CALL( SCIPlpiFree(&conshdlrdata->altlp) );
5529 
5530  /* save the information that the columns have been deleted */
5531  for (c = 0; c < nconss; ++c)
5532  {
5533  SCIP_CONSDATA* consdata;
5534 
5535  assert( conss != NULL );
5536  assert( conss[c] != NULL );
5537 
5538  consdata = SCIPconsGetData(conss[c]);
5539  assert( consdata != NULL );
5540  consdata->colindex = -1;
5541  }
5542  }
5543  }
5544  else
5545  {
5546  assert( conshdlrdata->slackhash == NULL );
5547  assert( conshdlrdata->varhash == NULL );
5548  assert( conshdlrdata->lbhash == NULL );
5549  assert( conshdlrdata->ubhash == NULL );
5550  }
5551 
5552  return SCIP_OKAY;
5553 }
5554 
5555 
5556 /** frees specific constraint data */
5557 static
5558 SCIP_DECL_CONSDELETE(consDeleteIndicator)
5560  assert( scip != NULL );
5561  assert( conshdlr != NULL );
5562  assert( cons != NULL );
5563  assert( consdata != NULL );
5564  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
5565 
5566 #ifdef SCIP_MORE_DEBUG
5567  SCIPdebugMsg(scip, "Deleting indicator constraint <%s>.\n", SCIPconsGetName(cons) );
5568 #endif
5569 
5570  /* drop events on transformed variables */
5571  if ( SCIPconsIsTransformed(cons) )
5572  {
5573  SCIP_CONSHDLRDATA* conshdlrdata;
5574 
5575  /* get constraint handler data */
5576  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5577  assert( conshdlrdata != NULL );
5578 
5579  if ( conshdlrdata->sepaalternativelp )
5580  {
5581  SCIP_CALL( deleteAltLPConstraint(scip, conshdlr, cons) );
5582  }
5583 
5584  assert( (*consdata)->slackvar != NULL );
5585  assert( (*consdata)->binvar != NULL );
5586 
5587  /* free events only in correct stages */
5589  {
5590  if ( (*consdata)->linconsactive )
5591  {
5592  assert( conshdlrdata->eventhdlrbound != NULL );
5593  SCIP_CALL( SCIPdropVarEvent(scip, (*consdata)->binvar, SCIP_EVENTTYPE_BOUNDCHANGED, conshdlrdata->eventhdlrbound,
5594  (SCIP_EVENTDATA*)*consdata, -1) );
5595  SCIP_CALL( SCIPdropVarEvent(scip, (*consdata)->slackvar, SCIP_EVENTTYPE_BOUNDCHANGED, conshdlrdata->eventhdlrbound,
5596  (SCIP_EVENTDATA*)*consdata, -1) );
5597  }
5598  if ( conshdlrdata->forcerestart )
5599  {
5600  assert( conshdlrdata->eventhdlrrestart != NULL );
5601  SCIP_CALL( SCIPdropVarEvent(scip, (*consdata)->binvar, SCIP_EVENTTYPE_GBDCHANGED, conshdlrdata->eventhdlrrestart,
5602  (SCIP_EVENTDATA*) conshdlrdata, -1) );
5603  }
5604  }
5605  }
5606 
5607  /* Can there be cases where lincons is NULL, e.g., if presolve found the problem infeasible? */
5608  assert( (*consdata)->lincons != NULL );
5609 
5610  /* release linear constraint and slack variable */
5611  SCIP_CALL( SCIPreleaseVar(scip, &(*consdata)->slackvar) );
5612  SCIP_CALL( SCIPreleaseCons(scip, &(*consdata)->lincons) );
5613 
5614  SCIPfreeBlockMemory(scip, consdata);
5615 
5616  return SCIP_OKAY;
5617 }
5618 
5619 
5620 /** transforms constraint data into data belonging to the transformed problem */
5621 static
5622 SCIP_DECL_CONSTRANS(consTransIndicator)
5624  SCIP_CONSDATA* consdata;
5625  SCIP_CONSHDLRDATA* conshdlrdata;
5626  SCIP_CONSDATA* sourcedata;
5627  char s[SCIP_MAXSTRLEN];
5628 
5629  assert( scip != NULL );
5630  assert( conshdlr != NULL );
5631  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
5632  assert( sourcecons != NULL );
5633  assert( targetcons != NULL );
5634 
5635  /* get constraint handler data */
5636  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5637  assert( conshdlrdata != NULL );
5638  assert( conshdlrdata->eventhdlrbound != NULL );
5639 
5640 #ifdef SCIP_MORE_DEBUG
5641  SCIPdebugMsg(scip, "Transforming indicator constraint: <%s>.\n", SCIPconsGetName(sourcecons) );
5642 #endif
5643 
5644  /* get data of original constraint */
5645  sourcedata = SCIPconsGetData(sourcecons);
5646  assert( sourcedata != NULL );
5647  assert( sourcedata->binvar != NULL );
5648 
5649  /* check for slackvar */
5650  if ( sourcedata->slackvar == NULL )
5651  {
5652  SCIPerrorMessage("The indicator constraint <%s> needs a slack variable.\n", SCIPconsGetName(sourcecons));
5653  return SCIP_INVALIDDATA;
5654  }
5655 
5656  /* check for linear constraint */
5657  if ( sourcedata->lincons == NULL )
5658  {
5659  SCIPerrorMessage("The indicator constraint <%s> needs a linear constraint variable.\n", SCIPconsGetName(sourcecons));
5660  return SCIP_INVALIDDATA;
5661  }
5662  assert( sourcedata->lincons != NULL );
5663  assert( sourcedata->slackvar != NULL );
5664 
5665  /* create constraint data */
5666  consdata = NULL;
5667  SCIP_CALL( consdataCreate(scip, conshdlr, conshdlrdata, SCIPconsGetName(sourcecons), &consdata, conshdlrdata->eventhdlrbound,
5668  conshdlrdata->eventhdlrrestart, sourcedata->binvar, sourcedata->slackvar, sourcedata->lincons, sourcedata->linconsactive) );
5669  assert( consdata != NULL );
5670 
5671  /* capture slack variable and linear constraint */
5672  SCIP_CALL( SCIPcaptureVar(scip, consdata->slackvar) );
5673  SCIP_CALL( SCIPcaptureCons(scip, consdata->lincons) );
5674 
5675  /* create transformed constraint with the same flags */
5676  (void) SCIPsnprintf(s, SCIP_MAXSTRLEN, "t_%s", SCIPconsGetName(sourcecons));
5677  SCIP_CALL( SCIPcreateCons(scip, targetcons, s, conshdlr, consdata,
5678  SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons),
5679  SCIPconsIsEnforced(sourcecons), SCIPconsIsChecked(sourcecons),
5680  SCIPconsIsPropagated(sourcecons), SCIPconsIsLocal(sourcecons),
5681  SCIPconsIsModifiable(sourcecons), SCIPconsIsDynamic(sourcecons),
5682  SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
5683 
5684  /* make sure that binary variable hash exists */
5685  if ( conshdlrdata->sepaalternativelp )
5686  {
5687  if ( conshdlrdata->binvarhash == NULL )
5688  {
5689  SCIP_CALL( SCIPhashmapCreate(&conshdlrdata->binvarhash, SCIPblkmem(scip), SCIPgetNOrigVars(scip)) );
5690  }
5691 
5692  /* check whether binary variable is present: note that a binary variable might appear several times, but this seldomly happens. */
5693  assert( conshdlrdata->binvarhash != NULL );
5694  if ( ! SCIPhashmapExists(conshdlrdata->binvarhash, (void*) consdata->binvar) )
5695  {
5696  SCIP_CALL( SCIPhashmapInsert(conshdlrdata->binvarhash, (void*) consdata->binvar, (void*) (*targetcons)) );
5697  }
5698  }
5699 
5700  return SCIP_OKAY;
5701 }
5702 
5703 
5704 /** presolving initialization method of constraint handler (called when presolving is about to begin) */
5705 static
5706 SCIP_DECL_CONSINITPRE(consInitpreIndicator)
5707 { /*lint --e{715}*/
5708  SCIP_CONSHDLRDATA* conshdlrdata;
5709  int c;
5710 
5711  assert( scip != NULL );
5712  assert( conshdlr != NULL );
5713  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
5714 
5715  if ( SCIPgetStatus(scip) != SCIP_STATUS_UNKNOWN )
5716  return SCIP_OKAY;
5717 
5718  SCIPdebugMsg(scip, "Initpre method for indicator constraints.\n");
5719 
5720  /* check each constraint and get transformed linear constraint */
5721  for (c = 0; c < nconss; ++c)
5722  {
5723  SCIP_CONSDATA* consdata;
5724 
5725  assert( conss != NULL );
5726  assert( conss[c] != NULL );
5727  assert( SCIPconsIsTransformed(conss[c]) );
5728 
5729  consdata = SCIPconsGetData(conss[c]);
5730  assert( consdata != NULL );
5731 
5732  /* if not happened already, get transformed linear constraint */
5733  assert( consdata->lincons != NULL );
5734  assert( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(consdata->lincons)), "linear") == 0 );
5735 
5736  /* in a restart the linear constraint might already be transformed */
5737  if ( ! SCIPconsIsTransformed(consdata->lincons) )
5738  {
5739  SCIP_CONS* translincons;
5740 
5741  SCIP_CALL( SCIPgetTransformedCons(scip, consdata->lincons, &translincons) );
5742  assert( translincons != NULL );
5743 
5744  SCIP_CALL( SCIPreleaseCons(scip, &consdata->lincons) );
5745  SCIP_CALL( SCIPcaptureCons(scip, translincons) );
5746  consdata->lincons = translincons;
5747  }
5748  }
5749 
5750  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5751  assert( conshdlrdata != NULL );
5752 
5753  /* reset flag, in case presolve was called for some problem before */
5754  conshdlrdata->addedcouplingcons = FALSE;
5755 
5756  return SCIP_OKAY;
5757 }
5758 
5759 
5760 /** presolving method of constraint handler
5761  *
5762  * For an indicator constraint with binary variable \f$y\f$ and slack variable \f$s\f$ the coupling
5763  * inequality \f$s \le M (1-y)\f$ (equivalently: \f$s + M y \le M\f$) is inserted, where \f$M\f$ is
5764  * an upper bound on the value of \f$s\f$. If \f$M\f$ is too large the inequality is not
5765  * inserted. Depending on the parameter @a addcouplingcons we add a variable upper bound or a row
5766  * (in consInitlpIndicator()).
5767  *
5768  * @warning We can never delete linear constraints, because we need them to get the right values
5769  * for the slack variables!
5770  */
5771 static
5772