Scippy

SCIP

Solving Constraint Integer Programs

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