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-2018 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( SCIPhashmapInsert(varhash, var, (void*) (size_t) nvars) );
1029  assert( nvars == (int) (size_t) SCIPhashmapGetImage(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] = (int) (size_t) SCIPhashmapGetImage(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( SCIPhashmapInsert(varhash, var, (void*) (size_t) nvars) );
1177  assert( nvars == (int) (size_t) SCIPhashmapGetImage(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] = (int) (size_t) SCIPhashmapGetImage(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 = (int) (size_t) SCIPhashmapGetImage(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 = (int) (size_t) SCIPhashmapGetImage(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 = (int) (size_t) SCIPhashmapGetImage(lbhash, var);
1816  SCIP_CALL( SCIPlpiChgCoef(altlp, 0, col, -SCIPvarGetLbGlobal(var)) );
1817  ++cnt;
1818  }
1819  if ( SCIPhashmapExists(ubhash, var) )
1820  {
1821  col = (int) (size_t) SCIPhashmapGetImage(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 = (int) (size_t) SCIPhashmapGetImage(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 = (int) (size_t) SCIPhashmapGetImage(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  SCIP_CALL( SCIPlpiGetNCols(conshdlrdata->altlp, &ncols) );
2055  *colindex = ncols;
2056 
2057  /* handle first row */
2058  if ( ! SCIPisFeasZero(scip, rhscoef) )
2059  {
2060  matind[cnt] = 0;
2061  matval[cnt++] = sign * rhscoef;
2062  }
2063 
2064  /* set up column (recognize new original variables) */
2065  for (v = 0; v < nvars; ++v)
2066  {
2067  SCIP_VAR* var;
2068 
2069  var = vars[v];
2070  assert( var != NULL );
2071 
2072  /* if variable is a slack variable */
2073  if ( SCIPhashmapExists(conshdlrdata->slackhash, var) )
2074  {
2075  /* to avoid trivial rows: only add row corresponding to slack variable if it appears outside its own constraint */
2076  if ( var != slackvar )
2077  {
2078  int ind;
2079 
2080  ind = (int) (size_t) SCIPhashmapGetImage(conshdlrdata->slackhash, var);
2081 
2082  if ( ind < INT_MAX )
2083  matind[cnt] = ind;
2084  else
2085  {
2086  /* correct number of variable already in map/array and remember to add a new row */
2087  SCIP_CALL( SCIPhashmapSetImage(conshdlrdata->slackhash, var, (void*) (size_t) conshdlrdata->nrows) );
2088  assert( conshdlrdata->nrows == (int) (size_t) SCIPhashmapGetImage(conshdlrdata->slackhash, var) );
2089  SCIPdebugMsg(scip, "Inserted slack variable <%s> into hashmap (row: %d).\n", SCIPvarGetName(var), conshdlrdata->nrows);
2090  matind[cnt] = (conshdlrdata->nrows)++;
2091 
2092  /* store new variables */
2093  newrowsslack[nnewrows++] = TRUE;
2094  }
2095  assert( conshdlrdata->nrows >= (int) (size_t) SCIPhashmapGetImage(conshdlrdata->slackhash, var) );
2096  matval[cnt++] = sign * vals[v];
2097  }
2098  }
2099  else
2100  {
2101  /* if variable exists */
2102  if ( SCIPhashmapExists(conshdlrdata->varhash, var) )
2103  matind[cnt] = (int) (size_t) SCIPhashmapGetImage(conshdlrdata->varhash, var);
2104  else
2105  {
2106  /* add variable in map and array and remember to add a new row */
2107  SCIP_CALL( SCIPhashmapInsert(conshdlrdata->varhash, var, (void*) (size_t) conshdlrdata->nrows) );
2108  assert( conshdlrdata->nrows == (int) (size_t) SCIPhashmapGetImage(conshdlrdata->varhash, var) );
2109  SCIPdebugMsg(scip, "Inserted variable <%s> into hashmap (row: %d).\n", SCIPvarGetName(var), conshdlrdata->nrows);
2110  matind[cnt] = (conshdlrdata->nrows)++;
2111 
2112  /* store new variables */
2113  newrowsslack[nnewrows++] = FALSE;
2114  newvars[nnewvars++] = var;
2115  }
2116  assert( SCIPhashmapExists(conshdlrdata->varhash, var) );
2117  matval[cnt++] = sign * vals[v];
2118  }
2119  }
2120 
2121  /* add new rows */
2122  if ( nnewrows > 0 )
2123  {
2124  SCIP_Real* lhs;
2125  SCIP_Real* rhs;
2126  int i;
2127 
2128  SCIP_CALL( SCIPallocBufferArray(scip, &lhs, nnewrows) );
2129  SCIP_CALL( SCIPallocBufferArray(scip, &rhs, nnewrows) );
2130  for (i = 0; i < nnewrows; ++i)
2131  {
2132  if ( newrowsslack[i] )
2133  lhs[i] = -SCIPlpiInfinity(conshdlrdata->altlp);
2134  else
2135  lhs[i] = 0.0;
2136  rhs[i] = 0.0;
2137  }
2138  /* add new rows */
2139  SCIP_CALL( SCIPlpiAddRows(conshdlrdata->altlp, nnewrows, lhs, rhs, NULL, 0, NULL, NULL, NULL) );
2140 
2141  SCIPfreeBufferArray(scip, &lhs);
2142  SCIPfreeBufferArray(scip, &rhs);
2143  }
2144 
2145  /* now add column */
2146  obj[0] = objcoef;
2147  if ( colfree )
2148  {
2149  /* create a free variable -> should only happen for additional linear constraints */
2150  assert( slackvar == NULL );
2151  lb[0] = -SCIPlpiInfinity(conshdlrdata->altlp);
2152  }
2153  else
2154  lb[0] = 0.0;
2155  ub[0] = SCIPlpiInfinity(conshdlrdata->altlp);
2156  matbeg[0] = 0;
2157 
2158  SCIP_CALL( SCIPlpiAddCols(conshdlrdata->altlp, 1, obj, lb, ub, NULL, cnt, matbeg, matind, matval) );
2159 
2160  /* add columns corresponding to bounds of original variables - no bounds needed for slack vars */
2161  cnt = 0;
2162  for (v = 0; v < nnewvars; ++v)
2163  {
2164  SCIP_VAR* var = newvars[v];
2165  assert( var != NULL );
2166 
2167  /* if the lower bound is finite */
2168  val = SCIPvarGetLbGlobal(var);
2169  if ( ! SCIPisInfinity(scip, -val) )
2170  {
2171  matbeg[nnewcols] = cnt;
2172  if ( ! SCIPisZero(scip, val) )
2173  {
2174  matind[cnt] = 0;
2175  matval[cnt++] = -val;
2176  }
2177  assert( SCIPhashmapExists(conshdlrdata->varhash, var) );
2178 
2179  matind[cnt] = (int) (size_t) SCIPhashmapGetImage(conshdlrdata->varhash, var);
2180  matval[cnt++] = -1.0;
2181  obj[nnewcols] = 0.0;
2182  lb[nnewcols] = 0.0;
2183  ub[nnewcols] = SCIPlpiInfinity(conshdlrdata->altlp);
2184  ++conshdlrdata->nlbbounds;
2185 
2186  SCIP_CALL( SCIPhashmapInsert(conshdlrdata->lbhash, var, (void*) (size_t) (ncols + 1 + nnewcols)) );
2187  assert( SCIPhashmapExists(conshdlrdata->lbhash, var) );
2188  SCIPdebugMsg(scip, "Added column for lower bound (%f) of variable <%s> to alternative polyhedron (col: %d).\n",
2189  val, SCIPvarGetName(var), ncols + 1 + nnewcols);
2190  ++nnewcols;
2191  }
2192 
2193  /* if the upper bound is finite */
2194  val = SCIPvarGetUbGlobal(var);
2195  if ( ! SCIPisInfinity(scip, val) )
2196  {
2197  matbeg[nnewcols] = cnt;
2198  if ( ! SCIPisZero(scip, val) )
2199  {
2200  matind[cnt] = 0;
2201  matval[cnt++] = val;
2202  }
2203  assert( SCIPhashmapExists(conshdlrdata->varhash, var) );
2204 
2205  matind[cnt] = (int) (size_t) SCIPhashmapGetImage(conshdlrdata->varhash, var);
2206  matval[cnt++] = 1.0;
2207  obj[nnewcols] = 0.0;
2208  lb[nnewcols] = 0.0;
2209  ub[nnewcols] = SCIPlpiInfinity(conshdlrdata->altlp);
2210  ++conshdlrdata->nubbounds;
2211 
2212  SCIP_CALL( SCIPhashmapInsert(conshdlrdata->ubhash, var, (void*) (size_t) (ncols + 1 + nnewcols)) );
2213  assert( SCIPhashmapExists(conshdlrdata->ubhash, var) );
2214  SCIPdebugMsg(scip, "Added column for upper bound (%f) of variable <%s> to alternative polyhedron (col: %d).\n",
2215  val, SCIPvarGetName(var), ncols + 1 + nnewcols);
2216  ++nnewcols;
2217  }
2218  }
2219 
2220  /* add columns if necessary */
2221  if ( nnewcols > 0 )
2222  {
2223  SCIP_CALL( SCIPlpiAddCols(conshdlrdata->altlp, nnewcols, obj, lb, ub, NULL, cnt, matbeg, matind, matval) );
2224  }
2225 
2226 #ifndef NDEBUG
2227  SCIP_CALL( SCIPlpiGetNCols(conshdlrdata->altlp, &cnt) );
2228  assert( cnt == ncols + nnewcols + 1 );
2229 #endif
2230 
2231  SCIPfreeBufferArray(scip, &ub);
2232  SCIPfreeBufferArray(scip, &lb);
2233  SCIPfreeBufferArray(scip, &obj);
2234  SCIPfreeBufferArray(scip, &matind);
2235  SCIPfreeBufferArray(scip, &matval);
2236  SCIPfreeBufferArray(scip, &matbeg);
2237  SCIPfreeBufferArray(scip, &newvars);
2238  SCIPfreeBufferArray(scip, &newrowsslack);
2239 
2240  conshdlrdata->scaled = FALSE;
2241 
2242 #ifdef SCIP_OUTPUT
2243  SCIP_CALL( SCIPlpiWriteLP(conshdlrdata->altlp, "alt.lp") );
2244 #endif
2245 
2246  return SCIP_OKAY;
2247 }
2248 
2249 
2250 /** add column corresponding to constraint to alternative LP
2251  *
2252  * See the description at the top of the file for more information.
2253  */
2254 static
2256  SCIP* scip, /**< SCIP pointer */
2257  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
2258  SCIP_CONS* lincons, /**< linear constraint */
2259  SCIP_VAR* slackvar, /**< slack variable or NULL */
2260  SCIP_Real objcoef, /**< objective coefficient */
2261  int* colindex /**< index of new column */
2262  )
2263 {
2264  SCIP_CONSHDLRDATA* conshdlrdata;
2265  SCIP_VAR** linvars;
2266  SCIP_Real* linvals;
2267  SCIP_Real linrhs;
2268  SCIP_Real linlhs;
2269  int nlinvars;
2270 
2271  assert( scip != NULL );
2272  assert( conshdlr != NULL );
2273  assert( lincons != NULL );
2274  assert( colindex != NULL );
2275  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2276 
2277  *colindex = -1;
2278 
2279  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2280  assert( conshdlrdata != NULL );
2281 
2282  /* if the slack variable is aggregated (multi-aggregation should not happen) */
2283  assert( slackvar == NULL || SCIPvarGetStatus(slackvar) != SCIP_VARSTATUS_MULTAGGR );
2284  if ( slackvar != NULL && SCIPvarGetStatus(slackvar) == SCIP_VARSTATUS_AGGREGATED )
2285  {
2286  SCIP_VAR* var;
2287  SCIP_Real scalar = 1.0;
2288  SCIP_Real constant = 0.0;
2289 
2290  var = slackvar;
2291 
2292  SCIP_CALL( SCIPgetProbvarSum(scip, &var, &scalar, &constant) );
2293 
2294  SCIPdebugMsg(scip, "Slack variable is aggregated (scalar: %f, constant: %f).\n", scalar, constant);
2295 
2296  /* if the slack variable is fixed */
2297  if ( SCIPisZero(scip, scalar) && ! SCIPconsIsActive(lincons) )
2298  return SCIP_OKAY;
2299 
2300  /* otherwise construct a linear constraint */
2301  SCIP_CALL( SCIPallocBufferArray(scip, &linvars, 1) );
2302  SCIP_CALL( SCIPallocBufferArray(scip, &linvals, 1) );
2303  linvars[0] = var;
2304  linvals[0] = scalar;
2305  nlinvars = 1;
2306  linlhs = -SCIPinfinity(scip);
2307  linrhs = constant;
2308  }
2309  else
2310  {
2311  /* exit if linear constraint is not active */
2312  if ( ! SCIPconsIsActive(lincons) && slackvar != NULL )
2313  return SCIP_OKAY;
2314 
2315  /* in this case, the linear constraint is directly usable */
2316  linvars = SCIPgetVarsLinear(scip, lincons);
2317  linvals = SCIPgetValsLinear(scip, lincons);
2318  nlinvars = SCIPgetNVarsLinear(scip, lincons);
2319  linlhs = SCIPgetLhsLinear(scip, lincons);
2320  linrhs = SCIPgetRhsLinear(scip, lincons);
2321  }
2322 
2323  /* create column */
2324  if ( SCIPisEQ(scip, linlhs, linrhs) )
2325  {
2326  /* create free variable for equations (should only happen for additional linear constraints) */
2327  SCIP_CALL( addAltLPColumn(scip, conshdlr, conshdlrdata, slackvar, nlinvars, linvars, linvals, linrhs, objcoef, 1.0, TRUE, colindex) );
2328  }
2329  else if ( ! SCIPisInfinity(scip, linrhs) )
2330  {
2331  /* create column for rhs */
2332  SCIP_CALL( addAltLPColumn(scip, conshdlr, conshdlrdata, slackvar, nlinvars, linvars, linvals, linrhs, objcoef, 1.0, FALSE, colindex) );
2333  }
2334  else
2335  {
2336  /* create column for lhs */
2337  assert( ! SCIPisInfinity(scip, -linlhs) );
2338  SCIP_CALL( addAltLPColumn(scip, conshdlr, conshdlrdata, slackvar, nlinvars, linvars, linvals, linlhs, objcoef, -1.0, FALSE, colindex) );
2339  }
2340 
2341  if ( slackvar != NULL && SCIPvarGetStatus(slackvar) == SCIP_VARSTATUS_AGGREGATED )
2342  {
2343  SCIPfreeBufferArray(scip, &linvals);
2344  SCIPfreeBufferArray(scip, &linvars);
2345  }
2346 
2347  return SCIP_OKAY;
2348 }
2349 
2350 
2351 /** add column corresponding to row to alternative LP
2352  *
2353  * See the description at the top of the file for more information.
2354  */
2355 static
2357  SCIP* scip, /**< SCIP pointer */
2358  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
2359  SCIP_ROW* row, /**< row to add */
2360  SCIP_Real objcoef, /**< objective coefficient */
2361  int* colindex /**< index of new column */
2362  )
2363 {
2364  SCIP_CONSHDLRDATA* conshdlrdata;
2365  SCIP_COL** rowcols;
2366  SCIP_Real* rowvals;
2367  SCIP_VAR** rowvars;
2368  SCIP_Real rowrhs;
2369  SCIP_Real rowlhs;
2370  int nrowcols;
2371  int j;
2372 
2373  assert( scip != NULL );
2374  assert( conshdlr != NULL );
2375  assert( row != NULL );
2376  assert( colindex != NULL );
2377  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2378 
2379  /* initialize data */
2380  *colindex = -1;
2381 
2382  /* exit if row is not global */
2383  if ( SCIProwIsLocal(row) )
2384  return SCIP_OKAY;
2385 
2386  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2387  assert( conshdlrdata != NULL );
2388 
2389  /* get row data */
2390  rowcols = SCIProwGetCols(row);
2391  rowvals = SCIProwGetVals(row);
2392  nrowcols = SCIProwGetNNonz(row);
2393  rowlhs = SCIProwGetLhs(row) - SCIProwGetConstant(row);
2394  rowrhs = SCIProwGetRhs(row) - SCIProwGetConstant(row);
2395 
2396  SCIP_CALL( SCIPallocBufferArray(scip, &rowvars, nrowcols) );
2397  for (j = 0; j < nrowcols; ++j)
2398  {
2399  rowvars[j] = SCIPcolGetVar(rowcols[j]);
2400  assert( rowvars[j] != NULL );
2401  }
2402 
2403  /* create column */
2404  if ( SCIPisEQ(scip, rowlhs, rowrhs) )
2405  {
2406  /* create free variable for equations (should only happen for additional linear constraints) */
2407  SCIP_CALL( addAltLPColumn(scip, conshdlr, conshdlrdata, NULL, nrowcols, rowvars, rowvals, rowrhs, objcoef, 1.0, TRUE, colindex) );
2408  }
2409  else if ( ! SCIPisInfinity(scip, rowrhs) )
2410  {
2411  /* create column for rhs */
2412  SCIP_CALL( addAltLPColumn(scip, conshdlr, conshdlrdata, NULL, nrowcols, rowvars, rowvals, rowrhs, objcoef, 1.0, FALSE, colindex) );
2413  }
2414  else
2415  {
2416  /* create column for lhs */
2417  assert( ! SCIPisInfinity(scip, -rowlhs) );
2418  SCIP_CALL( addAltLPColumn(scip, conshdlr, conshdlrdata, NULL, nrowcols, rowvars, rowvals, rowlhs, objcoef, -1.0, FALSE, colindex) );
2419  }
2420 
2421  SCIPfreeBufferArray(scip, &rowvars);
2422 
2423  return SCIP_OKAY;
2424 }
2425 
2426 
2427 /** try to add objective cut as column to alternative LP */
2428 static
2430  SCIP* scip, /**< SCIP pointer */
2431  SCIP_CONSHDLR* conshdlr /**< constraint handler */
2432  )
2433 {
2434  SCIP_CONSHDLRDATA* conshdlrdata;
2435  SCIP_VAR** objvars;
2436  SCIP_Real* objvals;
2437  SCIP_VAR** vars;
2438  int nobjvars = 0;
2439  int nvars;
2440  int v;
2441 
2442  assert( scip != NULL );
2443  assert( conshdlr != NULL );
2444  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2445 
2446  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2447  assert( conshdlrdata != NULL );
2448 
2449  /* skip procedure if already added */
2450  if ( conshdlrdata->objcutindex >= 0 )
2451  return SCIP_OKAY;
2452 
2453  /* check whether we can add objective cut: all indicator variables have zero objective */
2454  if ( ! conshdlrdata->objothervarsonly )
2455  return SCIP_OKAY;
2456 
2457  assert( ! SCIPisInfinity(scip, conshdlrdata->objupperbound) );
2458  SCIPdebugMsg(scip, "Add objective cut to alternative LP (obj. bound: %g).\n", conshdlrdata->objupperbound);
2459 
2460  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, NULL, NULL, NULL, NULL) );
2461  SCIP_CALL( SCIPallocBufferArray(scip, &objvars, nvars) );
2462  SCIP_CALL( SCIPallocBufferArray(scip, &objvals, nvars) );
2463 
2464  /* collect nonzeros */
2465  for (v = 0; v < nvars; ++v)
2466  {
2467  SCIP_VAR* var;
2468  SCIP_Real objval;
2469 
2470  var = vars[v];
2471  assert( var != NULL );
2472  objval = SCIPvarGetObj(var);
2473 
2474  /* skip variables with zero objective - this includes slack and indicator variables */
2475  if ( ! SCIPisZero(scip, objval) )
2476  {
2477  objvars[nobjvars] = var;
2478  objvals[nobjvars++] = objval;
2479  }
2480  }
2481 
2482  /* create column (with rhs = upperbound, objective 0, and scaling factor 1.0) */
2483  SCIP_CALL( addAltLPColumn(scip, conshdlr, conshdlrdata, NULL, nobjvars, objvars, objvals, conshdlrdata->objupperbound, 0.0, 1.0, FALSE, &conshdlrdata->objcutindex) );
2484  assert( conshdlrdata->objcutindex >= 0 );
2485  conshdlrdata->objaltlpbound = conshdlrdata->objupperbound;
2486 
2487  SCIPfreeBufferArray(scip, &objvals);
2488  SCIPfreeBufferArray(scip, &objvars);
2489 
2490  return SCIP_OKAY;
2491 }
2492 
2493 
2494 /** delete column corresponding to constraint in alternative LP
2495  *
2496  * We currently just fix the corresponding variable to 0.
2497  */
2498 static
2500  SCIP* scip, /**< SCIP pointer */
2501  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
2502  SCIP_CONS* cons /**< indicator constraint */
2503  )
2504 {
2505  SCIP_CONSHDLRDATA* conshdlrdata;
2506 
2507  assert( scip != NULL );
2508  assert( conshdlr != NULL );
2509  assert( cons != NULL );
2510  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2511 
2512  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2513  assert( conshdlrdata != NULL );
2514 
2515  if ( conshdlrdata->altlp != NULL )
2516  {
2517  SCIP_CONSDATA* consdata;
2518 
2519  consdata = SCIPconsGetData(cons);
2520  assert( consdata != NULL );
2521 
2522  if ( consdata->colindex >= 0 )
2523  {
2524  SCIP_CALL( fixAltLPVariable(conshdlrdata->altlp, consdata->colindex) );
2525  }
2526  consdata->colindex = -1;
2527 
2528  SCIPdebugMsg(scip, "Fixed variable for column %d (constraint: <%s>) from alternative LP to 0.\n", consdata->colindex, SCIPconsGetName(cons));
2529  }
2530  conshdlrdata->scaled = FALSE;
2531 
2532  return SCIP_OKAY;
2533 }
2534 
2535 
2536 /** update upper bound in alternative LP */
2537 static
2539  SCIP* scip, /**< SCIP pointer */
2540  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
2541  SCIP_CONSHDLRDATA* conshdlrdata /**< constraint handler data */
2542  )
2543 {
2544  SCIP_Real objbnd;
2545 
2546  assert( scip != NULL );
2547  assert( conshdlrdata != NULL );
2548 
2549  if ( ! conshdlrdata->useobjectivecut )
2550  return SCIP_OKAY;
2551 
2552  if ( conshdlrdata->altlp == NULL )
2553  return SCIP_OKAY;
2554 
2555  /* first check whether we can improve the upper bound */
2556  objbnd = SCIPgetUpperbound(scip);
2557  if ( ! SCIPisInfinity(scip, objbnd) )
2558  {
2559  if ( SCIPisObjIntegral(scip) )
2560  objbnd = SCIPfeasCeil(scip, objbnd) - (1.0 - SCIPcutoffbounddelta(scip));
2561  else
2562  objbnd -= SCIPcutoffbounddelta(scip);
2563 
2564  if ( SCIPisLT(scip, objbnd, conshdlrdata->objupperbound) )
2565  conshdlrdata->objupperbound = objbnd;
2566  }
2567 
2568  if ( SCIPisInfinity(scip, conshdlrdata->objupperbound) )
2569  return SCIP_OKAY;
2570 
2571  /* if we can improve on the bound stored in the alternative LP */
2572  if ( SCIPisLT(scip, conshdlrdata->objupperbound, conshdlrdata->objaltlpbound) )
2573  {
2574  SCIPdebugMsg(scip, "Update objective bound to %g.\n", conshdlrdata->objupperbound);
2575 
2576  /* possibly add column for objective cut */
2577  if ( conshdlrdata->objcutindex < 0 )
2578  {
2579  SCIP_CALL( addObjcut(scip, conshdlr) );
2580  }
2581  else
2582  {
2583 #ifndef NDEBUG
2584  SCIP_Real oldbnd;
2585  SCIP_CALL( SCIPlpiGetCoef(conshdlrdata->altlp, 0, conshdlrdata->objcutindex, &oldbnd) );
2586  assert( SCIPisEQ(scip, oldbnd, conshdlrdata->objaltlpbound) );
2587 #endif
2588 
2589  /* update bound */
2590  SCIP_CALL( SCIPlpiChgCoef(conshdlrdata->altlp, 0, conshdlrdata->objcutindex, conshdlrdata->objupperbound) );
2591  conshdlrdata->objaltlpbound = conshdlrdata->objupperbound;
2592 
2593 #ifdef SCIP_OUTPUT
2594  SCIP_CALL( SCIPlpiWriteLP(conshdlrdata->altlp, "alt.lp") );
2595 #endif
2596  }
2597  }
2598 
2599  return SCIP_OKAY;
2600 }
2601 
2602 
2603 /** check whether the given LP is infeasible
2604  *
2605  * If @a primal is false we assume that the problem is <em>dual feasible</em>, e.g., the problem
2606  * was only changed by fixing bounds!
2607  *
2608  * This is the workhorse for all methods that have to solve the alternative LP. We try in several
2609  * ways to recover from possible stability problems.
2610  *
2611  * @pre It is assumed that all parameters for the alternative LP are set.
2612  */
2613 static
2615  SCIP* scip, /**< SCIP pointer */
2616  SCIP_LPI* lp, /**< LP */
2617  SCIP_Real maxcondition, /**< maximal allowed condition of LP solution basis matrix */
2618  SCIP_Bool primal, /**< whether we are using the primal or dual simplex */
2619  SCIP_Bool* infeasible, /**< output: whether the LP is infeasible */
2620  SCIP_Bool* error /**< output: whether an error occurred */
2621  )
2622 {
2623  SCIP_RETCODE retcode;
2624  SCIP_Real condition;
2625 
2626  assert( scip != NULL );
2627  assert( lp != NULL );
2628  assert( infeasible != NULL );
2629  assert( error != NULL );
2630 
2631  *error = FALSE;
2632 
2633  /* solve LP */
2634  if ( primal )
2635  retcode = SCIPlpiSolvePrimal(lp); /* use primal simplex */
2636  else
2637  retcode = SCIPlpiSolveDual(lp); /* use dual simplex */
2638  if ( retcode == SCIP_LPERROR )
2639  {
2640  *error = TRUE;
2641  return SCIP_OKAY;
2642  }
2643  SCIP_CALL( retcode );
2644 
2645  /* resolve if LP is not stable */
2646  if ( ! SCIPlpiIsStable(lp) )
2647  {
2650  SCIPwarningMessage(scip, "Numerical problems, retrying ...\n");
2651 
2652  /* re-solve LP */
2653  if ( primal )
2654  retcode = SCIPlpiSolvePrimal(lp); /* use primal simplex */
2655  else
2656  retcode = SCIPlpiSolveDual(lp); /* use dual simplex */
2657 
2658  /* reset parameters */
2661 
2662  if ( retcode == SCIP_LPERROR )
2663  {
2664  *error = TRUE;
2665  return SCIP_OKAY;
2666  }
2667  SCIP_CALL( retcode );
2668  }
2669 
2670  /* check whether we want to ignore the result, because the condition number is too large */
2671  if ( maxcondition > 0.0 )
2672  {
2673  /* check estimated condition number of basis matrix */
2675  if ( condition != SCIP_INVALID && condition > maxcondition ) /*lint !e777*/
2676  {
2677  SCIPdebugMsg(scip, "Estimated condition number of basis matrix (%e) exceeds maximal allowance (%e).\n", condition, maxcondition);
2678 
2679  *error = TRUE;
2680 
2681  return SCIP_OKAY;
2682  }
2683  else if ( condition != SCIP_INVALID ) /*lint !e777*/
2684  {
2685  SCIPdebugMsg(scip, "Estimated condition number of basis matrix (%e) is below maximal allowance (%e).\n", condition, maxcondition);
2686  }
2687  else
2688  {
2689  SCIPdebugMsg(scip, "Estimated condition number of basis matrix not available.\n");
2690  }
2691  }
2692 
2693  /* check whether we are in the paradoxical situation that
2694  * - the primal is not infeasible
2695  * - the primal is not unbounded
2696  * - the LP is not optimal
2697  * - we have a primal ray
2698  *
2699  * If we ran the dual simplex algorithm, then we run again with the primal simplex
2700  */
2702  ! SCIPlpiIsOptimal(lp) && SCIPlpiExistsPrimalRay(lp) && ! primal )
2703  {
2704  SCIPwarningMessage(scip, "The dual simplex produced a primal ray. Retrying with primal ...\n");
2705 
2706  /* the following settings might be changed: */
2710 
2711  SCIP_CALL( SCIPlpiSolvePrimal(lp) ); /* use primal simplex */
2712 
2713  /* reset parameters */
2717  }
2718 
2719  /* examine LP solution status */
2720  if ( SCIPlpiIsPrimalInfeasible(lp) ) /* the LP is provably infeasible */
2721  {
2722  assert( ! SCIPlpiIsPrimalUnbounded(lp) ); /* can't be unbounded or optimal */
2723  assert( ! SCIPlpiIsOptimal(lp) ); /* if it is infeasible! */
2724 
2725  *infeasible = TRUE; /* LP is infeasible */
2726  return SCIP_OKAY;
2727  }
2728  else
2729  {
2730  /* By assumption the dual is feasible if the dual simplex is run, therefore
2731  * the status has to be primal unbounded or optimal. */
2732  if ( ! SCIPlpiIsPrimalUnbounded(lp) && ! SCIPlpiIsOptimal(lp) )
2733  {
2734  /* We have a status different from unbounded or optimal. This should not be the case ... */
2735  if (primal)
2736  SCIPwarningMessage(scip, "Primal simplex returned with unknown status: %d\n", SCIPlpiGetInternalStatus(lp));
2737  else
2738  SCIPwarningMessage(scip, "Dual simplex returned with unknown status: %d\n", SCIPlpiGetInternalStatus(lp));
2739 
2740  /* SCIP_CALL( SCIPlpiWriteLP(lp, "debug.lp") ); */
2741  *error = TRUE;
2742  return SCIP_OKAY;
2743  }
2744  }
2745 
2746  /* at this point we have a feasible solution */
2747  *infeasible = FALSE;
2748  return SCIP_OKAY;
2749 }
2750 
2751 
2752 /** tries to extend a given set of variables to a cover
2753  *
2754  * At each step we include a variable which covers a new IIS. The corresponding IIS inequalities are added to the LP,
2755  * if this not already happened.
2756  *
2757  * @pre It is assumed that all parameters for the alternative LP are set and that the variables
2758  * corresponding to @a S are fixed. Furthermore @c xVal_ should contain the current LP solution.
2759  */
2760 static
2762  SCIP* scip, /**< SCIP pointer */
2763  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
2764  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
2765  SCIP_LPI* lp, /**< LP */
2766  SCIP_SOL* sol, /**< solution to be separated */
2767  SCIP_Bool removable, /**< whether cuts should be removable */
2768  SCIP_Bool genlogicor, /**< should logicor constraints be generated? */
2769  int nconss, /**< number of constraints */
2770  SCIP_CONS** conss, /**< indicator constraints */
2771  SCIP_Bool* S, /**< bitset of variables */
2772  int* size, /**< size of S */
2773  SCIP_Real* value, /**< objective value of S */
2774  SCIP_Bool* error, /**< output: whether an error occurred */
2775  SCIP_Bool* cutoff, /**< whether we detected a cutoff by an infeasible inequality */
2776  int* nGen /**< number of generated cuts */
2777  )
2778 {
2779 #ifdef SCIP_DEBUG
2780  char name[SCIP_MAXSTRLEN];
2781 #endif
2782  SCIP_Real* primsol;
2783  int nnonviolated = 0;
2784  int step = 0;
2785  int nCols;
2786 
2787  assert( scip != NULL );
2788  assert( lp != NULL );
2789  assert( conss != NULL );
2790  assert( S != NULL );
2791  assert( size != NULL );
2792  assert( value != NULL );
2793  assert( error != NULL );
2794  assert( cutoff != NULL );
2795  assert( nGen != NULL );
2796 
2797  *error = FALSE;
2798  *cutoff = FALSE;
2799  *nGen = 0;
2800 
2801  SCIP_CALL( SCIPlpiGetNCols(lp, &nCols) );
2802  SCIP_CALL( SCIPallocBufferArray(scip, &primsol, nCols) );
2803  assert( nconss <= nCols );
2804 
2805  do
2806  {
2807  SCIP_Bool infeasible;
2808  SCIP_Real sum = 0.0;
2809  SCIP_Real candobj = -1.0;
2810  SCIP_Real candval = 2.0;
2811  SCIP_Real norm = 1.0;
2812  int sizeIIS = 0;
2813  int candidate = -1;
2814  int candindex = -1;
2815  int j;
2816 
2817  if ( step == 0 )
2818  {
2819  /* the first LP is solved without warm start, after that we use a warmstart. */
2821  SCIP_CALL( checkAltLPInfeasible(scip, lp, conshdlrdata->maxconditionaltlp, TRUE, &infeasible, error) );
2823  }
2824  else
2825  SCIP_CALL( checkAltLPInfeasible(scip, lp, conshdlrdata->maxconditionaltlp, FALSE, &infeasible, error) );
2826 
2827  if ( *error )
2828  break;
2829 
2830  /* if the alternative polyhedron is infeasible, we found a cover */
2831  if ( infeasible )
2832  {
2833  /* Note: checking for a primal solution is done in extendToCover(). */
2834  SCIPdebugMsg(scip, " size: %4d produced possible cover with indicator variable objective value %f.\n", *size, *value);
2835 
2836  /* we currently cannot call probing if there are cuts in the sepastore; @todo fix this */
2837  if ( conshdlrdata->trysolfromcover )
2838  {
2839  /* Check whether we want to try to construct a feasible solution: there should be no integer/binary variables
2840  * except the indicator variables. Thus, there should be no integral variables and the number of indicator
2841  * variables should be at least (actually equal to) the number of binary variables. */
2842  if ( SCIPgetNIntVars(scip) == 0 && nconss >= SCIPgetNBinVars(scip) )
2843  {
2844  SCIP_HEUR* heurindicator;
2845 
2846  heurindicator = SCIPfindHeur(scip, "indicator");
2847  if ( heurindicator == NULL )
2848  {
2849  SCIPerrorMessage("Could not find heuristic \"indicator\".\n");
2850  return SCIP_PLUGINNOTFOUND;
2851  }
2852 
2853  SCIP_CALL( SCIPheurPassIndicator(scip, heurindicator, nconss, conss, S, -*value) );
2854  SCIPdebugMsg(scip, "Passed feasible solution to indicator heuristic.\n");
2855  }
2856  }
2857  break;
2858  }
2859 
2860  /* get solution of alternative LP */
2861  SCIP_CALL( SCIPlpiGetSol(lp, NULL, primsol, NULL, NULL, NULL) );
2862 
2863  /* get value of cut and find candidate for variable to add */
2864  for (j = 0; j < nconss; ++j)
2865  {
2866  SCIP_CONSDATA* consdata;
2867  int ind;
2868 
2869  consdata = SCIPconsGetData(conss[j]);
2870  assert( consdata != NULL );
2871  ind = consdata->colindex;
2872 
2873  if ( ind >= 0 )
2874  {
2875  assert( ind < nCols );
2876 
2877  /* check support of the solution, i.e., the corresponding IIS */
2878  if ( ! SCIPisFeasZero(scip, primsol[ind]) )
2879  {
2880  SCIP_Real val;
2881 
2882  assert( ! S[j] );
2883  ++sizeIIS;
2884  val = SCIPgetSolVal(scip, sol, consdata->binvar);
2885  sum += val;
2886 
2887  /* take element with smallest relaxation value */
2888  if ( val < candval )
2889  {
2890  candidate = j;
2891  candindex = ind;
2892  candval = val;
2893  candobj = varGetObjDelta(consdata->binvar);
2894  }
2895  }
2896  }
2897  }
2898 
2899  /* check for error */
2900  if ( candidate < 0 )
2901  {
2902  /* Because of numerical problems it might happen that the solution primsol above is zero
2903  * within the tolerances. In this case we quit. */
2904  break;
2905  }
2906  assert( candidate >= 0 );
2907  assert( ! S[candidate] );
2908  assert( sizeIIS > 0 );
2909 
2910  /* get the type of norm to use for efficacy calculations */
2911  switch ( conshdlrdata->normtype )
2912  {
2913  case 'e':
2914  norm = sqrt((SCIP_Real) sizeIIS);
2915  break;
2916  case 'm':
2917  norm = 1.0;
2918  break;
2919  case 's':
2920  norm = (SCIP_Real) sizeIIS;
2921  break;
2922  case 'd':
2923  norm = 1.0;
2924  break;
2925  default:
2926  SCIPerrorMessage("Invalid efficacy norm parameter '%c'.\n", conshdlrdata->normtype);
2927  SCIPABORT();
2928  norm = 1.0; /*lint !e527*/
2929  }
2930 
2931  SCIPdebugMsg(scip, " size: %4d, add var. %4d (obj: %-6g, alt-LP sol: %-8.4f); IIS size: %4d, eff.: %g.\n",
2932  *size, candidate, candobj, primsol[SCIPconsGetData(conss[candidate])->colindex], sizeIIS, (sum - (SCIP_Real) (sizeIIS - 1))/norm);
2933 
2934  /* update new set S */
2935  S[candidate] = TRUE;
2936  ++(*size);
2937  *value += candobj;
2938 
2939  /* fix chosen variable to 0 */
2940  SCIP_CALL( fixAltLPVariable(lp, candindex) );
2941 
2942  /* if cut is violated, i.e., sum - sizeIIS + 1 > 0 */
2943  if ( SCIPisEfficacious(scip, (sum - (SCIP_Real) (sizeIIS - 1))/norm) )
2944  {
2945  SCIP_Bool isLocal = FALSE;
2946 
2947 #ifdef SCIP_ENABLE_IISCHECK
2948  /* check whether we really have an infeasible subsystem */
2949  SCIP_CALL( checkIIS(scip, nconss, conss, primsol) );
2950 #endif
2951 
2952  /* check whether IIS corresponds to a local cut */
2953  if ( conshdlrdata->updatebounds )
2954  {
2955  SCIP_CALL( checkIISlocal(scip, conshdlrdata, primsol, &isLocal) );
2956  }
2957 
2958  if ( genlogicor )
2959  {
2960  SCIP_CONS* cons;
2961  SCIP_VAR** vars;
2962  int cnt = 0;
2963 
2964  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nconss) );
2965 
2966  /* collect variables corresponding to support to cut */
2967  for (j = 0; j < nconss; ++j)
2968  {
2969  SCIP_CONSDATA* consdata;
2970  int ind;
2971 
2972  consdata = SCIPconsGetData(conss[j]);
2973  ind = consdata->colindex;
2974 
2975  if ( ind >= 0 )
2976  {
2977  assert( ind < nCols );
2978  assert( consdata->binvar != NULL );
2979 
2980  /* check support of the solution, i.e., the corresponding IIS */
2981  if ( ! SCIPisFeasZero(scip, primsol[ind]) )
2982  {
2983  SCIP_VAR* var;
2984  SCIP_CALL( SCIPgetNegatedVar(scip, consdata->binvar, &var) );
2985  vars[cnt++] = var;
2986  }
2987  }
2988  }
2989  assert( cnt == sizeIIS );
2990 
2991 #ifdef SCIP_DEBUG
2992  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "iis%d", conshdlrdata->niiscutsgen + *nGen);
2993  SCIP_CALL( SCIPcreateConsLogicor(scip, &cons, name, cnt, vars, FALSE, TRUE, TRUE, TRUE, TRUE, isLocal, FALSE, TRUE, removable, FALSE) );
2994 #else
2995  SCIP_CALL( SCIPcreateConsLogicor(scip, &cons, "", cnt, vars, FALSE, TRUE, TRUE, TRUE, TRUE, isLocal, FALSE, TRUE, removable, FALSE) );
2996 #endif
2997 
2998 #ifdef SCIP_OUTPUT
2999  SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
3000  SCIPinfoMessage(scip, NULL, ";\n");
3001 #endif
3002 
3003  SCIP_CALL( SCIPaddCons(scip, cons) );
3004  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
3005 
3006  SCIPfreeBufferArray(scip, &vars);
3007  ++(*nGen);
3008  }
3009  else
3010  {
3011  SCIP_ROW* row;
3012 
3013  /* create row */
3014 #ifdef SCIP_DEBUG
3015  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "iis%d", conshdlrdata->niiscutsgen + *nGen);
3016  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, conshdlr, name, -SCIPinfinity(scip), (SCIP_Real) (sizeIIS - 1), isLocal, FALSE, removable) );
3017 #else
3018  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, conshdlr, "", -SCIPinfinity(scip), (SCIP_Real) (sizeIIS - 1), isLocal, FALSE, removable) );
3019 #endif
3020  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
3021 
3022  /* add variables corresponding to support to cut */
3023  for (j = 0; j < nconss; ++j)
3024  {
3025  int ind;
3026  SCIP_CONSDATA* consdata;
3027 
3028  consdata = SCIPconsGetData(conss[j]);
3029  ind = consdata->colindex;
3030 
3031  if ( ind >= 0 )
3032  {
3033  assert( ind < nCols );
3034  assert( consdata->binvar != NULL );
3035 
3036  /* check support of the solution, i.e., the corresponding IIS */
3037  if ( ! SCIPisFeasZero(scip, primsol[ind]) )
3038  {
3039  SCIP_VAR* var = consdata->binvar;
3040  SCIP_CALL( SCIPaddVarToRow(scip, row, var, 1.0) );
3041  }
3042  }
3043  }
3044  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
3045 #ifdef SCIP_OUTPUT
3046  SCIP_CALL( SCIPprintRow(scip, row, NULL) );
3047 #endif
3048  SCIP_CALL( SCIPaddRow(scip, row, FALSE, cutoff) );
3049  if ( *cutoff )
3050  {
3051  SCIPfreeBufferArray(scip, &primsol);
3052  return SCIP_OKAY;
3053  }
3054 
3055  /* cut should be violated: */
3056  assert( SCIPisFeasNegative(scip, SCIPgetRowSolFeasibility(scip, row, sol)) );
3057 
3058  /* add cuts to pool if they are globally valid */
3059  if ( ! isLocal )
3060  SCIP_CALL( SCIPaddPoolCut(scip, row) );
3061  SCIP_CALL( SCIPreleaseRow(scip, &row));
3062  ++(*nGen);
3063  }
3064  nnonviolated = 0;
3065  }
3066  else
3067  ++nnonviolated;
3068  ++step;
3069 
3070  if ( nnonviolated > conshdlrdata->maxsepanonviolated )
3071  {
3072  SCIPdebugMsg(scip, "Stop separation after %d non violated IISs.\n", nnonviolated);
3073  break;
3074  }
3075  }
3076  while (step < nconss);
3077 
3078  SCIPfreeBufferArray(scip, &primsol);
3079 
3080  return SCIP_OKAY;
3081 }
3082 
3083 
3084 /* ---------------------------- constraint handler local methods ----------------------*/
3085 
3086 /** creates and initializes consdata */
3087 static
3089  SCIP* scip, /**< SCIP data structure */
3090  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
3091  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
3092  const char* consname, /**< name of constraint (or NULL) */
3093  SCIP_CONSDATA** consdata, /**< pointer to linear constraint data */
3094  SCIP_EVENTHDLR* eventhdlrbound, /**< event handler for bound change events */
3095  SCIP_EVENTHDLR* eventhdlrrestart, /**< event handler for handling restarts */
3096  SCIP_VAR* binvar, /**< binary variable (or NULL) */
3097  SCIP_VAR* slackvar, /**< slack variable */
3098  SCIP_CONS* lincons, /**< linear constraint (or NULL) */
3099  SCIP_Bool linconsactive /**< whether the linear constraint is active */
3100  )
3101 {
3102  assert( scip != NULL );
3103  assert( conshdlr != NULL );
3104  assert( conshdlrdata != NULL );
3105  assert( consdata != NULL );
3106  assert( slackvar != NULL );
3107  assert( eventhdlrbound != NULL );
3108  assert( eventhdlrrestart != NULL );
3109 
3110  /* create constraint data */
3111  SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
3112  (*consdata)->nfixednonzero = 0;
3113  (*consdata)->colindex = -1;
3114  (*consdata)->linconsactive = linconsactive;
3115  (*consdata)->binvar = binvar;
3116  (*consdata)->slackvar = slackvar;
3117  (*consdata)->lincons = lincons;
3118  (*consdata)->implicationadded = FALSE;
3119  (*consdata)->slacktypechecked = FALSE;
3120 
3121  /* if we are transformed, obtain transformed variables and catch events */
3122  if ( SCIPisTransformed(scip) )
3123  {
3124  SCIP_VAR* var;
3125 
3126  /* handle binary variable */
3127  if ( binvar != NULL )
3128  {
3129  SCIP_CALL( SCIPgetTransformedVar(scip, binvar, &var) );
3130  assert( var != NULL );
3131  (*consdata)->binvar = var;
3132 
3133  /* check type */
3134  if ( SCIPvarGetType(var) != SCIP_VARTYPE_BINARY )
3135  {
3136  SCIPerrorMessage("Indicator variable <%s> is not binary %d.\n", SCIPvarGetName(var), SCIPvarGetType(var));
3137  return SCIP_ERROR;
3138  }
3139 
3140  /* catch local bound change events on binary variable */
3141  if ( linconsactive )
3142  {
3143  SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlrbound, (SCIP_EVENTDATA*)*consdata, NULL) );
3144  }
3145 
3146  /* catch global bound change events on binary variable */
3147  if ( conshdlrdata->forcerestart )
3148  {
3149  SCIPdebugMsg(scip, "Catching GBDCHANGED event for <%s>.\n", SCIPvarGetName(var));
3150  SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_GBDCHANGED, eventhdlrrestart, (SCIP_EVENTDATA*) conshdlrdata, NULL) );
3151  }
3152 
3153  /* if binary variable is fixed to be nonzero */
3154  if ( SCIPvarGetLbLocal(var) > 0.5 )
3155  ++((*consdata)->nfixednonzero);
3156  }
3157 
3158  /* handle slack variable */
3159  SCIP_CALL( SCIPgetTransformedVar(scip, slackvar, &var) );
3160  assert( var != NULL );
3161  (*consdata)->slackvar = var;
3162 
3163  /* catch bound change events on slack variable and adjust nfixednonzero */
3164  if ( linconsactive )
3165  {
3166  SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlrbound, (SCIP_EVENTDATA*)*consdata, NULL) );
3167 
3168  /* if slack variable is fixed to be nonzero */
3169  if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var)) )
3170  ++((*consdata)->nfixednonzero);
3171  }
3172 
3173  /* add corresponding column to alternative LP if the constraint is new */
3174  if ( conshdlrdata->sepaalternativelp && SCIPgetStage(scip) >= SCIP_STAGE_INITSOLVE && lincons != NULL )
3175  {
3176  assert( lincons != NULL );
3177  assert( consname != NULL );
3178 
3179  SCIP_CALL( addAltLPConstraint(scip, conshdlr, lincons, var, 1.0, &(*consdata)->colindex) );
3180 
3181  SCIPdebugMsg(scip, "Added column for <%s> to alternative LP with column index %d.\n", consname, (*consdata)->colindex);
3182 #ifdef SCIP_OUTPUT
3183  SCIP_CALL( SCIPprintCons(scip, lincons, NULL) );
3184  SCIPinfoMessage(scip, NULL, ";\n");
3185 #endif
3186  }
3187 
3188 #ifdef SCIP_DEBUG
3189  if ( (*consdata)->nfixednonzero > 0 )
3190  {
3191  SCIPdebugMsg(scip, "Constraint <%s> has %d variables fixed to be nonzero.\n", consname, (*consdata)->nfixednonzero);
3192  }
3193 #endif
3194  }
3195 
3196  return SCIP_OKAY;
3197 }
3198 
3199 
3200 /** create variable upper bounds for constraints */
3201 static
3203  SCIP* scip, /**< SCIP pointer */
3204  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
3205  SCIP_CONS** conss, /**< constraints */
3206  int nconss, /**< number of constraints */
3207  int* ngen /**< number of successful operations */
3208  )
3209 {
3210  char name[50];
3211  int c;
3212 
3213  assert( scip != NULL );
3214  assert( conshdlrdata != NULL );
3215  assert( ngen != NULL );
3216 
3217  *ngen = 0;
3218 
3219  /* check each constraint */
3220  for (c = 0; c < nconss; ++c)
3221  {
3222  SCIP_CONSDATA* consdata;
3223  SCIP_Real ub;
3224 
3225  consdata = SCIPconsGetData(conss[c]);
3226  assert( consdata != NULL );
3227 
3228  ub = SCIPvarGetUbGlobal(consdata->slackvar);
3229  assert( ! SCIPisNegative(scip, ub) );
3230 
3231  /* insert corresponding row if helpful and coefficient is not too large */
3232  if ( ub <= conshdlrdata->maxcouplingvalue )
3233  {
3234  SCIP_CONS* cons;
3235 
3236 #ifndef NDEBUG
3237  (void) SCIPsnprintf(name, 50, "couple%d", c);
3238 #else
3239  name[0] = '\0';
3240 #endif
3241 
3242  SCIPdebugMsg(scip, "Insert coupling varbound constraint for indicator constraint <%s> (coeff: %f).\n", SCIPconsGetName(conss[c]), ub);
3243 
3244  /* add variable upper bound:
3245  * - check constraint if we remove the indicator constraint afterwards
3246  * - constraint is dynamic if we do not remove indicator constraints
3247  * - constraint is removable if we do not remove indicator constraints
3248  */
3249  SCIP_CALL( SCIPcreateConsVarbound(scip, &cons, name, consdata->slackvar, consdata->binvar, ub, -SCIPinfinity(scip), ub,
3250  TRUE, TRUE, TRUE, conshdlrdata->removeindicators, TRUE, FALSE, FALSE,
3251  !conshdlrdata->removeindicators, !conshdlrdata->removeindicators, FALSE) );
3252 
3253  SCIP_CALL( SCIPaddCons(scip, cons) );
3254  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
3255 
3256  /* remove indicator constraint if required */
3257  if ( conshdlrdata->removeindicators )
3258  {
3259  SCIPdebugMsg(scip, "Removing indicator constraint <%s>.\n", SCIPconsGetName(conss[c]));
3260  assert( ! SCIPconsIsModifiable(conss[c]) );
3261 
3262  /* mark linear constraint to be upgrade-able */
3263  if ( SCIPconsIsActive(consdata->lincons) )
3264  {
3265  SCIPconsAddUpgradeLocks(consdata->lincons, -1);
3266  assert( SCIPconsGetNUpgradeLocks(consdata->lincons) == 0 );
3267  }
3268 
3269  SCIP_CALL( SCIPdelCons(scip, conss[c]) );
3270  }
3271 
3272  ++(*ngen);
3273  }
3274  }
3275 
3276  return SCIP_OKAY;
3277 }
3278 
3279 
3280 /** perform one presolving round */
3281 static
3283  SCIP* scip, /**< SCIP pointer */
3284  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
3285  SCIP_CONS* cons, /**< constraint */
3286  SCIP_CONSDATA* consdata, /**< constraint data */
3287  SCIP_Bool dualreductions, /**< should dual reductions be performed? */
3288  SCIP_Bool* cutoff, /**< whether a cutoff happened */
3289  SCIP_Bool* success, /**< whether we performed a successful reduction */
3290  int* ndelconss, /**< number of deleted constraints */
3291  int* nfixedvars /**< number of fixed variables */
3292  )
3293 {
3294  SCIP_Bool infeasible;
3295  SCIP_Bool fixed;
3296 
3297  assert( scip != NULL );
3298  assert( cons != NULL );
3299  assert( consdata != NULL );
3300  assert( cutoff != NULL );
3301  assert( success != NULL );
3302  assert( ndelconss != NULL );
3303  assert( nfixedvars != NULL );
3304  assert( consdata->binvar != NULL );
3305  assert( consdata->slackvar != NULL );
3306 
3307  *cutoff = FALSE;
3308  *success = FALSE;
3309 
3310  /* if the binary variable is fixed to nonzero */
3311  if ( SCIPvarGetLbLocal(consdata->binvar) > 0.5 )
3312  {
3313  SCIPdebugMsg(scip, "Presolving <%s>: Binary variable fixed to 1.\n", SCIPconsGetName(cons));
3314 
3315  /* if slack variable is fixed to nonzero, we are infeasible */
3316  if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(consdata->slackvar)) )
3317  {
3318  SCIPdebugMsg(scip, "The problem is infeasible: binary and slack variable are fixed to be nonzero.\n");
3319  *cutoff = TRUE;
3320  return SCIP_OKAY;
3321  }
3322 
3323  /* otherwise fix slack variable to 0 */
3324  SCIPdebugMsg(scip, "Fix slack variable to 0 and delete constraint.\n");
3325  SCIP_CALL( SCIPfixVar(scip, consdata->slackvar, 0.0, &infeasible, &fixed) );
3326  assert( ! infeasible );
3327  if ( fixed )
3328  ++(*nfixedvars);
3329 
3330  /* mark linear constraint to be update-able */
3331  if ( SCIPconsIsActive(consdata->lincons) )
3332  {
3333  SCIPconsAddUpgradeLocks(consdata->lincons, -1);
3334  assert( SCIPconsGetNUpgradeLocks(consdata->lincons) == 0 );
3335  }
3336 
3337  /* delete indicator constraint (leave linear constraint) */
3338  assert( ! SCIPconsIsModifiable(cons) );
3339  SCIP_CALL( SCIPdelCons(scip, cons) );
3340  ++(*ndelconss);
3341  *success = TRUE;
3342  return SCIP_OKAY;
3343  }
3344 
3345  /* if the binary variable is fixed to zero */
3346  if ( SCIPvarGetUbLocal(consdata->binvar) < 0.5 )
3347  {
3348  SCIPdebugMsg(scip, "Presolving <%s>: Binary variable fixed to 0, deleting indicator constraint.\n", SCIPconsGetName(cons));
3349 
3350  /* mark linear constraint to be update-able */
3351  if ( SCIPconsIsActive(consdata->lincons) )
3352  {
3353  SCIPconsAddUpgradeLocks(consdata->lincons, -1);
3354  assert( SCIPconsGetNUpgradeLocks(consdata->lincons) == 0 );
3355  }
3356 
3357  /* delete indicator constraint */
3358  assert( ! SCIPconsIsModifiable(cons) );
3359  SCIP_CALL( SCIPdelCons(scip, cons) );
3360  ++(*ndelconss);
3361  *success = TRUE;
3362  return SCIP_OKAY;
3363  }
3364 
3365  /* if the slack variable is fixed to nonzero */
3366  if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(consdata->slackvar)) )
3367  {
3368  SCIPdebugMsg(scip, "Presolving <%s>: Slack variable fixed to nonzero.\n", SCIPconsGetName(cons));
3369 
3370  /* if binary variable is fixed to nonzero, we are infeasible */
3371  if ( SCIPvarGetLbLocal(consdata->binvar) > 0.5 )
3372  {
3373  SCIPdebugMsg(scip, "The problem is infeasible: binary and slack variable are fixed to be nonzero.\n");
3374  *cutoff = TRUE;
3375  return SCIP_OKAY;
3376  }
3377 
3378  /* otherwise fix binary variable to 0 */
3379  SCIPdebugMsg(scip, "Fix binary variable to 0 and delete indicator constraint.\n");
3380  SCIP_CALL( SCIPfixVar(scip, consdata->binvar, 0.0, &infeasible, &fixed) );
3381  assert( ! infeasible );
3382  if ( fixed )
3383  ++(*nfixedvars);
3384 
3385  /* mark linear constraint to be update-able */
3386  if ( SCIPconsIsActive(consdata->lincons) )
3387  {
3388  SCIPconsAddUpgradeLocks(consdata->lincons, -1);
3389  assert( SCIPconsGetNUpgradeLocks(consdata->lincons) == 0 );
3390  }
3391 
3392  /* delete constraint */
3393  assert( ! SCIPconsIsModifiable(cons) );
3394  SCIP_CALL( SCIPdelCons(scip, cons) );
3395  ++(*ndelconss);
3396  *success = TRUE;
3397  return SCIP_OKAY;
3398  }
3399 
3400  /* if the slack variable is fixed to zero */
3401  if ( SCIPisFeasZero(scip, SCIPvarGetUbLocal(consdata->slackvar)) )
3402  {
3403  /* perform dual reductions - if required */
3404  if ( dualreductions )
3405  {
3406  SCIP_VAR* binvar;
3407  SCIP_Real obj;
3408 
3409  /* check objective of binary variable */
3410  binvar = consdata->binvar;
3411  obj = varGetObjDelta(binvar);
3412 
3413  /* if obj = 0, we prefer fixing the binary variable to 1 (if possible) */
3414  if ( obj <= 0.0 )
3415  {
3416  /* In this case we would like to fix the binary variable to 1, if it is not locked up
3417  except by this indicator constraint. If more than one indicator constraint is
3418  effected, we have to hope that they are all fulfilled - in this case the last
3419  constraint will fix the binary variable to 1. */
3420  if ( SCIPvarGetNLocksUpType(binvar, SCIP_LOCKTYPE_MODEL) <= 1 )
3421  {
3422  if ( SCIPvarGetUbGlobal(binvar) > 0.5 )
3423  {
3424  SCIPdebugMsg(scip, "Presolving <%s> - dual reduction: Slack variable fixed to 0, fix binary variable to 1.\n", SCIPconsGetName(cons));
3425  SCIP_CALL( SCIPfixVar(scip, binvar, 1.0, &infeasible, &fixed) );
3426  assert( ! infeasible );
3427  if ( fixed )
3428  ++(*nfixedvars);
3429  /* make sure that the other case does not occur */
3430  obj = -1.0;
3431  }
3432  }
3433  }
3434  if ( obj >= 0.0 )
3435  {
3436  /* In this case we would like to fix the binary variable to 0, if it is not locked down
3437  (should also have been performed by other dual reductions). */
3438  if ( SCIPvarGetNLocksDownType(binvar, SCIP_LOCKTYPE_MODEL) == 0 )
3439  {
3440  if ( SCIPvarGetLbGlobal(binvar) < 0.5 )
3441  {
3442  SCIPdebugMsg(scip, "Presolving <%s> - dual reduction: Slack variable fixed to 0, fix binary variable to 0.\n", SCIPconsGetName(cons));
3443  SCIP_CALL( SCIPfixVar(scip, binvar, 0.0, &infeasible, &fixed) );
3444  assert( ! infeasible );
3445  if ( fixed )
3446  ++(*nfixedvars);
3447  }
3448  }
3449  }
3450  }
3451 
3452  SCIPdebugMsg(scip, "Presolving <%s>: Slack variable fixed to zero, delete redundant indicator constraint.\n", SCIPconsGetName(cons));
3453 
3454  /* mark linear constraint to be upgrade-able */
3455  if ( SCIPconsIsActive(consdata->lincons) )
3456  {
3457  SCIPconsAddUpgradeLocks(consdata->lincons, -1);
3458  assert( SCIPconsGetNUpgradeLocks(consdata->lincons) == 0 );
3459  }
3460 
3461  /* delete constraint */
3462  assert( ! SCIPconsIsModifiable(cons) );
3463  SCIP_CALL( SCIPdelCons(scip, cons) );
3464  ++(*ndelconss);
3465  *success = TRUE;
3466  return SCIP_OKAY;
3467  }
3468 
3469  /* check whether indicator variable is aggregated */
3470  if ( SCIPvarGetStatus(consdata->binvar) == SCIP_VARSTATUS_AGGREGATED )
3471  {
3472  SCIP_Bool negated = FALSE;
3473  SCIP_VAR* var;
3474 
3475  /* possibly get representation of indicator variable by active variable */
3476  var = consdata->binvar;
3477  SCIP_CALL( SCIPvarGetProbvarBinary(&var, &negated) );
3478  assert( var == consdata->binvar || SCIPvarIsActive(var) || SCIPvarIsNegated(var) );
3479 
3480  /* we can replace the binary variable by the active variable if it is not negated */
3481  if ( var != consdata->binvar && ! negated )
3482  {
3483  SCIPdebugMsg(scip, "Indicator variable <%s> is aggregated and replaced by active/negated variable <%s>.\n", SCIPvarGetName(consdata->binvar), SCIPvarGetName(var) );
3484 
3485  /* we need to update the events and locks */
3486  assert( conshdlrdata->eventhdlrbound != NULL );
3487  SCIP_CALL( SCIPdropVarEvent(scip, consdata->binvar, SCIP_EVENTTYPE_BOUNDCHANGED, conshdlrdata->eventhdlrbound, (SCIP_EVENTDATA*) consdata, -1) );
3488  SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_BOUNDCHANGED, conshdlrdata->eventhdlrbound, (SCIP_EVENTDATA*) consdata, NULL) );
3489 
3490  SCIP_CALL( SCIPaddVarLocksType(scip, consdata->binvar, SCIP_LOCKTYPE_MODEL, 0, -1) );
3491  SCIP_CALL( SCIPaddVarLocksType(scip, var, SCIP_LOCKTYPE_MODEL, 0, 1) );
3492 
3493  /* change binvary variable */
3494  consdata->binvar = var;
3495  }
3496  }
3497  else if ( SCIPvarGetStatus(consdata->binvar) == SCIP_VARSTATUS_NEGATED )
3498  {
3499  SCIP_VAR* var;
3500 
3501  var = SCIPvarGetNegatedVar(consdata->binvar);
3502  assert( var != NULL );
3503 
3504  /* if the binary variable is the negated slack variable, we have 1 - s = 1 -> s = 0, i.e., the constraint is redundant */
3505  if ( var == consdata->slackvar )
3506  {
3507  /* delete constraint */
3508  assert( ! SCIPconsIsModifiable(cons) );
3509  SCIP_CALL( SCIPdelCons(scip, cons) );
3510  ++(*ndelconss);
3511  *success = TRUE;
3512  return SCIP_OKAY;
3513  }
3514  }
3515 
3516  /* check whether slack variable is aggregated */
3517  if ( SCIPvarGetStatus(consdata->slackvar) == SCIP_VARSTATUS_AGGREGATED || SCIPvarGetStatus(consdata->slackvar) == SCIP_VARSTATUS_NEGATED )
3518  {
3520  SCIP_Real bound;
3521  SCIP_VAR* var;
3522 
3523  /* possibly get representation of slack variable by active variable */
3524  var = consdata->slackvar;
3525  bound = SCIPvarGetLbGlobal(var);
3526 
3527  SCIP_CALL( SCIPvarGetProbvarBound(&var, &bound, &boundtype) );
3528  assert( var != consdata->slackvar );
3529 
3530  /* we can replace the slack variable by the active variable if it is also a >= variable */
3531  if ( var != consdata->binvar && boundtype == SCIP_BOUNDTYPE_LOWER && SCIPisGE(scip, bound, 0.0) )
3532  {
3533  assert( SCIPvarIsActive(var) );
3534  SCIPdebugMsg(scip, "Slack variable <%s> is aggregated or negated and replaced by active variable <%s>.\n", SCIPvarGetName(consdata->slackvar), SCIPvarGetName(var) );
3535 
3536  /* we need to update the events, locks, and captures */
3537  assert( conshdlrdata->eventhdlrbound != NULL );
3538  SCIP_CALL( SCIPdropVarEvent(scip, consdata->slackvar, SCIP_EVENTTYPE_BOUNDCHANGED, conshdlrdata->eventhdlrbound, (SCIP_EVENTDATA*) consdata, -1) );
3539  SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_BOUNDCHANGED, conshdlrdata->eventhdlrbound, (SCIP_EVENTDATA*) consdata, NULL) );
3540 
3541  SCIP_CALL( SCIPaddVarLocksType(scip, consdata->slackvar, SCIP_LOCKTYPE_MODEL, 0, -1) );
3542  SCIP_CALL( SCIPaddVarLocksType(scip, var, SCIP_LOCKTYPE_MODEL, 0, 1) );
3543 
3544  SCIP_CALL( SCIPreleaseVar(scip, &consdata->slackvar) );
3545  SCIP_CALL( SCIPcaptureVar(scip, var) );
3546 
3547  /* change slack variable */
3548  consdata->slackvar = var;
3549  }
3550  else if ( var == consdata->binvar )
3551  {
3552  /* check special case that aggregating variable is equal to the indicator variable */
3553  assert( SCIPisEQ(scip, bound, 0.0) || SCIPisEQ(scip, bound, 1.0) );
3554 
3555  /* if the lower bound is transformed to an upper bound, we have "y = 1 -> 1 - y = 0", i.e., the constraint is redundant */
3556  if ( boundtype == SCIP_BOUNDTYPE_UPPER )
3557  {
3558  SCIPdebugMsg(scip, "Slack variable <%s> is aggregated to negated indicator variable <%s> -> constraint redundant.\n",
3559  SCIPvarGetName(consdata->slackvar), SCIPvarGetName(consdata->binvar));
3560  assert( SCIPisEQ(scip, bound, 1.0) );
3561 
3562  /* delete constraint */
3563  assert( ! SCIPconsIsModifiable(cons) );
3564  SCIP_CALL( SCIPdelCons(scip, cons) );
3565  ++(*ndelconss);
3566  *success = TRUE;
3567  return SCIP_OKAY;
3568  }
3569  else
3570  {
3571  /* 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 */
3572  SCIPdebugMsg(scip, "Slack variable <%s> is aggregated to the indicator variable <%s> -> fix indicator variable to 0.\n",
3573  SCIPvarGetName(consdata->slackvar), SCIPvarGetName(consdata->binvar));
3574  assert( boundtype == SCIP_BOUNDTYPE_LOWER );
3575  assert( SCIPisEQ(scip, bound, 0.0) );
3576 
3577  SCIP_CALL( SCIPfixVar(scip, consdata->binvar, 0.0, &infeasible, &fixed) );
3578  assert( ! infeasible );
3579 
3580  if ( fixed )
3581  ++(*nfixedvars);
3582 
3583  SCIP_CALL( SCIPdelCons(scip, cons) );
3584 
3585  ++(*ndelconss);
3586  *success = TRUE;
3587 
3588  return SCIP_OKAY;
3589  }
3590  }
3591  }
3592 
3593  /* Note that because of possible multi-aggregation we cannot simply remove the indicator
3594  * constraint if the linear constraint is not active or disabled - see the note in @ref
3595  * PREPROC. */
3596 
3597  return SCIP_OKAY;
3598 }
3599 
3600 
3601 /** propagate indicator constraint */
3602 static
3604  SCIP* scip, /**< SCIP pointer */
3605  SCIP_CONS* cons, /**< constraint */
3606  SCIP_CONSDATA* consdata, /**< constraint data */
3607  SCIP_Bool dualreductions, /**< should dual reductions be performed? */
3608  SCIP_Bool addopposite, /**< add opposite inequalities if binary var = 0? */
3609  SCIP_Bool* cutoff, /**< whether a cutoff happened */
3610  int* nGen /**< number of domain changes */
3611  )
3612 {
3613  SCIP_Bool infeasible;
3614  SCIP_Bool tightened;
3615 
3616  assert( scip != NULL );
3617  assert( cons != NULL );
3618  assert( consdata != NULL );
3619  assert( cutoff != NULL );
3620  assert( nGen != NULL );
3621 
3622  *cutoff = FALSE;
3623  *nGen = 0;
3624 
3625  /* if the linear constraint has not been generated, we do nothing */
3626  if ( ! consdata->linconsactive )
3627  return SCIP_OKAY;
3628 
3629  assert( consdata->slackvar != NULL );
3630  assert( consdata->binvar != NULL );
3631  assert( SCIPisFeasGE(scip, SCIPvarGetLbLocal(consdata->slackvar), 0.0) );
3632 
3633  /* if both slackvar and binvar are fixed to be nonzero */
3634  if ( consdata->nfixednonzero > 1 )
3635  {
3636  SCIPdebugMsg(scip, "The node is infeasible, both the slack variable and the binary variable are fixed to be nonzero.\n");
3637  *cutoff = TRUE;
3638 
3639  SCIP_CALL( SCIPresetConsAge(scip, cons) );
3640  assert( SCIPvarGetLbLocal(consdata->binvar) > 0.5 );
3641  assert( SCIPisPositive(scip, SCIPvarGetLbLocal(consdata->slackvar)) );
3642 
3643  /* check if conflict analysis is turned on */
3644  if ( ! SCIPisConflictAnalysisApplicable(scip) )
3645  return SCIP_OKAY;
3646 
3647  /* conflict analysis can only be applied in solving stage */
3648  assert( SCIPgetStage(scip) == SCIP_STAGE_SOLVING || SCIPinProbing(scip) );
3649 
3650  /* perform conflict analysis */
3652 
3653  SCIP_CALL( SCIPaddConflictBinvar(scip, consdata->binvar) );
3654  SCIP_CALL( SCIPaddConflictLb(scip, consdata->slackvar, NULL) );
3655  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
3656 
3657  return SCIP_OKAY;
3658  }
3659 
3660  /* if exactly one of the variables is fixed to be nonzero */
3661  if ( consdata->nfixednonzero == 1 )
3662  {
3663  /* increase age of constraint; age is reset to zero, if a conflict or a propagation was found */
3664  if ( ! SCIPinRepropagation(scip) )
3665  SCIP_CALL( SCIPincConsAge(scip, cons) );
3666 
3667  /* if binvar is fixed to be nonzero */
3668  if ( SCIPvarGetLbLocal(consdata->binvar) > 0.5 )
3669  {
3670  assert( SCIPvarGetStatus(consdata->slackvar) != SCIP_VARSTATUS_MULTAGGR );
3671 
3672  /* if slack variable is not already fixed to 0 */
3673  if ( ! SCIPisZero(scip, SCIPvarGetUbLocal(consdata->slackvar)) )
3674  {
3675  SCIPdebugMsg(scip, "Binary variable <%s> is fixed to be nonzero, fixing slack variable <%s> to 0.\n",
3676  SCIPvarGetName(consdata->binvar), SCIPvarGetName(consdata->slackvar));
3677 
3678  /* fix slack variable to 0 */
3679  SCIP_CALL( SCIPinferVarUbCons(scip, consdata->slackvar, 0.0, cons, 0, FALSE, &infeasible, &tightened) );
3680  assert( ! infeasible );
3681  if ( tightened )
3682  ++(*nGen);
3683  }
3684  }
3685 
3686  /* if slackvar is fixed to be nonzero */
3687  if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(consdata->slackvar)) )
3688  {
3689  /* if binary variable is not yet fixed to 0 */
3690  if ( SCIPvarGetUbLocal(consdata->binvar) > 0.5 )
3691  {
3692  SCIPdebugMsg(scip, "Slack variable <%s> is fixed to be nonzero, fixing binary variable <%s> to 0.\n",
3693  SCIPvarGetName(consdata->slackvar), SCIPvarGetName(consdata->binvar));
3694 
3695  /* fix binary variable to 0 */
3696  SCIP_CALL( SCIPinferVarUbCons(scip, consdata->binvar, 0.0, cons, 1, FALSE, &infeasible, &tightened) );
3697  assert( ! infeasible );
3698  if ( tightened )
3699  ++(*nGen);
3700  }
3701  }
3702 
3703  /* reset constraint age counter */
3704  if ( *nGen > 0 )
3705  SCIP_CALL( SCIPresetConsAge(scip, cons) );
3706 
3707  /* mark linear constraint to be update-able */
3708  if ( SCIPgetDepth(scip) == 0 && SCIPconsIsActive(consdata->lincons) )
3709  {
3710  SCIPconsAddUpgradeLocks(consdata->lincons, -1);
3711  assert( SCIPconsGetNUpgradeLocks(consdata->lincons) == 0 );
3712  }
3713 
3714  /* delete constraint locally */
3715  assert( ! SCIPconsIsModifiable(cons) );
3716  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
3717  }
3718  else
3719  {
3720  /* if the binary variable is fixed to zero */
3721  if ( SCIPvarGetUbLocal(consdata->binvar) < 0.5 )
3722  {
3723  if ( addopposite && consdata->linconsactive )
3724  {
3725  char name[SCIP_MAXSTRLEN];
3726  SCIP_CONS* reversecons;
3727  SCIP_VAR** linvars;
3728  SCIP_Real* linvals;
3729  SCIP_Bool allintegral = TRUE;
3730  SCIP_VAR* slackvar;
3731  SCIP_VAR** vars;
3732  SCIP_Real* vals;
3733  SCIP_Real lhs;
3734  SCIP_Real rhs;
3735  int nlinvars;
3736  int nvars = 0;
3737  int j;
3738 
3739  /* determine lhs/rhs (first exchange lhs/rhs) */
3740  lhs = SCIPgetRhsLinear(scip, consdata->lincons);
3741  if ( SCIPisInfinity(scip, lhs) )
3742  lhs = -SCIPinfinity(scip);
3743  rhs = SCIPgetRhsLinear(scip, consdata->lincons);
3744  if ( SCIPisInfinity(scip, -rhs) )
3745  rhs = SCIPinfinity(scip);
3746 
3747  assert( ! SCIPisInfinity(scip, lhs) );
3748  assert( ! SCIPisInfinity(scip, -rhs) );
3749 
3750  /* consider only finite lhs/rhs */
3751  if ( ! SCIPisInfinity(scip, -lhs) || ! SCIPisInfinity(scip, rhs) )
3752  {
3753  /* ignore equations (cannot add opposite constraint) */
3754  if ( ! SCIPisEQ(scip, lhs, rhs) )
3755  {
3756  assert( consdata->lincons != NULL );
3757  nlinvars = SCIPgetNVarsLinear(scip, consdata->lincons);
3758  linvars = SCIPgetVarsLinear(scip, consdata->lincons);
3759  linvals = SCIPgetValsLinear(scip, consdata->lincons);
3760  slackvar = consdata->slackvar;
3761  assert( slackvar != NULL );
3762 
3763  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nlinvars) );
3764  SCIP_CALL( SCIPallocBufferArray(scip, &vals, nlinvars) );
3765 
3766  /* copy data and check whether the linear constraint is integral */
3767  for (j = 0; j < nlinvars; ++j)
3768  {
3769  if ( linvars[j] != slackvar )
3770  {
3771  if (! SCIPvarIsIntegral(linvars[j]) || ! SCIPisIntegral(scip, linvals[j]) )
3772  allintegral = FALSE;
3773 
3774  vars[nvars] = linvars[j];
3775  vals[nvars++] = linvals[j];
3776  }
3777  }
3778  assert( nlinvars == nvars + 1 );
3779 
3780  /* possibly adjust lhs/rhs */
3781  if ( allintegral && ! SCIPisInfinity(scip, REALABS(lhs)) )
3782  lhs += 1.0;
3783 
3784  if ( allintegral && ! SCIPisInfinity(scip, REALABS(rhs)) )
3785  rhs -= 1.0;
3786 
3787  /* create reverse constraint */
3788  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "reverse_%s", SCIPconsGetName(consdata->lincons));
3789 
3790  /* constraint is initial, separated, not enforced, not checked, propagated, local, not modifiable, dynamic, removable */
3791  SCIP_CALL( SCIPcreateConsLinear(scip, &reversecons, name, nvars, vars, vals, lhs, rhs,
3792  TRUE, TRUE, FALSE, FALSE, TRUE, TRUE, FALSE, TRUE, TRUE, FALSE) );
3793 
3794  SCIPdebugMsg(scip, "Binary variable <%s> fixed to 0. Adding opposite linear inequality.\n", SCIPvarGetName(consdata->binvar));
3795  SCIPdebugPrintCons(scip, reversecons, NULL);
3796 
3797  /* add constraint */
3798  SCIP_CALL( SCIPaddCons(scip, reversecons) );
3799  SCIP_CALL( SCIPreleaseCons(scip, &reversecons) );
3800 
3801  SCIPfreeBufferArray(scip, &vals);
3802  SCIPfreeBufferArray(scip, &vars);
3803  }
3804  }
3805  }
3806 
3807  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
3808  }
3809 
3810  /* if the slack variable is fixed to zero */
3811  if ( SCIPisFeasZero(scip, SCIPvarGetUbLocal(consdata->slackvar)) )
3812  {
3813  /* perform dual reduction - if required */
3814  if ( dualreductions )
3815  {
3816  SCIP_VAR* binvar;
3817  SCIP_Real obj;
3818 
3819  /* check objective of binary variable */
3820  binvar = consdata->binvar;
3821  obj = varGetObjDelta(binvar);
3822 
3823  /* if obj = 0, we prefer setting the binary variable to 1 (if possible) */
3824  if ( obj <= 0.0 )
3825  {
3826  /* In this case we would like to fix the binary variable to 1, if it is not locked up
3827  except by this indicator constraint. If more than one indicator constraint is
3828  affected, we have to hope that they are all fulfilled - in this case the last
3829  constraint will fix the binary variable to 1. */
3830  if ( SCIPvarGetNLocksUpType(binvar, SCIP_LOCKTYPE_MODEL) <= 1 )
3831  {
3832  if ( SCIPvarGetUbLocal(binvar) > 0.5 )
3833  {
3834  SCIPdebugMsg(scip, "Propagating <%s> - dual reduction: Slack variable fixed to 0, fix binary variable to 1.\n", SCIPconsGetName(cons));
3835  SCIP_CALL( SCIPinferVarLbCons(scip, binvar, 1.0, cons, 2, FALSE, &infeasible, &tightened) );
3836  assert( ! infeasible );
3837  if ( tightened )
3838  ++(*nGen);
3839  /* Make sure that the other case does not occur, since we are not sure whether SCIPinferVarLbCons() directly changes the bounds. */
3840  obj = -1.0;
3841  }
3842  }
3843  }
3844  if ( obj >= 0.0 )
3845  {
3846  /* In this case we would like to fix the binary variable to 0, if it is not locked down
3847  (should also have been performed by other dual reductions). */
3848  if ( SCIPvarGetNLocksDownType(binvar, SCIP_LOCKTYPE_MODEL) == 0 )
3849  {
3850  if ( SCIPvarGetLbLocal(binvar) < 0.5 )
3851  {
3852  SCIPdebugMsg(scip, "Propagating <%s> - dual reduction: Slack variable fixed to 0, fix binary variable to 0.\n", SCIPconsGetName(cons));
3853  SCIP_CALL( SCIPinferVarUbCons(scip, binvar, 0.0, cons, 2, FALSE, &infeasible, &tightened) );
3854  assert( ! infeasible );
3855  if ( tightened )
3856  ++(*nGen);
3857  }
3858  }
3859  }
3860  }
3861 
3862  SCIPdebugMsg(scip, "Slack variable fixed to zero, delete redundant indicator constraint <%s>.\n", SCIPconsGetName(cons));
3863 
3864  /* delete constraint */
3865  assert( ! SCIPconsIsModifiable(cons) );
3866 
3867  /* mark linear constraint to be update-able */
3868  if ( SCIPgetDepth(scip) == 0 && SCIPconsIsActive(consdata->lincons) )
3869  {
3870  SCIPconsAddUpgradeLocks(consdata->lincons, -1);
3871  assert( SCIPconsGetNUpgradeLocks(consdata->lincons) == 0 );
3872  }
3873 
3874  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
3875  SCIP_CALL( SCIPresetConsAge(scip, cons) );
3876  ++(*nGen);
3877  }
3878 
3879  /* Note that because of possible multi-aggregation we cannot simply remove the indicator
3880  * constraint if the linear constraint is not active or disabled - see the note in @ref
3881  * PREPROC and consPresolIndicator(). Moreover, it would drastically increase memory
3882  * consumption, because the linear constraints have to be stored in each node. */
3883  }
3884 
3885  return SCIP_OKAY;
3886 }
3887 
3888 
3889 /** enforcement method that produces cuts if possible
3890  *
3891  * This is a variant of the enforcement method that generates cuts/constraints via the alternative
3892  * LP, if possible.
3893  */
3894 static
3896  SCIP* scip, /**< SCIP pointer */
3897  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
3898  int nconss, /**< number of constraints */
3899  SCIP_CONS** conss, /**< indicator constraints */
3900  SCIP_SOL* sol, /**< solution to be enforced */
3901  SCIP_Bool genlogicor, /**< whether logicor constraint should be generated */
3902  SCIP_Bool* cutoff, /**< whether we detected a cutoff by an infeasible inequality */
3903  int* nGen /**< number of cuts generated */
3904  )
3905 {
3906  SCIP_CONSHDLRDATA* conshdlrdata;
3907  SCIP_LPI* lp;
3908  SCIP_Bool* S;
3909  SCIP_Real value = 0.0;
3910  SCIP_Bool error;
3911  int size = 0;
3912  int nCuts;
3913  int j;
3914 
3915  assert( scip != NULL );
3916  assert( conshdlr != NULL );
3917  assert( conss != NULL );
3918  assert( cutoff != NULL );
3919  assert( nGen != NULL );
3920 
3921  SCIPdebugMsg(scip, "Enforcing via cuts ...\n");
3922  *cutoff = FALSE;
3923  *nGen = 0;
3924 
3925  conshdlrdata = SCIPconshdlrGetData(conshdlr);
3926  assert( conshdlrdata != NULL );
3927  lp = conshdlrdata->altlp;
3928  assert( lp != NULL );
3929 
3930 #ifndef NDEBUG
3931  SCIP_CALL( checkLPBoundsClean(scip, lp, nconss, conss) );
3932 #endif
3933 
3934  /* change coefficients of bounds in alternative LP */
3935  if ( conshdlrdata->updatebounds )
3936  SCIP_CALL( updateFirstRowGlobal(scip, conshdlrdata) );
3937 
3938  /* possibly update upper bound */
3939  SCIP_CALL( updateObjUpperbound(scip, conshdlr, conshdlrdata) );
3940 
3941  /* scale first row if necessary */
3942  SCIP_CALL( scaleFirstRow(scip, conshdlrdata) );
3943 
3944  /* set objective function to current solution */
3945  SCIP_CALL( setAltLPObjZero(scip, lp, nconss, conss) );
3946 
3947  SCIP_CALL( SCIPallocBufferArray(scip, &S, nconss) );
3948 
3949  /* set up variables fixed to 1 */
3950  for (j = 0; j < nconss; ++j)
3951  {
3952  SCIP_CONSDATA* consdata;
3953 
3954  assert( conss[j] != NULL );
3955  consdata = SCIPconsGetData(conss[j]);
3956  assert( consdata != NULL );
3957 
3958  assert( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, consdata->binvar)) );
3959  if ( SCIPisFeasZero(scip, SCIPgetSolVal(scip, sol, consdata->binvar)) )
3960  {
3961  ++size;
3962  value += varGetObjDelta(consdata->binvar);
3963  S[j] = TRUE;
3964  }
3965  else
3966  S[j] = FALSE;
3967  }
3968 
3969  /* fix the variables in S */
3970  SCIP_CALL( fixAltLPVariables(scip, lp, nconss, conss, S) );
3971 
3972  /* extend set S to a cover and generate cuts */
3973  error = FALSE;
3974  SCIP_CALL( extendToCover(scip, conshdlr, conshdlrdata, lp, sol, conshdlrdata->removable, genlogicor, nconss, conss, S, &size, &value, &error, cutoff, &nCuts) );
3975  *nGen = nCuts;
3976 
3977  /* return with an error if no cuts have been produced and and error occurred in extendToCover() */
3978  if ( nCuts == 0 && error )
3979  return SCIP_LPERROR;
3980 
3981  SCIPdebugMsg(scip, "Generated %d IIS-cuts.\n", nCuts);
3982 
3983  /* reset bounds */
3984  SCIP_CALL( unfixAltLPVariables(scip, lp, nconss, conss, S) );
3985 
3986 #ifndef NDEBUG
3987  SCIP_CALL( checkLPBoundsClean(scip, lp, nconss, conss) );
3988 #endif
3989 
3990  SCIPfreeBufferArray(scip, &S);
3991 
3992  return SCIP_OKAY;
3993 }
3994 
3995 
3996 /** enforcement method
3997  *
3998  * We check whether the current solution is feasible, i.e., if binvar = 1
3999  * implies that slackvar = 0. If not, we branch as follows:
4000  *
4001  * In one branch we fix binvar = 1 and slackvar = 0. In the other branch
4002  * we fix binvar = 0 and leave slackvar unchanged.
4003  */
4004 static
4006  SCIP* scip, /**< SCIP pointer */
4007  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
4008  int nconss, /**< number of constraints */
4009  SCIP_CONS** conss, /**< indicator constraints */
4010  SCIP_SOL* sol, /**< solution to be enforced (NULL for LP solution) */
4011  SCIP_Bool genlogicor, /**< whether logicor constraint should be generated */
4012  SCIP_RESULT* result /**< result */
4013  )
4014 {
4015  SCIP_CONSDATA* consdata;
4016  SCIP_CONSHDLRDATA* conshdlrdata;
4017  SCIP_NODE* node1;
4018  SCIP_NODE* node2;
4019  SCIP_VAR* slackvar;
4020  SCIP_VAR* binvar;
4022  SCIP_Real maxSlack = -1.0;
4023  SCIP_Bool someLinconsNotActive = FALSE;
4024  int c;
4025 
4026  assert( scip != NULL );
4027  assert( conshdlr != NULL );
4028  assert( conss != NULL );
4029  assert( result != NULL );
4030 
4031  *result = SCIP_FEASIBLE;
4032 
4033  SCIPdebugMsg(scip, "Enforcing indicator constraints for <%s> ...\n", SCIPconshdlrGetName(conshdlr) );
4034 
4035  /* get constraint handler data */
4036  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4037  assert( conshdlrdata != NULL );
4038 
4039 #ifdef SCIP_OUTPUT
4040  SCIP_CALL( SCIPwriteTransProblem(scip, "ind.cip", "cip", FALSE) );
4041 #endif
4042 
4043  /* check each constraint */
4044  for (c = 0; c < nconss; ++c)
4045  {
4046  SCIP_Bool cutoff;
4047  SCIP_Real valSlack;
4048  int cnt;
4049 
4050  assert( conss[c] != NULL );
4051  consdata = SCIPconsGetData(conss[c]);
4052  assert( consdata != NULL );
4053  assert( consdata->lincons != NULL );
4054 
4055  /* if the linear constraint has not been generated, we do nothing */
4056  if ( ! consdata->linconsactive )
4057  {
4058  someLinconsNotActive = TRUE;
4059  continue;
4060  }
4061 
4062  /* first perform propagation (it might happen that standard propagation is turned off) */
4063  SCIP_CALL( propIndicator(scip, conss[c], consdata,
4064  conshdlrdata->dualreductions && SCIPallowDualReds(scip), conshdlrdata->addopposite,
4065  &cutoff, &cnt) );
4066  if ( cutoff )
4067  {
4068  SCIPdebugMsg(scip, "Propagation in enforcing <%s> detected cutoff.\n", SCIPconsGetName(conss[c]));
4069  *result = SCIP_CUTOFF;
4070  return SCIP_OKAY;
4071  }
4072  if ( cnt > 0 )
4073  {
4074  SCIPdebugMsg(scip, "Propagation in enforcing <%s> reduced domains: %d.\n", SCIPconsGetName(conss[c]), cnt);
4075  *result = SCIP_REDUCEDDOM;
4076  return SCIP_OKAY;
4077  }
4078 
4079  /* check whether constraint is infeasible */
4080  binvar = consdata->binvar;
4081  valSlack = SCIPgetSolVal(scip, sol, consdata->slackvar);
4082  assert( ! SCIPisFeasNegative(scip, valSlack) );
4083  if ( ! SCIPisFeasZero(scip, SCIPgetSolVal(scip, sol, binvar)) && ! SCIPisFeasZero(scip, valSlack) )
4084  {
4085  /* binary variable is not fixed - otherwise we would not be infeasible */
4086  assert( SCIPvarGetLbLocal(binvar) < 0.5 && SCIPvarGetUbLocal(binvar) > 0.5 );
4087 
4088  if ( valSlack > maxSlack )
4089  {
4090  maxSlack = valSlack;
4091  branchCons = conss[c];
4092 #ifdef SCIP_OUTPUT
4093  SCIPinfoMessage(scip, NULL, "Violated indicator constraint:\n");
4094  SCIP_CALL( SCIPprintCons(scip, conss[c], NULL) );
4095  SCIPinfoMessage(scip, NULL, ";\n");
4096  SCIPinfoMessage(scip, NULL, "Corresponding linear constraint:\n");
4097  SCIP_CALL( SCIPprintCons(scip, consdata->lincons, NULL) );
4098  SCIPinfoMessage(scip, NULL, ";\n");
4099 #endif
4100  }
4101  }
4102  }
4103 
4104  /* if some constraint has a linear constraint that is not active, we need to check feasibility via the alternative polyhedron */
4105  if ( (someLinconsNotActive || conshdlrdata->enforcecuts) && conshdlrdata->sepaalternativelp )
4106  {
4107  SCIP_Bool cutoff;
4108  int ngen;
4109 
4110  SCIP_CALL( enforceCuts(scip, conshdlr, nconss, conss, sol, genlogicor, &cutoff, &ngen) );
4111  if ( cutoff )
4112  {
4113  conshdlrdata->niiscutsgen += ngen;
4114  *result = SCIP_CUTOFF;
4115  return SCIP_OKAY;
4116  }
4117 
4118  if ( ngen > 0 )
4119  {
4120  conshdlrdata->niiscutsgen += ngen;
4121  if ( genlogicor )
4122  {
4123  SCIPdebugMsg(scip, "Generated %d constraints.\n", ngen);
4124  *result = SCIP_CONSADDED;
4125  }
4126  else
4127  {
4128  SCIPdebugMsg(scip, "Generated %d cuts.\n", ngen);
4129  *result = SCIP_SEPARATED;
4130  }
4131  return SCIP_OKAY;
4132  }
4133  SCIPdebugMsg(scip, "Enforcing produced no cuts.\n");
4134 
4135  assert( ! someLinconsNotActive || branchCons == NULL );
4136  }
4137 
4138  /* if all constraints are feasible */
4139  if ( branchCons == NULL )
4140  {
4141  SCIPdebugMsg(scip, "All indicator constraints are feasible.\n");
4142  return SCIP_OKAY;
4143  }
4144 
4145  /* skip branching if required */
4146  if ( ! conshdlrdata->branchindicators )
4147  {
4148  *result = SCIP_INFEASIBLE;
4149  return SCIP_OKAY;
4150  }
4151 
4152  /* otherwise create branches */
4153  SCIPdebugMsg(scip, "Branching on constraint <%s> (slack value: %f).\n", SCIPconsGetName(branchCons), maxSlack);
4154  consdata = SCIPconsGetData(branchCons);
4155  assert( consdata != NULL );
4156  binvar = consdata->binvar;
4157  slackvar = consdata->slackvar;
4158 
4159  /* node1: binvar = 1, slackvar = 0 */
4160  SCIP_CALL( SCIPcreateChild(scip, &node1, 0.0, SCIPcalcChildEstimate(scip, binvar, 1.0) ) );
4161 
4162  if ( SCIPvarGetLbLocal(binvar) < 0.5 )
4163  {
4164  SCIP_CALL( SCIPchgVarLbNode(scip, node1, binvar, 1.0) );
4165  }
4166 
4167  /* if slack-variable is multi-aggregated */
4168  assert( SCIPvarGetStatus(slackvar) != SCIP_VARSTATUS_MULTAGGR );
4169  if ( ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(slackvar)) )
4170  {
4171  SCIP_CALL( SCIPchgVarUbNode(scip, node1, slackvar, 0.0) );
4172  }
4173 
4174  /* node2: binvar = 0, no restriction on slackvar */
4175  SCIP_CALL( SCIPcreateChild(scip, &node2, 0.0, SCIPcalcChildEstimate(scip, binvar, 0.0) ) );
4176 
4177  if ( SCIPvarGetUbLocal(binvar) > 0.5 )
4178  {
4179  SCIP_CALL( SCIPchgVarUbNode(scip, node2, binvar, 0.0) );
4180  }
4181 
4182  SCIP_CALL( SCIPresetConsAge(scip, branchCons) );
4183  *result = SCIP_BRANCHED;
4184 
4185  return SCIP_OKAY;
4186 }
4187 
4188 
4189 /** separate IIS-cuts via rounding
4190  *
4191  * @todo Check whether the cover produced at the end is a feasible solution.
4192  */
4193 static
4195  SCIP* scip, /**< SCIP pointer */
4196  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
4197  SCIP_SOL* sol, /**< solution to be separated */
4198  int nconss, /**< number of constraints */
4199  SCIP_CONS** conss, /**< indicator constraints */
4200  int maxsepacuts, /**< maximal number of cuts to be generated */
4201  SCIP_Bool* cutoff, /**< whether we detected a cutoff by an infeasible inequality */
4202  int* nGen /**< number of domain changes */
4203  )
4204 { /*lint --e{850}*/
4205  SCIP_CONSHDLRDATA* conshdlrdata;
4206  SCIP_LPI* lp;
4207  int rounds;
4208  SCIP_Real threshold;
4209  SCIP_Bool* S;
4210  SCIP_Bool error;
4211  int oldsize = -1;
4212  /* cppcheck-suppress unassignedVariable */
4213  int nGenOld;
4214 
4215  assert( scip != NULL );
4216  assert( conshdlr != NULL );
4217  assert( conss != NULL );
4218  assert( cutoff != NULL );
4219  assert( nGen != NULL );
4220 
4221  if ( *nGen >= maxsepacuts )
4222  return SCIP_OKAY;
4223 
4224  *cutoff = FALSE;
4225  rounds = 0;
4226 
4227  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4228  assert( conshdlrdata != NULL );
4229  lp = conshdlrdata->altlp;
4230  assert( lp != NULL );
4231 
4232  SCIPdebug( nGenOld = *nGen; )
4233  SCIPdebugMsg(scip, "Separating IIS-cuts by rounding ...\n");
4234 
4235 #ifndef NDEBUG
4236  SCIP_CALL( checkLPBoundsClean(scip, lp, nconss, conss) );
4237 #endif
4238 
4239  /* change coefficients of bounds in alternative LP */
4240  if ( conshdlrdata->updatebounds )
4241  {
4242  /* update to local bounds */
4243  SCIP_CALL( updateFirstRow(scip, conshdlrdata) );
4244  }
4245 
4246  /* possibly update upper bound */
4247  SCIP_CALL( updateObjUpperbound(scip, conshdlr, conshdlrdata) );
4248 
4249  /* scale first row if necessary */
4250  SCIP_CALL( scaleFirstRow(scip, conshdlrdata) );
4251 
4252  /* set objective function to current solution */
4253  SCIP_CALL( setAltLPObj(scip, lp, sol, nconss, conss) );
4254 
4255  SCIP_CALL( SCIPallocBufferArray(scip, &S, nconss) );
4256 
4257  /* loop through the possible thresholds */
4258  for (threshold = conshdlrdata->roundingmaxthres;
4259  rounds < conshdlrdata->maxroundingrounds && threshold >= conshdlrdata->roundingminthres && *nGen < maxsepacuts && ! (*cutoff);
4260  threshold -= conshdlrdata->roundingoffset )
4261  {
4262  SCIP_Real value = 0.0;
4263  int size = 0;
4264  int nCuts = 0;
4265  int j;
4266 #ifdef SCIP_DEBUG
4267  int nvarsone = 0;
4268  int nvarszero = 0;
4269  int nvarsfrac = 0;
4270 #endif
4271 
4272  SCIPdebugMsg(scip, "Threshold: %g.\n", threshold);
4273 
4274  /* choose variables that have a value < current threshold value */
4275  for (j = 0; j < nconss; ++j)
4276  {
4277  SCIP_CONSDATA* consdata;
4278  SCIP_Real binvarval;
4279  SCIP_VAR* binvarneg;
4280 
4281  assert( conss[j] != NULL );
4282  consdata = SCIPconsGetData(conss[j]);
4283  assert( consdata != NULL );
4284 
4285  binvarval = SCIPgetVarSol(scip, consdata->binvar);
4286 
4287 #ifdef SCIP_DEBUG
4288  if ( SCIPisFeasEQ(scip, binvarval, 1.0) )
4289  ++nvarsone;
4290  else if ( SCIPisFeasZero(scip, binvarval) )
4291  ++nvarszero;
4292  else
4293  ++nvarsfrac;
4294 #endif
4295 
4296  /* check whether complementary (negated) variable is present as well */
4297  binvarneg = SCIPvarGetNegatedVar(consdata->binvar);
4298  assert( binvarneg != NULL );
4299 
4300  /* negated variable is present as well */
4301  assert( conshdlrdata->binvarhash != NULL );
4302  if ( SCIPhashmapExists(conshdlrdata->binvarhash, (void*) binvarneg) )
4303  {
4304  SCIP_Real binvarnegval = SCIPgetVarSol(scip, binvarneg);
4305 
4306  /* take larger one */
4307  if ( binvarval > binvarnegval )
4308  S[j] = TRUE;
4309  else
4310  S[j] = FALSE;
4311  continue;
4312  }
4313 
4314  /* check for threshold */
4315  if ( SCIPisFeasLT(scip, SCIPgetVarSol(scip, consdata->binvar), threshold) )
4316  {
4317  S[j] = TRUE;
4318  value += varGetObjDelta(consdata->binvar);
4319  ++size;
4320  }
4321  else
4322  S[j] = FALSE;
4323  }
4324 
4325  if ( size == nconss )
4326  {
4327  SCIPdebugMsg(scip, "All variables in the set. Continue ...\n");
4328  continue;
4329  }
4330 
4331  /* skip computation if size has not changed (computation is likely the same) */
4332  if ( size == oldsize )
4333  {
4334  SCIPdebugMsg(scip, "Skipping computation: size support has not changed.\n");
4335  continue;
4336  }
4337  oldsize = size;
4338 
4339 #ifdef SCIP_DEBUG
4340  SCIPdebugMsg(scip, " Vars with value 1: %d 0: %d and fractional: %d.\n", nvarsone, nvarszero, nvarsfrac);
4341 #endif
4342 
4343  /* fix the variables in S */
4344  SCIP_CALL( fixAltLPVariables(scip, lp, nconss, conss, S) );
4345 
4346  /* extend set S to a cover and generate cuts */
4347  SCIP_CALL( extendToCover(scip, conshdlr, conshdlrdata, lp, sol, conshdlrdata->removable, conshdlrdata->genlogicor, nconss, conss, S, &size, &value, &error, cutoff, &nCuts) );
4348 
4349  /* we ignore errors in extendToCover */
4350  if ( nCuts > 0 )
4351  {
4352  *nGen += nCuts;
4353  ++rounds;
4354  }
4355  else
4356  {
4357  /* possibly update upper bound */
4358  SCIP_CALL( updateObjUpperbound(scip, conshdlr, conshdlrdata) );
4359  }
4360 
4361  /* reset bounds */
4362  SCIP_CALL( unfixAltLPVariables(scip, lp, nconss, conss, S) );
4363  }
4364  SCIPdebugMsg(scip, "Generated %d IISs.\n", *nGen - nGenOld);
4365 
4366 #ifndef NDEBUG
4367  SCIP_CALL( checkLPBoundsClean(scip, lp, nconss, conss) );
4368 #endif
4369 
4370  SCIPfreeBufferArray(scip, &S);
4371 
4372  return SCIP_OKAY;
4373 }
4374 
4375 
4376 
4377 /** separate cuts based on perspective formulation
4378  *
4379  * Hijazi, Bonami, and Ouorou (2014) introduced the following cuts: We consider an indicator constraint
4380  * \f[
4381  * y = 1 \rightarrow \alpha^T x \leq \beta
4382  * \f]
4383  * and assume finite bounds \f$\ell \leq x \leq u\f$. Then for \f$I \subseteq \{1, \dots, n\}\f$ define
4384  * \f[
4385  * \Sigma(I,x,y) = \sum_{i \notin I} \alpha_i x_i +
4386  * y \Big(\sum_{i \in I, \alpha_i < 0} \alpha_i u_i + \sum_{i \in I, \alpha_i > 0} \alpha_i \ell_i +
4387  * \sum_{i \notin I, \alpha_i < 0} \alpha_i \ell_i + \sum_{i \notin I, \alpha_i > 0} \alpha_i u_i - \beta\Big).
4388  * \f]
4389  * Then the cuts
4390  * \f[
4391  * \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
4392  * \f]
4393  * are valid for the disjunction
4394  * \f[
4395  * \{y = 0,\; \ell \leq x \leq u\} \cup \{y = 1,\; \ell \leq x \leq u,\; \alpha^T x \leq \beta\}.
4396  * \f]
4397  * 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
4398  * \f[
4399  * y^*(\alpha_i\, u_i\, [\alpha_i < 0] + \alpha_i\, \ell_i\, [\alpha_i > 0]) >
4400  * \alpha_i x_i^* + y^* )\alpha_i \ell_i [\alpha_i < 0] + \alpha_i u_i [\alpha_i > 0]),
4401  * \f]
4402  * where \f$[C] = 1\f$ if condition \f$C\f$ is satisfied, otherwise it is 0.
4403  * If the above inequality holds, \f$i\f$ is included in \f$I\f$, otherwise not.
4404  */
4405 static
4407  SCIP* scip, /**< SCIP pointer */
4408  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
4409  SCIP_SOL* sol, /**< solution to be separated */
4410  int nconss, /**< number of constraints */
4411  SCIP_CONS** conss, /**< indicator constraints */
4412  int maxsepacuts, /**< maximal number of cuts to be generated */
4413  int* nGen /**< number of generated cuts */
4414  )
4415 { /*lint --e{850}*/
4416  SCIP_CONSHDLRDATA* conshdlrdata;
4417  SCIP_VAR** cutvars;
4418  SCIP_Real* cutvals;
4419  int nvars;
4420  int c;
4421 
4422  assert( scip != NULL );
4423  assert( conshdlr != NULL );
4424  assert( conss != NULL );
4425  assert( nGen != NULL );
4426 
4427  if ( *nGen >= maxsepacuts )
4428  return SCIP_OKAY;
4429 
4430  nvars = SCIPgetNVars(scip);
4431  SCIP_CALL( SCIPallocBufferArray(scip, &cutvars, nvars+1) );
4432  SCIP_CALL( SCIPallocBufferArray(scip, &cutvals, nvars+1) );
4433 
4434  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4435  assert( conshdlrdata != NULL );
4436 
4437  /* loop through constraints */
4438  for (c = 0; c < nconss; ++c)
4439  {
4440  SCIP_CONSDATA* consdata;
4441  SCIP_CONS* lincons;
4442  SCIP_VAR* slackvar;
4443  SCIP_VAR* binvar;
4444  SCIP_Real binval;
4445 
4446  assert( conss[c] != NULL );
4447  consdata = SCIPconsGetData(conss[c]);
4448  assert( consdata != NULL );
4449  slackvar = consdata->slackvar;
4450 
4451  lincons = consdata->lincons;
4452  assert( lincons != NULL );
4453 
4454  binvar = consdata->binvar;
4455  assert( binvar != NULL );
4456  binval = SCIPgetSolVal(scip, sol, binvar);
4457 
4458  if ( SCIPconsIsActive(lincons) )
4459  {
4460  SCIP_VAR** linvars;
4461  SCIP_Real* linvals;
4462  SCIP_Real linrhs;
4463  SCIP_Bool finitebound = TRUE;
4464  SCIP_Real cutrhs = 0.0;
4465  SCIP_Real cutval;
4466  SCIP_Real signfactor = 1.0;
4467  SCIP_Real ypart;
4468  SCIP_Bool islocal = FALSE;
4469  int nlinvars;
4470  int cnt = 0;
4471  int j;
4472 
4473  linvars = SCIPgetVarsLinear(scip, lincons);
4474  linvals = SCIPgetValsLinear(scip, lincons);
4475  nlinvars = SCIPgetNVarsLinear(scip, lincons);
4476 
4477  linrhs = SCIPgetRhsLinear(scip, lincons);
4478  if ( SCIPisInfinity(scip, linrhs) )
4479  {
4480  if ( ! SCIPisInfinity(scip, SCIPgetLhsLinear(scip, lincons)) )
4481  {
4482  linrhs = -SCIPgetLhsLinear(scip, lincons);
4483  signfactor = -1.0;
4484  }
4485  else
4486  continue;
4487  }
4488  ypart = -linrhs;
4489  cutval = binval * ypart;
4490 
4491  for (j = 0; j < nlinvars; ++j)
4492  {
4493  SCIP_Real linval;
4494  SCIP_Real lb;
4495  SCIP_Real ub;
4496  SCIP_Real din = 0.0;
4497  SCIP_Real dout = 0.0;
4498  SCIP_Real xpart;
4499  SCIP_Real xval;
4500 
4501  if ( linvars[j] == slackvar )
4502  continue;
4503 
4504  if ( conshdlrdata->sepapersplocal )
4505  {
4506  lb = SCIPvarGetLbLocal(linvars[j]);
4507  ub = SCIPvarGetUbLocal(linvars[j]);
4508 
4509  if ( lb > SCIPvarGetLbGlobal(linvars[j]) )
4510  islocal = TRUE;
4511  if ( ub < SCIPvarGetUbGlobal(linvars[j]) )
4512  islocal = TRUE;
4513  }
4514  else
4515  {
4516  lb = SCIPvarGetLbGlobal(linvars[j]);
4517  ub = SCIPvarGetUbGlobal(linvars[j]);
4518  }
4519 
4520  /* skip cases with unbounded variables */
4521  if ( SCIPisInfinity(scip, -lb) || SCIPisInfinity(scip, ub) )
4522  {
4523  finitebound = FALSE;
4524  break;
4525  }
4526 
4527  /* compute rest parts for i in the set (din) or not in the set (dout) */
4528  linval = signfactor * linvals[j];
4529  if ( SCIPisNegative(scip, linval) )
4530  {
4531  din += linval * ub;
4532  dout += linval * lb;
4533  }
4534  else if ( SCIPisPositive(scip, linval) )
4535  {
4536  din += linval * lb;
4537  dout += linval * ub;
4538  }
4539 
4540  xval = SCIPgetSolVal(scip, sol, linvars[j]);
4541  xpart = linval * xval;
4542 
4543  /* if din > dout, we want to include i in the set */
4544  if ( SCIPisGT(scip, binval * din, binval * dout + xpart) )
4545  {
4546  ypart += din;
4547  cutval += binval * din;
4548  }
4549  else
4550  {
4551  /* otherwise i is not in the set */
4552  ypart += dout;
4553 
4554  cutrhs += dout;
4555  cutval += binval * dout + xpart;
4556 
4557  cutvars[cnt] = linvars[j];
4558  cutvals[cnt++] = linval;
4559  }
4560  }
4561 
4562  if ( ! finitebound )
4563  continue;
4564 
4565  if ( SCIPisEfficacious(scip, cutval - cutrhs) )
4566  {
4567  SCIP_ROW* row;
4568  SCIP_Bool infeasible;
4569  char name[50];
4570 
4571  /* add y-variable */
4572  cutvars[cnt] = binvar;
4573  cutvals[cnt] = ypart;
4574  ++cnt;
4575 
4576  SCIPdebugMsg(scip, "Found cut of lhs value %f > %f.\n", cutval, cutrhs);
4577  (void) SCIPsnprintf(name, 50, "persp%d", conshdlrdata->nperspcutsgen + *nGen);
4578  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(conss[c]), name, -SCIPinfinity(scip), cutrhs, islocal, FALSE, conshdlrdata->removable) );
4579  SCIP_CALL( SCIPaddVarsToRow(scip, row, cnt, cutvars, cutvals) );
4580 #ifdef SCIP_OUTPUT
4581  SCIP_CALL( SCIPprintRow(scip, row, NULL) );
4582 #endif
4583  SCIP_CALL( SCIPaddRow(scip, row, FALSE, &infeasible) );
4584  assert( ! infeasible );
4585  SCIP_CALL( SCIPreleaseRow(scip, &row));
4586  SCIP_CALL( SCIPresetConsAge(scip, conss[c]) );
4587  ++(*nGen);
4588  }
4589  }
4590  if ( *nGen >= maxsepacuts )
4591  break;
4592  }
4593 
4594  SCIPfreeBufferArray(scip, &cutvals);
4595  SCIPfreeBufferArray(scip, &cutvars);
4596 
4597  return SCIP_OKAY;
4598 }
4599 
4600 
4601 /** separation method
4602  *
4603  * We first check whether coupling inequalities can be separated (if required). If not enough of
4604  * these could be generated, we check whether IIS inequalities can be separated.
4605  */
4606 static
4608  SCIP* scip, /**< SCIP pointer */
4609  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
4610  int nconss, /**< number of constraints */
4611  int nusefulconss, /**< number of useful constraints */
4612  SCIP_CONS** conss, /**< indicator constraints */
4613  SCIP_SOL* sol, /**< solution to be separated */
4614  SCIP_RESULT* result /**< result */
4615  )
4616 {
4617  SCIP_CONSHDLRDATA* conshdlrdata;
4618  int maxsepacuts;
4619  int ncuts;
4620 
4621  assert( scip != NULL );
4622  assert( conshdlr != NULL );
4623  assert( conss != NULL );
4624  assert( result != NULL );
4625 
4626  *result = SCIP_DIDNOTRUN;
4627 
4628  if ( nconss == 0 )
4629  return SCIP_OKAY;
4630 
4631  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4632  assert( conshdlrdata != NULL );
4633  ncuts = 0;
4634 
4635  /* get the maximal number of cuts allowed in a separation round */
4636  if ( SCIPgetDepth(scip) == 0 )
4637  maxsepacuts = conshdlrdata->maxsepacutsroot;
4638  else
4639  maxsepacuts = conshdlrdata->maxsepacuts;
4640 
4641  /* first separate coupling inequalities (if required) */
4642  if ( conshdlrdata->sepacouplingcuts )
4643  {
4644  int c;
4645 
4646  *result = SCIP_DIDNOTFIND;
4647 
4648  /* check each constraint */
4649  for (c = 0; c < nusefulconss && ncuts < maxsepacuts; ++c)
4650  {
4651  SCIP_CONSDATA* consdata;
4652  SCIP_Bool islocal;
4653  SCIP_Real ub;
4654 
4655  assert( conss != NULL );
4656  assert( conss[c] != NULL );
4657  consdata = SCIPconsGetData(conss[c]);
4658  assert( consdata != NULL );
4659  assert( consdata->slackvar != NULL );
4660  assert( consdata->binvar != NULL );
4661 
4662  /* get upper bound for slack variable in linear constraint */
4663  islocal = FALSE;
4664  if ( conshdlrdata->sepacouplinglocal )
4665  {
4666  ub = SCIPvarGetUbLocal(consdata->slackvar);
4667  if ( ub < SCIPvarGetUbGlobal(consdata->slackvar) )
4668  islocal = TRUE;
4669  }
4670  else
4671  ub = SCIPvarGetUbGlobal(consdata->slackvar);
4672  assert( ! SCIPisFeasNegative(scip, ub) );
4673 
4674  /* only use coefficients that are not too large */
4675  if ( ub <= conshdlrdata->sepacouplingvalue )
4676  {
4677  SCIP_Real activity;
4678 
4679  activity = SCIPgetSolVal(scip, sol, consdata->slackvar) + ub * SCIPgetSolVal(scip, sol, consdata->binvar) - ub;
4680  if ( SCIPisEfficacious(scip, activity) )
4681  {
4682  SCIP_ROW* row;
4683  SCIP_Bool infeasible;
4684 #ifndef NDEBUG
4685  char name[50];
4686 
4687  (void) SCIPsnprintf(name, 50, "couple%d", c);
4688  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(conss[c]), name, -SCIPinfinity(scip), ub, islocal, FALSE, conshdlrdata->removable) );
4689 #else
4690  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(conss[c]), "", -SCIPinfinity(scip), ub, islocal, FALSE, conshdlrdata->removable) );
4691 #endif
4692  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
4693 
4694  SCIP_CALL( SCIPaddVarToRow(scip, row, consdata->slackvar, 1.0) );
4695  SCIP_CALL( SCIPaddVarToRow(scip, row, consdata->binvar, ub) );
4696  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
4697 
4698  SCIPdebugMsg(scip, "Separated coupling inequality for indicator constraint <%s> (coeff: %f).\n", SCIPconsGetName(conss[c]), ub);
4699 #ifdef SCIP_OUTPUT
4700  SCIP_CALL( SCIPprintRow(scip, row, NULL) );
4701 #endif
4702  SCIP_CALL( SCIPaddRow(scip, row, FALSE, &infeasible) );
4703  assert( ! infeasible );
4704  SCIP_CALL( SCIPreleaseRow(scip, &row));
4705 
4706  SCIP_CALL( SCIPresetConsAge(scip, conss[c]) );
4707  *result = SCIP_SEPARATED;
4708 
4709  ++ncuts;
4710  }
4711  }
4712  }
4713  SCIPdebugMsg(scip, "Number of separated coupling inequalities: %d.\n", ncuts);
4714  }
4715 
4716  /* separate cuts from the alternative lp (if required) */
4717  if ( conshdlrdata->sepaalternativelp && ncuts < SEPAALTTHRESHOLD )
4718  {
4719  SCIP_Bool cutoff;
4720  int noldcuts;
4721 
4722  SCIPdebugMsg(scip, "Separating inequalities for indicator constraints.\n");
4723 
4724  noldcuts = ncuts;
4725  if ( *result == SCIP_DIDNOTRUN )
4726  *result = SCIP_DIDNOTFIND;
4727 
4728  /* start separation */
4729  SCIP_CALL( separateIISRounding(scip, conshdlr, sol, nconss, conss, maxsepacuts, &cutoff, &ncuts) );
4730  SCIPdebugMsg(scip, "Separated %d cuts from indicator constraints.\n", ncuts - noldcuts);
4731 
4732  if ( cutoff )
4733  *result = SCIP_CUTOFF;
4734  else if ( ncuts > noldcuts )
4735  {
4736  conshdlrdata->niiscutsgen += ncuts;
4737 
4738  /* possibly overwrite result from separation above */
4739  if ( conshdlrdata->genlogicor )
4740  *result = SCIP_CONSADDED;
4741  else
4742  *result = SCIP_SEPARATED;
4743  }
4744  }
4745 
4746  /* separate cuts based on perspective formulation */
4747  if ( conshdlrdata->sepaperspective && ncuts < SEPAALTTHRESHOLD )
4748  {
4749  int noldcuts;
4750 
4751  SCIPdebugMsg(scip, "Separating inequalities based on perspective formulation.\n");
4752 
4753  noldcuts = ncuts;
4754  if ( *result == SCIP_DIDNOTRUN )
4755  *result = SCIP_DIDNOTFIND;
4756 
4757  /* start separation */
4758  SCIP_CALL( separatePerspective(scip, conshdlr, sol, nconss, conss, maxsepacuts, &ncuts) );
4759  SCIPdebugMsg(scip, "Separated %d cuts from perspective formulation.\n", ncuts - noldcuts);
4760 
4761  if ( ncuts > noldcuts )
4762  {
4763  conshdlrdata->nperspcutsgen += ncuts;
4764 
4765  /* possibly overwrite result from separation above */
4766  *result = SCIP_SEPARATED;
4767  }
4768  }
4769 
4770  return SCIP_OKAY;
4771 }
4772 
4773 
4774 /** initializes the constraint handler data */
4775 static
4776 void initConshdlrData(
4777  SCIP* scip, /**< SCIP pointer */
4778  SCIP_CONSHDLRDATA* conshdlrdata /**< constraint handler data */
4779  )
4780 {
4781  assert( conshdlrdata != NULL );
4782 
4783  conshdlrdata->removable = TRUE;
4784  conshdlrdata->scaled = FALSE;
4785  conshdlrdata->altlp = NULL;
4786  conshdlrdata->nrows = 0;
4787  conshdlrdata->varhash = NULL;
4788  conshdlrdata->slackhash = NULL;
4789  conshdlrdata->lbhash = NULL;
4790  conshdlrdata->ubhash = NULL;
4791  conshdlrdata->nlbbounds = 0;
4792  conshdlrdata->nubbounds = 0;
4793  conshdlrdata->nslackvars = 0;
4794  conshdlrdata->objcutindex = -1;
4795  conshdlrdata->objupperbound = SCIPinfinity(scip);
4796  conshdlrdata->objaltlpbound = SCIPinfinity(scip);
4797  conshdlrdata->roundingminthres = 0.1;
4798  conshdlrdata->roundingmaxthres = 0.6;
4799  conshdlrdata->maxroundingrounds = MAXROUNDINGROUNDS;
4800  conshdlrdata->roundingoffset = 0.1;
4801  conshdlrdata->addedcouplingcons = FALSE;
4802  conshdlrdata->ninitconss = 0;
4803  conshdlrdata->nbinvarszero = 0;
4804  conshdlrdata->performedrestart = FALSE;
4805  conshdlrdata->objindicatoronly = FALSE;
4806  conshdlrdata->objothervarsonly = FALSE;
4807  conshdlrdata->minabsobj = 0.0;
4808  conshdlrdata->normtype = 'e';
4809  conshdlrdata->niiscutsgen = 0;
4810  conshdlrdata->nperspcutsgen = 0;
4811 }
4812 
4813 
4814 /* ---------------------------- upgrading methods -----------------------------------*/
4815 
4816 /** tries to upgrade a linear constraint into an indicator constraint
4817  *
4818  * 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
4819  * it to an indicator constraint if for the residual value \f$a^T x \geq \gamma\f$, we have \f$\alpha + \gamma \geq
4820  * \beta\f$: in this case, the constraint is always satisfied if \f$y = 1\f$.
4821  *
4822  * 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
4823  * upgrade it to an indicator constraint if for the residual value \f$a^T x \leq \gamma\f$, we have \f$\alpha + \gamma
4824  * \leq \beta\f$.
4825  */
4826 static
4827 SCIP_DECL_LINCONSUPGD(linconsUpgdIndicator)
4828 { /*lint --e{715}*/
4829  SCIP_CONSHDLRDATA* conshdlrdata;
4830  SCIP_CONSHDLR* conshdlr;
4831  SCIP_Real minactivity = 0.0;
4832  SCIP_Real maxactivity = 0.0;
4833  SCIP_Real maxabsval = -1.0;
4834  SCIP_Real secabsval = -1.0;
4835  int maxabsvalidx = -1;
4836  int j;
4837 
4838  assert( scip != NULL );
4839  assert( upgdcons != NULL );
4840  assert( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(cons)), "linear") == 0 );
4841  assert( ! SCIPconsIsModifiable(cons) );
4842 
4843  /* do not upgrade if there are at most 2 variables (2 variables should be upgraded to a varbound constraint) */
4844  if ( nvars <= 2 )
4845  return SCIP_OKAY;
4846 
4847  /* cannot currently ranged constraints, since we can only return one constraint (and we would need one for each side each) */
4848  if ( ! SCIPisInfinity(scip, -lhs) && ! SCIPisInfinity(scip, rhs) )
4849  return SCIP_OKAY;
4850 
4851  /* check whether upgrading is turned on */
4852  conshdlr = SCIPfindConshdlr(scip, "indicator");
4853  assert( conshdlr != NULL );
4854  conshdlrdata = SCIPconshdlrGetData(conshdlr);
4855  assert( conshdlrdata != NULL );
4856 
4857  if ( ! conshdlrdata->upgradelinear )
4858  return SCIP_OKAY;
4859 
4860  /* calculate activities */
4861  for (j = 0; j < nvars; ++j)
4862  {
4863  SCIP_VAR* var;
4864  SCIP_Real val;
4865  SCIP_Real lb;
4866  SCIP_Real ub;
4867 
4868  val = vals[j];
4869  assert( ! SCIPisZero(scip, val) );
4870 
4871  var = vars[j];
4872  assert( var != NULL );
4873 
4874  /* store maximal (and second to largest) value of coefficients */
4875  if ( SCIPisGE(scip, REALABS(val), maxabsval) )
4876  {
4877  secabsval = maxabsval;
4878  maxabsval = REALABS(val);
4879  maxabsvalidx = j;
4880  }
4881 
4882  if ( val > 0 )
4883  {
4884  lb = SCIPvarGetLbGlobal(var);
4885  ub = SCIPvarGetUbGlobal(var);
4886  }
4887  else
4888  {
4889  ub = SCIPvarGetLbGlobal(var);
4890  lb = SCIPvarGetUbGlobal(var);
4891  }
4892 
4893  /* compute minimal activity */
4894  if ( SCIPisInfinity(scip, -lb) )
4895  minactivity = -SCIPinfinity(scip);
4896  else
4897  {
4898  if ( ! SCIPisInfinity(scip, -minactivity) )
4899  minactivity += val * lb;
4900  }
4901 
4902  /* compute maximal activity */
4903  if ( SCIPisInfinity(scip, ub) )
4904  maxactivity = SCIPinfinity(scip);
4905  else
4906  {
4907  if ( ! SCIPisInfinity(scip, maxactivity) )
4908  maxactivity += val * ub;
4909  }
4910  }
4911  assert( maxabsval >= 0.0 );
4912  assert( 0 <= maxabsvalidx && maxabsvalidx < nvars );
4913 
4914  /* exit if largest coefficient does not belong to binary variable */
4915  if ( ! SCIPvarIsBinary(vars[maxabsvalidx]) )
4916  return SCIP_OKAY;
4917 
4918  /* exit if the second largest coefficient is as large as largest */
4919  if ( SCIPisEQ(scip, secabsval, maxabsval) )
4920  return SCIP_OKAY;
4921 
4922  /* cannot upgrade if all activities are infinity */
4923  if ( SCIPisInfinity(scip, -minactivity) && SCIPisInfinity(scip, maxactivity) )
4924  return SCIP_OKAY;
4925 
4926  /* check each variable as indicator variable */
4927  for (j = 0; j < nvars; ++j)
4928  {
4929  SCIP_VAR** indconsvars;
4930  SCIP_Real* indconsvals;
4931  SCIP_Bool upgdlhs = FALSE;
4932  SCIP_Bool upgdrhs = FALSE;
4933  SCIP_Bool indneglhs = FALSE;
4934  SCIP_Bool indnegrhs = FALSE;
4935  SCIP_VAR* indvar;
4936  SCIP_Real indval;
4937  int l;
4938 
4939  indvar = vars[j];
4940  indval = vals[j];
4941  assert( ! SCIPisZero(scip, indval) );
4942 
4943  if ( ! SCIPvarIsBinary(indvar) )
4944  continue;
4945 
4946  /* check for upgrading of lhs */
4947  if ( ! SCIPisInfinity(scip, -minactivity) && ! SCIPisInfinity(scip, -lhs) )
4948  {
4949  /* upgrading is possible with binary variable */
4950  if ( SCIPisGE(scip, minactivity, lhs) )
4951  upgdlhs = TRUE;
4952 
4953  /* upgrading is possible with negated binary variable */
4954  if ( SCIPisGE(scip, minactivity + indval, lhs) )
4955  {
4956  upgdlhs = TRUE;
4957  indneglhs = TRUE;
4958  }
4959  }
4960 
4961  /* check for upgrading of rhs */
4962  if ( ! SCIPisInfinity(scip, maxactivity) && ! SCIPisInfinity(scip, rhs) )
4963  {
4964  /* upgrading is possible with binary variable */
4965  if ( SCIPisLE(scip, maxactivity, rhs) )
4966  {
4967  upgdrhs = TRUE;
4968  indnegrhs = TRUE;
4969  }
4970 
4971  /* upgrading is possible with negated binary variable */
4972  if ( SCIPisLE(scip, maxactivity - indval, rhs) )
4973  upgdrhs = TRUE;
4974  }
4975 
4976  /* upgrade constraint */
4977  if ( upgdlhs || upgdrhs )
4978  {
4979  SCIP_VAR* indvar2;
4980  SCIP_Real bnd;
4981  int cnt = 0;
4982 
4983  assert( ! upgdlhs || ! upgdrhs ); /* cannot treat ranged rows */
4984  SCIPdebugMsg(scip, "upgrading constraint <%s> to an indicator constraint.\n", SCIPconsGetName(cons));
4985 
4986  SCIP_CALL( SCIPallocBufferArray(scip, &indconsvars, nvars - 1) );
4987  SCIP_CALL( SCIPallocBufferArray(scip, &indconsvals, nvars - 1) );
4988 
4989  /* create constraint */
4990  for (l = 0; l < nvars; ++l)
4991  {
4992  if ( vars[l] == indvar )
4993  continue;
4994  indconsvars[cnt] = vars[l];
4995  if ( upgdlhs )
4996  indconsvals[cnt] = -vals[l];
4997  else
4998  indconsvals[cnt] = vals[l];
4999  ++cnt;
5000  }
5001 
5002  if ( indneglhs || indnegrhs )
5003  {
5004  SCIP_CALL( SCIPgetNegatedVar(scip, indvar, &indvar2) );
5005  }
5006  else
5007  indvar2 = indvar;
5008 
5009  if ( upgdlhs )
5010  {
5011  bnd = -lhs;
5012  if ( ! indneglhs )
5013  bnd -= indval;
5014  SCIP_CALL( SCIPcreateConsIndicator(scip, upgdcons, SCIPconsGetName(cons), indvar2, nvars-1, indconsvars, indconsvals, bnd,
5017  }
5018  else
5019  {
5020  bnd = rhs;
5021  if ( ! indnegrhs )
5022  bnd -= indval;
5023  SCIP_CALL( SCIPcreateConsIndicator(scip, upgdcons, SCIPconsGetName(cons), indvar2, nvars-1, indconsvars, indconsvals, bnd,
5026  }
5027 
5028 #ifdef SCIP_DEBUG
5029  SCIPinfoMessage(scip, NULL, "upgrade: \n");
5030  SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
5031  SCIPinfoMessage(scip, NULL, "\n");
5032  SCIP_CALL( SCIPprintCons(scip, *upgdcons, NULL) );
5033  SCIPinfoMessage(scip, NULL, "\n");
5035  SCIPinfoMessage(scip, NULL, " (minact: %f, maxact: %f)\n", minactivity, maxactivity);
5036 #endif
5037 
5038  SCIPfreeBufferArray(scip, &indconsvars);
5039  SCIPfreeBufferArray(scip, &indconsvals);
5040 
5041  return SCIP_OKAY;
5042  }
5043  }
5044 
5045  return SCIP_OKAY;
5046 }
5047 
5048 
5049 /* ---------------------------- constraint handler callback methods ----------------------*/
5050 
5051 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
5052 static
5053 SCIP_DECL_CONSHDLRCOPY(conshdlrCopyIndicator)
5054 { /*lint --e{715}*/
5055  assert( scip != NULL );
5056  assert( conshdlr != NULL );
5057  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
5058  assert( valid != NULL );
5059 
5060  /* call inclusion method of constraint handler */
5062 
5063  *valid = TRUE;
5064 
5065  return SCIP_OKAY;
5066 }
5067 
5068 
5069 /** initialization method of constraint handler (called after problem was transformed) */
5070 static
5071 SCIP_DECL_CONSINIT(consInitIndicator)
5072 { /*lint --e{715}*/
5073  SCIP_CONSHDLRDATA* conshdlrdata;
5074 
5075  assert( scip != NULL );
5076  assert( conshdlr != NULL );
5077  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
5078 
5079  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5080  assert( conshdlrdata != NULL );
5081 
5082  initConshdlrData(scip, conshdlrdata);
5083 
5084  /* find trysol heuristic */
5085  if ( conshdlrdata->trysolutions && conshdlrdata->heurtrysol == NULL )
5086  {
5087  conshdlrdata->heurtrysol = SCIPfindHeur(scip, "trysol");
5088  }
5089 
5090  return SCIP_OKAY;
5091 }
5092 
5093 
5094 /** deinitialization method of constraint handler (called before transformed problem is freed) */
5095 static
5096 SCIP_DECL_CONSEXIT(consExitIndicator)
5097 { /*lint --e{715}*/
5098  SCIP_CONSHDLRDATA* conshdlrdata;
5099 
5100  assert( scip != NULL );
5101  assert( conshdlr != NULL );
5102  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
5103 
5104  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5105 
5106  if ( conshdlrdata->binvarhash != NULL )
5107  SCIPhashmapFree(&conshdlrdata->binvarhash);
5108 
5109  SCIPfreeBlockMemoryArrayNull(scip, &conshdlrdata->addlincons, conshdlrdata->maxaddlincons);
5110  conshdlrdata->maxaddlincons = 0;
5111  conshdlrdata->naddlincons = 0;
5112  conshdlrdata->nrows = 0;
5113 
5114  return SCIP_OKAY;
5115 }
5116 
5117 
5118 /** destructor of constraint handler to free constraint handler data (called when SCIP is exiting) */
5119 static
5120 SCIP_DECL_CONSFREE(consFreeIndicator)
5122  SCIP_CONSHDLRDATA* conshdlrdata;
5123 
5124  assert( scip != NULL );
5125  assert( conshdlr != NULL );
5126  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
5127 
5128  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5129  assert( conshdlrdata != NULL );
5130  assert( conshdlrdata->altlp == NULL );
5131  assert( conshdlrdata->varhash == NULL );
5132  assert( conshdlrdata->lbhash == NULL );
5133  assert( conshdlrdata->ubhash == NULL );
5134  assert( conshdlrdata->slackhash == NULL );
5135 
5136  if ( conshdlrdata->maxaddlincons > 0 )
5137  {
5138  /* if problem was not yet transformed the array may need to be freed, because we did not call the EXIT callback */
5139  SCIPfreeBlockMemoryArrayNull(scip, &conshdlrdata->addlincons, conshdlrdata->maxaddlincons);
5140  }
5141  assert( conshdlrdata->addlincons == NULL );
5142  conshdlrdata->naddlincons = 0;
5143  conshdlrdata->maxaddlincons = 0;
5144 
5145  SCIPfreeBlockMemory(scip, &conshdlrdata);
5146 
5147  return SCIP_OKAY;
5148 }
5149 
5150 
5151 /** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */
5152 static
5153 SCIP_DECL_CONSINITSOL(consInitsolIndicator)
5155  SCIP_CONSHDLRDATA* conshdlrdata;
5156  int c;
5157 
5158  assert( scip != NULL );
5159  assert( conshdlr != NULL );
5160  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
5161 
5164  return SCIP_OKAY;
5165 
5166  SCIPdebugMsg(scip, "Initsol for indicator constraints.\n");
5167 
5168  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5169  assert( conshdlrdata != NULL );
5170  assert( conshdlrdata->slackhash == NULL );
5171 
5172  SCIP_CALL( SCIPgetCharParam(scip, "separating/efficacynorm", &conshdlrdata->normtype) );
5173 
5174  if ( conshdlrdata->sepaalternativelp )
5175  {
5176  /* generate hash for storing all slack variables (size is just a guess) */
5177  SCIP_CALL( SCIPhashmapCreate(&conshdlrdata->slackhash, SCIPblkmem(scip), SCIPgetNVars(scip)) );
5178  assert( conshdlrdata->slackhash != NULL );
5179 
5180  /* first initialize slack hash */
5181  for (c = 0; c < nconss; ++c)
5182  {
5183  SCIP_CONSDATA* consdata;
5184 
5185  assert( conss != NULL );
5186  assert( conss[c] != NULL );
5187  assert( SCIPconsIsTransformed(conss[c]) );
5188 
5189  consdata = SCIPconsGetData(conss[c]);
5190  assert( consdata != NULL );
5191 
5192  assert( consdata->slackvar != NULL );
5193 
5194  /* insert slack variable into hash */
5195  SCIP_CALL( SCIPhashmapInsert(conshdlrdata->slackhash, consdata->slackvar, (void*) (size_t) (INT_MAX)) );
5196  assert( SCIPhashmapExists(conshdlrdata->slackhash, consdata->slackvar) );
5197  ++conshdlrdata->nslackvars;
5198  }
5199 
5200  if ( conshdlrdata->genlogicor )
5201  {
5202  SCIP_CONSHDLR* logicorconshdlr;
5203  int logicorsepafreq;
5204  int sepafreq;
5205 
5206  /* If we generate logicor constraints, make sure that we separate them with the same frequency */
5207  logicorconshdlr = SCIPfindConshdlr(scip, "logicor");
5208  if ( logicorconshdlr == NULL )
5209  {
5210  SCIPerrorMessage("Logicor constraint handler not included, cannot generate constraints.\n");
5211  return SCIP_ERROR;
5212  }
5213  logicorsepafreq = SCIPconshdlrGetSepaFreq(logicorconshdlr);
5214  sepafreq = SCIPconshdlrGetSepaFreq(conshdlr);
5215  if ( sepafreq != -1 && ((logicorsepafreq == 0 && sepafreq > 0) || sepafreq < logicorsepafreq) )
5216  {
5217  SCIPverbMessage(scip, SCIP_VERBLEVEL_MINIMAL, NULL, "Set sepafreq of logicor constraint handler to %d.\n", sepafreq);
5218  SCIP_CALL( SCIPsetIntParam(scip, "constraints/logicor/sepafreq", sepafreq) );
5219  }
5220  }
5221  }
5222 
5223  /* check each constraint */
5224  conshdlrdata->objothervarsonly = TRUE;
5225  for (c = 0; c < nconss; ++c)
5226  {
5227  SCIP_CONSDATA* consdata;
5228 
5229  assert( conss != NULL );
5230  assert( conss[c] != NULL );
5231  assert( SCIPconsIsTransformed(conss[c]) );
5232 
5233  consdata = SCIPconsGetData(conss[c]);
5234  assert( consdata != NULL );
5235  assert( consdata->binvar != NULL );
5236  assert( consdata->slackvar != NULL );
5237 
5238  /* Presolving might replace a slack variable by an active variable. Thus, the objective of a slack variables might
5239  * be nonzero. However, we do not need to check slack variables here. */
5240  if ( ! SCIPisZero(scip, varGetObjDelta(consdata->binvar)) )
5241  conshdlrdata->objothervarsonly = FALSE;
5242 
5243  /* deactivate */
5244  if ( ! consdata->linconsactive )
5245  {
5246  SCIP_CALL( SCIPdisableCons(scip, consdata->lincons) );
5247  }
5248  else
5249  {
5250  /* add constraint to alternative LP if not already done */
5251  if ( conshdlrdata->sepaalternativelp && consdata->colindex < 0 )
5252  {
5253  SCIP_CALL( addAltLPConstraint(scip, conshdlr, consdata->lincons, consdata->slackvar, 1.0, &consdata->colindex) );
5254  SCIPdebugMsg(scip, "Added column for <%s> to alternative LP with column index %d.\n", SCIPconsGetName(conss[c]),consdata->colindex);
5255 #ifdef SCIP_OUTPUT
5256  SCIP_CALL( SCIPprintCons(scip, consdata->lincons, NULL) );
5257  SCIPinfoMessage(scip, NULL, ";\n");
5258 #endif
5259  }
5260  }
5261 
5262  /* add nlrow representation to NLP, if NLP had been constructed
5263  *
5264  * Note, that we did not tell SCIP in exitpre that we have something to add to the NLP, thus
5265  * indicators are only available in the NLP for MINLPs, but not for MIPs with indicators.
5266  */
5267  if ( SCIPisNLPConstructed(scip) && SCIPconsIsChecked(conss[c]) )
5268  {
5269  SCIP_NLROW* nlrow;
5270  SCIP_VAR* quadvars[2];
5271  SCIP_QUADELEM quadelem;
5272 
5273  /* create nonlinear row binary variable * slack variable = 0 */
5274  quadvars[0] = consdata->binvar;
5275  quadvars[1] = consdata->slackvar;
5276  quadelem.idx1 = 0;
5277  quadelem.idx2 = 1;
5278  quadelem.coef = 1.0;
5279 
5280  SCIP_CALL( SCIPcreateNlRow(scip, &nlrow, SCIPconsGetName(conss[c]), 0.0, 0, NULL, NULL, 2, quadvars, 1,
5281  &quadelem, NULL, 0.0, 0.0, SCIP_EXPRCURV_UNKNOWN) );
5282 
5283  /* add row to NLP and forget about it */
5284  SCIP_CALL( SCIPaddNlRow(scip, nlrow) );
5285  SCIP_CALL( SCIPreleaseNlRow(scip, &nlrow) );
5286  }
5287  }
5288 
5289  SCIPdebugMsg(scip, "Initialized %d indicator constraints.\n", nconss);
5290 
5291  /* check additional constraints */
5292  if ( conshdlrdata->sepaalternativelp )
5293  {
5294  SCIP_CONS* cons;
5295  int colindex;
5296  int cnt = 0;
5297 
5298  /* add stored linear constraints if they exist */
5299  if ( conshdlrdata->naddlincons > 0 )
5300  {
5301  for (c = 0; c < conshdlrdata->naddlincons; ++c)
5302  {
5303  cons = conshdlrdata->addlincons[c];
5304 
5305  /* get transformed constraint - since it is needed only here, we do not store the information */
5306  if ( ! SCIPconsIsTransformed(cons) )
5307  {
5308  SCIP_CALL( SCIPgetTransformedCons(scip, conshdlrdata->addlincons[c], &cons) );
5309 
5310  /* @todo check when exactly the transformed constraint does not exist - SCIPisActive() does not suffice */
5311  if ( cons == NULL )
5312  continue;
5313  }
5314  SCIP_CALL( addAltLPConstraint(scip, conshdlr, cons, NULL, 0.0, &colindex) );
5315  ++cnt;
5316 
5317 #ifdef SCIP_OUTPUT
5318  SCIP_CALL( SCIPprintCons(scip, cons, NULL) );
5319  SCIPinfoMessage(scip, NULL, ";\n");
5320 #endif
5321  }
5322  SCIPdebugMsg(scip, "Added %d additional columns to alternative LP.\n", cnt);
5323  }
5324  else
5325  {
5326  /* if no stored linear constraints are available, possibly collect other linear constraints; we only use linear
5327  * constraints, since most other constraints involve integral variables, and in this context we will likely
5328  * benefit much more from continuous variables. */
5329  if ( conshdlrdata->useotherconss )
5330  {
5331  const char* conshdlrname;
5332  SCIP_CONS** allconss;
5333  int nallconss;
5334 
5335  nallconss = SCIPgetNConss(scip);
5336  allconss = SCIPgetConss(scip);
5337 
5338  /* loop through all constraints */
5339  for (c = 0; c < nallconss; ++c)
5340  {
5341  /* get constraint */
5342  cons = allconss[c];
5343  assert( cons != NULL );
5344  assert( SCIPconsIsTransformed(cons) );
5345 
5346  /* get constraint handler name */
5347  conshdlrname = SCIPconshdlrGetName(SCIPconsGetHdlr(cons));
5348 
5349  /* check type of constraint (only take linear constraints) */
5350  if ( strcmp(conshdlrname, "linear") == 0 )
5351  {
5352  /* avoid adding linear constraints that correspond to indicator constraints */
5353  if ( strncmp(SCIPconsGetName(cons), "indlin", 6) != 0 )
5354  {
5355  SCIP_CALL( addAltLPConstraint(scip, conshdlr, cons, NULL, 0.0, &colindex) );
5356  SCIPdebugMsg(scip, "Added column for linear constraint <%s> to alternative LP with column index %d.\n", SCIPconsGetName(cons), colindex);
5357  ++cnt;
5358  }
5359  }
5360  }
5361  SCIPdebugMsg(scip, "Added %d additional columns from linear constraints to alternative LP.\n", cnt);
5362  }
5363  }
5364  }
5365 
5366  /* initialize event handler if restart should be forced */
5367  if ( conshdlrdata->forcerestart )
5368  {
5369  SCIP_Bool* covered;
5370  SCIP_VAR** vars;
5371  int nvars;
5372  int j;
5373 
5374  assert( conshdlrdata->eventhdlrrestart != NULL );
5375 
5376  /* store number of initial constraints */
5377  conshdlrdata->ninitconss = SCIPconshdlrGetNActiveConss(conshdlr);
5378 
5379  /* reset number of fixed binary variables */
5380  conshdlrdata->nbinvarszero = 0;
5381 
5382  /* loop through variables */
5383  nvars = SCIPgetNVars(scip);
5384  vars = SCIPgetVars(scip);
5385 
5386  conshdlrdata->objindicatoronly = FALSE;
5387  conshdlrdata->minabsobj = SCIP_REAL_MAX;
5388 
5389  /* unmark all variables */
5390  SCIP_CALL( SCIPallocBufferArray(scip, &covered, nvars) );
5391  for (j = 0; j < nvars; ++j)
5392  covered[j] = FALSE;
5393 
5394  /* mark indicator variables */
5395  for (c = 0; c < nconss; ++c)
5396  {
5397  SCIP_CONSDATA* consdata;
5398  int probindex;
5399 
5400  assert( conss != NULL );
5401  assert( conss[c] != NULL );
5402 
5403  /* avoid non-active indicator constraints */
5404  if ( ! SCIPconsIsActive(conss[c]) )
5405  continue;
5406 
5407  consdata = SCIPconsGetData(conss[c]);
5408  assert( consdata != NULL );
5409  assert( consdata->binvar != NULL );
5410 
5411  if ( SCIPvarIsNegated(consdata->binvar) )
5412  {
5413  assert( SCIPvarGetNegatedVar(consdata->binvar) != NULL );
5414  probindex = SCIPvarGetProbindex(SCIPvarGetNegatedVar(consdata->binvar));
5415  }
5416  else
5417  probindex = SCIPvarGetProbindex(consdata->binvar);
5418 
5419  /* if presolving detected infeasibility it might be that the binary variables are not active */
5420  if ( probindex < 0 )
5421  continue;
5422 
5423  assert( 0 <= probindex && probindex < nvars );
5424  covered[probindex] = TRUE;
5425  }
5426 
5427  /* check all variables */
5428  for (j = 0; j < nvars; ++j)
5429  {
5430  SCIP_Real obj;
5431 
5432  obj = SCIPvarGetObj(vars[j]);
5433  if ( ! SCIPisZero(scip, obj) )
5434  {
5435  if ( ! covered[j] )
5436  break;
5437  if ( ! SCIPisIntegral(scip, obj) )
5438  break;
5439  if ( REALABS(obj) < conshdlrdata->minabsobj )
5440  conshdlrdata->minabsobj = REALABS(obj);
5441  }
5442  }
5443 
5444  /* if all variables have integral objective and only indicator variables have nonzero objective */
5445  if ( j >= nvars )
5446  {
5447  /* if there are variables with nonzero objective */
5448  if ( conshdlrdata->minabsobj < SCIP_REAL_MAX )
5449  {
5450  assert( SCIPisIntegral(scip, conshdlrdata->minabsobj) );
5451  assert( SCIPisGE(scip, conshdlrdata->minabsobj, 1.0) );
5452 
5453  conshdlrdata->objindicatoronly = TRUE;
5454 
5455  assert( conshdlrdata->eventhdlrrestart != NULL );
5456  SCIP_CALL( SCIPcatchEvent(scip, SCIP_EVENTTYPE_BESTSOLFOUND, conshdlrdata->eventhdlrrestart, (SCIP_EVENTDATA*) conshdlrdata, NULL) );
5457  }
5458  }
5459 
5460  SCIPfreeBufferArray(scip, &covered);
5461  }
5462 
5463  return SCIP_OKAY;
5464 }
5465 
5466 
5467 /** solving process deinitialization method of constraint handler (called before branch and bound process data is freed) */
5468 static
5469 SCIP_DECL_CONSEXITSOL(consExitsolIndicator)
5470 { /*lint --e{715}*/
5471  SCIP_CONSHDLRDATA* conshdlrdata;
5472  int c;
5473 
5474  assert( scip != NULL );
5475  assert( conshdlr != NULL );
5476  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
5477 
5478  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5479  assert( conshdlrdata != NULL );
5480 
5481  if ( conshdlrdata->sepaalternativelp )
5482  {
5483  if ( conshdlrdata->slackhash != NULL )
5484  {
5485 #ifdef SCIP_DEBUG
5486  SCIPinfoMessage(scip, NULL, "\nStatistics for cons_indicator slack hash:\n");
5487  SCIPhashmapPrintStatistics(conshdlrdata->slackhash, SCIPgetMessagehdlr(scip));
5488 #endif
5489  SCIPhashmapFree(&conshdlrdata->slackhash);
5490  }
5491 
5492  if ( conshdlrdata->altlp != NULL )
5493  {
5494  assert( conshdlrdata->varhash != NULL );
5495  assert( conshdlrdata->lbhash != NULL );
5496  assert( conshdlrdata->ubhash != NULL );
5497 
5498 #ifdef SCIP_DEBUG
5499  SCIPinfoMessage(scip, NULL, "\nStatistics for cons_indicator var hash:\n");
5500  SCIPhashmapPrintStatistics(conshdlrdata->varhash, SCIPgetMessagehdlr(scip));
5501  SCIPinfoMessage(scip, NULL, "\nStatistics for cons_indicator lower bound hash:\n");
5502  SCIPhashmapPrintStatistics(conshdlrdata->lbhash, SCIPgetMessagehdlr(scip));
5503  SCIPinfoMessage(scip, NULL, "\nStatistics for cons_indicator upper bound hash:\n");
5504  SCIPhashmapPrintStatistics(conshdlrdata->ubhash, SCIPgetMessagehdlr(scip));
5505 #endif
5506 
5507  SCIPhashmapFree(&conshdlrdata->varhash);
5508  SCIPhashmapFree(&conshdlrdata->lbhash);
5509  SCIPhashmapFree(&conshdlrdata->ubhash);
5510 
5511  SCIP_CALL( SCIPlpiFree(&conshdlrdata->altlp) );
5512 
5513  /* save the information that the columns have been deleted */
5514  for (c = 0; c < nconss; ++c)
5515  {
5516  SCIP_CONSDATA* consdata;
5517 
5518  assert( conss != NULL );
5519  assert( conss[c] != NULL );
5520 
5521  consdata = SCIPconsGetData(conss[c]);
5522  assert( consdata != NULL );
5523  consdata->colindex = -1;
5524  }
5525  }
5526  }
5527  else
5528  {
5529  assert( conshdlrdata->slackhash == NULL );
5530  assert( conshdlrdata->varhash == NULL );
5531  assert( conshdlrdata->lbhash == NULL );
5532  assert( conshdlrdata->ubhash == NULL );
5533  }
5534 
5535  return SCIP_OKAY;
5536 }
5537 
5538 
5539 /** frees specific constraint data */
5540 static
5541 SCIP_DECL_CONSDELETE(consDeleteIndicator)
5543  assert( scip != NULL );
5544  assert( conshdlr != NULL );
5545  assert( cons != NULL );
5546  assert( consdata != NULL );
5547  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
5548 
5549 #ifdef SCIP_MORE_DEBUG
5550  SCIPdebugMsg(scip, "Deleting indicator constraint <%s>.\n", SCIPconsGetName(cons) );
5551 #endif
5552 
5553  /* drop events on transformed variables */
5554  if ( SCIPconsIsTransformed(cons) )
5555  {
5556  SCIP_CONSHDLRDATA* conshdlrdata;
5557 
5558  /* get constraint handler data */
5559  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5560  assert( conshdlrdata != NULL );
5561 
5562  if ( conshdlrdata->sepaalternativelp )
5563  {
5564  SCIP_CALL( deleteAltLPConstraint(scip, conshdlr, cons) );
5565  }
5566 
5567  assert( (*consdata)->slackvar != NULL );
5568  assert( (*consdata)->binvar != NULL );
5569 
5570  /* free events only in correct stages */
5572  {
5573  if ( (*consdata)->linconsactive )
5574  {
5575  assert( conshdlrdata->eventhdlrbound != NULL );
5576  SCIP_CALL( SCIPdropVarEvent(scip, (*consdata)->binvar, SCIP_EVENTTYPE_BOUNDCHANGED, conshdlrdata->eventhdlrbound,
5577  (SCIP_EVENTDATA*)*consdata, -1) );
5578  SCIP_CALL( SCIPdropVarEvent(scip, (*consdata)->slackvar, SCIP_EVENTTYPE_BOUNDCHANGED, conshdlrdata->eventhdlrbound,
5579  (SCIP_EVENTDATA*)*consdata, -1) );
5580  }
5581  if ( conshdlrdata->forcerestart )
5582  {
5583  assert( conshdlrdata->eventhdlrrestart != NULL );
5584  SCIP_CALL( SCIPdropVarEvent(scip, (*consdata)->binvar, SCIP_EVENTTYPE_GBDCHANGED, conshdlrdata->eventhdlrrestart,
5585  (SCIP_EVENTDATA*) conshdlrdata, -1) );
5586  }
5587  }
5588  }
5589 
5590  /* Can there be cases where lincons is NULL, e.g., if presolve found the problem infeasible? */
5591  assert( (*consdata)->lincons != NULL );
5592 
5593  /* release linear constraint and slack variable */
5594  SCIP_CALL( SCIPreleaseVar(scip, &(*consdata)->slackvar) );
5595  SCIP_CALL( SCIPreleaseCons(scip, &(*consdata)->lincons) );
5596 
5597  SCIPfreeBlockMemory(scip, consdata);
5598 
5599  return SCIP_OKAY;
5600 }
5601 
5602 
5603 /** transforms constraint data into data belonging to the transformed problem */
5604 static
5605 SCIP_DECL_CONSTRANS(consTransIndicator)
5607  SCIP_CONSDATA* consdata;
5608  SCIP_CONSHDLRDATA* conshdlrdata;
5609  SCIP_CONSDATA* sourcedata;
5610  char s[SCIP_MAXSTRLEN];
5611 
5612  assert( scip != NULL );
5613  assert( conshdlr != NULL );
5614  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
5615  assert( sourcecons != NULL );
5616  assert( targetcons != NULL );
5617 
5618  /* get constraint handler data */
5619  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5620  assert( conshdlrdata != NULL );
5621  assert( conshdlrdata->eventhdlrbound != NULL );
5622 
5623 #ifdef SCIP_MORE_DEBUG
5624  SCIPdebugMsg(scip, "Transforming indicator constraint: <%s>.\n", SCIPconsGetName(sourcecons) );
5625 #endif
5626 
5627  /* get data of original constraint */
5628  sourcedata = SCIPconsGetData(sourcecons);
5629  assert( sourcedata != NULL );
5630  assert( sourcedata->binvar != NULL );
5631 
5632  /* check for slackvar */
5633  if ( sourcedata->slackvar == NULL )
5634  {
5635  SCIPerrorMessage("The indicator constraint <%s> needs a slack variable.\n", SCIPconsGetName(sourcecons));
5636  return SCIP_INVALIDDATA;
5637  }
5638 
5639  /* check for linear constraint */
5640  if ( sourcedata->lincons == NULL )
5641  {
5642  SCIPerrorMessage("The indicator constraint <%s> needs a linear constraint variable.\n", SCIPconsGetName(sourcecons));
5643  return SCIP_INVALIDDATA;
5644  }
5645  assert( sourcedata->lincons != NULL );
5646  assert( sourcedata->slackvar != NULL );
5647 
5648  /* create constraint data */
5649  consdata = NULL;
5650  SCIP_CALL( consdataCreate(scip, conshdlr, conshdlrdata, SCIPconsGetName(sourcecons), &consdata, conshdlrdata->eventhdlrbound,
5651  conshdlrdata->eventhdlrrestart, sourcedata->binvar, sourcedata->slackvar, sourcedata->lincons, sourcedata->linconsactive) );
5652  assert( consdata != NULL );
5653 
5654  /* capture slack variable and linear constraint */
5655  SCIP_CALL( SCIPcaptureVar(scip, consdata->slackvar) );
5656  SCIP_CALL( SCIPcaptureCons(scip, consdata->lincons) );
5657 
5658  /* create transformed constraint with the same flags */
5659  (void) SCIPsnprintf(s, SCIP_MAXSTRLEN, "t_%s", SCIPconsGetName(sourcecons));
5660  SCIP_CALL( SCIPcreateCons(scip, targetcons, s, conshdlr, consdata,
5661  SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons),
5662  SCIPconsIsEnforced(sourcecons), SCIPconsIsChecked(sourcecons),
5663  SCIPconsIsPropagated(sourcecons), SCIPconsIsLocal(sourcecons),
5664  SCIPconsIsModifiable(sourcecons), SCIPconsIsDynamic(sourcecons),
5665  SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
5666 
5667  /* make sure that binary variable hash exists */
5668  if ( conshdlrdata->sepaalternativelp )
5669  {
5670  if ( conshdlrdata->binvarhash == NULL )
5671  {
5672  SCIP_CALL( SCIPhashmapCreate(&conshdlrdata->binvarhash, SCIPblkmem(scip), SCIPgetNOrigVars(scip)) );
5673  }
5674 
5675  /* check whether binary variable is present: note that a binary variable might appear several times, but this seldomly happens. */
5676  assert( conshdlrdata->binvarhash != NULL );
5677  if ( ! SCIPhashmapExists(conshdlrdata->binvarhash, (void*) consdata->binvar) )
5678  {
5679  SCIP_CALL( SCIPhashmapInsert(conshdlrdata->binvarhash, (void*) consdata->binvar, (void*) (*targetcons)) );
5680  }
5681  }
5682 
5683  return SCIP_OKAY;
5684 }
5685 
5686 
5687 /** presolving initialization method of constraint handler (called when presolving is about to begin) */
5688 static
5689 SCIP_DECL_CONSINITPRE(consInitpreIndicator)
5690 { /*lint --e{715}*/
5691  SCIP_CONSHDLRDATA* conshdlrdata;
5692  int c;
5693 
5694  assert( scip != NULL );
5695  assert( conshdlr != NULL );
5696  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
5697 
5698  if ( SCIPgetStatus(scip) != SCIP_STATUS_UNKNOWN )
5699  return SCIP_OKAY;
5700 
5701  SCIPdebugMsg(scip, "Initpre method for indicator constraints.\n");
5702 
5703  /* check each constraint and get transformed linear constraint */
5704  for (c = 0; c < nconss; ++c)
5705  {
5706  SCIP_CONSDATA* consdata;
5707 
5708  assert( conss != NULL );
5709  assert( conss[c] != NULL );
5710  assert( SCIPconsIsTransformed(conss[c]) );
5711 
5712  consdata = SCIPconsGetData(conss[c]);
5713  assert( consdata != NULL );
5714 
5715  /* if not happened already, get transformed linear constraint */
5716  assert( consdata->lincons != NULL );
5717  assert( strcmp(SCIPconshdlrGetName(SCIPconsGetHdlr(consdata->lincons)), "linear") == 0 );
5718 
5719  /* in a restart the linear constraint might already be transformed */
5720  if ( ! SCIPconsIsTransformed(consdata->lincons) )
5721  {
5722  SCIP_CONS* translincons;
5723 
5724  SCIP_CALL( SCIPgetTransformedCons(scip, consdata->lincons, &translincons) );
5725  assert( translincons != NULL );
5726 
5727  SCIP_CALL( SCIPreleaseCons(scip, &consdata->lincons) );
5728  SCIP_CALL( SCIPcaptureCons(scip, translincons) );
5729  consdata->lincons = translincons;
5730  }
5731  }
5732 
5733  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5734  assert( conshdlrdata != NULL );
5735 
5736  /* reset flag, in case presolve was called for some problem before */
5737  conshdlrdata->addedcouplingcons = FALSE;
5738 
5739  return SCIP_OKAY;
5740 }
5741 
5742 
5743 /** presolving method of constraint handler
5744  *
5745  * For an indicator constraint with binary variable \f$y\f$ and slack variable \f$s\f$ the coupling
5746  * inequality \f$s \le M (1-y)\f$ (equivalently: \f$s + M y \le M\f$) is inserted, where \f$M\f$ is
5747  * an upper bound on the value of \f$s\f$. If \f$M\f$ is too large the inequality is not
5748  * inserted. Depending on the parameter @a addcouplingcons we add a variable upper bound or a row
5749  * (in consInitlpIndicator()).
5750  *
5751  * @warning We can never delete linear constraints, because we need them to get the right values
5752  * for the slack variables!
5753  */
5754 static
5755 SCIP_DECL_CONSPRESOL(consPresolIndicator)
5756 { /*lint --e{715}*/
5757  SCIP_CONSHDLRDATA* conshdlrdata;
5758  SCIP_Bool noReductions;
5759  int oldnfixedvars;
5760  int oldndelconss;
5761  int removedvars = 0;
5762  int c;
5763 
5764  assert( scip != NULL );
5765  assert( conshdlr != NULL );
5766  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
5767  assert( result != NULL );
5768 
5769  *result = SCIP_DIDNOTRUN;
5770  SCIPdebug( oldnfixedvars = *nfixedvars; )
5771  SCIPdebug( oldndelconss = *ndelconss; )
5772  /* get constraint handler data */
5773  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5774  assert( conshdlrdata != NULL );
5775 
5776  SCIPdebugMsg(scip, "Presolving indicator constraints.\n");
5777 
5778  /* only run if success is possible */
5779  if ( nrounds == 0 || nnewfixedvars > 0 || nnewchgbds > 0 || nnewaggrvars > 0 )
5780  {
5781  *result = SCIP_DIDNOTFIND;
5782 
5783  /* check each constraint */
5784  for (c = 0; c < nconss; ++c)
5785