Scippy

SCIP

Solving Constraint Integer Programs

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