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