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