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