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