Scippy

SCIP

Solving Constraint Integer Programs

cons_sos1.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-2017 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not email to scip@zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file cons_sos1.c
17  * @brief constraint handler for SOS type 1 constraints
18  * @author Tobias Fischer
19  * @author Marc Pfetsch
20  *
21  * A specially ordered set of type 1 (SOS1) is a sequence of variables such that at most one
22  * variable is nonzero. The special case of two variables arises, for instance, from equilibrium or
23  * complementary conditions like \f$x \cdot y = 0\f$. Note that it is in principle allowed that a
24  * variables appears twice, but it then can be fixed to 0.
25  *
26  * This implementation of this constraint handler is based on classical ideas, see e.g.@n
27  * "Special Facilities in General Mathematical Programming System for
28  * Non-Convex Problems Using Ordered Sets of Variables"@n
29  * E. Beale and J. Tomlin, Proc. 5th IFORS Conference, 447-454 (1970)
30  *
31  *
32  * The order of the variables is determined as follows:
33  *
34  * - If the constraint is created with SCIPcreateConsSOS1() and weights are given, the weights
35  * determine the order (decreasing weights). Additional variables can be added with
36  * SCIPaddVarSOS1(), which adds a variable with given weight.
37  *
38  * - If an empty constraint is created and then variables are added with SCIPaddVarSOS1(), weights
39  * are needed and stored.
40  *
41  * - All other calls ignore the weights, i.e., if a nonempty constraint is created or variables are
42  * added with SCIPappendVarSOS1().
43  *
44  * The validity of the SOS1 constraints can be enforced by different branching rules:
45  *
46  * - If classical SOS branching is used, branching is performed on only one SOS1 constraint.
47  * Depending on the parameters, there are two ways to choose this branching constraint. Either
48  * the constraint with the most number of nonzeros or the one with the largest nonzero-variable
49  * weight. The later version allows the user to specify an order for the branching importance of
50  * the constraints. Constraint branching can also be turned off.
51  *
52  * - Another way is to branch on the neighborhood of a single variable @p i, i.e., in one branch
53  * \f$x_i\f$ is fixed to zero and in the other its neighbors from the conflict graph.
54  *
55  * - If bipartite branching is used, then we branch using complete bipartite subgraphs of the
56  * conflict graph, i.e., in one branch fix the variables from the first bipartite partition and
57  * the variables from the second bipartite partition in the other.
58  *
59  * - In addition to variable domain fixings, it is sometimes also possible to add new SOS1
60  * constraints to the branching nodes. This results in a nonstatic conflict graph, which may
61  * change dynamically with every branching node.
62  *
63  *
64  * @todo Possibly allow to generate local cuts via strengthened local cuts (would need to modified coefficients of rows).
65  *
66  * @todo Check whether we can avoid turning off multi-aggregation (it is sometimes possible to fix a multi-aggregated
67  * variable to 0 by fixing the aggregating variables to 0).
68  */
69 
70 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
71 
72 #include <assert.h>
73 
74 #include "scip/cons_sos1.h"
75 #include "scip/cons_linear.h"
76 #include "scip/cons_setppc.h"
77 #include "scip/pub_misc.h"
78 #include "scip/misc.h"
79 #include "scip/struct_misc.h"
80 #include "tclique/tclique.h"
81 #include <string.h>
82 #include <ctype.h>
83 
84 
85 /* constraint handler properties */
86 #define CONSHDLR_NAME "SOS1"
87 #define CONSHDLR_DESC "SOS1 constraint handler"
88 #define CONSHDLR_SEPAPRIORITY 1000 /**< priority of the constraint handler for separation */
89 #define CONSHDLR_ENFOPRIORITY 100 /**< priority of the constraint handler for constraint enforcing */
90 #define CONSHDLR_CHECKPRIORITY -10 /**< priority of the constraint handler for checking feasibility */
91 #define CONSHDLR_SEPAFREQ 10 /**< frequency for separating cuts; zero means to separate only in the root node */
92 #define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
93 #define CONSHDLR_EAGERFREQ 100 /**< frequency for using all instead of only the useful constraints in separation,
94  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
95 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
96 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
97 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
98 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
99 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
100 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM
102 /* adjacency matrix */
103 #define DEFAULT_MAXSOSADJACENCY 10000 /**< do not create an adjacency matrix if number of SOS1 variables is larger than predefined value
104  * (-1: no limit) */
105 
106 /* presolving */
107 #define DEFAULT_MAXEXTENSIONS 1 /**< maximal number of extensions that will be computed for each SOS1 constraint */
108 #define DEFAULT_MAXTIGHTENBDS 5 /**< maximal number of bound tightening rounds per presolving round (-1: no limit) */
109 #define DEFAULT_PERFIMPLANALYSIS FALSE /**< if TRUE then perform implication graph analysis (might add additional SOS1 constraints) */
110 #define DEFAULT_DEPTHIMPLANALYSIS -1 /**< number of recursive calls of implication graph analysis (-1: no limit) */
112 /* propagation */
113 #define DEFAULT_CONFLICTPROP TRUE /**< whether to use conflict graph propagation */
114 #define DEFAULT_IMPLPROP TRUE /**< whether to use implication graph propagation */
115 #define DEFAULT_SOSCONSPROP FALSE /**< whether to use SOS1 constraint propagation */
117 /* branching rules */
118 #define DEFAULT_BRANCHSTRATEGIES "nbs" /**< possible branching strategies (see parameter DEFAULT_BRANCHINGRULE) */
119 #define DEFAULT_BRANCHINGRULE 'n' /**< which branching rule should be applied ? ('n': neighborhood, 'b': bipartite, 's': SOS1/clique)
120  * (note: in some cases an automatic switching to SOS1 branching is possible) */
121 #define DEFAULT_AUTOSOS1BRANCH TRUE /**< if TRUE then automatically switch to SOS1 branching if the SOS1 constraints do not overlap */
122 #define DEFAULT_FIXNONZERO FALSE /**< if neighborhood branching is used, then fix the branching variable (if positive in sign) to the value of the
123  * feasibility tolerance */
124 #define DEFAULT_ADDCOMPS FALSE /**< if TRUE then add complementarity constraints to the branching nodes (can be used in combination with
125  * neighborhood or bipartite branching) */
126 #define DEFAULT_MAXADDCOMPS -1 /**< maximal number of complementarity constraints added per branching node (-1: no limit) */
127 #define DEFAULT_ADDCOMPSDEPTH 30 /**< only add complementarity constraints to branching nodes for predefined depth (-1: no limit) */
128 #define DEFAULT_ADDCOMPSFEAS -0.6 /**< minimal feasibility value for complementarity constraints in order to be added to the branching node */
129 #define DEFAULT_ADDBDSFEAS 1.0 /**< minimal feasibility value for bound inequalities in order to be added to the branching node */
130 #define DEFAULT_ADDEXTENDEDBDS TRUE /**< should added complementarity constraints be extended to SOS1 constraints to get tighter bound inequalities */
132 /* selection rules */
133 #define DEFAULT_NSTRONGROUNDS 0 /**< maximal number of strong branching rounds to perform for each node (-1: auto)
134  * (only available for neighborhood and bipartite branching) */
135 #define DEFAULT_NSTRONGITER 10000 /**< maximal number LP iterations to perform for each strong branching round (-2: auto, -1: no limit) */
136 
137 /* separation */
138 #define DEFAULT_BOUNDCUTSFROMSOS1 FALSE /**< if TRUE separate bound inequalities from SOS1 constraints */
139 #define DEFAULT_BOUNDCUTSFROMGRAPH TRUE /**< if TRUE separate bound inequalities from the conflict graph */
140 #define DEFAULT_AUTOCUTSFROMSOS1 TRUE /**< if TRUE then automatically switch to separating from SOS1 constraints if the SOS1 constraints do not overlap */
141 #define DEFAULT_BOUNDCUTSFREQ 10 /**< frequency for separating bound cuts; zero means to separate only in the root node */
142 #define DEFAULT_BOUNDCUTSDEPTH 40 /**< node depth of separating bound cuts (-1: no limit) */
143 #define DEFAULT_MAXBOUNDCUTS 50 /**< maximal number of bound cuts separated per branching node */
144 #define DEFAULT_MAXBOUNDCUTSROOT 150 /**< maximal number of bound cuts separated per iteration in the root node */
145 #define DEFAULT_STRTHENBOUNDCUTS TRUE /**< if TRUE then bound cuts are strengthened in case bound variables are available */
146 #define DEFAULT_IMPLCUTSFREQ 0 /**< frequency for separating implied bound cuts; zero means to separate only in the root node */
147 #define DEFAULT_IMPLCUTSDEPTH 40 /**< node depth of separating implied bound cuts (-1: no limit) */
148 #define DEFAULT_MAXIMPLCUTS 50 /**< maximal number of implied bound cuts separated per branching node */
149 #define DEFAULT_MAXIMPLCUTSROOT 150 /**< maximal number of implied bound cuts separated per iteration in the root node */
151 /* event handler properties */
152 #define EVENTHDLR_NAME "SOS1"
153 #define EVENTHDLR_DESC "bound change event handler for SOS1 constraints"
155 /* defines */
156 #define DIVINGCUTOFFVALUE 1e6
157 
159 /** constraint data for SOS1 constraints */
160 struct SCIP_ConsData
161 {
162  int nvars; /**< number of variables in the constraint */
163  int maxvars; /**< maximal number of variables (= size of storage) */
164  int nfixednonzeros; /**< number of variables fixed to be nonzero */
165  SCIP_Bool local; /**< TRUE if constraint is only valid locally */
166  SCIP_VAR** vars; /**< variables in constraint */
167  SCIP_ROW* rowlb; /**< row corresponding to lower bounds, or NULL if not yet created */
168  SCIP_ROW* rowub; /**< row corresponding to upper bounds, or NULL if not yet created */
169  SCIP_Real* weights; /**< weights determining the order (ascending), or NULL if not used */
170 };
171 
172 
173 /** node data of a given node in the conflict graph */
174 struct SCIP_NodeData
175 {
176  SCIP_VAR* var; /**< variable belonging to node */
177  SCIP_VAR* lbboundvar; /**< bound variable @p z from constraint \f$x \geq \mu \cdot z\f$ (or NULL if not existent) */
178  SCIP_VAR* ubboundvar; /**< bound variable @p z from constraint \f$x \leq \mu \cdot z\f$ (or NULL if not existent) */
179  SCIP_Real lbboundcoef; /**< value \f$\mu\f$ from constraint \f$x \geq \mu z \f$ (0.0 if not existent) */
180  SCIP_Real ubboundcoef; /**< value \f$\mu\f$ from constraint \f$x \leq \mu z \f$ (0.0 if not existent) */
181  SCIP_Bool lbboundcomp; /**< TRUE if the nodes from the connected component of the conflict graph the given node belongs to
182  * all have the same lower bound variable */
183  SCIP_Bool ubboundcomp; /**< TRUE if the nodes from the connected component of the conflict graph the given node belongs to
184  * all have the same lower bound variable */
185 };
186 typedef struct SCIP_NodeData SCIP_NODEDATA;
187 
188 
189 /** successor data of a given nodes successor in the implication graph */
190 struct SCIP_SuccData
191 {
192  SCIP_Real lbimpl; /**< lower bound implication */
193  SCIP_Real ubimpl; /**< upper bound implication */
194 };
195 typedef struct SCIP_SuccData SCIP_SUCCDATA;
196 
197 
198 /** tclique data for bound cut generation */
199 struct TCLIQUE_Data
200 {
201  SCIP* scip; /**< SCIP data structure */
202  SCIP_CONSHDLR* conshdlr; /**< SOS1 constraint handler */
203  SCIP_DIGRAPH* conflictgraph; /**< conflict graph */
204  SCIP_SOL* sol; /**< LP solution to be separated (or NULL) */
205  SCIP_Real scaleval; /**< factor for scaling weights */
206  SCIP_Bool cutoff; /**< whether a cutoff occurred */
207  int ncuts; /**< number of bound cuts found in this iteration */
208  int nboundcuts; /**< number of bound cuts found so far */
209  int maxboundcuts; /**< maximal number of clique cuts separated per separation round (-1: no limit) */
210  SCIP_Bool strthenboundcuts; /**< if TRUE then bound cuts are strengthened in case bound variables are available */
211 };
214 /** SOS1 constraint handler data */
215 struct SCIP_ConshdlrData
216 {
217  /* conflict graph */
218  SCIP_DIGRAPH* conflictgraph; /**< conflict graph */
219  SCIP_DIGRAPH* localconflicts; /**< local conflicts */
220  SCIP_Bool isconflocal; /**< if TRUE then local conflicts are present and conflict graph has to be updated for each node */
221  SCIP_HASHMAP* varhash; /**< hash map from variable to node in the conflict graph */
222  int nsos1vars; /**< number of problem variables that are part of the SOS1 conflict graph */
223  /* adjacency matrix */
224  int maxsosadjacency; /**< do not create an adjacency matrix if number of SOS1 variables is larger than predefined
225  * value (-1: no limit) */
226  /* implication graph */
227  SCIP_DIGRAPH* implgraph; /**< implication graph (@p j is successor of @p i if and only if \f$ x_i\not = 0 \Rightarrow x_j\not = 0\f$) */
228  int nimplnodes; /**< number of nodes in the implication graph */
229  /* tclique graph */
230  TCLIQUE_GRAPH* tcliquegraph; /**< tclique graph data structure */
231  TCLIQUE_DATA* tcliquedata; /**< tclique data */
232  /* event handler */
233  SCIP_EVENTHDLR* eventhdlr; /**< event handler for bound change events */
234  SCIP_VAR** fixnonzerovars; /**< stack of variables fixed to nonzero marked by event handler */
235  int maxnfixnonzerovars; /**< size of stack fixnonzerovars */
236  int nfixnonzerovars; /**< number of variables fixed to nonzero marked by event handler */
237  /* presolving */
238  int cntextsos1; /**< counts number of extended SOS1 constraints */
239  int maxextensions; /**< maximal number of extensions that will be computed for each SOS1 constraint */
240  int maxtightenbds; /**< maximal number of bound tightening rounds per presolving round (-1: no limit) */
241  SCIP_Bool perfimplanalysis; /**< if TRUE then perform implication graph analysis (might add additional SOS1 constraints) */
242  int depthimplanalysis; /**< number of recursive calls of implication graph analysis (-1: no limit) */
243  /* propagation */
244  SCIP_Bool conflictprop; /**< whether to use conflict graph propagation */
245  SCIP_Bool implprop; /**< whether to use implication graph propagation */
246  SCIP_Bool sosconsprop; /**< whether to use SOS1 constraint propagation */
247  /* branching */
248  char branchingrule; /**< which branching rule should be applied ? ('n': neighborhood, 'b': bipartite, 's': SOS1/clique)
249  * (note: in some cases an automatic switching to SOS1 branching is possible) */
250  SCIP_Bool autosos1branch; /**< if TRUE then automatically switch to SOS1 branching if the SOS1 constraints do not overlap */
251  SCIP_Bool fixnonzero; /**< if neighborhood branching is used, then fix the branching variable (if positive in sign) to the value of the
252  * feasibility tolerance */
253  SCIP_Bool addcomps; /**< if TRUE then add complementarity constraints to the branching nodes additionally to domain fixings
254  * (can be used in combination with neighborhood or bipartite branching) */
255  int maxaddcomps; /**< maximal number of complementarity cons. and cor. bound ineq. added per branching node (-1: no limit) */
256  int addcompsdepth; /**< only add complementarity constraints to branching nodes for predefined depth (-1: no limit) */
257  SCIP_Real addcompsfeas; /**< minimal feasibility value for complementarity constraints in order to be added to the branching node */
258  SCIP_Real addbdsfeas; /**< minimal feasibility value for bound inequalities in order to be added to the branching node */
259  SCIP_Bool addextendedbds; /**< should added complementarity constraints be extended to SOS1 constraints to get tighter bound inequalities */
260  SCIP_Bool branchsos; /**< Branch on SOS condition in enforcing? This value can only be set to false if all SOS1 variables are binary */
261  SCIP_Bool branchnonzeros; /**< Branch on SOS cons. with most number of nonzeros? */
262  SCIP_Bool branchweight; /**< Branch on SOS cons. with highest nonzero-variable weight for branching - needs branchnonzeros to be false */
263  SCIP_Bool switchsos1branch; /**< whether to switch to SOS1 branching */
264  /* selection rules */
265  int nstrongrounds; /**< maximal number of strong branching rounds to perform for each node (-1: auto)
266  * (only available for neighborhood and bipartite branching) */
267  int nstrongiter; /**< maximal number LP iterations to perform for each strong branching round (-2: auto, -1: no limit) */
268  /* separation */
269  SCIP_Bool boundcutsfromsos1; /**< if TRUE separate bound inequalities from SOS1 constraints */
270  SCIP_Bool boundcutsfromgraph; /**< if TRUE separate bound inequalities from the conflict graph */
271  SCIP_Bool autocutsfromsos1; /**< if TRUE then automatically switch to separating SOS1 constraints if the SOS1 constraints do not overlap */
272  SCIP_Bool switchcutsfromsos1; /**< whether to switch to separate bound inequalities from SOS1 constraints */
273  int boundcutsfreq; /**< frequency for separating bound cuts; zero means to separate only in the root node */
274  int boundcutsdepth; /**< node depth of separating bound cuts (-1: no limit) */
275  int maxboundcuts; /**< maximal number of bound cuts separated per branching node */
276  int maxboundcutsroot; /**< maximal number of bound cuts separated per iteration in the root node */
277  int nboundcuts; /**< number of bound cuts found so far */
278  SCIP_Bool strthenboundcuts; /**< if TRUE then bound cuts are strengthened in case bound variables are available */
279  int implcutsfreq; /**< frequency for separating implied bound cuts; zero means to separate only in the root node */
280  int implcutsdepth; /**< node depth of separating implied bound cuts (-1: no limit) */
281  int maximplcuts; /**< maximal number of implied bound cuts separated per branching node */
282  int maximplcutsroot; /**< maximal number of implied bound cuts separated per iteration in the root node */
283 };
284 
285 
286 
287 /*
288  * local methods
289  */
290 
291 /** returns whether two vertices are adjacent in the conflict graph */
292 static
294  SCIP_Bool** adjacencymatrix, /**< adjacency matrix of conflict graph (lower half) (or NULL if an adjacencymatrix is not at hand) */
295  SCIP_DIGRAPH* conflictgraph, /**< conflict graph (or NULL if an adjacencymatrix is at hand) */
296  int vertex1, /**< first vertex */
297  int vertex2 /**< second vertex */
298  )
299 {
300  assert( adjacencymatrix != NULL || conflictgraph != NULL );
301 
302  /* we do not allow self-loops */
303  if ( vertex1 == vertex2 )
304  return FALSE;
305 
306  /* for debugging */
307  if ( adjacencymatrix == NULL )
308  {
309  int succvertex;
310  int* succ;
311  int nsucc1;
312  int nsucc2;
313  int j;
314 
315  nsucc1 = SCIPdigraphGetNSuccessors(conflictgraph, vertex1);
316  nsucc2 = SCIPdigraphGetNSuccessors(conflictgraph, vertex2);
317 
318  if ( nsucc1 < 1 || nsucc2 < 1 )
319  return FALSE;
320 
321  if ( nsucc1 > nsucc2 )
322  {
323  SCIPswapInts(&vertex1, &vertex2);
324  SCIPswapInts(&nsucc1, &nsucc2);
325  }
326 
327  succ = SCIPdigraphGetSuccessors(conflictgraph, vertex1);
328  SCIPsortInt(succ, nsucc1);
329 
330  for (j = 0; j < nsucc1; ++j)
331  {
332  succvertex = succ[j];
333  if ( succvertex == vertex2 )
334  return TRUE;
335  else if ( succvertex > vertex2 )
336  return FALSE;
337  }
338  }
339  else
340  {
341  if ( vertex1 < vertex2 )
342  return adjacencymatrix[vertex2][vertex1];
343  else
344  return adjacencymatrix[vertex1][vertex2];
345  }
346 
347  return FALSE;
348 }
349 
350 
351 /** checks whether a variable violates an SOS1 constraint w.r.t. sol together with at least one other variable */
352 static
354  SCIP* scip, /**< SCIP data structure */
355  SCIP_DIGRAPH* conflictgraph, /**< conflict graph (or NULL if an adjacencymatrix is at hand) */
356  int node, /**< node of variable in the conflict graph */
357  SCIP_SOL* sol /**< solution, or NULL to use current node's solution */
358  )
359 {
360  SCIP_Real solval;
361  SCIP_VAR* var;
362 
363  assert( scip != NULL );
364  assert( conflictgraph != NULL );
365  assert( node >= 0 );
366 
367  var = SCIPnodeGetVarSOS1(conflictgraph, node);
368  assert( var != NULL );
369  solval = SCIPgetSolVal(scip, sol, var);
370 
371  /* check whether variable is nonzero w.r.t. sol and the bounds have not been fixed to zero by propagation */
372  if ( ! SCIPisFeasZero(scip, solval) && ( ! SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) || ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) ) )
373  {
374  int* succ;
375  int nsucc;
376  int s;
377 
378  nsucc = SCIPdigraphGetNSuccessors(conflictgraph, node);
379  succ = SCIPdigraphGetSuccessors(conflictgraph, node);
380 
381  /* check whether a neighbor variable is nonzero w.r.t. sol */
382  for (s = 0; s < nsucc; ++s)
383  {
384  var = SCIPnodeGetVarSOS1(conflictgraph, succ[s]);
385  assert( var != NULL );
386  solval = SCIPgetSolVal(scip, sol, var);
387  if ( ! SCIPisFeasZero(scip, solval) && ( ! SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) || ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) ) )
388  return TRUE;
389  }
390  }
391 
392  return FALSE;
393 }
394 
395 
396 /** returns solution value of imaginary binary big-M variable of a given node from the conflict graph */
397 static
399  SCIP* scip, /**< SCIP pointer */
400  SCIP_DIGRAPH* conflictgraph, /**< conflict graph */
401  SCIP_SOL* sol, /**< primal solution, or NULL for current LP/pseudo solution */
402  int node /**< node of the conflict graph */
403  )
404 {
406  SCIP_VAR* var;
407  SCIP_Real val;
408 
409  assert( scip != NULL );
410  assert( conflictgraph != NULL );
411  assert( node >= 0 && node < SCIPdigraphGetNNodes(conflictgraph) );
412 
413  var = SCIPnodeGetVarSOS1(conflictgraph, node);
414  val = SCIPgetSolVal(scip, sol, var);
415 
416  if ( SCIPisFeasNegative(scip, val) )
417  {
418  bound = SCIPvarGetLbLocal(var);
419  assert( SCIPisFeasNegative(scip, bound) );
420 
421  if ( SCIPisInfinity(scip, -val) )
422  return 1.0;
423  else if ( SCIPisInfinity(scip, -bound) )
424  return 0.0;
425  else
426  return (val/bound);
427  }
428  else if ( SCIPisFeasPositive(scip, val) )
429  {
430  bound = SCIPvarGetUbLocal(var);
431  assert( SCIPisFeasPositive(scip, bound) );
432  assert( SCIPisFeasPositive(scip, val) );
433 
434  if ( SCIPisInfinity(scip, val) )
435  return 1.0;
436  else if ( SCIPisInfinity(scip, bound) )
437  return 0.0;
438  else
439  return (val/bound);
440  }
441  else
442  return 0.0;
443 }
444 
445 
446 /** gets (variable) lower bound value of current LP relaxation solution for a given node from the conflict graph */
447 static
449  SCIP* scip, /**< SCIP pointer */
450  SCIP_DIGRAPH* conflictgraph, /**< conflict graph */
451  SCIP_SOL* sol, /**< primal solution, or NULL for current LP/pseudo solution */
452  int node /**< node of the conflict graph */
453  )
454 {
455  SCIP_NODEDATA* nodedata;
456 
457  assert( scip != NULL );
458  assert( conflictgraph != NULL );
459  assert( node >= 0 && node < SCIPdigraphGetNNodes(conflictgraph) );
460 
461  /* get node data */
462  nodedata = (SCIP_NODEDATA*)SCIPdigraphGetNodeData(conflictgraph, node);
463  assert( nodedata != NULL );
464 
465  /* if variable is not involved in a variable upper bound constraint */
466  if ( nodedata->lbboundvar == NULL || ! nodedata->lbboundcomp )
467  return SCIPvarGetLbLocal(nodedata->var);
468 
469  return nodedata->lbboundcoef * SCIPgetSolVal(scip, sol, nodedata->lbboundvar);
470 }
471 
472 
473 /** gets (variable) upper bound value of current LP relaxation solution for a given node from the conflict graph */
474 static
476  SCIP* scip, /**< SCIP pointer */
477  SCIP_DIGRAPH* conflictgraph, /**< conflict graph */
478  SCIP_SOL* sol, /**< primal solution, or NULL for current LP/pseudo solution */
479  int node /**< node of the conflict graph */
480  )
481 {
482  SCIP_NODEDATA* nodedata;
483 
484  assert( scip != NULL );
485  assert( conflictgraph != NULL );
486  assert( node >= 0 && node < SCIPdigraphGetNNodes(conflictgraph) );
487 
488  /* get node data */
489  nodedata = (SCIP_NODEDATA*)SCIPdigraphGetNodeData(conflictgraph, node);
490  assert( nodedata != NULL );
491 
492  /* if variable is not involved in a variable upper bound constraint */
493  if ( nodedata->ubboundvar == NULL || ! nodedata->ubboundcomp )
494  return SCIPvarGetUbLocal(nodedata->var);
495 
496  return nodedata->ubboundcoef * SCIPgetSolVal(scip, sol, nodedata->ubboundvar);
497 }
498 
499 
500 /** returns whether variable is part of the SOS1 conflict graph */
501 static
503  SCIP_CONSHDLRDATA* conshdlrdata, /**< SOS1 constraint handler */
504  SCIP_VAR* var /**< variable */
505  )
506 {
507  assert( conshdlrdata != NULL );
508  assert( var != NULL );
509 
510  if ( conshdlrdata->varhash == NULL || ! SCIPhashmapExists(conshdlrdata->varhash, var) )
511  return FALSE;
512 
513  return TRUE;
514 }
515 
516 
517 /** returns SOS1 index of variable or -1 if variable is not part of the SOS1 conflict graph */
518 static
519 int varGetNodeSOS1(
520  SCIP_CONSHDLRDATA* conshdlrdata, /**< SOS1 constraint handler */
521  SCIP_VAR* var /**< variable */
522  )
523 {
524  assert( conshdlrdata != NULL );
525  assert( var != NULL );
526  assert( conshdlrdata->varhash != NULL );
527 
528  if ( ! SCIPhashmapExists(conshdlrdata->varhash, var) )
529  return -1;
530 
531  return (int) (size_t) SCIPhashmapGetImage(conshdlrdata->varhash, var);
532 }
533 
534 
535 /** fix variable in given node to 0 or add constraint if variable is multi-aggregated
536  *
537  * @todo Try to handle multi-aggregated variables as in fixVariableZero() below.
538  */
539 static
541  SCIP* scip, /**< SCIP pointer */
542  SCIP_VAR* var, /**< variable to be fixed to 0*/
543  SCIP_NODE* node, /**< node */
544  SCIP_Bool* infeasible /**< if fixing is infeasible */
545  )
546 {
547  /* if variable cannot be nonzero */
548  *infeasible = FALSE;
550  {
551  *infeasible = TRUE;
552  return SCIP_OKAY;
553  }
554 
555  /* if variable is multi-aggregated */
557  {
558  SCIP_CONS* cons;
559  SCIP_Real val;
560 
561  val = 1.0;
562 
563  if ( ! SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) || ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) )
564  {
565  SCIPdebugMsg(scip, "creating constraint to force multi-aggregated variable <%s> to 0.\n", SCIPvarGetName(var));
566  /* we have to insert a local constraint var = 0 */
567  SCIP_CALL( SCIPcreateConsLinear(scip, &cons, "branch", 1, &var, &val, 0.0, 0.0, TRUE, TRUE, TRUE, TRUE, TRUE,
568  TRUE, FALSE, FALSE, FALSE, FALSE) );
569  SCIP_CALL( SCIPaddConsNode(scip, node, cons, NULL) );
570  SCIP_CALL( SCIPreleaseCons(scip, &cons) );
571  }
572  }
573  else
574  {
575  if ( ! SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) )
576  SCIP_CALL( SCIPchgVarLbNode(scip, node, var, 0.0) );
577  if ( ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) )
578  SCIP_CALL( SCIPchgVarUbNode(scip, node, var, 0.0) );
579  }
580 
581  return SCIP_OKAY;
582 }
583 
584 
585 /** try to fix variable to 0
586  *
587  * Try to treat fixing by special consideration of multiaggregated variables. For a multi-aggregation
588  * \f[
589  * x = \sum_{i=1}^n \alpha_i x_i + c,
590  * \f]
591  * we can express the fixing \f$x = 0\f$ by fixing all \f$x_i\f$ to 0 if \f$c = 0\f$ and the lower bounds of \f$x_i\f$
592  * are nonnegative if \f$\alpha_i > 0\f$ or the upper bounds are nonpositive if \f$\alpha_i < 0\f$.
593  */
594 static
596  SCIP* scip, /**< SCIP pointer */
597  SCIP_VAR* var, /**< variable to be fixed to 0*/
598  SCIP_Bool* infeasible, /**< if fixing is infeasible */
599  SCIP_Bool* tightened /**< if fixing was performed */
600  )
601 {
602  assert( scip != NULL );
603  assert( var != NULL );
604  assert( infeasible != NULL );
605  assert( tightened != NULL );
606 
607  *infeasible = FALSE;
608  *tightened = FALSE;
609 
611  {
612  SCIP_Real aggrconst;
613 
614  /* if constant is 0 */
615  aggrconst = SCIPvarGetMultaggrConstant(var);
616  if ( SCIPisZero(scip, aggrconst) )
617  {
618  SCIP_VAR** aggrvars;
619  SCIP_Real* aggrvals;
620  SCIP_Bool allnonnegative = TRUE;
621  int naggrvars;
622  int i;
623 
625 
626  /* check whether all variables are "nonnegative" */
627  naggrvars = SCIPvarGetMultaggrNVars(var);
628  aggrvars = SCIPvarGetMultaggrVars(var);
629  aggrvals = SCIPvarGetMultaggrScalars(var);
630  for (i = 0; i < naggrvars; ++i)
631  {
632  if ( (SCIPisPositive(scip, aggrvals[i]) && SCIPisNegative(scip, SCIPvarGetLbLocal(aggrvars[i]))) ||
633  (SCIPisNegative(scip, aggrvals[i]) && SCIPisPositive(scip, SCIPvarGetUbLocal(aggrvars[i]))) )
634  {
635  allnonnegative = FALSE;
636  break;
637  }
638  }
639 
640  if ( allnonnegative )
641  {
642  /* all variables are nonnegative -> fix variables */
643  for (i = 0; i < naggrvars; ++i)
644  {
645  SCIP_Bool fixed;
646  SCIP_CALL( SCIPfixVar(scip, aggrvars[i], 0.0, infeasible, &fixed) );
647  if ( *infeasible )
648  return SCIP_OKAY;
649  *tightened = *tightened || fixed;
650  }
651  }
652  }
653  }
654  else
655  {
656  SCIP_CALL( SCIPfixVar(scip, var, 0.0, infeasible, tightened) );
657  }
658 
659  return SCIP_OKAY;
660 }
661 
662 
663 /** fix variable in local node to 0, and return whether the operation was feasible
664  *
665  * @note We do not add a linear constraint if the variable is multi-aggregated as in
666  * fixVariableZeroNode(), since this would be too time consuming.
667  */
668 static
670  SCIP* scip, /**< SCIP pointer */
671  SCIP_VAR* var, /**< variable to be fixed to 0*/
672  SCIP_CONS* cons, /**< constraint */
673  int inferinfo, /**< info for reverse prop. */
674  SCIP_Bool* infeasible, /**< if fixing is infeasible */
675  SCIP_Bool* tightened, /**< if fixing was performed */
676  SCIP_Bool* success /**< whether fixing was successful, i.e., variable is not multi-aggregated */
677  )
678 {
679  *infeasible = FALSE;
680  *tightened = FALSE;
681  *success = FALSE;
682 
683  /* if variable cannot be nonzero */
685  {
686  *infeasible = TRUE;
687  return SCIP_OKAY;
688  }
689 
690  /* directly fix variable if it is not multi-aggregated */
692  {
693  SCIP_Bool tighten;
694 
695  /* fix lower bound */
696  SCIP_CALL( SCIPinferVarLbCons(scip, var, 0.0, cons, inferinfo, FALSE, infeasible, &tighten) );
697  *tightened = *tightened || tighten;
698 
699  /* fix upper bound */
700  SCIP_CALL( SCIPinferVarUbCons(scip, var, 0.0, cons, inferinfo, FALSE, infeasible, &tighten) );
701  *tightened = *tightened || tighten;
702 
703  *success = TRUE;
704  }
705 
706  return SCIP_OKAY;
707 }
708 
709 
710 /** add lock on variable */
711 static
713  SCIP* scip, /**< SCIP data structure */
714  SCIP_CONS* cons, /**< constraint */
715  SCIP_VAR* var /**< variable */
716  )
717 {
718  assert( scip != NULL );
719  assert( cons != NULL );
720  assert( var != NULL );
721 
722  /* rounding down == bad if lb < 0, rounding up == bad if ub > 0 */
724 
725  return SCIP_OKAY;
726 }
727 
728 
729 /** remove lock on variable */
730 static
732  SCIP* scip, /**< SCIP data structure */
733  SCIP_CONS* cons, /**< constraint */
734  SCIP_VAR* var /**< variable */
735  )
736 {
737  assert( scip != NULL );
738  assert( cons != NULL );
739  assert( var != NULL );
740 
741  /* rounding down == bad if lb < 0, rounding up == bad if ub > 0 */
743 
744  return SCIP_OKAY;
745 }
746 
747 
748 /** ensures that the vars and weights array can store at least num entries */
749 static
751  SCIP* scip, /**< SCIP data structure */
752  SCIP_CONSDATA* consdata, /**< constraint data */
753  int num, /**< minimum number of entries to store */
754  SCIP_Bool reserveWeights /**< whether the weights array is handled */
755  )
756 {
757  assert( consdata != NULL );
758  assert( consdata->nvars <= consdata->maxvars );
759 
760  if ( num > consdata->maxvars )
761  {
762  int newsize;
763 
764  newsize = SCIPcalcMemGrowSize(scip, num);
765  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->vars, consdata->maxvars, newsize) );
766  if ( reserveWeights )
767  SCIP_CALL( SCIPreallocBlockMemoryArray(scip, &consdata->weights, consdata->maxvars, newsize) );
768  consdata->maxvars = newsize;
769  }
770  assert( num <= consdata->maxvars );
771 
772  return SCIP_OKAY;
773 }
774 
775 
776 /** handle new variable */
777 static
779  SCIP* scip, /**< SCIP data structure */
780  SCIP_CONS* cons, /**< constraint */
781  SCIP_CONSDATA* consdata, /**< constraint data */
782  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
783  SCIP_VAR* var, /**< variable */
784  SCIP_Bool transformed /**< whether original variable was transformed */
785  )
786 {
787  SCIP_DIGRAPH* conflictgraph;
788  int node;
789 
790  assert( scip != NULL );
791  assert( cons != NULL );
792  assert( consdata != NULL );
793  assert( conshdlrdata != NULL );
794  assert( var != NULL );
795 
796  /* if we are in transformed problem, catch the variable's events */
797  if ( transformed )
798  {
799  assert( conshdlrdata->eventhdlr != NULL );
800 
801  /* catch bound change events of variable */
802  SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_BOUNDCHANGED, conshdlrdata->eventhdlr,
803  (SCIP_EVENTDATA*)cons, NULL) ); /*lint !e740*/
804 
805  /* if the variable if fixed to nonzero */
806  assert( consdata->nfixednonzeros >= 0 );
808  ++consdata->nfixednonzeros;
809  }
810 
811  /* install the rounding locks for the new variable */
812  SCIP_CALL( lockVariableSOS1(scip, cons, var) );
813 
814  /* branching on multiaggregated variables does not seem to work well, so avoid it */
815  SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, var) );
816 
817  /* add the new coefficient to the upper bound LP row, if necessary */
818  if ( consdata->rowub != NULL && ! SCIPisInfinity(scip, SCIPvarGetUbGlobal(var)) && ! SCIPisZero(scip, SCIPvarGetUbGlobal(var)) )
819  {
820  SCIP_CALL( SCIPaddVarToRow(scip, consdata->rowub, var, 1.0/SCIPvarGetUbGlobal(var)) );
821  }
822 
823  /* add the new coefficient to the lower bound LP row, if necessary */
824  if ( consdata->rowlb != NULL && ! SCIPisInfinity(scip, SCIPvarGetLbGlobal(var)) && ! SCIPisZero(scip, SCIPvarGetLbGlobal(var)) )
825  {
826  SCIP_CALL( SCIPaddVarToRow(scip, consdata->rowlb, var, 1.0/SCIPvarGetLbGlobal(var)) );
827  }
828 
829  /* return if the conflict graph has not been created yet */
830  conflictgraph = conshdlrdata->conflictgraph;
831  if ( conflictgraph == NULL )
832  return SCIP_OKAY;
833 
834  /* get node of variable in the conflict graph (or -1) */
835  node = varGetNodeSOS1(conshdlrdata, var);
836  assert( node < conshdlrdata->nsos1vars );
837 
838  /* if the variable is not already a node of the conflict graph */
839  if ( node < 0 )
840  {
841  /* variable does not appear in the conflict graph: switch to SOS1 branching rule, which does not make use of a conflict graph
842  * @todo: maybe recompute the conflict graph, implication graph and varhash instead */
843  SCIPdebugMsg(scip, "Switched to SOS1 branching rule, since conflict graph could be infeasible.\n");
844  conshdlrdata->switchsos1branch = TRUE;
845  return SCIP_OKAY;
846  }
847 
848  /* if the constraint is local, then there is no need to act, since local constraints are handled by the local conflict graph in the
849  * function enforceConflictgraph() */
850  if ( ! consdata->local )
851  {
852  SCIP_VAR** vars;
853  int nvars;
854  int v;
855 
856  vars = consdata->vars;
857  nvars = consdata->nvars;
858 
859  for (v = 0; v < nvars; ++v)
860  {
861  int nodev;
862 
863  if ( var == vars[v] )
864  continue;
865 
866  /* get node of variable in the conflict graph (or -1) */
867  nodev = varGetNodeSOS1(conshdlrdata, vars[v]);
868  assert( nodev < conshdlrdata->nsos1vars );
869 
870  /* if the variable is already a node of the conflict graph */
871  if ( nodev >= 0 )
872  {
873  int nsucc;
874  int nsuccv;
875 
876  nsucc = SCIPdigraphGetNSuccessors(conflictgraph, node);
877  nsuccv = SCIPdigraphGetNSuccessors(conflictgraph, nodev);
878 
879  /* add arcs if not existent */
880  SCIP_CALL( SCIPdigraphAddArcSafe(conflictgraph, nodev, node, NULL) );
881  SCIP_CALL( SCIPdigraphAddArcSafe(conflictgraph, node, nodev, NULL) );
882 
883  /* in case of new arcs: sort successors in ascending order */
884  if ( nsucc < SCIPdigraphGetNSuccessors(conflictgraph, node) )
885  {
886  SCIPdebugMsg(scip, "Added new conflict graph arc from variable %s to variable %s.\n", SCIPvarGetName(var), SCIPvarGetName(vars[v]));
887  SCIPsortInt(SCIPdigraphGetSuccessors(conflictgraph, node), SCIPdigraphGetNSuccessors(conflictgraph, node));
888  }
889 
890  if ( nsuccv < SCIPdigraphGetNSuccessors(conflictgraph, nodev) )
891  {
892  SCIPdebugMsg(scip, "Added new conflict graph arc from variable %s to variable %s.\n", SCIPvarGetName(vars[v]), SCIPvarGetName(var));
893  SCIPsortInt(SCIPdigraphGetSuccessors(conflictgraph, nodev), SCIPdigraphGetNSuccessors(conflictgraph, nodev));
894  }
895  }
896  else
897  {
898  /* variable does not appear in the conflict graph: switch to SOS1 branching rule, which does not make use of a conflict graph
899  * @todo: maybe recompute the conflict graph, implication graph and varhash instead */
900  SCIPdebugMsg(scip, "Switched to SOS1 branching rule, since conflict graph could be infeasible.\n");
901  conshdlrdata->switchsos1branch = TRUE;
902  return SCIP_OKAY;
903  }
904  }
905  }
906 
907  return SCIP_OKAY;
908 }
909 
910 
911 /** adds a variable to an SOS1 constraint, at position given by weight - ascending order */
912 static
914  SCIP* scip, /**< SCIP data structure */
915  SCIP_CONS* cons, /**< constraint */
916  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
917  SCIP_VAR* var, /**< variable to add to the constraint */
918  SCIP_Real weight /**< weight to determine position */
919  )
920 {
921  SCIP_CONSDATA* consdata;
922  SCIP_Bool transformed;
923  int pos;
924  int j;
925 
926  assert( var != NULL );
927  assert( cons != NULL );
928  assert( conshdlrdata != NULL );
929 
930  consdata = SCIPconsGetData(cons);
931  assert( consdata != NULL );
932 
933  if ( consdata->weights == NULL && consdata->maxvars > 0 )
934  {
935  SCIPerrorMessage("cannot add variable to SOS1 constraint <%s> that does not contain weights.\n", SCIPconsGetName(cons));
936  return SCIP_INVALIDCALL;
937  }
938 
939  /* are we in the transformed problem? */
940  transformed = SCIPconsIsTransformed(cons);
941 
942  /* always use transformed variables in transformed constraints */
943  if ( transformed )
944  {
945  SCIP_CALL( SCIPgetTransformedVar(scip, var, &var) );
946  }
947  assert( var != NULL );
948  assert( transformed == SCIPvarIsTransformed(var) );
949 
950  SCIP_CALL( consdataEnsurevarsSizeSOS1(scip, consdata, consdata->nvars + 1, TRUE) );
951  assert( consdata->weights != NULL );
952  assert( consdata->maxvars >= consdata->nvars+1 );
953 
954  /* find variable position */
955  for (pos = 0; pos < consdata->nvars; ++pos)
956  {
957  if ( consdata->weights[pos] > weight )
958  break;
959  }
960  assert( 0 <= pos && pos <= consdata->nvars );
961 
962  /* move other variables, if necessary */
963  for (j = consdata->nvars; j > pos; --j)
964  {
965  consdata->vars[j] = consdata->vars[j-1];
966  consdata->weights[j] = consdata->weights[j-1];
967  }
968 
969  /* insert variable */
970  consdata->vars[pos] = var;
971  consdata->weights[pos] = weight;
972  ++consdata->nvars;
973 
974  /* handle the new variable */
975  SCIP_CALL( handleNewVariableSOS1(scip, cons, consdata, conshdlrdata, var, transformed) );
976 
977  return SCIP_OKAY;
978 }
979 
980 
981 /** appends a variable to an SOS1 constraint */
982 static
984  SCIP* scip, /**< SCIP data structure */
985  SCIP_CONS* cons, /**< constraint */
986  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
987  SCIP_VAR* var /**< variable to add to the constraint */
988  )
989 {
990  SCIP_CONSDATA* consdata;
991  SCIP_Bool transformed;
992 
993  assert( var != NULL );
994  assert( cons != NULL );
995  assert( conshdlrdata != NULL );
996 
997  consdata = SCIPconsGetData(cons);
998  assert( consdata != NULL );
999 
1000  /* are we in the transformed problem? */
1001  transformed = SCIPconsIsTransformed(cons);
1002 
1003  /* always use transformed variables in transformed constraints */
1004  if ( transformed )
1005  {
1006  SCIP_CALL( SCIPgetTransformedVar(scip, var, &var) );
1007  }
1008  assert( var != NULL );
1009  assert( transformed == SCIPvarIsTransformed(var) );
1010 
1011  SCIP_CALL( consdataEnsurevarsSizeSOS1(scip, consdata, consdata->nvars + 1, FALSE) );
1012 
1013  /* insert variable */
1014  consdata->vars[consdata->nvars] = var;
1015  assert( consdata->weights != NULL || consdata->nvars > 0 );
1016  if ( consdata->weights != NULL && consdata->nvars > 0 )
1017  consdata->weights[consdata->nvars] = consdata->weights[consdata->nvars-1] + 1.0;
1018  ++consdata->nvars;
1019 
1020  /* handle the new variable */
1021  SCIP_CALL( handleNewVariableSOS1(scip, cons, consdata, conshdlrdata, var, transformed) );
1022 
1023  return SCIP_OKAY;
1024 }
1025 
1026 
1027 /** deletes a variable of an SOS1 constraint */
1028 static
1030  SCIP* scip, /**< SCIP data structure */
1031  SCIP_CONS* cons, /**< constraint */
1032  SCIP_CONSDATA* consdata, /**< constraint data */
1033  SCIP_EVENTHDLR* eventhdlr, /**< corresponding event handler */
1034  int pos /**< position of variable in array */
1035  )
1036 {
1037  int j;
1038 
1039  assert( 0 <= pos && pos < consdata->nvars );
1040 
1041  /* remove lock of variable */
1042  SCIP_CALL( unlockVariableSOS1(scip, cons, consdata->vars[pos]) );
1043 
1044  /* drop events on variable */
1045  SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[pos], SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlr, (SCIP_EVENTDATA*)cons, -1) ); /*lint !e740*/
1046 
1047  /* delete variable - need to copy since order is important */
1048  for (j = pos; j < consdata->nvars-1; ++j)
1049  {
1050  consdata->vars[j] = consdata->vars[j+1]; /*lint !e679*/
1051  if ( consdata->weights != NULL )
1052  consdata->weights[j] = consdata->weights[j+1]; /*lint !e679*/
1053  }
1054  --consdata->nvars;
1055 
1056  return SCIP_OKAY;
1057 }
1058 
1059 
1060 /* ----------------------------- presolving --------------------------------------*/
1061 
1062 /** extends a given clique of the conflict graph
1063  *
1064  * Implementation of the Bron-Kerbosch Algorithm from the paper:
1065  * Algorithm 457: Finding all Cliques of an Undirected Graph, Bron & Kerbosch, Commun. ACM, 1973
1066  */
1067 static
1069  SCIP* scip, /**< SCIP pointer */
1070  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
1071  SCIP_Bool** adjacencymatrix, /**< adjacencymatrix of the conflict graph (only lower half filled) */
1072  SCIP_DIGRAPH* vertexcliquegraph, /**< graph that contains the information which cliques contain a given vertex
1073  * vertices of variables = 0, ..., nsos1vars-1; vertices of cliques = nsos1vars, ..., nsos1vars+ncliques-1*/
1074  int nsos1vars, /**< number of SOS1 variables */
1075  int nconss, /**< number of SOS1 constraints */
1076  SCIP_CONS* cons, /**< constraint to be extended */
1077  SCIP_VAR** vars, /**< variables of extended clique */
1078  SCIP_Real* weights, /**< weights of extended clique */
1079  SCIP_Bool firstcall, /**< whether this is the first call of extension operator */
1080  SCIP_Bool usebacktrack, /**< whether backtracking is needed for the computation */
1081  int** cliques, /**< all cliques found so far */
1082  int* ncliques, /**< number of clique found so far */
1083  int* cliquesizes, /**< number of variables of current clique */
1084  int* newclique, /**< clique we want to extended*/
1085  int* workingset, /**< set of vertices that already served as extension and set of candidates that probably will lead to an extension */
1086  int nworkingset, /**< length of array workingset */
1087  int nexts, /**< number of vertices that already served as extension */
1088  int pos, /**< position of potential candidate */
1089  int* maxextensions, /**< maximal number of extensions */
1090  int* naddconss, /**< number of added constraints */
1091  SCIP_Bool* success /**< pointer to store if at least one new clique was found */
1092  )
1093 {
1094  int* workingsetnew = NULL;
1095  int nextsnew;
1096  int nworkingsetnew;
1097  int mincands;
1098  int btriter = 0; /* backtrack iterator */
1099  int selvertex;
1100  int selpos = -1;
1101  int fixvertex = -1;
1102  int i;
1103  int j;
1104 
1105  assert( scip != NULL );
1106  assert( conshdlrdata != NULL );
1107  assert( adjacencymatrix != NULL );
1108  assert( vertexcliquegraph != NULL );
1109  assert( cons != NULL );
1110  assert( cliques != NULL );
1111  assert( cliquesizes != NULL );
1112  assert( newclique != NULL );
1113  assert( workingset != NULL );
1114  assert( maxextensions != NULL );
1115  assert( naddconss != NULL );
1116  assert( success != NULL );
1117 
1118  if ( firstcall )
1119  *success = FALSE;
1120 
1121  mincands = nworkingset;
1122  if ( mincands < 1 )
1123  return SCIP_OKAY;
1124 
1125  /* allocate buffer array */
1126  SCIP_CALL( SCIPallocBufferArray(scip, &workingsetnew, nworkingset) );
1127 
1128 #ifdef SCIP_DEBUG
1129  for (i = 0; i < nexts; ++i)
1130  {
1131  int vertex = workingset[i];
1132  for (j = nexts; j < nworkingset; ++j)
1133  {
1134  assert( isConnectedSOS1(adjacencymatrix, NULL, vertex, workingset[j]) );
1135  }
1136  }
1137 #endif
1138 
1139  /* determine candidate with minimum number of disconnections */
1140  for (i = 0; i < nworkingset; ++i)
1141  {
1142  int vertex;
1143  int cnt = 0;
1144 
1145  vertex = workingset[i];
1146 
1147  /* count disconnections */
1148  for (j = nexts; j < nworkingset && cnt < mincands; ++j)
1149  {
1150  if ( vertex != workingset[j] && ! isConnectedSOS1(adjacencymatrix, NULL, vertex, workingset[j]) )
1151  {
1152  cnt++;
1153 
1154  /* save position of potential candidate */
1155  pos = j;
1156  }
1157  }
1158 
1159  /* check whether a new minimum was found */
1160  if ( cnt < mincands )
1161  {
1162  fixvertex = vertex;
1163  mincands = cnt;
1164  if ( i < nexts )
1165  {
1166  assert( pos >= 0 );
1167  selpos = pos;
1168  }
1169  else
1170  {
1171  selpos = i;
1172 
1173  /* preincrement */
1174  btriter = 1;
1175  }
1176  }
1177  }
1178 
1179  /* If fixed point is initially chosen from candidates then number of disconnections will be preincreased by one. */
1180 
1181  /* backtrackcycle */
1182  for (btriter = mincands + btriter; btriter >= 1; --btriter)
1183  {
1184  assert( selpos >= 0);
1185  assert( fixvertex >= 0);
1186 
1187  /* interchange */
1188  selvertex = workingset[selpos];
1189  workingset[selpos] = workingset[nexts];
1190  workingset[nexts] = selvertex;
1191 
1192  /* create new workingset */
1193  nextsnew = 0;
1194  for (j = 0 ; j < nexts; ++j)
1195  {
1196  if ( isConnectedSOS1(adjacencymatrix, NULL, selvertex, workingset[j]) )
1197  workingsetnew[nextsnew++] = workingset[j];
1198  }
1199  nworkingsetnew = nextsnew;
1200  for (j = nexts + 1; j < nworkingset; ++j)
1201  {
1202  if ( isConnectedSOS1(adjacencymatrix, NULL, selvertex, workingset[j]) )
1203  workingsetnew[nworkingsetnew++] = workingset[j];
1204  }
1205 
1206  newclique[cliquesizes[*ncliques]++] = selvertex;
1207 
1208  /* if we found a new clique */
1209  if ( nworkingsetnew == 0 )
1210  {
1211  char consname[SCIP_MAXSTRLEN];
1212  SCIP_CONSDATA* consdata;
1213  SCIP_CONS* newcons;
1214  int cliqueind;
1215 
1216  cliqueind = nsos1vars + *ncliques; /* index of clique in the vertex-clique graph */
1217 
1218  /* save new clique */
1219  assert( cliquesizes[*ncliques] >= 0 && cliquesizes[*ncliques] <= nsos1vars );
1220  assert( *ncliques < MAX(1, conshdlrdata->maxextensions) * nconss );
1221  SCIP_CALL( SCIPallocBufferArray(scip, &(cliques[*ncliques]), cliquesizes[*ncliques]) );/*lint !e866*/
1222  for (j = 0 ; j < cliquesizes[*ncliques]; ++j)
1223  {
1224  vars[j] = SCIPnodeGetVarSOS1(conshdlrdata->conflictgraph, newclique[j]);
1225  weights[j] = j+1;
1226  cliques[*ncliques][j] = newclique[j];
1227  }
1228 
1229  SCIPsortInt(cliques[*ncliques], cliquesizes[*ncliques]);
1230 
1231  /* create new constraint */
1232  (void) SCIPsnprintf(consname, SCIP_MAXSTRLEN, "extsos1_%" SCIP_LONGINT_FORMAT, conshdlrdata->cntextsos1, conshdlrdata->cntextsos1);
1233 
1234  SCIP_CALL( SCIPcreateConsSOS1(scip, &newcons, consname, cliquesizes[*ncliques], vars, weights,
1238  SCIPconsIsDynamic(cons),
1240 
1241  consdata = SCIPconsGetData(newcons);
1242 
1243  /* add directed edges to the vertex-clique graph */
1244  for (j = 0; j < consdata->nvars; ++j)
1245  {
1246  /* add arc from clique vertex to clique (needed in presolRoundConssSOS1() to delete redundand cliques) */
1247  SCIP_CALL( SCIPdigraphAddArcSafe(vertexcliquegraph, cliques[*ncliques][j], cliqueind, NULL) );
1248  }
1249 
1250  SCIP_CALL( SCIPaddCons(scip, newcons) );
1251  SCIP_CALL( SCIPreleaseCons(scip, &newcons) );
1252 
1253  ++(*naddconss);
1254  ++(conshdlrdata->cntextsos1);
1255  ++(*ncliques);
1256  cliquesizes[*ncliques] = cliquesizes[*ncliques-1]; /* cliquesizes[*ncliques] = size of newclique */
1257 
1258  *success = TRUE;
1259 
1260  --(*maxextensions);
1261 
1262  if ( *maxextensions <= 0 )
1263  {
1264  SCIPfreeBufferArray(scip, &workingsetnew);
1265  return SCIP_OKAY;
1266  }
1267  }
1268  else if ( nextsnew < nworkingsetnew ) /* else if the number of of candidates equals zero */
1269  {
1270  /* if backtracking is used, it is necessary to keep the memory for 'workingsetnew' */
1271  if ( usebacktrack )
1272  {
1273  SCIP_CALL( extensionOperatorSOS1(scip, conshdlrdata, adjacencymatrix, vertexcliquegraph, nsos1vars, nconss, cons, vars, weights, FALSE, usebacktrack,
1274  cliques, ncliques, cliquesizes, newclique, workingsetnew, nworkingsetnew, nextsnew, pos, maxextensions, naddconss, success) );
1275  if ( *maxextensions <= 0 )
1276  {
1277  SCIPfreeBufferArrayNull(scip, &workingsetnew);
1278  return SCIP_OKAY;
1279  }
1280  }
1281  else
1282  {
1283  int w;
1284 
1285  assert( nworkingset >= nworkingsetnew );
1286  for (w = 0; w < nworkingsetnew; ++w)
1287  workingset[w] = workingsetnew[w];
1288  nworkingset = nworkingsetnew;
1289 
1290  SCIPfreeBufferArrayNull(scip, &workingsetnew);
1291 
1292  SCIP_CALL( extensionOperatorSOS1(scip, conshdlrdata, adjacencymatrix, vertexcliquegraph, nsos1vars, nconss, cons, vars, weights, FALSE, usebacktrack,
1293  cliques, ncliques, cliquesizes, newclique, workingset, nworkingset, nextsnew, pos, maxextensions, naddconss, success) );
1294  assert( *maxextensions <= 0 );
1295  return SCIP_OKAY;
1296  }
1297  }
1298  assert( workingsetnew != NULL );
1299  assert( workingset != NULL );
1300 
1301  /* remove selvertex from clique */
1302  --cliquesizes[*ncliques];
1303 
1304  /* add selvertex to the set of vertices that already served as extension */
1305  ++nexts;
1306 
1307  if ( btriter > 1 )
1308  {
1309  /* select a candidate that is not connected to the fixed vertex */
1310  for (j = nexts; j < nworkingset; ++j)
1311  {
1312  assert( fixvertex != workingset[j] );
1313  if ( ! isConnectedSOS1(adjacencymatrix, NULL, fixvertex, workingset[j]) )
1314  {
1315  selpos = j;
1316  break;
1317  }
1318  }
1319  }
1320  }
1321 
1322  SCIPfreeBufferArrayNull(scip, &workingsetnew);
1323 
1324  return SCIP_OKAY;
1325 }
1326 
1327 
1328 /** generates conflict graph that is induced by the variables of a linear constraint */
1329 static
1331  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
1332  SCIP_DIGRAPH* conflictgraphlin, /**< conflict graph of linear constraint (nodes: 1, ..., nlinvars) */
1333  SCIP_DIGRAPH* conflictgraphorig, /**< original conflict graph (nodes: 1, ..., nsos1vars) */
1334  SCIP_VAR** linvars, /**< linear variables in linear constraint */
1335  int nlinvars, /**< number of linear variables in linear constraint */
1336  int* posinlinvars /**< posinlinvars[i] = position (index) of SOS1 variable i in linear constraint,
1337  * posinlinvars[i]= -1 if @p i is not a SOS1 variable or not a variable of the linear constraint */
1338  )
1339 {
1340  int indexinsosvars;
1341  int indexinlinvars;
1342  int* succ;
1343  int nsucc;
1344  int v;
1345  int s;
1346 
1347  assert( conflictgraphlin != NULL );
1348  assert( conflictgraphorig != NULL );
1349  assert( linvars != NULL );
1350  assert( posinlinvars != NULL );
1351 
1352  for (v = 1; v < nlinvars; ++v) /* we start with v = 1, since "indexinlinvars < v" (see below) is never fulfilled for v = 0 */
1353  {
1354  indexinsosvars = varGetNodeSOS1(conshdlrdata, linvars[v]);
1355 
1356  /* if linvars[v] is contained in at least one SOS1 constraint */
1357  if ( indexinsosvars >= 0 )
1358  {
1359  succ = SCIPdigraphGetSuccessors(conflictgraphorig, indexinsosvars);
1360  nsucc = SCIPdigraphGetNSuccessors(conflictgraphorig, indexinsosvars);
1361 
1362  for (s = 0; s < nsucc; ++s)
1363  {
1364  assert( succ[s] >= 0 );
1365  indexinlinvars = posinlinvars[succ[s]];
1366  assert( indexinlinvars < nlinvars );
1367 
1368  if ( indexinlinvars >= 0 && indexinlinvars < v )
1369  {
1370  SCIP_CALL( SCIPdigraphAddArcSafe(conflictgraphlin, v, indexinlinvars, NULL) );
1371  SCIP_CALL( SCIPdigraphAddArcSafe(conflictgraphlin, indexinlinvars, v, NULL) );
1372  }
1373  }
1374  }
1375  }
1376 
1377  return SCIP_OKAY;
1378 }
1379 
1380 
1381 /** determine the common successors of the vertices from the considered clique */
1382 static
1384  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
1385  SCIP_DIGRAPH* conflictgraph, /**< conflict graph */
1386  int* clique, /**< current clique */
1387  SCIP_VAR** vars, /**< clique variables */
1388  int nvars, /**< number of clique variables */
1389  int* comsucc, /**< pointer to store common successors of clique vertices (size = nvars) */
1390  int* ncomsucc /**< pointer to store number common successors of clique vertices */
1391  )
1392 {
1393  int nsucc;
1394  int* succ;
1395  int ind;
1396  int k = 0;
1397  int v;
1398  int i;
1399  int j;
1400 
1401  assert( conflictgraph != NULL );
1402  assert( clique != NULL );
1403  assert( vars != NULL );
1404  assert( comsucc != NULL );
1405  assert( ncomsucc != NULL );
1406 
1407  *ncomsucc = 0;
1408 
1409  /* determine the common successors of the vertices from the considered clique */
1410 
1411  /* determine successors of variable var[0] that are not in the clique */
1412  assert(vars[0] != NULL );
1413  ind = varGetNodeSOS1(conshdlrdata, vars[0]);
1414  assert( ind >= 0 && ind < SCIPdigraphGetNNodes(conflictgraph) );
1415  nsucc = SCIPdigraphGetNSuccessors(conflictgraph, ind);
1416  succ = SCIPdigraphGetSuccessors(conflictgraph, ind);
1417 
1418  for (j = 0; j < nvars; ++j)
1419  {
1420  for (i = k; i < nsucc; ++i)
1421  {
1422  if ( succ[i] > clique[j] )
1423  {
1424  k = i;
1425  break;
1426  }
1427  else if ( succ[i] == clique[j] )
1428  {
1429  k = i + 1;
1430  break;
1431  }
1432  else
1433  comsucc[(*ncomsucc)++] = succ[i];
1434  }
1435  }
1436 
1437  /* for all variables except the first one */
1438  for (v = 1; v < nvars; ++v)
1439  {
1440  int ncomsuccsave = 0;
1441  k = 0;
1442 
1443  assert(vars[v] != NULL );
1444  ind = varGetNodeSOS1(conshdlrdata, vars[v]);
1445  assert( ind >= 0 && ind < SCIPdigraphGetNNodes(conflictgraph) );
1446 
1447  if ( ind >= 0 )
1448  {
1449  nsucc = SCIPdigraphGetNSuccessors(conflictgraph, ind);
1450  succ = SCIPdigraphGetSuccessors(conflictgraph, ind);
1451 
1452  /* determine successors that are in comsucc */
1453  for (j = 0; j < *ncomsucc; ++j)
1454  {
1455  for (i = k; i < nsucc; ++i)
1456  {
1457  if ( succ[i] > comsucc[j] )
1458  {
1459  k = i;
1460  break;
1461  }
1462  else if ( succ[i] == comsucc[j] )
1463  {
1464  comsucc[ncomsuccsave++] = succ[i];
1465  k = i + 1;
1466  break;
1467  }
1468  }
1469  }
1470  *ncomsucc = ncomsuccsave;
1471  }
1472  }
1473 
1474  return SCIP_OKAY;
1475 }
1476 
1477 
1478 /** get nodes whose corresponding SOS1 variables are nonzero if an SOS1 variable of a given node is nonzero */
1479 static
1481  SCIP* scip, /**< SCIP pointer */
1482  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
1483  SCIP_VAR** vars, /**< problem and SOS1 variables */
1484  SCIP_DIGRAPH* implgraph, /**< implication graph (@p j is successor of @p i if and only if \f$ x_i\not = 0 \Rightarrow x_j\not = 0\f$) */
1485  SCIP_HASHMAP* implhash, /**< hash map from variable to node in implication graph */
1486  SCIP_Bool* implnodes, /**< implnodes[i] = TRUE if the SOS1 variable corresponding to node i in the implication graph is implied to be nonzero */
1487  int node /**< node of the implication graph */
1488  )
1489 {
1490  SCIP_SUCCDATA** succdatas;
1491  int sos1node;
1492  int* succ;
1493  int nsucc;
1494  int s;
1495 
1496  assert( scip != NULL );
1497  assert( implgraph != NULL );
1498  assert( implnodes != NULL );
1499  assert( node >= 0 );
1500  assert( vars[node] != NULL );
1501  assert( (int) (size_t) SCIPhashmapGetImage(implhash, vars[node]) == node );
1502 
1503  /* get node of variable in the conflict graph (-1 if variable is no SOS1 variable) */
1504  sos1node = varGetNodeSOS1(conshdlrdata, vars[node]);
1505  if ( sos1node < 0 )
1506  return SCIP_OKAY;
1507 
1508  succdatas = (SCIP_SUCCDATA**) SCIPdigraphGetSuccessorsData(implgraph, node);
1509  nsucc = SCIPdigraphGetNSuccessors(implgraph, node);
1510  succ = SCIPdigraphGetSuccessors(implgraph, node);
1511 
1512  for (s = 0; s < nsucc; ++s)
1513  {
1514  SCIP_SUCCDATA* data;
1515  int succnode;
1516  succnode = succ[s];
1517  data = succdatas[s];
1518  sos1node = varGetNodeSOS1(conshdlrdata, vars[succnode]);
1519 
1520  /* if node is SOS1 and the corresponding variable is implied to be nonzero */
1521  assert( succdatas[s] != NULL );
1522  if ( sos1node >= 0 && ! implnodes[sos1node] && ( SCIPisFeasPositive(scip, data->lbimpl) || SCIPisFeasNegative(scip, data->ubimpl) ) )
1523  {
1524  assert( sos1node == succnode );
1525  implnodes[sos1node] = TRUE;
1526  SCIP_CALL( getSOS1Implications(scip, conshdlrdata, vars, implgraph, implhash, implnodes, succnode) );
1527  }
1528  }
1529 
1530  return SCIP_OKAY;
1531 }
1532 
1533 
1534 /** perform one presolving round for a single SOS1 constraint
1535  *
1536  * We perform the following presolving steps.
1537  *
1538  * - If the bounds of some variable force it to be nonzero, we can
1539  * fix all other variables to zero and remove the SOS1 constraints
1540  * that contain it.
1541  * - If a variable is fixed to zero, we can remove the variable.
1542  * - If a variable appears twice, it can be fixed to 0.
1543  * - We substitute appregated variables.
1544  */
1545 static
1547  SCIP* scip, /**< SCIP pointer */
1548  SCIP_CONS* cons, /**< constraint */
1549  SCIP_CONSDATA* consdata, /**< constraint data */
1550  SCIP_EVENTHDLR* eventhdlr, /**< event handler */
1551  SCIP_Bool* substituted, /**< whether a variable was substituted */
1552  SCIP_Bool* cutoff, /**< whether a cutoff happened */
1553  SCIP_Bool* success, /**< whether we performed a successful reduction */
1554  int* ndelconss, /**< number of deleted constraints */
1555  int* nupgdconss, /**< number of upgraded constraints */
1556  int* nfixedvars, /**< number of fixed variables */
1557  int* nremovedvars /**< number of variables removed */
1558  )
1559 {
1560  SCIP_VAR** vars;
1561  SCIP_Bool allvarsbinary;
1562  SCIP_Bool infeasible;
1563  SCIP_Bool fixed;
1564  int nfixednonzeros;
1565  int lastFixedNonzero;
1566  int j;
1567 
1568  assert( scip != NULL );
1569  assert( cons != NULL );
1570  assert( consdata != NULL );
1571  assert( eventhdlr != NULL );
1572  assert( cutoff != NULL );
1573  assert( success != NULL );
1574  assert( ndelconss != NULL );
1575  assert( nfixedvars != NULL );
1576  assert( nremovedvars != NULL );
1577 
1578  *substituted = FALSE;
1579  *cutoff = FALSE;
1580  *success = FALSE;
1581 
1582  SCIPdebugMsg(scip, "Presolving SOS1 constraint <%s>.\n", SCIPconsGetName(cons) );
1583 
1584  j = 0;
1585  nfixednonzeros = 0;
1586  lastFixedNonzero = -1;
1587  allvarsbinary = TRUE;
1588  vars = consdata->vars;
1589 
1590  /* check for variables fixed to 0 and bounds that fix a variable to be nonzero */
1591  while ( j < consdata->nvars )
1592  {
1593  int l;
1594  SCIP_VAR* var;
1595  SCIP_Real lb;
1596  SCIP_Real ub;
1597  SCIP_Real scalar;
1598  SCIP_Real constant;
1599 
1600  scalar = 1.0;
1601  constant = 0.0;
1602 
1603  /* check for aggregation: if the constant is zero the variable is zero iff the aggregated
1604  * variable is 0 */
1605  var = vars[j];
1606  SCIP_CALL( SCIPgetProbvarSum(scip, &var, &scalar, &constant) );
1607 
1608  /* if constant is zero and we get a different variable, substitute variable */
1609  if ( SCIPisZero(scip, constant) && ! SCIPisZero(scip, scalar) && var != vars[j] )
1610  {
1611  SCIPdebugMsg(scip, "substituted variable <%s> by <%s>.\n", SCIPvarGetName(vars[j]), SCIPvarGetName(var));
1612  SCIP_CALL( SCIPdropVarEvent(scip, consdata->vars[j], SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlr, (SCIP_EVENTDATA*)cons, -1) ); /*lint !e740*/
1613  SCIP_CALL( SCIPcatchVarEvent(scip, var, SCIP_EVENTTYPE_BOUNDCHANGED, eventhdlr, (SCIP_EVENTDATA*)cons, NULL) ); /*lint !e740*/
1614 
1615  /* change the rounding locks */
1616  SCIP_CALL( unlockVariableSOS1(scip, cons, consdata->vars[j]) );
1617  SCIP_CALL( lockVariableSOS1(scip, cons, var) );
1618 
1619  vars[j] = var;
1620  *substituted = TRUE;
1621  }
1622 
1623  /* check whether the variable appears again later */
1624  for (l = j+1; l < consdata->nvars; ++l)
1625  {
1626  /* if variable appeared before, we can fix it to 0 and remove it */
1627  if ( vars[j] == vars[l] )
1628  {
1629  SCIPdebugMsg(scip, "variable <%s> appears twice in constraint, fixing it to 0.\n", SCIPvarGetName(vars[j]));
1630  SCIP_CALL( SCIPfixVar(scip, vars[j], 0.0, &infeasible, &fixed) );
1631 
1632  if ( infeasible )
1633  {
1634  *cutoff = TRUE;
1635  return SCIP_OKAY;
1636  }
1637  if ( fixed )
1638  ++(*nfixedvars);
1639  }
1640  }
1641 
1642  /* get bounds */
1643  lb = SCIPvarGetLbLocal(vars[j]);
1644  ub = SCIPvarGetUbLocal(vars[j]);
1645 
1646  /* if the variable if fixed to nonzero */
1647  if ( SCIPisFeasPositive(scip, lb) || SCIPisFeasNegative(scip, ub) )
1648  {
1649  ++nfixednonzeros;
1650  lastFixedNonzero = j;
1651  }
1652 
1653  /* if the variable is fixed to 0 */
1654  if ( SCIPisFeasZero(scip, lb) && SCIPisFeasZero(scip, ub) )
1655  {
1656  SCIPdebugMsg(scip, "deleting variable <%s> fixed to 0.\n", SCIPvarGetName(vars[j]));
1657  SCIP_CALL( deleteVarSOS1(scip, cons, consdata, eventhdlr, j) );
1658  ++(*nremovedvars);
1659  }
1660  else
1661  {
1662  /* check whether all variables are binary */
1663  if ( ! SCIPvarIsBinary(vars[j]) )
1664  allvarsbinary = FALSE;
1665 
1666  ++j;
1667  }
1668  }
1669 
1670  /* if the number of variables is less than 2 */
1671  if ( consdata->nvars < 2 )
1672  {
1673  SCIPdebugMsg(scip, "Deleting SOS1 constraint <%s> with < 2 variables.\n", SCIPconsGetName(cons));
1674 
1675  /* delete constraint */
1676  assert( ! SCIPconsIsModifiable(cons) );
1677  SCIP_CALL( SCIPdelCons(scip, cons) );
1678  ++(*ndelconss);
1679  *success = TRUE;
1680  return SCIP_OKAY;
1681  }
1682 
1683  /* if more than one variable are fixed to be nonzero, we are infeasible */
1684  if ( nfixednonzeros > 1 )
1685  {
1686  SCIPdebugMsg(scip, "The problem is infeasible: more than one variable has bounds that keep it from being 0.\n");
1687  assert( lastFixedNonzero >= 0 );
1688  *cutoff = TRUE;
1689  return SCIP_OKAY;
1690  }
1691 
1692  /* if there is exactly one fixed nonzero variable */
1693  if ( nfixednonzeros == 1 )
1694  {
1695  assert( lastFixedNonzero >= 0 );
1696 
1697  /* fix all other variables to zero */
1698  for (j = 0; j < consdata->nvars; ++j)
1699  {
1700  if ( j != lastFixedNonzero )
1701  {
1702  SCIP_CALL( fixVariableZero(scip, vars[j], &infeasible, &fixed) );
1703  if ( infeasible )
1704  {
1705  *cutoff = TRUE;
1706  return SCIP_OKAY;
1707  }
1708  if ( fixed )
1709  ++(*nfixedvars);
1710  }
1711  }
1712 
1713  SCIPdebugMsg(scip, "Deleting redundant SOS1 constraint <%s> with one variable.\n", SCIPconsGetName(cons));
1714 
1715  /* delete original constraint */
1716  assert( ! SCIPconsIsModifiable(cons) );
1717  SCIP_CALL( SCIPdelCons(scip, cons) );
1718  ++(*ndelconss);
1719  *success = TRUE;
1720  }
1721  /* note: there is no need to update consdata->nfixednonzeros, since the constraint is deleted as soon nfixednonzeros > 0. */
1722  else
1723  {
1724  /* if all variables are binary create a set packing constraint */
1725  if ( allvarsbinary && SCIPfindConshdlr(scip, "setppc") != NULL )
1726  {
1727  SCIP_CONS* setpackcons;
1728 
1729  /* create, add, and release the logicor constraint */
1730  SCIP_CALL( SCIPcreateConsSetpack(scip, &setpackcons, SCIPconsGetName(cons), consdata->nvars, consdata->vars,
1734  SCIP_CALL( SCIPaddCons(scip, setpackcons) );
1735  SCIP_CALL( SCIPreleaseCons(scip, &setpackcons) );
1736 
1737  SCIPdebugMsg(scip, "Upgrading SOS1 constraint <%s> to set packing constraint.\n", SCIPconsGetName(cons));
1738 
1739  /* remove the SOS1 constraint globally */
1740  assert( ! SCIPconsIsModifiable(cons) );
1741  SCIP_CALL( SCIPdelCons(scip, cons) );
1742  ++(*nupgdconss);
1743  *success = TRUE;
1744  }
1745  }
1746 
1747  return SCIP_OKAY;
1748 }
1749 
1750 
1751 
1752 /** perform one presolving round for all SOS1 constraints
1753  *
1754  * We perform the following presolving steps.
1755  *
1756  * - If the bounds of some variable force it to be nonzero, we can
1757  * fix all other variables to zero and remove the SOS1 constraints
1758  * that contain it.
1759  * - If a variable is fixed to zero, we can remove the variable.
1760  * - If a variable appears twice, it can be fixed to 0.
1761  * - We substitute appregated variables.
1762  * - Remove redundant SOS1 constraints
1763  *
1764  * If the adjacency matrix of the conflict graph is present, then
1765  * we perform the following additional presolving steps
1766  *
1767  * - Search for larger SOS1 constraints in the conflict graph
1768  */
1769 static
1771  SCIP* scip, /**< SCIP pointer */
1772  SCIP_EVENTHDLR* eventhdlr, /**< event handler */
1773  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
1774  SCIP_DIGRAPH* conflictgraph, /**< conflict graph */
1775  SCIP_Bool** adjacencymatrix, /**< adjacency matrix of conflict graph (or NULL) */
1776  SCIP_CONS** conss, /**< SOS1 constraints */
1777  int nconss, /**< number of SOS1 constraints */
1778  int nsos1vars, /**< number of SOS1 variables */
1779  int* naddconss, /**< number of added constraints */
1780  int* ndelconss, /**< number of deleted constraints */
1781  int* nupgdconss, /**< number of upgraded constraints */
1782  int* nfixedvars, /**< number of fixed variables */
1783  int* nremovedvars, /**< number of variables removed */
1784  SCIP_RESULT* result /**< result */
1785  )
1786 {
1787  SCIP_DIGRAPH* vertexcliquegraph;
1788  SCIP_VAR** consvars;
1789  SCIP_Real* consweights;
1790  int** cliques = NULL;
1791  int ncliques = 0;
1792  int* cliquesizes = NULL;
1793  int* newclique = NULL;
1794  int* indconss = NULL;
1795  int* lengthconss = NULL;
1796  int* comsucc = NULL;
1797  int csize;
1798  int iter;
1799  int c;
1800 
1801  assert( scip != NULL );
1802  assert( eventhdlr != NULL );
1803  assert( conshdlrdata != NULL );
1804  assert( conflictgraph != NULL );
1805  assert( conss != NULL );
1806  assert( naddconss != NULL );
1807  assert( ndelconss != NULL );
1808  assert( nupgdconss != NULL );
1809  assert( nfixedvars != NULL );
1810  assert( nremovedvars != NULL );
1811  assert( result != NULL );
1812 
1813  /* create digraph whose nodes represent variables and cliques in the conflict graph */
1814  csize = MAX(1, conshdlrdata->maxextensions) * nconss;
1815  SCIP_CALL( SCIPdigraphCreate(&vertexcliquegraph, nsos1vars + csize) );
1816 
1817  /* allocate buffer arrays */
1818  SCIP_CALL( SCIPallocBufferArray(scip, &consvars, nsos1vars) );
1819  SCIP_CALL( SCIPallocBufferArray(scip, &consweights, nsos1vars) );
1820  SCIP_CALL( SCIPallocBufferArray(scip, &cliquesizes, csize) );
1821  SCIP_CALL( SCIPallocBufferArray(scip, &newclique, nsos1vars) );
1822  SCIP_CALL( SCIPallocBufferArray(scip, &indconss, csize) );
1823  SCIP_CALL( SCIPallocBufferArray(scip, &lengthconss, csize) );
1824  SCIP_CALL( SCIPallocBufferArray(scip, &comsucc, MAX(nsos1vars, csize)) );
1825  SCIP_CALL( SCIPallocBufferArray(scip, &cliques, csize) );
1826 
1827  /* get constraint indices and sort them in descending order of their lengths */
1828  for (c = 0; c < nconss; ++c)
1829  {
1830  SCIP_CONSDATA* consdata;
1831 
1832  consdata = SCIPconsGetData(conss[c]);
1833  assert( consdata != NULL );
1834 
1835  indconss[c] = c;
1836  lengthconss[c] = consdata->nvars;
1837  }
1838  SCIPsortDownIntInt(lengthconss, indconss, nconss);
1839 
1840  /* check each constraint */
1841  for (iter = 0; iter < nconss; ++iter)
1842  {
1843  SCIP_CONSDATA* consdata;
1844  SCIP_CONS* cons;
1845  SCIP_Bool substituted;
1846  SCIP_Bool success;
1847  SCIP_Bool cutoff;
1848  int savennupgdconss;
1849  int savendelconss;
1850 
1851  SCIP_VAR** vars;
1852  int nvars;
1853 
1854  c = indconss[iter];
1855 
1856  assert( conss != NULL );
1857  assert( conss[c] != NULL );
1858  cons = conss[c];
1859  consdata = SCIPconsGetData(cons);
1860 
1861  assert( consdata != NULL );
1862  assert( consdata->nvars >= 0 );
1863  assert( consdata->nvars <= consdata->maxvars );
1864  assert( ! SCIPconsIsModifiable(cons) );
1865  assert( ncliques < csize );
1866 
1867  savendelconss = *ndelconss;
1868  savennupgdconss = *nupgdconss;
1869 
1870  /* perform one presolving round for SOS1 constraint */
1871  SCIP_CALL( presolRoundConsSOS1(scip, cons, consdata, eventhdlr, &substituted, &cutoff, &success, ndelconss, nupgdconss, nfixedvars, nremovedvars) );
1872 
1873  if ( cutoff )
1874  {
1875  *result = SCIP_CUTOFF;
1876  break;
1877  }
1878 
1879  if ( *ndelconss > savendelconss || *nupgdconss > savennupgdconss || substituted )
1880  {
1881  *result = SCIP_SUCCESS;
1882  continue;
1883  }
1884 
1885  if ( success )
1886  *result = SCIP_SUCCESS;
1887 
1888  /* get number of variables of constraint */
1889  nvars = consdata->nvars;
1890 
1891  /* get variables of constraint */
1892  vars = consdata->vars;
1893 
1894  if ( nvars > 1 && conshdlrdata->maxextensions != 0 )
1895  {
1896  SCIP_Bool extended = FALSE;
1897  int cliquesize = 0;
1898  int ncomsucc = 0;
1899  int varprobind;
1900  int j;
1901 
1902  /* get clique and size of clique */
1903  for (j = 0; j < nvars; ++j)
1904  {
1905  varprobind = varGetNodeSOS1(conshdlrdata, vars[j]);
1906 
1907  if ( varprobind >= 0 )
1908  newclique[cliquesize++] = varprobind;
1909  }
1910 
1911  if ( cliquesize > 1 )
1912  {
1913  cliquesizes[ncliques] = cliquesize;
1914 
1915  /* sort clique vertices */
1916  SCIPsortInt(newclique, cliquesizes[ncliques]);
1917 
1918  /* check if clique is contained in an already known clique */
1919  if ( ncliques > 0 )
1920  {
1921  int* succ;
1922  int nsucc;
1923  int v;
1924 
1925  varprobind = newclique[0];
1926  ncomsucc = SCIPdigraphGetNSuccessors(vertexcliquegraph, varprobind);
1927  succ = SCIPdigraphGetSuccessors(vertexcliquegraph, varprobind);
1928 
1929  /* get all (already processed) cliques that contain 'varpropind' */
1930  for (j = 0; j < ncomsucc; ++j)
1931  {
1932  /* successors should have been sorted in a former step of the algorithm */
1933  assert( j == 0 || succ[j] > succ[j-1] );
1934  comsucc[j] = succ[j];
1935  }
1936 
1937  /* loop through remaining nodes of clique (case v = 0 already processed) */
1938  for (v = 1; v < cliquesize && ncomsucc > 0; ++v)
1939  {
1940  varprobind = newclique[v];
1941 
1942  /* get all (already processed) cliques that contain 'varpropind' */
1943  nsucc = SCIPdigraphGetNSuccessors(vertexcliquegraph, varprobind);
1944  succ = SCIPdigraphGetSuccessors(vertexcliquegraph, varprobind);
1945  assert( succ != NULL || nsucc == 0 );
1946 
1947  if ( nsucc < 1 )
1948  {
1949  ncomsucc = 0;
1950  break;
1951  }
1952 
1953  /* get intersection with comsucc */
1954  SCIP_CALL( SCIPcomputeArraysIntersection(comsucc, ncomsucc, succ, nsucc, comsucc, &ncomsucc) );
1955  }
1956  }
1957 
1958  /* if constraint is redundand then delete it */
1959  if ( ncomsucc > 0 )
1960  {
1961  assert( ! SCIPconsIsModifiable(cons) );
1962  SCIP_CALL( SCIPdelCons(scip, cons) );
1963  ++(*ndelconss);
1964  *result = SCIP_SUCCESS;
1965  continue;
1966  }
1967 
1968  if ( conshdlrdata->maxextensions != 0 && adjacencymatrix != NULL )
1969  {
1970  int maxextensions;
1971  ncomsucc = 0;
1972 
1973  /* determine the common successors of the vertices from the considered clique */
1974  SCIP_CALL( cliqueGetCommonSuccessorsSOS1(conshdlrdata, conflictgraph, newclique, vars, nvars, comsucc, &ncomsucc) );
1975 
1976  /* find extensions for the clique */
1977  maxextensions = conshdlrdata->maxextensions;
1978  extended = FALSE;
1979  SCIP_CALL( extensionOperatorSOS1(scip, conshdlrdata, adjacencymatrix, vertexcliquegraph, nsos1vars, nconss, cons, consvars, consweights,
1980  TRUE, (maxextensions <= 1) ? FALSE : TRUE, cliques, &ncliques, cliquesizes, newclique, comsucc, ncomsucc, 0, -1, &maxextensions,
1981  naddconss, &extended) );
1982  }
1983 
1984  /* if an extension was found for the current clique then free the old SOS1 constraint */
1985  if ( extended )
1986  {
1987  assert( ! SCIPconsIsModifiable(cons) );
1988  SCIP_CALL( SCIPdelCons(scip, cons) );
1989  ++(*ndelconss);
1990  *result = SCIP_SUCCESS;
1991  }
1992  else /* if we keep the constraint */
1993  {
1994  int cliqueind;
1995 
1996  cliqueind = nsos1vars + ncliques; /* index of clique in vertex-clique graph */
1997 
1998  /* add directed edges to the vertex-clique graph */
1999  assert( cliquesize >= 0 && cliquesize <= nsos1vars );
2000  assert( ncliques < csize );
2001  SCIP_CALL( SCIPallocBufferArray(scip, &cliques[ncliques], cliquesize) );/*lint !e866*/
2002  for (j = 0; j < cliquesize; ++j)
2003  {
2004  cliques[ncliques][j] = newclique[j];
2005  SCIP_CALL( SCIPdigraphAddArcSafe(vertexcliquegraph, cliques[ncliques][j], cliqueind, NULL) );
2006  }
2007 
2008  /* update number of maximal cliques */
2009  ++ncliques;
2010  }
2011  }
2012  }
2013  }
2014 
2015  /* free buffer arrays */
2016  for (c = ncliques-1; c >= 0; --c)
2017  SCIPfreeBufferArrayNull(scip, &cliques[c]);
2018  SCIPfreeBufferArrayNull(scip, &cliques);
2019  SCIPfreeBufferArrayNull(scip, &comsucc);
2020  SCIPfreeBufferArrayNull(scip, &lengthconss);
2021  SCIPfreeBufferArrayNull(scip, &indconss);
2022  SCIPfreeBufferArrayNull(scip, &newclique);
2023  SCIPfreeBufferArrayNull(scip, &cliquesizes);
2024  SCIPfreeBufferArrayNull(scip, &consweights);
2025  SCIPfreeBufferArrayNull(scip, &consvars);
2026  SCIPdigraphFree(&vertexcliquegraph);
2027 
2028  return SCIP_OKAY;
2029 }
2030 
2031 
2032 /** performs implication graph analysis
2033  *
2034  * Tentatively fixes a variable to nonzeero and extracts consequences from it:
2035  * - adds (possibly new) complementarity constraints to the problem if variables are implied to be zero
2036  * - returns that the subproblem is infeasible if the domain of a variable turns out to be empty
2037  */
2038 static
2040  SCIP* scip, /**< SCIP pointer */
2041  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
2042  SCIP_DIGRAPH* conflictgraph, /**< conflict graph */
2043  SCIP_VAR** totalvars, /**< problem and SOS1 variables */
2044  SCIP_DIGRAPH* implgraph, /**< implication graph (@p j is successor of @p i if and only if \f$ x_i\not = 0 \Rightarrow x_j\not = 0\f$) */
2045  SCIP_HASHMAP* implhash, /**< hash map from variable to node in implication graph */
2046  SCIP_Bool** adjacencymatrix, /**< adjacencymatrix of the conflict graph (only lower half filled) */
2047  int givennode, /**< node of the conflict graph */
2048  int nonznode, /**< node of the conflict graph that is implied to be nonzero if given node is nonzero */
2049  SCIP_Real* impllbs, /**< current lower variable bounds if given node is nonzero (update possible) */
2050  SCIP_Real* implubs, /**< current upper variable bounds if given node is nonzero (update possible) */
2051  SCIP_Bool* implnodes, /**< indicates which variables are currently implied to be nonzero if given node is nonzero (update possible) */
2052  int* naddconss, /**< pointer to store number of added SOS1 constraints */
2053  int* probingdepth, /**< pointer to store current probing depth */
2054  SCIP_Bool* infeasible /**< pointer to store whether the subproblem gets infeasible if variable to 'nonznode' is nonzero */
2055  )
2056 {
2057  SCIP_SUCCDATA** succdatas;
2058  int succnode;
2059  int* succ;
2060  int nsucc;
2061  int s;
2062 
2063  assert( nonznode >= 0 && nonznode < SCIPdigraphGetNNodes(conflictgraph) );
2064 
2065  /* check probing depth */
2066  if ( conshdlrdata->depthimplanalysis >= 0 && *probingdepth >= conshdlrdata->depthimplanalysis )
2067  return SCIP_OKAY;
2068  ++(*probingdepth);
2069 
2070  /* get successors of 'nonznode' in the conflict graph */
2071  nsucc = SCIPdigraphGetNSuccessors(conflictgraph, nonznode);
2072  succ = SCIPdigraphGetSuccessors(conflictgraph, nonznode);
2073 
2074  /* loop through neighbors of 'nonznode' in the conflict graph; these variables are implied to be zero */
2075  for (s = 0; s < nsucc; ++s)
2076  {
2077  succnode = succ[s];
2078 
2079  /* if the current variable domain of the successor node does not contain the value zero then return that the problem is infeasible
2080  * else if 'succnode' is not already complementary to 'givennode' then add a new complementarity constraint */
2081  if ( givennode == succnode || SCIPisFeasPositive(scip, impllbs[succnode]) || SCIPisFeasNegative(scip, implubs[succnode]) )
2082  {
2083  *infeasible = TRUE;
2084  return SCIP_OKAY;
2085  }
2086  else if ( ! isConnectedSOS1(adjacencymatrix, NULL, givennode, succnode) )
2087  {
2088  char namesos[SCIP_MAXSTRLEN];
2089  SCIP_CONS* soscons = NULL;
2090  SCIP_VAR* var1;
2091  SCIP_VAR* var2;
2092 
2093  /* update implied bounds of succnode */
2094  impllbs[succnode] = 0;
2095  implubs[succnode] = 0;
2096 
2097  /* add arcs to the conflict graph */
2098  SCIP_CALL( SCIPdigraphAddArcSafe(conflictgraph, givennode, succnode, NULL) );
2099  SCIP_CALL( SCIPdigraphAddArcSafe(conflictgraph, succnode, givennode, NULL) );
2100 
2101  /* resort successors */
2102  SCIPsortInt(SCIPdigraphGetSuccessors(conflictgraph, givennode), SCIPdigraphGetNSuccessors(conflictgraph, givennode));
2103  SCIPsortInt(SCIPdigraphGetSuccessors(conflictgraph, succnode), SCIPdigraphGetNSuccessors(conflictgraph, succnode));
2104 
2105  /* update adjacencymatrix */
2106  if ( givennode > succnode )
2107  adjacencymatrix[givennode][succnode] = 1;
2108  else
2109  adjacencymatrix[succnode][givennode] = 1;
2110 
2111  var1 = SCIPnodeGetVarSOS1(conflictgraph, givennode);
2112  var2 = SCIPnodeGetVarSOS1(conflictgraph, succnode);
2113 
2114  /* create SOS1 constraint */
2115  assert( SCIPgetDepth(scip) == 0 );
2116  (void) SCIPsnprintf(namesos, SCIP_MAXSTRLEN, "presolved_sos1_%s_%s", SCIPvarGetName(var1), SCIPvarGetName(var2) );
2117  SCIP_CALL( SCIPcreateConsSOS1(scip, &soscons, namesos, 0, NULL, NULL, TRUE, TRUE, TRUE, FALSE, TRUE,
2118  FALSE, FALSE, FALSE, FALSE) );
2119 
2120  /* add variables to SOS1 constraint */
2121  SCIP_CALL( addVarSOS1(scip, soscons, conshdlrdata, var1, 1.0) );
2122  SCIP_CALL( addVarSOS1(scip, soscons, conshdlrdata, var2, 2.0) );
2123 
2124  /* add constraint */
2125  SCIP_CALL( SCIPaddCons(scip, soscons) );
2126 
2127  /* release constraint */
2128  SCIP_CALL( SCIPreleaseCons(scip, &soscons) );
2129 
2130  ++(*naddconss);
2131  }
2132  }
2133 
2134  /* by construction: nodes of SOS1 variables are equal for conflict graph and implication graph */
2135  assert( nonznode == (int) (size_t) SCIPhashmapGetImage(implhash, SCIPnodeGetVarSOS1(conflictgraph, nonznode)) );
2136  succdatas = (SCIP_SUCCDATA**) SCIPdigraphGetSuccessorsData(implgraph, nonznode);
2137  nsucc = SCIPdigraphGetNSuccessors(implgraph, nonznode);
2138  succ = SCIPdigraphGetSuccessors(implgraph, nonznode);
2139 
2140  /* go further in implication graph */
2141  for (s = 0; s < nsucc; ++s)
2142  {
2143  SCIP_SUCCDATA* data;
2144  int oldprobingdepth;
2145 
2146  succnode = succ[s];
2147  data = succdatas[s];
2148  oldprobingdepth = *probingdepth;
2149 
2150  /* if current lower bound is smaller than implied lower bound */
2151  if ( SCIPisFeasLT(scip, impllbs[succnode], data->lbimpl) )
2152  {
2153  impllbs[succnode] = data->lbimpl;
2154 
2155  /* if node is SOS1 and implied to be nonzero for the first time, then this recursively may imply further bound changes */
2156  if ( varGetNodeSOS1(conshdlrdata, totalvars[succnode]) >= 0 && ! implnodes[succnode] && SCIPisFeasPositive(scip, data->lbimpl) )
2157  {
2158  /* by construction: nodes of SOS1 variables are equal for conflict graph and implication graph */
2159  assert( succnode == (int) (size_t) SCIPhashmapGetImage(implhash, SCIPnodeGetVarSOS1(conflictgraph, succnode)) );
2160  implnodes[succnode] = TRUE; /* in order to avoid cycling */
2161  SCIP_CALL( performImplicationGraphAnalysis(scip, conshdlrdata, conflictgraph, totalvars, implgraph, implhash, adjacencymatrix, givennode, succnode, impllbs, implubs, implnodes, naddconss, probingdepth, infeasible) );
2162  *probingdepth = oldprobingdepth;
2163 
2164  /* return if the subproblem is known to be infeasible */
2165  if ( *infeasible )
2166  return SCIP_OKAY;
2167  }
2168  }
2169 
2170  /* if current upper bound is larger than implied upper bound */
2171  if ( SCIPisFeasGT(scip, implubs[succnode], data->ubimpl) )
2172  {
2173  implubs[succnode] = data->ubimpl;
2174 
2175  /* if node is SOS1 and implied to be nonzero for the first time, then this recursively may imply further bound changes */
2176  if ( varGetNodeSOS1(conshdlrdata, totalvars[succnode]) >= 0 && ! implnodes[succnode] && SCIPisFeasNegative(scip, data->ubimpl) )
2177  {
2178  /* by construction: nodes of SOS1 variables are equal for conflict graph and implication graph */
2179  assert( succnode == (int) (size_t) SCIPhashmapGetImage(implhash, SCIPnodeGetVarSOS1(conflictgraph, succnode)) );
2180  implnodes[succnode] = TRUE; /* in order to avoid cycling */
2181  SCIP_CALL( performImplicationGraphAnalysis(scip, conshdlrdata, conflictgraph, totalvars, implgraph, implhash, adjacencymatrix, givennode, succnode, impllbs, implubs, implnodes, naddconss, probingdepth, infeasible) );
2182  *probingdepth = oldprobingdepth;
2183 
2184  /* return if the subproblem is known to be infeasible */
2185  if ( *infeasible )
2186  return SCIP_OKAY;
2187  }
2188  }
2189  }
2190 
2191  return SCIP_OKAY;
2192 }
2193 
2194 
2195 /** returns whether node is implied to be zero; this information is taken from the input array 'implnodes' */
2196 static
2198  SCIP_DIGRAPH* conflictgraph, /**< conflict graph */
2199  SCIP_Bool* implnodes, /**< implnodes[i] = TRUE if the SOS1 variable corresponding to node i in the implication graph is implied to be nonzero */
2200  int node /**< node of the conflict graph (or -1) */
2201  )
2202 {
2203  int* succ;
2204  int nsucc;
2205  int s;
2206 
2207  if ( node < 0 )
2208  return FALSE;
2209 
2210  nsucc = SCIPdigraphGetNSuccessors(conflictgraph, node);
2211  succ = SCIPdigraphGetSuccessors(conflictgraph, node);
2212 
2213  /* check whether any successor is implied to be nonzero */
2214  for (s = 0; s < nsucc; ++s)
2215  {
2216  if ( implnodes[succ[s]] )
2217  return TRUE;
2218  }
2219 
2220  return FALSE;
2221 }
2222 
2223 
2224 /** updates arc data of implication graph */
2225 static
2227  SCIP* scip, /**< SCIP pointer */
2228  SCIP_DIGRAPH* implgraph, /**< implication graph */
2229  SCIP_HASHMAP* implhash, /**< hash map from variable to node in implication graph */
2230  SCIP_VAR** totalvars, /**< problem and SOS1 variables */
2231  SCIP_VAR* varv, /**< variable that is assumed to be nonzero */
2232  SCIP_VAR* varw, /**< implication variable */
2233  SCIP_Real lb, /**< old lower bound of \f$x_w\f$ */
2234  SCIP_Real ub, /**< old upper bound of \f$x_w\f$ */
2235  SCIP_Real newbound, /**< new bound of \f$x_w\f$ */
2236  SCIP_Bool lower, /**< whether to consider lower bound implication (otherwise upper bound) */
2237  int* nchgbds, /**< pointer to store number of changed bounds */
2238  SCIP_Bool* update, /**< pointer to store whether implication graph has been updated */
2239  SCIP_Bool* infeasible /**< pointer to store whether an infeasibility has been detected */
2240  )
2241 {
2242  SCIP_SUCCDATA** succdatas;
2243  SCIP_SUCCDATA* data = NULL;
2244  int nsucc;
2245  int* succ;
2246  int indv;
2247  int indw;
2248  int s;
2249 
2250  assert( scip != NULL );
2251  assert( implgraph != NULL );
2252  assert( implhash != NULL );
2253  assert( totalvars != NULL );
2254  assert( varv != NULL );
2255  assert( varw != NULL );
2256 
2257  /* if x_v != 0 turns out to be infeasible then fix x_v = 0 */
2258  if ( ( lower && SCIPisFeasLT(scip, ub, newbound) ) || ( ! lower && SCIPisFeasGT(scip, lb, newbound) ) )
2259  {
2260  SCIP_Bool infeasible1;
2261  SCIP_Bool infeasible2;
2262  SCIP_Bool tightened1;
2263  SCIP_Bool tightened2;
2264 
2265  SCIP_CALL( SCIPtightenVarLb(scip, varv, 0.0, FALSE, &infeasible1, &tightened1) );
2266  SCIP_CALL( SCIPtightenVarUb(scip, varv, 0.0, FALSE, &infeasible2, &tightened2) );
2267 
2268  if ( infeasible1 || infeasible2 )
2269  {
2270  SCIPdebugMsg(scip, "detected infeasibility while trying to fix variable <%s> to zero\n", SCIPvarGetName(varv));
2271  *infeasible = TRUE;
2272  }
2273 
2274  if ( tightened1 || tightened2 )
2275  {
2276  SCIPdebugMsg(scip, "fixed variable %s from lb = %f and ub = %f to 0.0 \n", SCIPvarGetName(varv), lb, ub);
2277  ++(*nchgbds);
2278  }
2279  }
2280 
2281  /* get successor information */
2282  indv = (int) (size_t) SCIPhashmapGetImage(implhash, varv); /* get index of x_v in implication graph */
2283  assert( (int) (size_t) SCIPhashmapGetImage(implhash, totalvars[indv]) == indv );
2284  succdatas = (SCIP_SUCCDATA**) SCIPdigraphGetSuccessorsData(implgraph, indv);
2285  nsucc = SCIPdigraphGetNSuccessors(implgraph, indv);
2286  succ = SCIPdigraphGetSuccessors(implgraph, indv);
2287 
2288  /* search for nodew in existing successors. If this is the case then check whether the lower implication bound may be updated ... */
2289  indw = (int) (size_t) SCIPhashmapGetImage(implhash, varw);
2290  assert( (int) (size_t) SCIPhashmapGetImage(implhash, totalvars[indw]) == indw );
2291  for (s = 0; s < nsucc; ++s)
2292  {
2293  if ( succ[s] == indw )
2294  {
2295  data = succdatas[s];
2296  assert( data != NULL );
2297  if ( lower && SCIPisFeasLT(scip, data->lbimpl, newbound) )
2298  {
2299  if ( SCIPvarIsIntegral(varw) )
2300  data->lbimpl = SCIPceil(scip, newbound);
2301  else
2302  data->lbimpl = newbound;
2303 
2304  *update = TRUE;
2305  SCIPdebugMsg(scip, "updated to implication %s != 0 -> %s >= %f\n", SCIPvarGetName(varv), SCIPvarGetName(varw), newbound);
2306  }
2307  else if ( ! lower && SCIPisFeasGT(scip, data->ubimpl, newbound) )
2308  {
2309  if ( SCIPvarIsIntegral(varw) )
2310  data->ubimpl = SCIPfloor(scip, newbound);
2311  else
2312  data->ubimpl = newbound;
2313 
2314  *update = TRUE;
2315  SCIPdebugMsg(scip, "updated to implication %s != 0 -> %s >= %f\n", SCIPvarGetName(varv), SCIPvarGetName(varw), newbound);
2316  }
2317  break;
2318  }
2319  }
2320 
2321  /* ..., otherwise if there does not exist an arc between indv and indw already, then create one and add implication */
2322  if ( s == nsucc )
2323  {
2324  assert( data == NULL );
2325  SCIP_CALL( SCIPallocBlockMemory(scip, &data) );
2326  if ( lower )
2327  {
2328  data->lbimpl = newbound;
2329  data->ubimpl = ub;
2330  SCIPdebugMsg(scip, "add implication %s != 0 -> %s >= %f\n", SCIPvarGetName(varv), SCIPvarGetName(varw), newbound);
2331  }
2332  else
2333  {
2334  data->lbimpl = lb;
2335  data->ubimpl = newbound;
2336  SCIPdebugMsg(scip, "add implication %s != 0 -> %s <= %f\n", SCIPvarGetName(varv), SCIPvarGetName(varw), newbound);
2337  }
2338  SCIP_CALL( SCIPdigraphAddArc(implgraph, indv, indw, (void*)data) );
2339  *update = TRUE;
2340  }
2341 
2342  return SCIP_OKAY;
2343 }
2344 
2345 
2346 /** updates implication graph
2347  *
2348  * Assume the variable from the input is nonzero. If this implies that some other variable is also nonzero, then
2349  * store this information in an implication graph
2350  */
2351 static
2353  SCIP* scip, /**< SCIP pointer */
2354  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
2355  SCIP_DIGRAPH* conflictgraph, /**< conflict graph */
2356  SCIP_Bool** adjacencymatrix, /**< adjacency matrix of conflict graph (lower half) */
2357  SCIP_DIGRAPH* implgraph, /**< implication graph (@p j is successor of @p i if and only if \f$ x_i\not = 0 \Rightarrow x_j\not = 0\f$) */
2358  SCIP_HASHMAP* implhash, /**< hash map from variable to node in implication graph */
2359  SCIP_Bool* implnodes, /**< implnodes[i] = TRUE if the SOS1 variable corresponding to node i in the implication graph is implied to be nonzero */
2360  SCIP_VAR** totalvars, /**< problem and SOS1 variables */
2361  int** cliquecovers, /**< clique covers of linear constraint */
2362  int* cliquecoversizes, /**< size of clique covers */
2363  int* varincover, /**< array with varincover[i] = cover of SOS1 index @p i */
2364  SCIP_VAR** vars, /**< variables to be checked */
2365  SCIP_Real* coefs, /**< coefficients of variables in linear constraint */
2366  int nvars, /**< number of variables to be checked */
2367  SCIP_Real* bounds, /**< bounds of variables */
2368  SCIP_VAR* var, /**< variable that is assumed to be nonzero */
2369  SCIP_Real bound, /**< bound of variable */
2370  SCIP_Real boundnonzero, /**< bound of variable if it is known to be nonzero if infinity values are not summarized */
2371  int ninftynonzero, /**< number of times infinity/-infinity has to be summarized to boundnonzero */
2372  SCIP_Bool lower, /**< TRUE if lower bounds are consideres; FALSE for upper bounds */
2373  int* nchgbds, /**< pointer to store number of changed bounds */
2374  SCIP_Bool* update, /**< pointer to store whether implication graph has been updated */
2375  SCIP_Bool* infeasible /**< pointer to store whether an infeasibility has been detected */
2376  )
2377 {
2378  int nodev;
2379  int w;
2380 
2381  assert( update != NULL );
2382 
2383  /* update implication graph if possible */
2384  *update = FALSE;
2385  *infeasible = FALSE;
2386  nodev = varGetNodeSOS1(conshdlrdata, var); /* possibly -1 if var is not involved in an SOS1 constraint */
2387 
2388  /* if nodev is an index of an SOS1 variable and at least one lower bound of a variable that is not x_v is infinity */
2389  if ( nodev < 0 || SCIPisInfinity(scip, REALABS(bound)) || ninftynonzero > 1 )
2390  return SCIP_OKAY;
2391 
2392  /* for every variable x_w: compute upper bound of a_w * x_w if x_v is known to be nonzero */
2393  for (w = 0; w < nvars; ++w)
2394  {
2395  int newninftynonzero;
2396  SCIP_Bool implinfty = FALSE;
2397  int nodew;
2398 
2399  /* get node of x_w in conflict graph: nodew = -1 if it is no SOS1 variable */
2400  nodew = varGetNodeSOS1(conshdlrdata, vars[w]);
2401 
2402  newninftynonzero = ninftynonzero;
2403 
2404  /* variable should not be fixed to be already zero (note x_v is fixed to be nonzero by assumption) */
2405  if ( nodew < 0 || ( nodev != nodew && ! isConnectedSOS1(adjacencymatrix, NULL, nodev, nodew) && ! isImpliedZero(conflictgraph, implnodes, nodew) ) )
2406  {
2407  SCIP_Real implbound;
2408  SCIP_Bool implcoverw;
2409  int nodecliq;
2410  int indcliq;
2411  int ind;
2412  int j;
2413 
2414  /* boundnonzero is the bound of x_v if x_v is nonzero we use this information to get a bound of x_w if x_v is
2415  * nonzero; therefore, we have to perform some recomputations */
2416  implbound = boundnonzero - bound;
2417  ind = varincover[w];
2418  assert( cliquecoversizes[ind] > 0 );
2419 
2420  implcoverw = FALSE;
2421  for (j = 0; j < cliquecoversizes[ind]; ++j)
2422  {
2423  indcliq = cliquecovers[ind][j];
2424  assert( 0 <= indcliq && indcliq < nvars );
2425 
2426  nodecliq = varGetNodeSOS1(conshdlrdata, vars[indcliq]); /* possibly -1 if variable is not involved in an SOS1 constraint */
2427 
2428  /* if nodecliq is not a member of an SOS1 constraint or the variable corresponding to nodecliq is not implied to be zero if x_v != 0 */
2429  if ( nodecliq < 0 || (! isConnectedSOS1(adjacencymatrix, NULL, nodev, nodecliq) && ! isImpliedZero(conflictgraph, implnodes, nodecliq) ) )
2430  {
2431  if ( indcliq == w )
2432  {
2433  if ( ! SCIPisInfinity(scip, REALABS(bounds[w])) )
2434  implbound += bounds[w];
2435  else
2436  --newninftynonzero;
2437  implcoverw = TRUE;
2438  }
2439  else if ( implcoverw )
2440  {
2441  if ( SCIPisInfinity(scip, REALABS( bounds[indcliq] )) )
2442  implinfty = TRUE;
2443  else
2444  implbound -= bounds[indcliq];
2445  break;
2446  }
2447  else
2448  {
2449  if ( SCIPisInfinity(scip, REALABS( bounds[indcliq] ) ) )
2450  implinfty = TRUE;
2451  break;
2452  }
2453  }
2454  }
2455 
2456  /* check whether x_v != 0 implies a bound change of x_w */
2457  if ( ! implinfty && newninftynonzero == 0 )
2458  {
2459  SCIP_Real newbound;
2460  SCIP_Real coef;
2461  SCIP_Real lb;
2462  SCIP_Real ub;
2463 
2464  lb = SCIPvarGetLbLocal(vars[w]);
2465  ub = SCIPvarGetUbLocal(vars[w]);
2466  coef = coefs[w];
2467 
2468  if ( SCIPisFeasZero(scip, coef) )
2469  continue;
2470 
2471  newbound = implbound / coef;
2472 
2473  /* check if an implication can be added/updated or assumption x_v != 0 is infeasible */
2474  if ( lower )
2475  {
2476  if ( SCIPisFeasPositive(scip, coef) && SCIPisFeasLT(scip, lb, newbound) )
2477  {
2478  SCIP_CALL( updateArcData(scip, implgraph, implhash, totalvars, var, vars[w], lb, ub, newbound, TRUE, nchgbds, update, infeasible) );
2479  }
2480  else if ( SCIPisFeasNegative(scip, coef) && SCIPisFeasGT(scip, ub, newbound) )
2481  {
2482  SCIP_CALL( updateArcData(scip, implgraph, implhash, totalvars, var, vars[w], lb, ub, newbound, FALSE, nchgbds, update, infeasible) );
2483  }
2484  }
2485  else
2486  {
2487  if ( SCIPisFeasPositive(scip, coef) && SCIPisFeasGT(scip, ub, newbound) )
2488  {
2489  SCIP_CALL( updateArcData(scip, implgraph, implhash, totalvars, var, vars[w], lb, ub, newbound, FALSE, nchgbds, update, infeasible) );
2490  }
2491  else if ( SCIPisFeasNegative(scip, coef) && SCIPisFeasLT(scip, lb, newbound) )
2492  {
2493  SCIP_CALL( updateArcData(scip, implgraph, implhash, totalvars, var, vars[w], lb, ub, newbound, TRUE, nchgbds, update, infeasible) );
2494  }
2495  }
2496  }
2497  }
2498  }
2499 
2500  return SCIP_OKAY;
2501 }
2502 
2503 
2504 /** search new disjoint clique that covers given node
2505  *
2506  * For a given vertex @p v search for a clique of the conflict graph induced by the variables of a linear constraint that
2507  * - covers @p v and
2508  * - has an an empty intersection with already computed clique cover.
2509  */
2510 static
2512  SCIP* scip, /**< SCIP pointer */
2513  SCIP_DIGRAPH* conflictgraphroot, /**< conflict graph of the root node (nodes: 1, ..., @p nsos1vars) */
2514  SCIP_DIGRAPH* conflictgraphlin, /**< conflict graph of linear constraint (nodes: 1, ..., @p nlinvars) */
2515  SCIP_VAR** linvars, /**< variables in linear constraint */
2516  SCIP_Bool* coveredvars, /**< states which variables of the linear constraint are currently covered by a clique */
2517  int* clique, /**< array to store new clique in cover */
2518  int* cliquesize, /**< pointer to store the size of @p clique */
2519  int v, /**< position of variable in linear constraint that should be covered */
2520  SCIP_Bool considersolvals /**< TRUE if largest auxiliary bigM values of variables should be prefered */
2521  )
2522 {
2523  int nsucc;
2524  int s;
2525 
2526  assert( conflictgraphlin != NULL );
2527  assert( linvars != NULL );
2528  assert( coveredvars != NULL );
2529  assert( clique != NULL );
2530  assert( cliquesize != NULL );
2531 
2532  assert( ! coveredvars[v] ); /* we should produce a new clique */
2533 
2534  /* add index 'v' to the clique cover */
2535  clique[0] = v;
2536  *cliquesize = 1;
2537 
2538  nsucc = SCIPdigraphGetNSuccessors(conflictgraphlin, v);
2539  if ( nsucc > 0 )
2540  {
2541  int* extensions;
2542  int nextensions = 0;
2543  int nextensionsnew;
2544  int succnode;
2545  int* succ;
2546 
2547  /* allocate buffer array */
2548  SCIP_CALL( SCIPallocBufferArray(scip, &extensions, nsucc) );
2549 
2550  succ = SCIPdigraphGetSuccessors(conflictgraphlin, v);
2551 
2552  /* compute possible extensions for the clique cover */
2553  for (s = 0; s < nsucc; ++s)
2554  {
2555  succnode = succ[s];
2556  if ( ! coveredvars[succnode] )
2557  extensions[nextensions++] = succ[s];
2558  }
2559 
2560  /* while there exist possible extensions for the clique cover */
2561  while ( nextensions > 0 )
2562  {
2563  int bestindex = -1;
2564 
2565  if ( considersolvals )
2566  {
2567  SCIP_Real bestbigMval;
2568  SCIP_Real bigMval;
2569 
2570  bestbigMval = -SCIPinfinity(scip);
2571 
2572  /* search for the extension with the largest absolute value of its LP relaxation solution value */
2573  for (s = 0; s < nextensions; ++s)
2574  {
2575  bigMval = nodeGetSolvalBinaryBigMSOS1(scip, conflictgraphroot, NULL, extensions[s]);
2576  if ( SCIPisFeasLT(scip, bestbigMval, bigMval) )
2577  {
2578  bestbigMval = bigMval;
2579  bestindex = extensions[s];
2580  }
2581  }
2582  }
2583  else
2584  bestindex = extensions[0];
2585 
2586  assert( bestindex != -1 );
2587 
2588  /* add bestindex to the clique cover */
2589  clique[(*cliquesize)++] = bestindex;
2590 
2591  /* compute new 'extensions' array */
2592  nextensionsnew = 0;
2593  for (s = 0; s < nextensions; ++s)
2594  {
2595  if ( s != bestindex && isConnectedSOS1(NULL, conflictgraphlin, bestindex, extensions[s]) )
2596  extensions[nextensionsnew++] = extensions[s];
2597  }
2598  nextensions = nextensionsnew;
2599  }
2600 
2601  /* free buffer array */
2602  SCIPfreeBufferArray(scip, &extensions);
2603  }
2604 
2605  /* mark covered indices */
2606  for (s = 0; s < *cliquesize; ++s)
2607  {
2608  int ind;
2609 
2610  ind = clique[s];
2611  assert( 0 <= ind );
2612  assert( ! coveredvars[ind] );
2613  coveredvars[ind] = TRUE;
2614  }
2615 
2616  return SCIP_OKAY;
2617 }
2618 
2619 
2620 /** try to tighten upper and lower bounds for variables */
2621 static
2623  SCIP* scip, /**< SCIP pointer */
2624  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
2625  SCIP_DIGRAPH* conflictgraph, /**< conflict graph */
2626  SCIP_DIGRAPH* implgraph, /**< implication graph (@p j is successor of @p i if and only if \f$ x_i\not = 0 \f$ implies a new lower/upper bound for \f$ x_j\f$) */
2627  SCIP_HASHMAP* implhash, /**< hash map from variable to node in implication graph */
2628  SCIP_Bool** adjacencymatrix, /**< adjacencymatrix of conflict graph */
2629  SCIP_VAR** totalvars, /**< problem and SOS1 vars */
2630  int ntotalvars, /**< number of problem and SOS1 variables*/
2631  int nsos1vars, /**< number of SOS1 variables */
2632  int* nchgbds, /**< pointer to store number of changed bounds */
2633  SCIP_Bool* implupdate, /**< pointer to store whether the implication graph has been updated in this function call */
2634  SCIP_Bool* cutoff /**< pointer to store if current nodes LP is infeasible */
2635  )
2636 {
2637  SCIP_CONSHDLR* conshdlrlinear;
2638  SCIP_CONS** linearconss;
2639  int nlinearconss;
2640 
2641  SCIP_Bool* implnodes = NULL; /* implnodes[i] = TRUE if the SOS1 variable corresponding to node i in the implication graph is implied to be nonzero */
2642  SCIP_Bool* coveredvars = NULL; /* coveredvars[i] = TRUE if variable with index i is covered by the clique cover */
2643  int* varindincons = NULL; /* varindincons[i] = position of SOS1 index i in linear constraint (-1 if x_i is not involved in linear constraint) */
2644 
2645  SCIP_VAR** trafolinvars = NULL; /* variables of transformed linear constraints without (multi)aggregated variables */
2646  int ntrafolinvars = 0;
2647  SCIP_Real* trafolinvals = NULL;
2648  SCIP_Real* trafoubs = NULL;
2649  SCIP_Real* trafolbs = NULL;
2650  SCIP_Real traforhs;
2651  SCIP_Real trafolhs;
2652 
2653  SCIP_VAR** sos1linvars = NULL; /* variables that are not contained in linear constraint, but are in conflict with a variable from the linear constraint */
2654  int nsos1linvars;
2655  int c;
2656 
2657  assert( scip != NULL );
2658  assert( conflictgraph != NULL );
2659  assert( adjacencymatrix != NULL );
2660  assert( nchgbds != NULL );
2661  assert( cutoff != NULL );
2662 
2663  *cutoff = FALSE;
2664  *implupdate = FALSE;
2665 
2666  /* get constraint handler data of linear constraints */
2667  conshdlrlinear = SCIPfindConshdlr(scip, "linear");
2668  if ( conshdlrlinear == NULL )
2669  return SCIP_OKAY;
2670 
2671  /* get linear constraints and number of linear constraints */
2672  nlinearconss = SCIPconshdlrGetNConss(conshdlrlinear);
2673  linearconss = SCIPconshdlrGetConss(conshdlrlinear);
2674 
2675  /* allocate buffer arrays */
2676  SCIP_CALL( SCIPallocBufferArray(scip, &sos1linvars, nsos1vars) );
2677  SCIP_CALL( SCIPallocBufferArray(scip, &implnodes, nsos1vars) );
2678  SCIP_CALL( SCIPallocBufferArray(scip, &varindincons, nsos1vars) );
2679  SCIP_CALL( SCIPallocBufferArray(scip, &coveredvars, ntotalvars) );
2680  SCIP_CALL( SCIPallocBufferArray(scip, &trafoubs, ntotalvars) );
2681  SCIP_CALL( SCIPallocBufferArray(scip, &trafolbs, ntotalvars) );
2682 
2683  /* for every linear constraint and every SOS1 variable */
2684  for (c = 0; c < nlinearconss + nsos1vars && ! (*cutoff); ++c)
2685  {
2686  SCIP_DIGRAPH* conflictgraphlin;
2687  int** cliquecovers = NULL; /* clique covers of indices of variables in linear constraint */
2688  int* cliquecoversizes = NULL; /* size of each cover */
2689  int ncliquecovers;
2690  SCIP_Real* cliquecovervals = NULL;
2691  int* varincover = NULL; /* varincover[i] = cover of SOS1 index i */
2692 
2693  int v;
2694  int i;
2695  int j;
2696 
2697  /* get transformed linear constraints (without aggregated variables) */
2698  if ( c < nlinearconss )
2699  {
2700  SCIP_VAR** origlinvars;
2701  int noriglinvars;
2702  SCIP_Real* origlinvals;
2703  SCIP_Real origrhs;
2704  SCIP_Real origlhs;
2705  SCIP_Real constant;
2706  int requiredsize;
2707 
2708  /* get data of linear constraint */
2709  noriglinvars = SCIPgetNVarsLinear(scip, linearconss[c]);
2710  origlinvars = SCIPgetVarsLinear(scip, linearconss[c]);
2711  origlinvals = SCIPgetValsLinear(scip, linearconss[c]);
2712  origrhs = SCIPgetRhsLinear(scip, linearconss[c]);
2713  origlhs = SCIPgetLhsLinear(scip, linearconss[c]);
2714 
2715  if ( noriglinvars < 1 )
2716  continue;
2717  assert( origlinvars != NULL );
2718  assert( origlinvals != NULL );
2719 
2720  /* copy variables and coefficients of linear constraint */
2721  SCIP_CALL( SCIPduplicateBufferArray(scip, &trafolinvars, origlinvars, noriglinvars) );
2722  SCIP_CALL( SCIPduplicateBufferArray(scip, &trafolinvals, origlinvals, noriglinvars) );
2723  ntrafolinvars = noriglinvars;
2724 
2725  /* transform linear constraint */
2726  constant = 0.0;
2727  SCIP_CALL( SCIPgetProbvarLinearSum(scip, trafolinvars, trafolinvals, &ntrafolinvars, noriglinvars, &constant, &requiredsize, TRUE) );
2728  if( requiredsize > ntrafolinvars )
2729  {
2730  SCIP_CALL( SCIPreallocBufferArray(scip, &trafolinvars, requiredsize) );
2731  SCIP_CALL( SCIPreallocBufferArray(scip, &trafolinvals, requiredsize) );
2732 
2733  SCIP_CALL( SCIPgetProbvarLinearSum(scip, trafolinvars, trafolinvals, &ntrafolinvars, requiredsize, &constant, &requiredsize, TRUE) );
2734  assert( requiredsize <= ntrafolinvars );
2735  }
2736  trafolhs = origlhs - constant;
2737  traforhs = origrhs - constant;
2738  }
2739  else
2740  {
2741  SCIP_VAR* var;
2742 
2743  var = SCIPnodeGetVarSOS1(conflictgraph, c-nlinearconss);
2744 
2746  {
2747  SCIP_Real constant;
2748 
2749  SCIP_CALL( SCIPallocBufferArray(scip, &trafolinvars, 2) );
2750  SCIP_CALL( SCIPallocBufferArray(scip, &trafolinvals, 2) );
2751 
2752  constant = SCIPvarGetAggrConstant(var);
2753  trafolinvars[0] = SCIPvarGetAggrVar(var);
2754  trafolinvals[0] = SCIPvarGetAggrScalar(var);
2755  trafolinvars[1] = var;
2756  trafolinvals[1] = -1.0;
2757  trafolhs = -constant;
2758  traforhs = -constant;
2759  ntrafolinvars = 2;
2760  }
2761  else if ( SCIPvarGetStatus(var) == SCIP_VARSTATUS_MULTAGGR )
2762  {
2763  SCIP_Real* scalars;
2764  SCIP_VAR** agrvars;
2765  SCIP_Real constant;
2766  int nagrvars;
2767 
2768  nagrvars = SCIPvarGetMultaggrNVars(var);
2769 
2770  SCIP_CALL( SCIPallocBufferArray(scip, &trafolinvars, nagrvars+1) );
2771  SCIP_CALL( SCIPallocBufferArray(scip, &trafolinvals, nagrvars+1) );
2772 
2773  agrvars = SCIPvarGetMultaggrVars(var);
2774  scalars = SCIPvarGetMultaggrScalars(var);
2775  constant = SCIPvarGetMultaggrConstant(var);
2776 
2777  for (v = 0; v < nagrvars; ++v)
2778  {
2779  trafolinvars[v] = agrvars[v];
2780  trafolinvals[v] = scalars[v];
2781  }
2782  trafolinvars[nagrvars] = var;
2783  trafolinvals[nagrvars] = -1.0;
2784  trafolhs = -constant;
2785  traforhs = -constant;
2786  ntrafolinvars = nagrvars + 1;
2787  }
2788  else if ( SCIPvarGetStatus(var) == SCIP_VARSTATUS_NEGATED )
2789  {
2790  SCIP_VAR* negvar;
2791  SCIP_Real negcons;
2792 
2793  /* get negation variable and negation offset */
2794  negvar = SCIPvarGetNegationVar(var);
2795  negcons = SCIPvarGetNegationConstant(var);
2796 
2797  SCIP_CALL( SCIPallocBufferArray(scip, &trafolinvars, 2) );
2798  SCIP_CALL( SCIPallocBufferArray(scip, &trafolinvals, 2) );
2799 
2800  trafolinvars[0] = negvar;
2801  trafolinvars[1] = var;
2802  trafolinvals[0] = 1.0;
2803  trafolinvals[1] = 1.0;
2804  trafolhs = negcons;
2805  traforhs = negcons;
2806  ntrafolinvars = 2;
2807  }
2808  else
2809  continue;
2810  }
2811 
2812  if ( ntrafolinvars == 0 )
2813  {
2814  SCIPfreeBufferArray(scip, &trafolinvars);
2815  SCIPfreeBufferArray(scip, &trafolinvals);
2816  continue;
2817  }
2818 
2819  /* compute lower and upper bounds of each term a_i * x_i of transformed constraint */
2820  for (v = 0; v < ntrafolinvars; ++v)
2821  {
2822  SCIP_Real lb = SCIPvarGetLbLocal(trafolinvars[v]);
2823  SCIP_Real ub = SCIPvarGetUbLocal(trafolinvars[v]);
2824 
2825  if ( trafolinvals[v] < 0.0 )
2826  {
2827  SCIP_Real temp;
2828 
2829  temp = lb;
2830  lb = ub;
2831  ub = temp;
2832  }
2833 
2834  if ( SCIPisInfinity(scip, REALABS(lb)) )
2835  trafolbs[v] = -SCIPinfinity(scip);
2836  else
2837  trafolbs[v] = lb * trafolinvals[v];
2838 
2839  if ( SCIPisInfinity(scip, REALABS(ub)) )
2840  trafoubs[v] = SCIPinfinity(scip);
2841  else
2842  trafoubs[v] = ub * trafolinvals[v];
2843  }
2844 
2845  /* initialization: mark all the SOS1 variables as 'not a member of the linear constraint' */
2846  for (v = 0; v < nsos1vars; ++v)
2847  varindincons[v] = -1;
2848 
2849  /* save position of SOS1 variables in linear constraint */
2850  for (v = 0; v < ntrafolinvars; ++v)
2851  {
2852  int node;
2853 
2854  node = varGetNodeSOS1(conshdlrdata, trafolinvars[v]);
2855 
2856  if ( node >= 0 )
2857  varindincons[node] = v;
2858  }
2859 
2860  /* create conflict graph of linear constraint */
2861  SCIP_CALL( SCIPdigraphCreate(&conflictgraphlin, ntrafolinvars) );
2862  SCIP_CALL( genConflictgraphLinearCons(conshdlrdata, conflictgraphlin, conflictgraph, trafolinvars, ntrafolinvars, varindincons) );
2863 
2864  /* mark all the variables as 'not covered by some clique cover' */
2865  for (i = 0; i < ntrafolinvars; ++i)
2866  coveredvars[i] = FALSE;
2867 
2868  /* allocate buffer array */
2869  SCIP_CALL( SCIPallocBufferArray(scip, &cliquecovervals, ntrafolinvars) );
2870  SCIP_CALL( SCIPallocBufferArray(scip, &cliquecoversizes, ntrafolinvars) );
2871  SCIP_CALL( SCIPallocBufferArray(scip, &cliquecovers, ntrafolinvars) );
2872 
2873  /* compute distinct cliques that cover all the variables of the linear constraint */
2874  ncliquecovers = 0;
2875  for (v = 0; v < ntrafolinvars; ++v)
2876  {
2877  /* if variable is not already covered by an already known clique cover */
2878  if ( ! coveredvars[v] )
2879  {
2880  SCIP_CALL( SCIPallocBufferArray(scip, &(cliquecovers[ncliquecovers]), ntrafolinvars) ); /*lint !e866*/
2881  SCIP_CALL( computeVarsCoverSOS1(scip, conflictgraph, conflictgraphlin, trafolinvars, coveredvars, cliquecovers[ncliquecovers], &(cliquecoversizes[ncliquecovers]), v, FALSE) );
2882  ++ncliquecovers;
2883  }
2884  }
2885 
2886  /* free conflictgraph */
2887  SCIPdigraphFree(&conflictgraphlin);
2888 
2889  /* compute variables that are not contained in transformed linear constraint, but are in conflict with a variable from the transformed linear constraint */
2890  nsos1linvars = 0;
2891  for (v = 0; v < ntrafolinvars; ++v)
2892  {
2893  int nodev;
2894 
2895  nodev = varGetNodeSOS1(conshdlrdata, trafolinvars[v]);
2896 
2897  /* if variable is an SOS1 variable */
2898  if ( nodev >= 0 )
2899  {
2900  int succnode;
2901  int nsucc;
2902  int* succ;
2903  int s;
2904 
2905  succ = SCIPdigraphGetSuccessors(conflictgraph, nodev);
2906  nsucc = SCIPdigraphGetNSuccessors(conflictgraph, nodev);
2907 
2908  for (s = 0; s < nsucc; ++s)
2909  {
2910  succnode = succ[s];
2911 
2912  /* if variable is not a member of linear constraint and not already listed in the array sos1linvars */
2913  if ( varindincons[succnode] == -1 )
2914  {
2915  sos1linvars[nsos1linvars] = SCIPnodeGetVarSOS1(conflictgraph, succnode);
2916  varindincons[succnode] = -2; /* mark variable as listed in array sos1linvars */
2917  ++nsos1linvars;
2918  }
2919  }
2920  }
2921  }
2922 
2923 
2924  /* try to tighten lower bounds */
2925 
2926  /* sort each cliquecover array in ascending order of the lower bounds of a_i * x_i; fill vector varincover */
2927  SCIP_CALL( SCIPallocBufferArray(scip, &varincover, ntrafolinvars) );
2928  for (i = 0; i < ncliquecovers; ++i)
2929  {
2930  for (j = 0; j < cliquecoversizes[i]; ++j)
2931  {
2932  int ind = cliquecovers[i][j];
2933 
2934  varincover[ind] = i;
2935  cliquecovervals[j] = trafoubs[ind];
2936  }
2937  SCIPsortDownRealInt(cliquecovervals, cliquecovers[i], cliquecoversizes[i]);
2938  }
2939 
2940  /* for every variable in transformed constraint: try lower bound tightening */
2941  for (v = 0; v < ntrafolinvars + nsos1linvars; ++v)
2942  {
2943  SCIP_Real newboundnonzero; /* new bound of a_v * x_v if we assume that x_v != 0 */
2944  SCIP_Real newboundnores; /* new bound of a_v * x_v if we assume that x_v = 0 is possible */
2945  SCIP_Real newbound; /* resulting new bound of x_v */
2946  SCIP_VAR* var;
2947  SCIP_Real trafoubv;
2948  SCIP_Real linval;
2949  SCIP_Real ub;
2950  SCIP_Real lb;
2951  SCIP_Bool tightened;
2952  SCIP_Bool infeasible;
2953  SCIP_Bool inftynores = FALSE;
2954  SCIP_Bool update;
2955  int ninftynonzero = 0;
2956  int nodev;
2957  int w;
2958 
2959  if ( v < ntrafolinvars )
2960  {
2961  var = trafolinvars[v];
2962  trafoubv = trafoubs[v];
2963  }
2964  else
2965  {
2966  assert( v >= ntrafolinvars );
2967  var = sos1linvars[v-ntrafolinvars];/*lint !e679*/
2968  trafoubv = 0.0;
2969  }
2970 
2971  ub = SCIPvarGetUbLocal(var);
2972  lb = SCIPvarGetLbLocal(var);
2973 
2974  if ( SCIPisInfinity(scip, -trafolhs) || SCIPisZero(scip, ub - lb) )
2975  continue;
2976 
2977  newboundnonzero = trafolhs;
2978  newboundnores = trafolhs;
2979  nodev = varGetNodeSOS1(conshdlrdata, var); /* possibly -1 if var is not involved in an SOS1 constraint */
2980  assert( nodev < nsos1vars );
2981 
2982  /* determine incidence vector of implication variables */
2983  for (w = 0; w < nsos1vars; ++w)
2984  implnodes[w] = FALSE;
2985  SCIP_CALL( getSOS1Implications(scip, conshdlrdata, totalvars, implgraph, implhash, implnodes, (int) (size_t) SCIPhashmapGetImage(implhash, var)) );
2986 
2987  /* compute new bound */
2988  for (i = 0; i < ncliquecovers; ++i)
2989  {
2990  int indcliq;
2991  int nodecliq;
2992 
2993  assert( cliquecoversizes[i] > 0 );
2994 
2995  indcliq = cliquecovers[i][0];
2996  assert( 0 <= indcliq && indcliq < ntrafolinvars );
2997 
2998  /* determine maximum without index v (note that the array 'cliquecovers' is sorted by the values of trafoub in non-increasing order) */
2999  if ( v != indcliq )
3000  {
3001  if ( SCIPisInfinity(scip, trafoubs[indcliq]) )
3002  inftynores = TRUE;
3003  else
3004  newboundnores -= trafoubs[indcliq];
3005  }
3006  else if ( cliquecoversizes[i] > 1 )
3007  {
3008  assert( 0 <= cliquecovers[i][1] && cliquecovers[i][1] < ntrafolinvars );
3009  if ( SCIPisInfinity(scip, trafoubs[cliquecovers[i][1]]) )
3010  inftynores = TRUE;
3011  else
3012  newboundnores -= trafoubs[cliquecovers[i][1]];/*lint --e{679}*/
3013  }
3014 
3015  /* determine maximum without index v and if x_v is nonzero (note that the array 'cliquecovers' is sorted by the values of trafoub in non-increasing order) */
3016  for (j = 0; j < cliquecoversizes[i]; ++j)
3017  {
3018  indcliq = cliquecovers[i][j];
3019  assert( 0 <= indcliq && indcliq < ntrafolinvars );
3020 
3021  nodecliq = varGetNodeSOS1(conshdlrdata, trafolinvars[indcliq]); /* possibly -1 if variable is not involved in an SOS1 constraint */
3022  assert( nodecliq < nsos1vars );
3023 
3024  if ( v != indcliq )
3025  {
3026  /* if nodev or nodecliq are not a member of an SOS1 constraint or the variable corresponding to nodecliq is not implied to be zero if x_v != 0 */
3027  if ( nodev < 0 || nodecliq < 0 || (! isConnectedSOS1(adjacencymatrix, NULL, nodev, nodecliq) && ! isImpliedZero(conflictgraph, implnodes, nodecliq) ) )
3028  {
3029  if ( SCIPisInfinity(scip, trafoubs[indcliq]) )
3030  ++ninftynonzero;
3031  else
3032  newboundnonzero -= trafoubs[indcliq];
3033  break; /* break since we are only interested in the maximum upper bound among the variables in the clique cover;
3034  * the variables in the clique cover form an SOS1 constraint, thus only one of them can be nonzero */
3035  }
3036  }
3037  }
3038  }
3039  assert( ninftynonzero == 0 || inftynores );
3040 
3041  /* if computed upper bound is not infinity and variable is contained in linear constraint */
3042  if ( ninftynonzero == 0 && v < ntrafolinvars )
3043  {
3044  linval = trafolinvals[v];
3045 
3046  if ( SCIPisFeasZero(scip, linval) )
3047  continue;
3048 
3049  /* compute new bound */
3050  if ( SCIPisFeasPositive(scip, newboundnores) && ! inftynores )
3051  newbound = newboundnonzero;
3052  else
3053  newbound = MIN(0, newboundnonzero);
3054  newbound /= linval;
3055 
3056  /* check if new bound is tighter than the old one or problem is infeasible */
3057  if ( SCIPisFeasPositive(scip, linval) && SCIPisFeasLT(scip, lb, newbound) )
3058  {
3059  if ( SCIPisFeasLT(scip, ub, newbound) )
3060  {
3061  *cutoff = TRUE;
3062  break;
3063  }
3064 
3065  if ( SCIPvarIsIntegral(var) )
3066  newbound = SCIPceil(scip, newbound);
3067 
3068  SCIP_CALL( SCIPtightenVarLb(scip, var, newbound, FALSE, &infeasible, &tightened) );
3069  assert( ! infeasible );
3070 
3071  if ( tightened )
3072  {
3073  SCIPdebugMsg(scip, "changed lower bound of variable %s from %f to %f \n", SCIPvarGetName(var), lb, newbound);
3074  ++(*nchgbds);
3075  }
3076  }
3077  else if ( SCIPisFeasNegative(scip, linval) && SCIPisFeasGT(scip, ub, newbound) )
3078  {
3079  /* if assumption a_i * x_i != 0 was not correct */
3080  if ( SCIPisFeasGT(scip, SCIPvarGetLbLocal(var), newbound) )
3081  {
3082  *cutoff = TRUE;
3083  break;
3084  }
3085 
3086  if ( SCIPvarIsIntegral(var) )
3087  newbound = SCIPfloor(scip, newbound);
3088 
3089  SCIP_CALL( SCIPtightenVarUb(scip, var, newbound, FALSE, &infeasible, &tightened) );
3090  assert( ! infeasible );
3091 
3092  if ( tightened )
3093  {
3094  SCIPdebugMsg(scip, "changed upper bound of variable %s from %f to %f \n", SCIPvarGetName(var), ub, newbound);
3095  ++(*nchgbds);
3096  }
3097  }
3098  }
3099 
3100  /* update implication graph if possible */
3101  SCIP_CALL( updateImplicationGraphSOS1(scip, conshdlrdata, conflictgraph, adjacencymatrix, implgraph, implhash, implnodes, totalvars, cliquecovers, cliquecoversizes, varincover,
3102  trafolinvars, trafolinvals, ntrafolinvars, trafoubs, var, trafoubv, newboundnonzero, ninftynonzero, TRUE, nchgbds, &update, &infeasible) );
3103  if ( infeasible )
3104  *cutoff = TRUE;
3105  else if ( update )
3106  *implupdate = TRUE;
3107  }
3108 
3109  if ( *cutoff == TRUE )
3110  {
3111  /* free memory */
3112  SCIPfreeBufferArrayNull(scip, &varincover);
3113  for (j = ncliquecovers-1; j >= 0; --j)
3114  SCIPfreeBufferArrayNull(scip, &cliquecovers[j]);
3115  SCIPfreeBufferArrayNull(scip, &cliquecovers);
3116  SCIPfreeBufferArrayNull(scip, &cliquecoversizes);
3117  SCIPfreeBufferArrayNull(scip, &cliquecovervals);
3118  SCIPfreeBufferArrayNull(scip, &trafolinvals);
3119  SCIPfreeBufferArrayNull(scip, &trafolinvars);
3120  break;
3121  }
3122 
3123 
3124  /* try to tighten upper bounds */
3125 
3126  /* sort each cliquecover array in ascending order of the lower bounds of a_i * x_i; fill vector varincover */
3127  for (i = 0; i < ncliquecovers; ++i)
3128  {
3129  for (j = 0; j < cliquecoversizes[i]; ++j)
3130  {
3131  int ind = cliquecovers[i][j];
3132 
3133  varincover[ind] = i;
3134  cliquecovervals[j] = trafolbs[ind];
3135  }
3136  SCIPsortRealInt(cliquecovervals, cliquecovers[i], cliquecoversizes[i]);
3137  }
3138 
3139  /* for every variable that is in transformed constraint or every variable that is in conflict with some variable from trans. cons.:
3140  try upper bound tightening */
3141  for (v = 0; v < ntrafolinvars + nsos1linvars; ++v)
3142  {
3143  SCIP_Real newboundnonzero; /* new bound of a_v*x_v if we assume that x_v != 0 */
3144  SCIP_Real newboundnores; /* new bound of a_v*x_v if there are no restrictions */
3145  SCIP_Real newbound; /* resulting new bound of x_v */
3146  SCIP_VAR* var;
3147  SCIP_Real linval;
3148  SCIP_Real trafolbv;
3149  SCIP_Real lb;
3150  SCIP_Real ub;
3151  SCIP_Bool tightened;
3152  SCIP_Bool infeasible;
3153  SCIP_Bool inftynores = FALSE;
3154  SCIP_Bool update;
3155  int ninftynonzero = 0;
3156  int nodev;
3157  int w;
3158 
3159  if ( v < ntrafolinvars )
3160  {
3161  var = trafolinvars[v];
3162  trafolbv = trafolbs[v];
3163  }
3164  else
3165  {
3166  assert( v-ntrafolinvars >= 0 );
3167  var = sos1linvars[v-ntrafolinvars];/*lint !e679*/
3168  trafolbv = 0.0; /* since variable is not a member of linear constraint */
3169  }
3170  lb = SCIPvarGetLbLocal(var);
3171  ub = SCIPvarGetUbLocal(var);
3172  if ( SCIPisInfinity(scip, traforhs) || SCIPisEQ(scip, lb, ub) )
3173  continue;
3174 
3175  newboundnonzero = traforhs;
3176  newboundnores = traforhs;
3177  nodev = varGetNodeSOS1(conshdlrdata, var); /* possibly -1 if var is not involved in an SOS1 constraint */
3178  assert( nodev < nsos1vars );
3179 
3180  /* determine incidence vector of implication variables (i.e., which SOS1 variables are nonzero if x_v is nonzero) */
3181  for (w = 0; w < nsos1vars; ++w)
3182  implnodes[w] = FALSE;
3183  SCIP_CALL( getSOS1Implications(scip, conshdlrdata, totalvars, implgraph, implhash, implnodes, (int) (size_t) SCIPhashmapGetImage(implhash, var)) );
3184 
3185  /* compute new bound */
3186  for (i = 0; i < ncliquecovers; ++i)
3187  {
3188  int indcliq;
3189  int nodecliq;
3190 
3191  assert( cliquecoversizes[i] > 0 );
3192 
3193  indcliq = cliquecovers[i][0];
3194  assert( 0 <= indcliq && indcliq < ntrafolinvars );
3195 
3196  /* determine minimum without index v (note that the array 'cliquecovers' is sorted by the values of trafolb in increasing order) */
3197  if ( v != indcliq )
3198  {
3199  /* if bound would be infinity */
3200  if ( SCIPisInfinity(scip, -trafolbs[indcliq]) )
3201  inftynores = TRUE;
3202  else
3203  newboundnores -= trafolbs[indcliq];
3204  }
3205  else if ( cliquecoversizes[i] > 1 )
3206  {
3207  assert( 0 <= cliquecovers[i][1] && cliquecovers[i][1] < ntrafolinvars );
3208  if ( SCIPisInfinity(scip, -trafolbs[cliquecovers[i][1]]) )
3209  inftynores = TRUE;
3210  else
3211  newboundnores -= trafolbs[cliquecovers[i][1]]; /*lint --e{679}*/
3212  }
3213 
3214  /* determine minimum without index v and if x_v is nonzero (note that the array 'cliquecovers' is sorted by the values of trafolb in increasing order) */
3215  for (j = 0; j < cliquecoversizes[i]; ++j)
3216  {
3217  indcliq = cliquecovers[i][j];
3218  assert( 0 <= indcliq && indcliq < ntrafolinvars );
3219 
3220  nodecliq = varGetNodeSOS1(conshdlrdata, trafolinvars[indcliq]); /* possibly -1 if variable is not involved in an SOS1 constraint */
3221  assert( nodecliq < nsos1vars );
3222 
3223  if ( v != indcliq )
3224  {
3225  /* if nodev or nodecliq are not a member of an SOS1 constraint or the variable corresponding to nodecliq is not implied to be zero if x_v != 0 */
3226  if ( nodev < 0 || nodecliq < 0 || (! isConnectedSOS1(adjacencymatrix, NULL, nodev, nodecliq) && ! isImpliedZero(conflictgraph, implnodes, nodecliq) ) )
3227  {
3228  /* if bound would be infinity */
3229  if ( SCIPisInfinity(scip, -trafolbs[indcliq]) )
3230  ++ninftynonzero;
3231  else
3232  newboundnonzero -= trafolbs[indcliq];
3233  break; /* break since we are only interested in the minimum lower bound among the variables in the clique cover;
3234  * the variables in the clique cover form an SOS1 constraint, thus only one of them can be nonzero */
3235  }
3236  }
3237  }
3238  }
3239  assert( ninftynonzero == 0 || inftynores );
3240 
3241 
3242  /* if computed bound is not infinity and variable is contained in linear constraint */
3243  if ( ninftynonzero == 0 && v < ntrafolinvars )
3244  {
3245  linval = trafolinvals[v];
3246 
3247  if ( SCIPisFeasZero(scip, linval) )
3248  continue;
3249 
3250  /* compute new bound */
3251  if ( SCIPisFeasNegative(scip, newboundnores) && ! inftynores )
3252  newbound = newboundnonzero;
3253  else
3254  newbound = MAX(0, newboundnonzero);
3255  newbound /= linval;
3256 
3257  /* check if new bound is tighter than the old one or problem is infeasible */
3258  if ( SCIPisFeasPositive(scip, linval) && SCIPisFeasGT(scip, ub, newbound) )
3259  {
3260  /* if new upper bound is smaller than the lower bound, we are infeasible */
3261  if ( SCIPisFeasGT(scip, lb, newbound) )
3262  {
3263  *cutoff = TRUE;
3264  break;
3265  }
3266 
3267  if ( SCIPvarIsIntegral(var) )
3268  newbound = SCIPfloor(scip, newbound);
3269 
3270  SCIP_CALL( SCIPtightenVarUb(scip, var, newbound, FALSE, &infeasible, &tightened) );
3271  assert( ! infeasible );
3272 
3273  if ( tightened )
3274  {
3275  SCIPdebugMsg(scip, "changed upper bound of variable %s from %f to %f \n", SCIPvarGetName(var), ub, newbound);
3276  ++(*nchgbds);
3277  }
3278  }
3279  else if ( SCIPisFeasNegative(scip, linval) && SCIPisFeasLT(scip, lb, newbound) )
3280  {
3281  /* if assumption a_i * x_i != 0 was not correct */
3282  if ( SCIPisFeasLT(scip, ub, newbound) )
3283  {
3284  *cutoff = TRUE;
3285  break;
3286  }
3287 
3288  if ( SCIPvarIsIntegral(var) )
3289  newbound = SCIPceil(scip, newbound);
3290 
3291  SCIP_CALL( SCIPtightenVarLb(scip, var, newbound, FALSE, &infeasible, &tightened) );
3292  assert( ! infeasible );
3293 
3294  if ( tightened )
3295  {
3296  SCIPdebugMsg(scip, "changed lower bound of variable %s from %f to %f \n", SCIPvarGetName(var), lb, newbound);
3297  ++(*nchgbds);
3298  }
3299  }
3300  }
3301 
3302  /* update implication graph if possible */
3303  SCIP_CALL( updateImplicationGraphSOS1(scip, conshdlrdata, conflictgraph, adjacencymatrix, implgraph, implhash, implnodes, totalvars, cliquecovers, cliquecoversizes, varincover,
3304  trafolinvars, trafolinvals, ntrafolinvars, trafolbs, var, trafolbv, newboundnonzero, ninftynonzero, FALSE, nchgbds, &update, &infeasible) );
3305  if ( infeasible )
3306  *cutoff = TRUE;
3307  else if ( update )
3308  *implupdate = TRUE;
3309  }
3310 
3311  /* free memory */
3312  SCIPfreeBufferArrayNull(scip, &varincover);
3313  for (j = ncliquecovers-1; j >= 0; --j)
3314  SCIPfreeBufferArrayNull(scip, &cliquecovers[j]);
3315  SCIPfreeBufferArrayNull(scip, &cliquecovers);
3316  SCIPfreeBufferArrayNull(scip, &cliquecoversizes);
3317  SCIPfreeBufferArrayNull(scip, &cliquecovervals);
3318  SCIPfreeBufferArrayNull(scip, &trafolinvals);
3319  SCIPfreeBufferArrayNull(scip, &trafolinvars);
3320 
3321  if ( *cutoff == TRUE )
3322  break;
3323  } /* end for every linear constraint */
3324 
3325  /* free buffer arrays */
3326  SCIPfreeBufferArrayNull(scip, &sos1linvars);
3327  SCIPfreeBufferArrayNull(scip, &trafolbs);
3328  SCIPfreeBufferArrayNull(scip, &trafoubs);
3329  SCIPfreeBufferArrayNull(scip, &coveredvars);
3330  SCIPfreeBufferArrayNull(scip, &varindincons);
3331  SCIPfreeBufferArrayNull(scip, &implnodes);
3332 
3333  return SCIP_OKAY;
3334 }
3335 
3336 
3337 /** perform one presolving round for variables
3338  *
3339  * We perform the following presolving steps:
3340  * - Tighten the bounds of the variables
3341  * - Update conflict graph based on bound implications of the variables
3342  */
3343 static
3345  SCIP* scip, /**< SCIP pointer */
3346  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
3347  SCIP_DIGRAPH* conflictgraph, /**< conflict graph */
3348  SCIP_Bool** adjacencymatrix, /**< adjacencymatrix of conflict graph */
3349  int nsos1vars, /**< number of SOS1 variables */
3350  int* nfixedvars, /**< pointer to store number of fixed variables */
3351  int* nchgbds, /**< pointer to store number of changed bounds */
3352  int* naddconss, /**< pointer to store number of addded constraints */
3353  SCIP_RESULT* result /**< result */
3354  )
3355 {
3356  SCIP_DIGRAPH* implgraph;
3357  SCIP_HASHMAP* implhash;
3358 
3359  SCIP_Bool cutoff = FALSE;
3360  SCIP_Bool updateconfl;
3361 
3362  SCIP_VAR** totalvars;
3363  SCIP_VAR** probvars;
3364  int ntotalvars = 0;
3365  int nprobvars;
3366  int i;
3367  int j;
3368 
3369  /* determine totalvars (union of SOS1 and problem variables) */
3370  probvars = SCIPgetVars(scip);
3371  nprobvars = SCIPgetNVars(scip);
3372  SCIP_CALL( SCIPhashmapCreate(&implhash, SCIPblkmem(scip), nsos1vars + nprobvars) );
3373  SCIP_CALL( SCIPallocBufferArray(scip, &totalvars, nsos1vars + nprobvars) );
3374 
3375  for (i = 0; i < nsos1vars; ++i)
3376  {
3377  SCIP_VAR* var;
3378  var = SCIPnodeGetVarSOS1(conflictgraph, i);
3379 
3380  /* insert node number to hash map */
3381  assert( ! SCIPhashmapExists(implhash, var) );
3382  SCIP_CALL( SCIPhashmapInsert(implhash, var, (void*) (size_t) ntotalvars) );/*lint !e571*/
3383  assert( ntotalvars == (int) (size_t) SCIPhashmapGetImage(implhash, var) );
3384  totalvars[ntotalvars++] = var;
3385  }
3386 
3387  for (i = 0; i < nprobvars; ++i)
3388  {
3389  SCIP_VAR* var;
3390  var = probvars[i];
3391 
3392  /* insert node number to hash map if not existent */
3393  if ( ! SCIPhashmapExists(implhash, var) )
3394  {
3395  SCIP_CALL( SCIPhashmapInsert(implhash, var, (void*) (size_t) ntotalvars) );/*lint !e571*/
3396  assert( ntotalvars == (int) (size_t) SCIPhashmapGetImage(implhash, var) );
3397  totalvars[ntotalvars++] = var;
3398  }
3399  }
3400 
3401  /* create implication graph */
3402  SCIP_CALL( SCIPdigraphCreate(&implgraph, ntotalvars) );
3403 
3404  /* try to tighten the lower and upper bounds of the variables */
3405  updateconfl = FALSE;
3406  for (j = 0; (j < conshdlrdata->maxtightenbds || conshdlrdata->maxtightenbds == -1 ) && ! cutoff; ++j)
3407  {
3408  SCIP_Bool implupdate;
3409  int nchgbdssave;
3410 
3411  nchgbdssave = *nchgbds;
3412 
3413  assert( ntotalvars > 0 );
3414  SCIP_CALL( tightenVarsBoundsSOS1(scip, conshdlrdata, conflictgraph, implgraph, implhash, adjacencymatrix, totalvars, ntotalvars, nsos1vars, nchgbds, &implupdate, &cutoff) );
3415  if ( *nchgbds > nchgbdssave )
3416  {
3417  *result = SCIP_SUCCESS;
3418  if ( implupdate )
3419  updateconfl = TRUE;
3420  }
3421  else if ( implupdate )
3422  updateconfl = TRUE;
3423  else
3424  break;
3425  }
3426 
3427  /* perform implication graph analysis */
3428  if ( updateconfl && conshdlrdata->perfimplanalysis && ! cutoff )
3429  {
3430  SCIP_Real* implubs;
3431  SCIP_Real* impllbs;
3432  SCIP_Bool* implnodes;
3433  SCIP_Bool infeasible;
3434  SCIP_Bool fixed;
3435  int naddconsssave;
3436  int probingdepth;
3437 
3438  /* allocate buffer arrays */
3439  SCIP_CALL( SCIPallocBufferArray(scip, &implnodes, nsos1vars) );
3440  SCIP_CALL( SCIPallocBufferArray(scip, &impllbs, ntotalvars) );
3441  SCIP_CALL( SCIPallocBufferArray(scip, &implubs, ntotalvars) );
3442 
3443  naddconsssave = *naddconss;
3444  for (i = 0; i < nsos1vars; ++i)
3445  {
3446  /* initialize data for implication graph analysis */
3447  infeasible = FALSE;
3448  probingdepth = 0;
3449  for (j = 0; j < nsos1vars; ++j)
3450  implnodes[j] = FALSE;
3451  for (j = 0; j < ntotalvars; ++j)
3452  {
3453  impllbs[j] = SCIPvarGetLbLocal(totalvars[j]);
3454  implubs[j] = SCIPvarGetUbLocal(totalvars[j]);
3455  }
3456 
3457  /* try to update the conflict graph based on the information of the implication graph */
3458  SCIP_CALL( performImplicationGraphAnalysis(scip, conshdlrdata, conflictgraph, totalvars, implgraph, implhash, adjacencymatrix, i, i, impllbs, implubs, implnodes, naddconss, &probingdepth, &infeasible) );
3459 
3460  /* if the subproblem turned out to be infeasible then fix variable to zero */
3461  if ( infeasible )
3462  {
3463  SCIP_CALL( SCIPfixVar(scip, totalvars[i], 0.0, &infeasible, &fixed) );
3464 
3465  if ( fixed )
3466  {
3467  SCIPdebugMsg(scip, "fixed variable %s with lower bound %f and upper bound %f to zero\n",
3468  SCIPvarGetName(totalvars[i]), SCIPvarGetLbLocal(totalvars[i]), SCIPvarGetUbLocal(totalvars[i]));
3469  ++(*nfixedvars);
3470  }
3471 
3472  if ( infeasible )
3473  cutoff = TRUE;
3474  }
3475  }
3476 
3477  if ( *naddconss > naddconsssave )
3478  *result = SCIP_SUCCESS;
3479 
3480  /* free buffer arrays */
3481  SCIPfreeBufferArrayNull(scip, &implubs);
3482  SCIPfreeBufferArrayNull(scip, &impllbs);
3483  SCIPfreeBufferArrayNull(scip, &implnodes);
3484  }
3485 
3486  /* if an infeasibility has been detected */
3487  if ( cutoff )
3488  {
3489  SCIPdebugMsg(scip, "cutoff \n");
3490  *result = SCIP_CUTOFF;
3491  }
3492 
3493  /* free memory */;
3494  for (j = ntotalvars-1; j >= 0; --j)
3495  {
3496  SCIP_SUCCDATA** succdatas;
3497  int nsucc;
3498  int s;
3499 
3500  succdatas = (SCIP_SUCCDATA**) SCIPdigraphGetSuccessorsData(implgraph, j);
3501  nsucc = SCIPdigraphGetNSuccessors(implgraph, j);
3502 
3503  for (s = nsucc-1; s >= 0; --s)
3504  SCIPfreeBlockMemory(scip, &succdatas[s]);/*lint !e866*/
3505  }
3506  SCIPdigraphFree(&implgraph);
3507  SCIPfreeBufferArrayNull(scip, &totalvars);
3508  SCIPhashmapFree(&implhash);
3509 
3510  return SCIP_OKAY;
3511 }
3512 
3513 
3514 /* ----------------------------- propagation -------------------------------------*/
3515 
3516 /** propagate variables of SOS1 constraint */
3517 static
3519  SCIP* scip, /**< SCIP pointer */
3520  SCIP_CONS* cons, /**< constraint */
3521  SCIP_CONSDATA* consdata, /**< constraint data */
3522  SCIP_Bool* cutoff, /**< whether a cutoff happened */
3523  int* ngen /**< number of domain changes */
3524  )
3525 {
3526  assert( scip != NULL );
3527  assert( cons != NULL );
3528  assert( consdata != NULL );
3529  assert( cutoff != NULL );
3530  assert( ngen != NULL );
3531 
3532  *cutoff = FALSE;
3533 
3534  /* if more than one variable is fixed to be nonzero */
3535  if ( consdata->nfixednonzeros > 1 )
3536  {
3537  SCIPdebugMsg(scip, "the node is infeasible, more than 1 variable is fixed to be nonzero.\n");
3538  SCIP_CALL( SCIPresetConsAge(scip, cons) );
3539  *cutoff = TRUE;
3540  return SCIP_OKAY;
3541  }
3542 
3543  /* if exactly one variable is fixed to be nonzero */
3544  if ( consdata->nfixednonzeros == 1 )
3545  {
3546  SCIP_VAR** vars;
3547  SCIP_Bool infeasible;
3548  SCIP_Bool tightened;
3549  SCIP_Bool success;
3550  SCIP_Bool allVarFixed;
3551  int firstFixedNonzero;
3552  int nvars;
3553  int j;
3554 
3555  firstFixedNonzero = -1;
3556  nvars = consdata->nvars;
3557  vars = consdata->vars;
3558  assert( vars != NULL );
3559 
3560  /* search nonzero variable - is needed for propinfo */
3561  for (j = 0; j < nvars; ++j)
3562  {
3563  if ( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(vars[j])) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(vars[j])) )
3564  {
3565  firstFixedNonzero = j;
3566  break;
3567  }
3568  }
3569  assert( firstFixedNonzero >= 0 );
3570 
3571  SCIPdebugMsg(scip, "variable <%s> is fixed nonzero, fixing other variables to 0.\n", SCIPvarGetName(vars[firstFixedNonzero]));
3572 
3573  /* fix variables before firstFixedNonzero to 0 */
3574  allVarFixed = TRUE;
3575  for (j = 0; j < firstFixedNonzero; ++j)
3576  {
3577  /* fix variable */
3578  SCIP_CALL( inferVariableZero(scip, vars[j], cons, firstFixedNonzero, &infeasible, &tightened, &success) );
3579  assert( ! infeasible );
3580  allVarFixed = allVarFixed && success;
3581  if ( tightened )
3582  ++(*ngen);
3583  }
3584 
3585  /* fix variables after firstFixedNonzero to 0 */
3586  for (j = firstFixedNonzero+1; j < nvars; ++j)
3587  {
3588  /* fix variable */
3589  SCIP_CALL( inferVariableZero(scip, vars[j], cons, firstFixedNonzero, &infeasible, &tightened, &success) );
3590  assert( ! infeasible ); /* there should be no variables after firstFixedNonzero that are fixed to be nonzero */
3591  allVarFixed = allVarFixed && success;
3592  if ( tightened )
3593  ++(*ngen);
3594  }
3595 
3596  /* reset constraint age counter */
3597  if ( *ngen > 0 )
3598  {
3599  SCIP_CALL( SCIPresetConsAge(scip, cons) );
3600  }
3601 
3602  /* delete constraint locally */
3603  if ( allVarFixed )
3604  {
3605  assert( !SCIPconsIsModifiable(cons) );
3606  SCIP_CALL( SCIPdelConsLocal(scip, cons) );
3607  }
3608  }
3609 
3610  return SCIP_OKAY;
3611 }
3612 
3613 
3614 /** propagate a variable that is known to be nonzero */
3615 static
3617  SCIP* scip, /**< SCIP pointer */
3618  SCIP_DIGRAPH* conflictgraph, /**< conflict graph */
3619  SCIP_DIGRAPH* implgraph, /**< implication graph */
3620  SCIP_CONS* cons, /**< some arbitrary SOS1 constraint */
3621  int node, /**< conflict graph node of variable that is known to be nonzero */
3622  SCIP_Bool implprop, /**< whether implication graph propagation shall be applied */
3623  SCIP_Bool* cutoff, /**< whether a cutoff happened */
3624  int* ngen /**< number of domain changes */
3625  )
3626 {
3627  int inferinfo;
3628  int* succ;
3629  int nsucc;
3630  int s;
3631 
3632  assert( scip != NULL );
3633  assert( conflictgraph != NULL );
3634  assert( cutoff != NULL );
3635  assert( ngen != NULL );
3636  assert( node >= 0 );
3637 
3638  *cutoff = FALSE;
3639  inferinfo = -node - 1;
3640 
3641  /* by assumption zero is outside the domain of variable */
3642  assert( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(SCIPnodeGetVarSOS1(conflictgraph, node))) || SCIPisFeasNegative(scip, SCIPvarGetUbLocal(SCIPnodeGetVarSOS1(conflictgraph, node))) );
3643 
3644  /* apply conflict graph propagation (fix all neighbors in the conflict graph to zero) */
3645  succ = SCIPdigraphGetSuccessors(conflictgraph, node);
3646  nsucc = SCIPdigraphGetNSuccessors(conflictgraph, node);
3647  for (s = 0; s < nsucc; ++s)
3648  {
3649  SCIP_VAR* succvar;
3650  SCIP_Real lb;
3651  SCIP_Real ub;
3652 
3653  succvar = SCIPnodeGetVarSOS1(conflictgraph, succ[s]);
3654  lb = SCIPvarGetLbLocal(succvar);
3655  ub = SCIPvarGetUbLocal(succvar);
3656 
3657  if ( ! SCIPisFeasZero(scip, lb) || ! SCIPisFeasZero(scip, ub) )
3658  {
3659  SCIP_Bool infeasible;
3660  SCIP_Bool tightened;
3661  SCIP_Bool success;
3662 
3663  /* fix variable if it is not multi-aggregated */
3664  SCIP_CALL( inferVariableZero(scip, succvar, cons, inferinfo, &infeasible, &tightened, &success) );
3665 
3666  if ( infeasible )
3667  {
3668  /* variable cannot be nonzero */
3669  *cutoff = TRUE;
3670  return SCIP_OKAY;
3671  }
3672  if ( tightened )
3673  ++(*ngen);
3674  assert( success || SCIPvarGetStatus(succvar) == SCIP_VARSTATUS_MULTAGGR );
3675  }
3676  }
3677 
3678 
3679  /* apply implication graph propagation */
3680  if ( implprop && implgraph != NULL )
3681  {
3682  SCIP_SUCCDATA** succdatas;
3683 
3684 #ifndef NDEBUG
3685  SCIP_NODEDATA* nodedbgdata;
3686  nodedbgdata = (SCIP_NODEDATA*) SCIPdigraphGetNodeData(implgraph, node);
3687  assert( SCIPvarCompare(nodedbgdata->var, SCIPnodeGetVarSOS1(conflictgraph, node)) == 0 );
3688 #endif
3689 
3690  /* get successor datas */
3691  succdatas = (SCIP_SUCCDATA**) SCIPdigraphGetSuccessorsData(implgraph, node);
3692 
3693  if ( succdatas != NULL )
3694  {
3695  succ = SCIPdigraphGetSuccessors(implgraph, node);
3696  nsucc = SCIPdigraphGetNSuccessors(implgraph, node);
3697  for (s = 0; s < nsucc; ++s)
3698  {
3699  SCIP_SUCCDATA* succdata;
3700  SCIP_NODEDATA* nodedata;
3701  SCIP_VAR* var;
3702 
3703  nodedata = (SCIP_NODEDATA*) SCIPdigraphGetNodeData(implgraph, succ[s]);
3704  assert( nodedata != NULL );
3705  succdata = succdatas[s];
3706  assert( succdata != NULL );
3707  var = nodedata->var;
3708  assert( var != NULL );
3709 
3710  /* tighten variable if it is not multi-aggregated */
3712  {
3713  /* check for lower bound implication */
3714  if ( SCIPisFeasLT(scip, SCIPvarGetLbLocal(var), succdata->lbimpl) )
3715  {
3716  SCIP_Bool infeasible;
3717  SCIP_Bool tightened;
3718 
3719  SCIP_CALL( SCIPinferVarLbCons(scip, var, succdata->lbimpl, cons, inferinfo, FALSE, &infeasible, &tightened) );
3720  if ( infeasible )
3721  {
3722  *cutoff = TRUE;
3723  return SCIP_OKAY;
3724  }
3725  if ( tightened )
3726  ++(*ngen);
3727  }
3728 
3729  /* check for upper bound implication */
3730  if ( SCIPisFeasGT(scip, SCIPvarGetUbLocal(var), succdata->ubimpl) )
3731  {
3732  SCIP_Bool infeasible;
3733  SCIP_Bool tightened;
3734 
3735  SCIP_CALL( SCIPinferVarUbCons(scip, var, succdata->ubimpl, cons, inferinfo, FALSE, &infeasible, &tightened) );
3736  if ( infeasible )
3737  {
3738  *cutoff = TRUE;
3739  return SCIP_OKAY;
3740  }
3741  if ( tightened )
3742  ++(*ngen);
3743  }
3744  }
3745  }
3746  }
3747  }
3748 
3749  return SCIP_OKAY;
3750 }
3751 
3752 
3753 /** initialize implication graph
3754  *
3755  * @p j is successor of @p i if and only if \f$ x_i\not = 0 \Rightarrow x_j\not = 0\f$
3756  *
3757  * @note By construction the implication graph is globally valid.
3758  */
3759 static
3761  SCIP* scip, /**< SCIP pointer */
3762  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
3763  SCIP_DIGRAPH* conflictgraph, /**< conflict graph */
3764  int nsos1vars, /**< number of SOS1 variables */
3765  int maxrounds, /**< maximal number of propagation rounds for generating implications */
3766  int* nchgbds, /**< pointer to store number of bound changes */
3767  SCIP_Bool* cutoff, /**< pointer to store whether a cutoff occurred */
3768  SCIP_Bool* success /**< whether initialization was successful */
3769  )
3770 {
3771  SCIP_HASHMAP* implhash = NULL;
3772  SCIP_Bool** adjacencymatrix = NULL;
3773  SCIP_Bool* implnodes = NULL;
3774  SCIP_VAR** implvars = NULL;
3775  SCIP_VAR** probvars;
3776  int nimplnodes;
3777  int nprobvars;
3778  int i;
3779  int j;
3780 
3781  assert( scip != NULL );
3782  assert( conshdlrdata != NULL );
3783  assert( conflictgraph != NULL );
3784  assert( conshdlrdata->implgraph == NULL );
3785  assert( conshdlrdata->nimplnodes == 0 );
3786  assert( cutoff != NULL );
3787  assert( nchgbds != NULL );
3788 
3789  *nchgbds = 0;
3790  *cutoff = FALSE;
3791 
3792  /* we do not create the adjacency matrix of the conflict graph if the number of SOS1 variables is larger than a predefined value */
3793  if ( conshdlrdata->maxsosadjacency != -1 && nsos1vars > conshdlrdata->maxsosadjacency )
3794  {
3795  *success = FALSE;
3796  SCIPdebugMsg(scip, "Implication graph was not created since number of SOS1 variables (%d) is larger than %d.\n", nsos1vars, conshdlrdata->maxsosadjacency);
3797 
3798  return SCIP_OKAY;
3799  }
3800  *success = TRUE;
3801 
3802  /* only add globally valid implications to implication graph */
3803  assert ( SCIPgetDepth(scip) == 0 );
3804 
3805  probvars = SCIPgetVars(scip);
3806  nprobvars = SCIPgetNVars(scip);
3807  nimplnodes = 0;
3808 
3809  /* create implication graph */
3810  SCIP_CALL( SCIPdigraphCreate(&conshdlrdata->implgraph, nsos1vars + nprobvars) );
3811 
3812  /* create hashmap */
3813  SCIP_CALL( SCIPhashmapCreate(&implhash, SCIPblkmem(scip), nsos1vars + nprobvars) );
3814 
3815  /* determine implvars (union of SOS1 and problem variables)
3816  * Note: For separation of implied bound cuts it is important that SOS1 variables are enumerated first
3817  */
3818  SCIP_CALL( SCIPallocBufferArray(scip, &implvars, nsos1vars + nprobvars) );
3819  for (i = 0; i < nsos1vars; ++i)
3820  {
3821  SCIP_VAR* var;
3822  var = SCIPnodeGetVarSOS1(conflictgraph, i);
3823 
3824  /* insert node number to hash map */
3825  assert( ! SCIPhashmapExists(implhash, var) );
3826  SCIP_CALL( SCIPhashmapInsert(implhash, var, (void*) (size_t) nimplnodes) );/*lint !e571*/
3827  assert( nimplnodes == (int) (size_t) SCIPhashmapGetImage(implhash, var) );
3828  implvars[nimplnodes++] = var;
3829  }
3830 
3831  for (i = 0; i < nprobvars; ++i)
3832  {
3833  SCIP_VAR* var;
3834  var = probvars[i];
3835 
3836  /* insert node number to hash map if not existent */
3837  if ( ! SCIPhashmapExists(implhash, var) )
3838  {
3839  SCIP_CALL( SCIPhashmapInsert(implhash, var, (void*) (size_t) nimplnodes) );/*lint !e571*/
3840  assert( nimplnodes == (int) (size_t) SCIPhashmapGetImage(implhash, var) );
3841  implvars[nimplnodes++] = var;
3842  }
3843  }
3844  conshdlrdata->nimplnodes = nimplnodes;
3845 
3846  /* add variables to nodes of implication graph */
3847  for (i = 0; i < nimplnodes; ++i)
3848  {
3849  SCIP_NODEDATA* nodedata = NULL;
3850 
3851  /* create node data */
3852  SCIP_CALL( SCIPallocBlockMemory(scip, &nodedata) );
3853  nodedata->var = implvars[i];
3854 
3855  /* set node data */
3856  SCIPdigraphSetNodeData(conshdlrdata->implgraph, (void*) nodedata, i);
3857  }
3858 
3859  /* allocate buffer arrays */
3860  SCIP_CALL( SCIPallocBufferArray(scip, &implnodes, nsos1vars) );
3861  SCIP_CALL( SCIPallocBufferArray(scip, &adjacencymatrix, nsos1vars) );
3862 
3863  for (i = 0; i < nsos1vars; ++i)
3864  SCIP_CALL( SCIPallocBufferArray(scip, &adjacencymatrix[i], i+1) ); /*lint !e866*/
3865 
3866  /* create adjacency matrix */
3867  for (i = 0; i < nsos1vars; ++i)
3868  {
3869  for (j = 0; j < i+1; ++j)
3870  adjacencymatrix[i][j] = 0;
3871  }
3872 
3873  for (i = 0; i < nsos1vars; ++i)
3874  {
3875  int* succ;
3876  int nsucc;
3877  succ = SCIPdigraphGetSuccessors(conflictgraph, i);
3878  nsucc = SCIPdigraphGetNSuccessors(conflictgraph, i);
3879 
3880  for (j = 0; j < nsucc; ++j)
3881  {
3882  if ( i > succ[j] )
3883  adjacencymatrix[i][succ[j]] = 1;
3884  }
3885  }
3886 
3887  assert( SCIPgetDepth(scip) == 0 );
3888 
3889  /* compute SOS1 implications from linear constraints and tighten bounds of variables */
3890  for (j = 0; (j < maxrounds || maxrounds == -1 ); ++j)
3891  {
3892  SCIP_Bool implupdate;
3893  int nchgbdssave;
3894 
3895  nchgbdssave = *nchgbds;
3896 
3897  assert( nimplnodes > 0 );
3898  SCIP_CALL( tightenVarsBoundsSOS1(scip, conshdlrdata, conflictgraph, conshdlrdata->implgraph, implhash, adjacencymatrix, implvars, nimplnodes, nsos1vars, nchgbds, &implupdate, cutoff) );
3899  if ( *cutoff || ( ! implupdate && ! ( *nchgbds > nchgbdssave ) ) )
3900  break;
3901  }
3902 
3903  /* free memory */
3904  for (i = nsos1vars-1; i >= 0; --i)
3905  SCIPfreeBufferArrayNull(scip, &adjacencymatrix[i]);
3906  SCIPfreeBufferArrayNull(scip, &adjacencymatrix);
3907  SCIPfreeBufferArrayNull(scip, &implnodes);
3908  SCIPfreeBufferArrayNull(scip, &implvars);
3909  SCIPhashmapFree(&implhash);
3910 
3911 #ifdef SCIP_DEBUG
3912  /* evaluate results */
3913  if ( cutoff )
3914  {
3915  SCIPdebugMsg(scip, "cutoff \n");
3916  }
3917  else if ( *nchgbds > 0 )
3918  {
3919  SCIPdebugMsg(scip, "found %d bound changes\n", *nchgbds);
3920  }
3921 #endif
3922 
3923  assert( conshdlrdata->implgraph != NULL );
3924 
3925  return SCIP_OKAY;
3926 }
3927 
3928 
3929 /** deinitialize implication graph */
3930 static
3932  SCIP* scip, /**< SCIP pointer */
3933  SCIP_CONSHDLRDATA* conshdlrdata /**< constraint handler data */
3934  )
3935 {
3936  int j;
3938  assert( scip != NULL );
3939  assert( conshdlrdata != NULL );
3940 
3941  /* free whole memory of implication graph */
3942  if ( conshdlrdata->implgraph == NULL )
3943  {
3944  assert( conshdlrdata->nimplnodes == 0 );
3945  return SCIP_OKAY;
3946  }
3947 
3948  /* free arc data */
3949  for (j = conshdlrdata->nimplnodes-1; j >= 0; --j)
3950  {
3951  SCIP_SUCCDATA** succdatas;
3952  int nsucc;
3953  int s;
3954 
3955  succdatas = (SCIP_SUCCDATA**) SCIPdigraphGetSuccessorsData(conshdlrdata->implgraph, j);
3956  nsucc = SCIPdigraphGetNSuccessors(conshdlrdata->implgraph, j);
3957 
3958  for (s = nsucc-1; s >= 0; --s)
3959  {
3960  assert( succdatas[s] != NULL );
3961  SCIPfreeBlockMemory(scip, &succdatas[s]);/*lint !e866*/
3962  }
3963  }
3964 
3965  /* free node data */
3966  for (j = conshdlrdata->nimplnodes-1; j >= 0; --j)
3967  {
3968  SCIP_NODEDATA* nodedata;
3969  nodedata = (SCIP_NODEDATA*)SCIPdigraphGetNodeData(conshdlrdata->implgraph, j);
3970  assert( nodedata != NULL );
3971  SCIPfreeBlockMemory(scip, &nodedata);
3972  SCIPdigraphSetNodeData(conshdlrdata->implgraph, NULL, j);
3973  }
3974 
3975  /* free implication graph */
3976  SCIPdigraphFree(&conshdlrdata->implgraph);
3977  conshdlrdata->nimplnodes = 0;
3978 
3979  return SCIP_OKAY;
3980 }
3981 
3982 
3983 /* ----------------------------- branching -------------------------------------*/
3984 
3985 /** get the vertices whose neighbor set covers a subset of the neighbor set of a given other vertex.
3986  *
3987  * This function can be used to compute sets of variables to branch on.
3988  */
3989 static
3991  SCIP_DIGRAPH* conflictgraph, /**< conflict graph */
3992  SCIP_Bool* verticesarefixed, /**< array that indicates which variables are currently fixed to zero */
3993  int vertex, /**< vertex (-1 if not needed) */
3994  int* neightocover, /**< neighbors of given vertex to be covered (or NULL if all neighbors shall be covered) */
3995  int nneightocover, /**< number of entries of neightocover (or 0 if all neighbors shall be covered )*/
3996  int* coververtices, /**< array to store the vertices whose neighbor set covers the neighbor set of the given vertex */
3997  int* ncoververtices /**< pointer to store size of coververtices */
3998  )
3999 {
4000  int* succ1;
4001  int nsucc1;
4002  int s;
4003 
4004  assert( conflictgraph != NULL );
4005  assert( verticesarefixed != NULL );
4006  assert( coververtices != NULL );
4007  assert( ncoververtices != NULL );
4008 
4009  *ncoververtices = 0;
4010 
4011  /* if all the neighbors shall be covered */
4012  if ( neightocover == NULL )
4013  {
4014  assert( nneightocover == 0 );
4015  nsucc1 = SCIPdigraphGetNSuccessors(conflictgraph, vertex);
4016  succ1 = SCIPdigraphGetSuccessors(conflictgraph, vertex);
4017  }
4018  else
4019  {
4020  nsucc1 = nneightocover;
4021  succ1 = neightocover;
4022  }
4023 
4024  /* determine all the successors of the first unfixed successor */
4025  for (s = 0; s < nsucc1; ++s)
4026  {
4027  int succvertex1 = succ1[s];
4028 
4029  if ( ! verticesarefixed[succvertex1] )
4030  {
4031  int succvertex2;
4032  int* succ2;
4033  int nsucc2;
4034  int j;
4035 
4036  nsucc2 = SCIPdigraphGetNSuccessors(conflictgraph, succvertex1);
4037  succ2 = SCIPdigraphGetSuccessors(conflictgraph, succvertex1);
4038 
4039  /* for the first unfixed vertex */
4040  if ( *ncoververtices == 0 )
4041  {
4042  for (j = 0; j < nsucc2; ++j)
4043  {
4044  succvertex2 = succ2[j];
4045  if ( ! verticesarefixed[succvertex2] )
4046  coververtices[(*ncoververtices)++] = succvertex2;
4047  }
4048  }
4049  else
4050  {
4051  int vv = 0;
4052  int k = 0;
4053  int v;
4054 
4055  /* determine all the successors that are in the set "coververtices" */
4056  for (v = 0; v < *ncoververtices; ++v)
4057  {
4058  assert( vv <= v );
4059  for (j = k; j < nsucc2; ++j)
4060  {
4061  succvertex2 = succ2[j];
4062  if ( succvertex2 > coververtices[v] )
4063  {
4064  /* coververtices[v] does not appear in succ2 list, go to next vertex in coververtices */
4065  k = j;
4066  break;
4067  }
4068  else if ( succvertex2 == coververtices[v] )
4069  {
4070  /* vertices are equal, copy to free position vv */
4071  coververtices[vv++] = succvertex2;
4072  k = j + 1;
4073  break;
4074  }
4075  }
4076  }
4077  /* store new size of coververtices */
4078  *ncoververtices = vv;
4079  }
4080  }
4081  }
4082 
4083 #ifdef SCIP_DEBUG
4084  /* check sorting */
4085  for (s = 0; s < *ncoververtices; ++s)
4086  {
4087  assert( *ncoververtices <= 1 || coververtices[*ncoververtices - 1] > coververtices[*ncoververtices - 2] );
4088  }
4089 #endif
4090 
4091  return SCIP_OKAY;
4092 }
4093 
4094 
4095 /** get vertices of variables that will be fixed to zero for each node */
4096 static
4098  SCIP* scip, /**< SCIP pointer */
4099  SCIP_DIGRAPH* conflictgraph, /**< conflict graph */
4100  SCIP_SOL* sol, /**< solution to be enforced (NULL for LP solution) */
4101  SCIP_Bool* verticesarefixed, /**< vector that indicates which variables are currently fixed to zero */
4102  SCIP_Bool bipbranch, /**< TRUE if bipartite branching method should be used */
4103  int branchvertex, /**< branching vertex */
4104  int* fixingsnode1, /**< vertices of variables that will be fixed to zero for the first node */
4105  int* nfixingsnode1, /**< pointer to store number of fixed variables for the first node */
4106  int* fixingsnode2, /**< vertices of variables that will be fixed to zero for the second node */
4107  int* nfixingsnode2 /**< pointer to store number of fixed variables for the second node */
4108  )
4109 {
4110  SCIP_Bool takeallsucc; /* whether to set fixingsnode1 = neighbors of 'branchvertex' in the conflict graph */
4111  int* succ;
4112  int nsucc;
4113  int j;
4114 
4115  assert( scip != NULL );
4116  assert( conflictgraph != NULL );
4117  assert( verticesarefixed != NULL );
4118  assert( ! verticesarefixed[branchvertex] );
4119  assert( fixingsnode1 != NULL );
4120  assert( fixingsnode2 != NULL );
4121  assert( nfixingsnode1 != NULL );
4122  assert( nfixingsnode2 != NULL );
4123 
4124  *nfixingsnode1 = 0;
4125  *nfixingsnode2 = 0;
4126  takeallsucc = TRUE;
4127 
4128  /* get successors and number of successors of branching vertex */
4129  nsucc = SCIPdigraphGetNSuccessors(conflictgraph, branchvertex);
4130  succ = SCIPdigraphGetSuccessors(conflictgraph, branchvertex);
4131 
4132  /* if bipartite branching method is turned on */
4133  if ( bipbranch )
4134  {
4135  SCIP_Real solval;
4136  int cnt = 0;
4137 
4138  /* get all the neighbors of the variable with index 'branchvertex' whose solution value is nonzero */
4139  for (j = 0; j < nsucc; ++j)
4140  {
4141  if ( ! SCIPisFeasZero(scip, SCIPgetSolVal(scip, sol, SCIPnodeGetVarSOS1(conflictgraph, succ[j]))) )
4142  {
4143  assert( ! verticesarefixed[succ[j]] );
4144  fixingsnode1[(*nfixingsnode1)++] = succ[j];
4145  }
4146  }
4147 
4148  /* if one of the sets fixingsnode1 or fixingsnode2 contains only one variable with a nonzero LP value we perform standard neighborhood branching */
4149  if ( *nfixingsnode1 > 0 )
4150  {
4151  /* get the vertices whose neighbor set cover the selected subset of the neighbors of the given branching vertex */
4152  SCIP_CALL( getCoverVertices(conflictgraph, verticesarefixed, branchvertex, fixingsnode1, *nfixingsnode1, fixingsnode2, nfixingsnode2) );
4153 
4154  /* determine the intersection of the neighbors of branchvertex with the intersection of all the neighbors of fixingsnode2 */
4155  SCIP_CALL( getCoverVertices(conflictgraph, verticesarefixed, branchvertex, fixingsnode2, *nfixingsnode2, fixingsnode1, nfixingsnode1) );
4156 
4157  for (j = 0; j < *nfixingsnode2; ++j)
4158  {
4159  solval = SCIPgetSolVal(scip, sol, SCIPnodeGetVarSOS1(conflictgraph, fixingsnode2[j]));
4160  if( ! SCIPisFeasZero(scip, solval) )
4161  ++cnt;
4162  }
4163 
4164  /* we decide whether to use all successors if one partition of complete bipartite subgraph has only one node */
4165  if ( cnt >= 2 )
4166  {
4167  cnt = 0;
4168  for (j = 0; j < *nfixingsnode1; ++j)
4169  {
4170  solval = SCIPgetSolVal(scip, sol, SCIPnodeGetVarSOS1(conflictgraph, fixingsnode1[j]));
4171  if( ! SCIPisFeasZero(scip, solval) )
4172  ++cnt;
4173  }
4174 
4175  if ( cnt >= 2 )
4176  takeallsucc = FALSE;
4177  }
4178  }
4179  }
4180 
4181  if ( takeallsucc )
4182  {
4183  /* get all the unfixed neighbors of the branching vertex */
4184  *nfixingsnode1 = 0;
4185  for (j = 0; j < nsucc; ++j)
4186  {
4187  if ( ! verticesarefixed[succ[j]] )
4188  fixingsnode1[(*nfixingsnode1)++] = succ[j];
4189  }
4190 
4191  if ( bipbranch )
4192  {
4193  /* get the vertices whose neighbor set covers the neighbor set of a given branching vertex */
4194  SCIP_CALL( getCoverVertices(conflictgraph, verticesarefixed, branchvertex, fixingsnode1, *nfixingsnode1, fixingsnode2, nfixingsnode2) );
4195  }
4196  else
4197  {
4198  /* use neighborhood branching, i.e, for the second node only the branching vertex can be fixed */
4199  fixingsnode2[0] = branchvertex;
4200  *nfixingsnode2 = 1;
4201  }
4202  }
4203 
4204  return SCIP_OKAY;
4205 }
4206 
4207 
4208 /** gets branching priorities for SOS1 variables and applies 'most infeasible selection' rule to determine a vertex for the next branching decision */
4209 static
4211  SCIP* scip, /**< SCIP pointer */
4212  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
4213  SCIP_DIGRAPH* conflictgraph, /**< conflict graph */
4214  SCIP_SOL* sol, /**< solution to be enforced (NULL for LP solution) */
4215  int nsos1vars, /**< number of SOS1 variables */
4216  SCIP_Bool* verticesarefixed, /**< vector that indicates which variables are currently fixed to zero */
4217  SCIP_Bool bipbranch, /**< TRUE if bipartite branching method should be used */
4218  int* fixingsnode1, /**< vertices of variables that will be fixed to zero for the first node (size = nsos1vars) */
4219  int* fixingsnode2, /**< vertices of variables that will be fixed to zero for the second node (size = nsos1vars) */
4220  SCIP_Real* branchpriors, /**< pointer to store branching priorities (size = nsos1vars) or NULL if not needed */
4221  int* vertexbestprior, /**< pointer to store vertex with the best branching priority or NULL if not needed */
4222  SCIP_Bool* relsolfeas /**< pointer to store if LP relaxation solution is feasible */
4223  )
4224 {
4225  SCIP_Real bestprior;
4226  int i;
4227 
4228  assert( scip != NULL );
4229  assert( conshdlrdata != NULL );
4230  assert( conflictgraph != NULL );
4231  assert( verticesarefixed != NULL );
4232  assert( fixingsnode1 != NULL );
4233  assert( fixingsnode2 != NULL );
4234  assert( relsolfeas != NULL );
4235 
4236  bestprior = -SCIPinfinity(scip);
4237 
4238  for (i = 0; i < nsos1vars; ++i)
4239  {
4240  SCIP_Real prior;
4241  SCIP_Real solval;
4242  SCIP_Real sum1;
4243  SCIP_Real sum2;
4244  int nfixingsnode1;
4245  int nfixingsnode2;
4246  int nsucc;
4247  int j;
4248 
4249  nsucc = SCIPdigraphGetNSuccessors(conflictgraph, i);
4250 
4251  if ( nsucc == 0 || SCIPisFeasZero(scip, SCIPgetSolVal(scip, sol, SCIPnodeGetVarSOS1(conflictgraph, i))) || verticesarefixed[i] )
4252  prior = -SCIPinfinity(scip);
4253  else
4254  {
4255  SCIP_Bool iszero1 = TRUE;
4256  SCIP_Bool iszero2 = TRUE;
4257 
4258  /* get vertices of variables that will be fixed to zero for each strong branching execution */
4259  assert( ! verticesarefixed[i] );
4260  SCIP_CALL( getBranchingVerticesSOS1(scip, conflictgraph, sol, verticesarefixed, bipbranch, i, fixingsnode1, &nfixingsnode1, fixingsnode2, &nfixingsnode2) );
4261 
4262  sum1 = 0.0;
4263  for (j = 0; j < nfixingsnode1; ++j)
4264  {
4265  solval = SCIPgetSolVal(scip, sol, SCIPnodeGetVarSOS1(conflictgraph, fixingsnode1[j]));
4266  if ( ! SCIPisFeasZero(scip, solval) )
4267  {
4268  sum1 += REALABS( solval );
4269  iszero1 = FALSE;
4270  }
4271  }
4272 
4273  sum2 = 0.0;
4274  for (j = 0; j < nfixingsnode2; ++j)
4275  {
4276  solval = SCIPgetSolVal(scip, sol, SCIPnodeGetVarSOS1(conflictgraph, fixingsnode2[j]));
4277  if ( ! SCIPisFeasZero(scip, solval) )
4278  {
4279  sum2 += REALABS( solval );
4280  iszero2 = FALSE;
4281  }
4282  }
4283 
4284  if ( iszero1 || iszero2 )
4285  prior = -SCIPinfinity(scip);
4286  else
4287  prior = sum1 * sum2;
4288  }
4289 
4290  if ( branchpriors != NULL )
4291  branchpriors[i] = prior;
4292  if ( bestprior < prior )
4293  {
4294  bestprior = prior;
4295 
4296  if ( vertexbestprior != NULL )
4297  *vertexbestprior = i;
4298  }
4299  }
4300 
4301  if ( SCIPisInfinity(scip, -bestprior) )
4302  *relsolfeas = TRUE;
4303  else
4304  *relsolfeas = FALSE;
4305 
4306  return SCIP_OKAY;
4307 }
4308 
4309 
4310 /** performs strong branching with given domain fixings */
4311 static
4313  SCIP* scip, /**< SCIP pointer */
4314  SCIP_DIGRAPH* conflictgraph, /**< conflict graph */
4315  int* fixingsexec, /**< vertices of variables to be fixed to zero for this strong branching execution */
4316  int nfixingsexec, /**< number of vertices of variables to be fixed to zero for this strong branching execution */
4317  int* fixingsop, /**< vertices of variables to be fixed to zero for the opposite strong branching execution */
4318  int nfixingsop, /**< number of vertices of variables to be fixed to zero for the opposite strong branching execution */
4319  int inititer, /**< maximal number of LP iterations to perform */
4320  SCIP_Bool fixnonzero, /**< shall opposite variable (if positive in sign) fixed to the feasibility tolerance
4321  * (only possible if nfixingsop = 1) */
4322  int* domainfixings, /**< vertices that can be used to reduce the domain (should have size equal to number of variables) */
4323  int* ndomainfixings, /**< pointer to store number of vertices that can be used to reduce the domain, could be filled by earlier calls */
4324  SCIP_Bool* infeasible, /**< pointer to store whether branch is infeasible */
4325  SCIP_Real* objval, /**< pointer to store objective value of LP with fixed variables (SCIP_INVALID if reddomain = TRUE or lperror = TRUE) */
4326  SCIP_Bool* lperror /**< pointer to store whether an unresolved LP error or a strange solution status occurred */
4327  )
4328 {
4329  SCIP_LPSOLSTAT solstat;
4330  int i;
4331 
4332  assert( scip != NULL );
4333  assert( conflictgraph != NULL );
4334  assert( fixingsexec != NULL );
4335  assert( nfixingsop > 0 );
4336  assert( fixingsop != NULL );
4337  assert( nfixingsop > 0 );
4338  assert( inititer >= -1 );
4339  assert( domainfixings != NULL );
4340  assert( ndomainfixings != NULL );
4341  assert( *ndomainfixings >= 0 );
4342  assert( infeasible != NULL );
4343  assert( objval != NULL );
4344  assert( lperror != NULL );
4345 
4346  *objval = SCIP_INVALID; /* for debugging */
4347  *lperror = FALSE;
4348  *infeasible = FALSE;
4349 
4350  /* start probing */
4351  SCIP_CALL( SCIPstartProbing(scip) );
4352 
4353  /* perform domain fixings */
4354  if ( fixnonzero && nfixingsop == 1 )
4355  {
4356  SCIP_VAR* var;
4357  SCIP_Real lb;
4358  SCIP_Real ub;
4359 
4360  var = SCIPnodeGetVarSOS1(conflictgraph, fixingsop[0]);
4361  lb = SCIPvarGetLbLocal(var);
4362  ub = SCIPvarGetUbLocal(var);
4363 
4365  {
4366  if ( SCIPisZero(scip, lb) )
4367  {
4368  /* fix variable to some very small, but positive number or to 1.0 if variable is integral */
4369  if (SCIPvarIsIntegral(var) )
4370  {
4371  SCIP_CALL( SCIPchgVarLbProbing(scip, var, 1.0) );
4372  }
4373  else
4374  {
4375  SCIP_CALL( SCIPchgVarLbProbing(scip, var, 1.5 * SCIPfeastol(scip)) );
4376  }
4377  }
4378  else if ( SCIPisZero(scip, ub) )
4379  {
4380  /* fix variable to some negative number with small absolute value or to -1.0 if variable is integral */
4381  if (SCIPvarIsIntegral(var) )
4382  {
4383  SCIP_CALL( SCIPchgVarUbProbing(scip, var, -1.0) );
4384  }
4385  else
4386  {
4387  SCIP_CALL( SCIPchgVarUbProbing(scip, var, -1.5 * SCIPfeastol(scip)) );
4388  }
4389  }
4390  }
4391  }
4392 
4393  /* injects variable fixings into current probing node */
4394  for (i = 0; i < nfixingsexec && ! *infeasible; ++i)
4395  {
4396  SCIP_VAR* var;
4397 
4398  var = SCIPnodeGetVarSOS1(conflictgraph, fixingsexec[i]);
4399  if ( SCIPisFeasGT(scip, SCIPvarGetLbLocal(var), 0.0) || SCIPisFeasLT(scip, SCIPvarGetUbLocal(var), 0.0) )
4400  *infeasible = TRUE;
4401  else
4402  {
4403  SCIP_CALL( SCIPfixVarProbing(scip, var, 0.0) );
4404  }
4405  }
4406 
4407  /* apply domain propagation */
4408  if ( ! *infeasible )
4409  {
4410  SCIP_CALL( SCIPpropagateProbing(scip, 0, infeasible, NULL) );
4411  }
4412 
4413  if ( *infeasible )
4414  solstat = SCIP_LPSOLSTAT_INFEASIBLE;
4415  else
4416  {
4417  /* solve the probing LP */
4418  SCIP_CALL( SCIPsolveProbingLP(scip, inititer, lperror, NULL) );
4419  if ( *lperror )
4420  {
4421  SCIP_CALL( SCIPendProbing(scip) );
4422  return SCIP_OKAY;
4423  }
4424 
4425  /* get solution status */
4426  solstat = SCIPgetLPSolstat(scip);
4427  }
4428 
4429  /* if objective limit was reached, then the domain can be reduced */
4430  if ( solstat == SCIP_LPSOLSTAT_OBJLIMIT || solstat == SCIP_LPSOLSTAT_INFEASIBLE )
4431  {
4432  *infeasible = TRUE;
4433 
4434  for (i = 0; i < nfixingsop; ++i)
4435  domainfixings[(*ndomainfixings)++] = fixingsop[i];
4436  }
4437  else if ( solstat == SCIP_LPSOLSTAT_OPTIMAL || solstat == SCIP_LPSOLSTAT_TIMELIMIT || solstat == SCIP_LPSOLSTAT_ITERLIMIT )
4438  {
4439  /* get objective value of probing LP */
4440  *objval = SCIPgetLPObjval(scip);
4441  }
4442  else
4443  *lperror = TRUE;
4444 
4445  /* end probing */
4446  SCIP_CALL( SCIPendProbing(scip) );
4447 
4448  return SCIP_OKAY;
4449 }
4450 
4451 
4452 /** apply strong branching to determine the vertex for the next branching decision */
4453 static
4455  SCIP* scip, /**< SCIP pointer */
4456  SCIP_CONSHDLRDATA* conshdlrdata, /**< SOS1 constraint handler data */
4457  SCIP_DIGRAPH* conflictgraph, /**< conflict graph */
4458  SCIP_SOL* sol, /**< solution to be enforced (NULL for LP solution) */
4459  int nsos1vars, /**< number of SOS1 variables */
4460  SCIP_Real lpobjval, /**< current LP relaxation solution */
4461  SCIP_Bool bipbranch, /**< TRUE if bipartite branching method should be used */
4462  int nstrongrounds, /**< number of strong branching rounds */
4463  SCIP_Bool* verticesarefixed, /**< vector that indicates which variables are currently fixed to zero */
4464  int* fixingsnode1, /**< pointer to store vertices of variables that will be fixed to zero for the first node (size = nsos1vars) */
4465  int* fixingsnode2, /**< pointer to store vertices of variables that will be fixed to zero for the second node (size = nsos1vars) */
4466  int* vertexbestprior, /**< pointer to store vertex with the best strong branching priority */
4467  SCIP_Real* bestobjval1, /**< pointer to store LP objective for left child node of branching decision with best priority */
4468  SCIP_Real* bestobjval2, /**< pointer to store LP objective for right child node of branching decision with best priority */
4469  SCIP_RESULT* result /**< pointer to store result of strong branching */
4470  )
4471 {
4472  SCIP_Real* branchpriors = NULL;
4473  int* indsos1vars = NULL;
4474  int* domainfixings = NULL;
4475  int ndomainfixings;
4476  int nfixingsnode1;
4477  int nfixingsnode2;
4478 
4479  SCIP_Bool relsolfeas;
4480  SCIP_Real bestscore;
4481  int lastscorechange;
4482  int maxfailures;
4483 
4484  SCIP_Longint nlpiterations;
4485  SCIP_Longint nlps;
4486  int inititer;
4487  int j;
4488  int i;
4489 
4490  assert( scip != NULL );
4491  assert( conshdlrdata != NULL );
4492  assert( conflictgraph != NULL );
4493  assert( verticesarefixed != NULL );
4494  assert( fixingsnode1 != NULL );
4495  assert( fixingsnode2 != NULL );
4496  assert( vertexbestprior != NULL );
4497  assert( result != NULL );
4498 
4499  /* allocate buffer arrays */
4500  SCIP_CALL( SCIPallocBufferArray(scip, &branchpriors, nsos1vars) );
4501 
4502  /* get branching priorities */
4503  SCIP_CALL( getBranchingPrioritiesSOS1(scip, conshdlrdata, conflictgraph, sol, nsos1vars, verticesarefixed,
4504  bipbranch, fixingsnode1, fixingsnode2, branchpriors, NULL, &relsolfeas) );
4505 
4506  /* if LP relaxation solution is feasible */
4507  if ( relsolfeas )
4508  {
4509  SCIPdebugMsg(scip, "all the SOS1 constraints are feasible.\n");
4510  *result = SCIP_FEASIBLE;
4511 
4512  /* free memory */
4513  SCIPfreeBufferArrayNull(scip, &branchpriors);
4514 
4515  return SCIP_OKAY;
4516  }
4517 
4518  /* allocate buffer arrays */
4519  SCIP_CALL( SCIPallocBufferArray(scip, &indsos1vars, nsos1vars) );
4520  SCIP_CALL( SCIPallocBufferArray(scip, &domainfixings, nsos1vars) );
4521 
4522  /* sort branching priorities (descending order) */
4523  for (j = 0; j < nsos1vars; ++j)
4524  indsos1vars[j] = j;
4525  SCIPsortDownRealInt(branchpriors, indsos1vars, nsos1vars);
4526 
4527  /* determine the number of LP iterations to perform in each strong branch */
4528  nlpiterations = SCIPgetNDualResolveLPIterations(scip);
4529  nlps = SCIPgetNDualResolveLPs(scip);
4530  if ( nlps == 0 )
4531  {
4532  nlpiterations = SCIPgetNNodeInitLPIterations(scip);
4533  nlps = SCIPgetNNodeInitLPs(scip);
4534  if ( nlps == 0 )
4535  {
4536  nlpiterations = 1000;
4537  nlps = 1;
4538  }
4539  }
4540  assert(nlps >= 1);
4541 
4542  /* compute number of LP iterations performed per strong branching iteration */
4543  if ( conshdlrdata->nstrongiter == -2 )
4544  {
4545  inititer = (int)(2*nlpiterations / nlps);
4546  inititer = (int)((SCIP_Real)inititer * (1.0 + 20.0/SCIPgetNNodes(scip)));
4547  inititer = MAX(inititer, 10);
4548  inititer = MIN(inititer, 500);
4549  }
4550  else
4551  inititer = conshdlrdata->nstrongiter;
4552 
4553  /* get current LP relaxation solution */
4554  lpobjval = SCIPgetLPObjval(scip);
4555 
4556  /* determine branching variable by strong branching or reduce domain */
4557  ndomainfixings = 0;
4558  lastscorechange = -1;
4559  *vertexbestprior = indsos1vars[0]; /* for the case that nstrongrounds = 0 */
4560  bestscore = -SCIPinfinity(scip);
4561  *bestobjval1 = -SCIPinfinity(scip);
4562  *bestobjval2 = -SCIPinfinity(scip);
4563  maxfailures = nstrongrounds;
4564 
4565  /* for each strong branching round */
4566  for (j = 0; j < nstrongrounds; ++j)
4567  {
4568  int testvertex;
4569 
4570  /* get branching vertex for the current strong branching iteration */
4571  testvertex = indsos1vars[j];
4572 
4573  /* if variable with index 'vertex' does not violate any complementarity in its neighborhood for the current LP relaxation solution */
4574  if ( SCIPisPositive(scip, branchpriors[j]) )
4575  {
4576  SCIP_Bool infeasible1;
4577  SCIP_Bool infeasible2;
4578  SCIP_Bool lperror;
4579  SCIP_Real objval1;
4580  SCIP_Real objval2;
4581  SCIP_Real score;
4582 
4583  /* get vertices of variables that will be fixed to zero for each strong branching execution */
4584  assert( ! verticesarefixed[testvertex] );
4585  SCIP_CALL( getBranchingVerticesSOS1(scip, conflictgraph, sol, verticesarefixed, bipbranch, testvertex, fixingsnode1, &nfixingsnode1, fixingsnode2, &nfixingsnode2) );
4586 
4587  /* get information for first strong branching execution */
4588  SCIP_CALL( performStrongbranchSOS1(scip, conflictgraph, fixingsnode1, nfixingsnode1, fixingsnode2, nfixingsnode2,
4589  inititer, conshdlrdata->fixnonzero, domainfixings, &ndomainfixings, &infeasible1, &objval1, &lperror) );
4590  if ( lperror )
4591  continue;
4592 
4593  /* get information for second strong branching execution */
4594  SCIP_CALL( performStrongbranchSOS1(scip, conflictgraph, fixingsnode2, nfixingsnode2, fixingsnode1, nfixingsnode1,
4595  inititer, FALSE, domainfixings, &ndomainfixings, &infeasible2, &objval2, &lperror) );
4596  if ( lperror )
4597  continue;
4598 
4599  /* if both subproblems are infeasible */
4600  if ( infeasible1 && infeasible2 )
4601  {
4602  SCIPdebugMsg(scip, "detected cutoff.\n");
4603 
4604  /* update result */
4605  *result = SCIP_CUTOFF;
4606 
4607  /* free memory */
4608  SCIPfreeBufferArrayNull(scip, &domainfixings);
4609  SCIPfreeBufferArrayNull(scip, &indsos1vars);
4610  SCIPfreeBufferArrayNull(scip, &branchpriors);
4611 
4612  return SCIP_OKAY;
4613  }
4614  else if ( ! infeasible1 && ! infeasible2 ) /* both subproblems are feasible */
4615  {
4616  /* if domain has not been reduced in this for-loop */
4617  if ( ndomainfixings == 0 )
4618  {
4619  score = MAX( REALABS( objval1 - lpobjval ), SCIPfeastol(scip) ) * MAX( REALABS( objval2 - lpobjval ), SCIPfeastol(scip) );/*lint !e666*/
4620 
4621  if ( SCIPisPositive(scip, score - bestscore) )
4622  {
4623  bestscore = score;
4624  *vertexbestprior = testvertex;
4625  *bestobjval1 = objval1;
4626  *bestobjval2 = objval2;
4627 
4628  lastscorechange = j;
4629  }
4630  else if ( j - lastscorechange > maxfailures )
4631  break;
4632  }
4633  }
4634  }
4635  }
4636 
4637  /* if variable fixings have been detected by probing, then reduce domain */
4638  if ( ndomainfixings > 0 )
4639  {
4640  SCIP_NODE* node = SCIPgetCurrentNode(scip);
4641  SCIP_Bool infeasible;
4642 
4643  for (i = 0; i < ndomainfixings; ++i)
4644  {
4645  SCIP_CALL( fixVariableZeroNode(scip, SCIPnodeGetVarSOS1(conflictgraph, domainfixings[i]), node, &infeasible) );
4646  assert( ! infeasible );
4647  }
4648 
4649  SCIPdebugMsg(scip, "found %d domain fixings.\n", ndomainfixings);
4650 
4651  /* update result */
4652  *result = SCIP_REDUCEDDOM;
4653  }
4654 
4655  /* free buffer arrays */
4656  SCIPfreeBufferArrayNull(scip, &domainfixings);
4657  SCIPfreeBufferArrayNull(scip, &indsos1vars);
4658  SCIPfreeBufferArrayNull(scip, &branchpriors);
4659 
4660  return SCIP_OKAY;
4661 }
4662 
4663 
4664 /** for two given vertices @p v1 and @p v2 search for a clique in the conflict graph that contains these vertices. From
4665  * this clique, we create a bound constraint.
4666  */
4667 static
4669  SCIP* scip, /**< SCIP pointer */
4670  SCIP_DIGRAPH* conflictgraph, /**< conflict graph */
4671  SCIP_SOL* sol, /**< solution to be enforced (NULL for LP solution) */
4672  int v1, /**< first vertex that shall be contained in bound constraint */
4673  int v2, /**< second vertex that shall be contained in bound constraint */
4674  SCIP_VAR* boundvar, /**< bound variable of @p v1 and @p v2 (or NULL if not existent) */
4675  SCIP_Bool extend, /**< should @p v1 and @p v2 be greedily extended to a clique of larger size */
4676  SCIP_CONS* cons, /**< bound constraint */
4677  SCIP_Real* feas /**< feasibility value of bound constraint */
4678  )
4679 {
4680  SCIP_NODEDATA* nodedata;
4681  SCIP_Bool addv2 = TRUE;
4682  SCIP_Real solval;
4683  SCIP_VAR* var;
4684  SCIP_Real coef = 0.0;
4685  int nsucc;
4686  int s;
4687 
4688  int* extensions = NULL;
4689  int nextensions = 0;
4690  int nextensionsnew;
4691  int* succ;
4692 
4693  assert( scip != NULL );
4694  assert( conflictgraph != NULL );
4695  assert( cons != NULL );
4696  assert( feas != NULL );
4697 
4698  *feas = 0.0;
4699 
4700  /* add index 'v1' to the clique */
4701  nodedata = (SCIP_NODEDATA*)SCIPdigraphGetNodeData(conflictgraph, v1);
4702  var = nodedata->var;
4703  assert( boundvar == NULL || SCIPvarCompare(boundvar, nodedata->ubboundvar) == 0 );
4704  solval = SCIPgetSolVal(scip, sol, var);
4705 
4706  /* if 'v1' and 'v2' have the same bound variable then the bound cut can be strengthened */
4707  if ( boundvar == NULL )
4708  {
4709  if ( SCIPisFeasPositive(scip, solval) )
4710  {
4711  SCIP_Real ub;
4712  ub = SCIPvarGetUbLocal(var);
4713  assert( SCIPisFeasPositive(scip, ub));
4714 
4715  if ( ! SCIPisInfinity(scip, ub) )
4716  coef = 1.0/ub;
4717  }
4718  else if ( SCIPisFeasNegative(scip, solval) )
4719  {
4720  SCIP_Real lb;
4721  lb = SCIPvarGetLbLocal(var);
4722  assert( SCIPisFeasNegative(scip, lb) );
4723  if ( ! SCIPisInfinity(scip, -lb) )
4724  coef = 1.0/lb;
4725  }
4726  }
4727  else if ( boundvar == nodedata->ubboundvar )
4728  {
4729  if ( SCIPisFeasPositive(scip, solval) )
4730  {
4731  SCIP_Real ub;
4732 
4733  ub = nodedata->ubboundcoef;
4734  assert( SCIPisFeasPositive(scip, ub) );
4735  if ( ! SCIPisInfinity(scip, ub) )
4736  coef = 1.0/ub;
4737  }
4738  else if ( SCIPisFeasNegative(scip, solval) )
4739  {
4740  SCIP_Real lb;
4741 
4742  lb = nodedata->lbboundcoef;
4743  assert( SCIPisFeasPositive(scip, lb) );
4744  if ( ! SCIPisInfinity(scip, lb) )
4745  coef = 1.0/lb;
4746  }
4747  }
4748 
4749  if ( ! SCIPisZero(scip, coef) )
4750  {
4751  *feas += coef * solval;
4752  SCIP_CALL( SCIPaddCoefLinear(scip, cons, var, coef) );
4753  }
4754 
4755  /* if clique shall be greedily extended to a clique of larger size */
4756  if ( extend )
4757  {
4758  /* get successors */
4759  nsucc = SCIPdigraphGetNSuccessors(conflictgraph, v1);
4760  succ = SCIPdigraphGetSuccessors(conflictgraph, v1);
4761  assert( nsucc > 0 );
4762 
4763  /* allocate buffer array */
4764  SCIP_CALL( SCIPallocBufferArray(scip, &extensions, nsucc) );
4765 
4766  /* get possible extensions for the clique cover */
4767  for (s = 0; s < nsucc; ++s)
4768  extensions[s] = succ[s];
4769  nextensions = nsucc;
4770  }
4771  else
4772  nextensions = 1;
4773 
4774  /* while there exist possible extensions for the clique cover */
4775  while ( nextensions > 0 )
4776  {
4777  SCIP_Real bestbigMval;
4778  SCIP_Real bigMval;
4779  int bestindex = -1;
4780  int ext;
4781 
4782  bestbigMval = -SCIPinfinity(scip);
4783 
4784  /* if v2 has not been added to clique already */
4785  if ( addv2 )
4786  {
4787  bestindex = v2;
4788  addv2 = FALSE;
4789  }
4790  else /* search for the extension with the largest absolute value of its LP relaxation solution value */
4791  {
4792  assert( extensions != NULL );
4793  for (s = 0; s < nextensions; ++s)
4794  {
4795  ext = extensions[s];
4796  bigMval = nodeGetSolvalBinaryBigMSOS1(scip, conflictgraph, sol, ext);
4797  if ( SCIPisFeasLT(scip, bestbigMval, bigMval) )
4798  {
4799  bestbigMval = bigMval;
4800  bestindex = ext;
4801  }
4802  }
4803  }
4804  assert( bestindex != -1 );
4805 
4806  /* add bestindex variable to the constraint */
4807  nodedata = (SCIP_NODEDATA*)SCIPdigraphGetNodeData(conflictgraph, bestindex);
4808  var = nodedata->var;
4809  solval = SCIPgetSolVal(scip, sol, var);
4810  coef = 0.0;
4811  if ( boundvar == NULL )
4812  {
4813  if ( SCIPisFeasPositive(scip, solval) )
4814  {
4815  SCIP_Real ub;
4816  ub = SCIPvarGetUbLocal(var);
4817  assert( SCIPisFeasPositive(scip, ub));
4818 
4819  if ( ! SCIPisInfinity(scip, ub) )
4820  coef = 1.0/ub;
4821  }
4822  else if ( SCIPisFeasNegative(scip, solval) )
4823  {
4824  SCIP_Real lb;
4825  lb = SCIPvarGetLbLocal(var);
4826  assert( SCIPisFeasNegative(scip, lb) );
4827  if ( ! SCIPisInfinity(scip, -lb) )
4828  coef = 1.0/lb;
4829  }
4830  }
4831  else if ( boundvar == nodedata->ubboundvar )
4832  {
4833  if ( SCIPisFeasPositive(scip, solval) )
4834  {
4835  SCIP_Real ub;
4836 
4837  ub = nodedata->ubboundcoef;
4838  assert( SCIPisFeasPositive(scip, ub) );
4839  if ( ! SCIPisInfinity(scip, ub) )
4840  coef = 1.0/ub;
4841  }
4842  else if ( SCIPisFeasNegative(scip, solval) )
4843  {
4844  SCIP_Real lb;
4845 
4846  lb = nodedata->lbboundcoef;
4847  assert( SCIPisFeasPositive(scip, lb) );
4848  if ( ! SCIPisInfinity(scip, -lb) )
4849  coef = 1.0/lb;
4850  }
4851  }
4852  if ( ! SCIPisZero(scip, coef) )
4853  {
4854  *feas += coef * solval;
4855  SCIP_CALL( SCIPaddCoefLinear(scip, cons, var, coef) );
4856  }
4857 
4858  if ( extend )
4859  {
4860  assert( extensions != NULL );
4861  /* compute new 'extensions' array */
4862  nextensionsnew = 0;
4863  for (s = 0; s < nextensions; ++s)
4864  {
4865  if ( s != bestindex && isConnectedSOS1(NULL, conflictgraph, bestindex, extensions[s]) )
4866  extensions[nextensionsnew++] = extensions[s];
4867  }
4868  nextensions = nextensionsnew;
4869  }
4870  else
4871  nextensions = 0;
4872  }
4873 
4874  /* free buffer array */
4875  if ( extend )
4876  SCIPfreeBufferArray(scip, &extensions);
4877 
4878  /* subtract rhs of constraint from feasibility value or add bound variable if existent */
4879  if ( boundvar == NULL )
4880  *feas -= 1.0;
4881  else
4882  {
4883  SCIP_CALL( SCIPaddCoefLinear(scip, cons, boundvar, -1.0) );
4884  *feas -= SCIPgetSolVal(scip, sol, boundvar);
4885  }
4886 
4887  return SCIP_OKAY;
4888 }
4889 
4890 
4891 /** tries to add feasible complementarity constraints to a given child branching node.
4892  *
4893  * @note In this function the conflict graph is updated to the conflict graph of the considered child branching node.
4894  */
4895 static
4897  SCIP* scip, /**< SCIP pointer */
4898  SCIP_NODE* node, /**< branching node */
4899  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
4900  SCIP_DIGRAPH* conflictgraph, /**< conflict graph of the current node */
4901  SCIP_DIGRAPH* localconflicts, /**< local conflicts (updates to local conflicts of child node) */
4902  SCIP_SOL* sol, /**< solution to be enforced (NULL for LP solution) */
4903  int nsos1vars, /**< number of SOS1 variables */
4904  SCIP_Bool* verticesarefixed, /**< vector that indicates which variables are currently fixed to zerox */
4905  int* fixingsnode1, /**< vertices of variables that will be fixed to zero for the branching node in the input of this function */
4906  int nfixingsnode1, /**< number of entries of array nfixingsnode1 */
4907  int* fixingsnode2, /**< vertices of variables that will be fixed to zero for the other branching node */
4908  int nfixingsnode2, /**< number of entries of array nfixingsnode2 */
4909  int* naddedconss, /**< pointer to store the number of added SOS1 constraints */
4910  SCIP_Bool onlyviolsos1 /**< should only SOS1 constraints be added that are violated by the LP solution */
4911  )
4912 {
4913  assert( scip != NULL );
4914  assert( node != NULL );
4915  assert( conshdlrdata != NULL );
4916  assert( conflictgraph != NULL );
4917  assert( verticesarefixed != NULL );
4918  assert( fixingsnode1 != NULL );
4919  assert( fixingsnode2 != NULL );
4920  assert( naddedconss != NULL );
4921 
4922  *naddedconss = 0;
4923 
4924  if ( nfixingsnode2 > 1 )
4925  {
4926  int* fixingsnode21; /* first partition of fixingsnode2 */
4927  int* fixingsnode22; /* second partition of fixingsnode2 */
4928  int nfixingsnode21;
4929  int nfixingsnode22;
4930 
4931  int* coverarray; /* vertices, not in fixingsnode1 that cover all the vertices in array fixingsnode22 */
4932  int ncoverarray;
4933 
4934  SCIP_Bool* mark;
4935  int* succarray;
4936  int nsuccarray;
4937  int* succ;
4938  int nsucc;
4939 
4940  int i;
4941  int s;
4942 
4943  /* allocate buffer arrays */
4944  SCIP_CALL( SCIPallocBufferArray(scip, &succarray, nsos1vars) );
4945  SCIP_CALL( SCIPallocBufferArray(scip, &mark, nsos1vars) );
4946  SCIP_CALL( SCIPallocBufferArray(scip, &fixingsnode21, nfixingsnode2) );
4947  SCIP_CALL( SCIPallocBufferArray(scip, &fixingsnode22, nfixingsnode2) );
4948 
4949  /* mark all the unfixed vertices with FALSE */
4950  for (i = 0; i < nsos1vars; ++i)
4951  mark[i] = (verticesarefixed[i]);
4952 
4953  /* mark all the vertices that are in the set fixingsnode1 */
4954  for (i = 0; i < nfixingsnode1; ++i)
4955  {
4956  assert( nfixingsnode1 <= 1 || (fixingsnode1[nfixingsnode1 - 1] > fixingsnode1[nfixingsnode1 - 2]) ); /* test: vertices are sorted */
4957  mark[fixingsnode1[i]] = TRUE;
4958  }
4959 
4960  /* mark all the vertices that are in the set fixingsnode2 */
4961  for (i = 0; i < nfixingsnode2; ++i)
4962  {
4963  assert( nfixingsnode2 <= 1 || (fixingsnode2[nfixingsnode2 - 1] > fixingsnode2[nfixingsnode2 - 2]) ); /* test: vertices are sorted */
4964  mark[fixingsnode2[i]] = TRUE;
4965  }
4966 
4967  /* compute the set of vertices that have a neighbor in the set fixingsnode2, but are not in the set fixingsnode1 or fixingsnode2 and are not already fixed */
4968  nsuccarray = 0;
4969  for (i = 0; i < nfixingsnode2; ++i)
4970  {
4971  nsucc = SCIPdigraphGetNSuccessors(conflictgraph, fixingsnode2[i]);
4972  succ = SCIPdigraphGetSuccessors(conflictgraph, fixingsnode2[i]);
4973 
4974  for (s = 0; s < nsucc; ++s)
4975  {
4976  int succnode = succ[s];
4977 
4978  if ( ! mark[succnode] )
4979  {
4980  mark[succnode] = TRUE;
4981  succarray[nsuccarray++] = succnode;
4982  }
4983  }
4984  }
4985 
4986  /* allocate buffer array */
4987  SCIP_CALL( SCIPallocBufferArray(scip, &coverarray, nsos1vars) );
4988 
4989  /* mark all the vertices with FALSE */
4990  for (i = 0; i < nsos1vars; ++i)
4991  mark[i] = FALSE;
4992 
4993  /* mark all the vertices that are in the set fixingsnode2 */
4994  for (i = 0; i < nfixingsnode2; ++i)
4995  mark[fixingsnode2[i]] = TRUE;
4996 
4997  /* for every node in succarray */
4998  for (i = 0; i < nsuccarray; ++i)
4999  {
5000  SCIP_Real solval1;
5001  SCIP_VAR* var1;
5002  int vertex1;
5003  int j;
5004 
5005  vertex1 = succarray[i];
5006  var1 = SCIPnodeGetVarSOS1(conflictgraph, vertex1);
5007  solval1 = SCIPgetSolVal(scip, sol, var1);
5008 
5009  /* we only add complementarity constraints if they are violated by the current LP solution */
5010  if ( ! onlyviolsos1 || ! SCIPisFeasZero(scip, solval1) )
5011  {
5012  /* compute first partition of fixingsnode2 that is the intersection of the neighbors of 'vertex1' with the set fixingsnode2 */
5013  nsucc = SCIPdigraphGetNSuccessors(conflictgraph, vertex1);
5014  succ = SCIPdigraphGetSuccessors(conflictgraph, vertex1);
5015  nfixingsnode21 = 0;
5016 
5017  for (s = 0; s < nsucc; ++s)
5018  {
5019  if ( mark[succ[s]] )
5020  {
5021  fixingsnode21[nfixingsnode21++] = succ[s];
5022  assert( nfixingsnode21 == 1 || (fixingsnode21[nfixingsnode21 - 1] > fixingsnode21[nfixingsnode21 - 2]) ); /* test: successor vertices are sorted */
5023  }
5024  }
5025 
5026  /* if variable can be fixed to zero */
5027  if ( nfixingsnode21 == nfixingsnode2 )
5028  {
5029  SCIP_Bool infeasible;
5030 
5031  SCIP_CALL( fixVariableZeroNode(scip, var1, node, &infeasible) );
5032  assert( ! infeasible );
5033  continue;
5034  }
5035 
5036  /* compute second partition of fixingsnode2 (that is fixingsnode2 \setminus fixingsnode21 ) */
5037  SCIP_CALL( SCIPcomputeArraysSetminus(fixingsnode2, nfixingsnode2, fixingsnode21, nfixingsnode21, fixingsnode22, &nfixingsnode22) );
5038  assert ( nfixingsnode22 + nfixingsnode21 == nfixingsnode2 );
5039 
5040  /* compute cover set (that are all the vertices not in fixingsnode1 and fixingsnode21, whose neighborhood covers all the vertices of fixingsnode22) */
5041  SCIP_CALL( getCoverVertices(conflictgraph, verticesarefixed, -1, fixingsnode22, nfixingsnode22, coverarray, &ncoverarray) );
5042  SCIP_CALL( SCIPcomputeArraysSetminus(coverarray, ncoverarray, fixingsnode1, nfixingsnode1, coverarray, &ncoverarray) );
5043  SCIP_CALL( SCIPcomputeArraysSetminus(coverarray, ncoverarray, fixingsnode21, nfixingsnode21, coverarray, &ncoverarray) );
5044 
5045  for (j = 0; j < ncoverarray; ++j)
5046  {
5047  int vertex2;
5048 
5049  vertex2 = coverarray[j];
5050  assert( vertex2 != vertex1 );
5051 
5052  /* prevent double enumeration */
5053  if ( vertex2 < vertex1 )
5054  {
5055  SCIP_VAR* var2;
5056  SCIP_Real solval2;
5057 
5058  var2 = SCIPnodeGetVarSOS1(conflictgraph, vertex2);
5059  solval2 = SCIPgetSolVal(scip, sol, var2);
5060 
5061  if ( onlyviolsos1 && ( SCIPisFeasZero(scip, solval1) || SCIPisFeasZero(scip, solval2) ) )
5062  continue;
5063 
5064  if ( ! isConnectedSOS1(NULL, conflictgraph, vertex1, vertex2) )
5065  {
5066  char name[SCIP_MAXSTRLEN];
5067  SCIP_CONS* conssos1 = NULL;
5068  SCIP_Bool takebound = FALSE;
5069  SCIP_Real feas;
5070 
5071  SCIP_NODEDATA* nodedata;
5072  SCIP_Real lbboundcoef1;
5073  SCIP_Real lbboundcoef2;
5074  SCIP_Real ubboundcoef1;
5075  SCIP_Real ubboundcoef2;
5076  SCIP_VAR* boundvar1;
5077  SCIP_VAR* boundvar2;
5078 
5079  /* get bound variables if available */
5080  nodedata = (SCIP_NODEDATA*)SCIPdigraphGetNodeData(conflictgraph, vertex1);
5081  assert( nodedata != NULL );
5082  boundvar1 = nodedata->ubboundvar;
5083  lbboundcoef1 = nodedata->lbboundcoef;
5084  ubboundcoef1 = nodedata->ubboundcoef;
5085  nodedata = (SCIP_NODEDATA*)SCIPdigraphGetNodeData(conflictgraph, vertex2);
5086  assert( nodedata != NULL );
5087  boundvar2 = nodedata->ubboundvar;
5088  lbboundcoef2 = nodedata->lbboundcoef;
5089  ubboundcoef2 = nodedata->ubboundcoef;
5090 
5091  if ( boundvar1 != NULL && boundvar2 != NULL && SCIPvarCompare(boundvar1, boundvar2) == 0 )
5092  takebound = TRUE;
5093 
5094  /* add new arc to local conflicts in order to generate tighter bound inequalities */
5095  if ( conshdlrdata->addextendedbds )
5096  {
5097  if ( localconflicts == NULL )
5098  {
5099  SCIP_CALL( SCIPdigraphCreate(&conshdlrdata->localconflicts, nsos1vars) );
5100  localconflicts = conshdlrdata->localconflicts;
5101  }
5102  SCIP_CALL( SCIPdigraphAddArc(localconflicts, vertex1, vertex2, NULL) );
5103  SCIP_CALL( SCIPdigraphAddArc(localconflicts, vertex2, vertex1, NULL) );
5104  SCIP_CALL( SCIPdigraphAddArc(conflictgraph, vertex1, vertex2, NULL) );
5105  SCIP_CALL( SCIPdigraphAddArc(conflictgraph, vertex2, vertex1, NULL) );
5106 
5107  /* can sort successors in place - do not use arcdata */
5108  SCIPsortInt(SCIPdigraphGetSuccessors(localconflicts, vertex1), SCIPdigraphGetNSuccessors(localconflicts, vertex1));
5109  SCIPsortInt(SCIPdigraphGetSuccessors(localconflicts, vertex2), SCIPdigraphGetNSuccessors(localconflicts, vertex2));
5110  SCIPsortInt(SCIPdigraphGetSuccessors(conflictgraph, vertex1), SCIPdigraphGetNSuccessors(conflictgraph, vertex1));
5111  SCIPsortInt(SCIPdigraphGetSuccessors(conflictgraph, vertex2), SCIPdigraphGetNSuccessors(conflictgraph, vertex2));
5112 
5113  /* mark conflictgraph as not local such that the new arcs are deleted after currents node processing */
5114  conshdlrdata->isconflocal = TRUE;
5115  }
5116 
5117  /* measure feasibility of complementarity between var1 and var2 */
5118  if ( ! takebound )
5119  {
5120  feas = -1.0;
5121  if ( SCIPisFeasPositive(scip, solval1) )
5122  {
5123  assert( SCIPisFeasPositive(scip, SCIPvarGetUbLocal(var1)));
5124  if ( ! SCIPisInfinity(scip, SCIPvarGetUbLocal(var1)) )
5125  feas += solval1/SCIPvarGetUbLocal(var1);
5126  }
5127  else if ( SCIPisFeasNegative(scip, solval1) )
5128  {
5129  assert( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var1)));
5130  if ( ! SCIPisInfinity(scip, -SCIPvarGetLbLocal(var1)) )
5131  feas += solval1/SCIPvarGetLbLocal(var1);
5132  }
5133 
5134  if ( SCIPisFeasPositive(scip, solval2) )
5135  {
5136  assert( SCIPisFeasPositive(scip, SCIPvarGetUbLocal(var2)));
5137  if ( ! SCIPisInfinity(scip, SCIPvarGetUbLocal(var2)) )
5138  feas += solval2/SCIPvarGetUbLocal(var2);
5139  }
5140  else if ( SCIPisFeasNegative(scip, solval2) )
5141  {
5142  assert( SCIPisFeasPositive(scip, SCIPvarGetLbLocal(var2)));
5143  if ( ! SCIPisInfinity(scip, -SCIPvarGetLbLocal(var2)) )
5144  feas += solval2/SCIPvarGetLbLocal(var2);
5145  }
5146  }
5147  else
5148  {
5149  feas = -SCIPgetSolVal(scip, sol, boundvar1);
5150  if ( SCIPisFeasPositive(scip, solval1) )
5151  {
5152  assert( SCIPisFeasPositive(scip, ubboundcoef1));
5153  if ( ! SCIPisInfinity(scip, ubboundcoef1) )
5154  feas += solval1/ubboundcoef1;
5155  }
5156  else if ( SCIPisFeasNegative(scip, solval1) )
5157  {
5158  assert( SCIPisFeasPositive(scip, lbboundcoef1));
5159  if ( ! SCIPisInfinity(scip, -lbboundcoef1) )
5160  feas += solval1/lbboundcoef1;
5161  }
5162 
5163  if ( SCIPisFeasPositive(scip, solval2) )
5164  {
5165  assert( SCIPisFeasPositive(scip, ubboundcoef2));
5166  if ( ! SCIPisInfinity(scip, ubboundcoef2) )
5167  feas += solval2/ubboundcoef2;
5168  }
5169  else if ( SCIPisFeasNegative(scip, solval2) )
5170  {
5171  assert( SCIPisFeasPositive(scip, lbboundcoef2));
5172  if ( ! SCIPisInfinity(scip, -lbboundcoef2) )
5173  feas += solval2/lbboundcoef2;
5174  }
5175  assert( ! SCIPisFeasNegative(scip, solval2) );
5176  }
5177 
5178  if ( SCIPisGT(scip, feas, conshdlrdata->addcompsfeas) )
5179  {
5180  /* create SOS1 constraint */
5181  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "sos1_branchnode_%i_no_%i", SCIPnodeGetNumber(node), *naddedconss);
5182  SCIP_CALL( SCIPcreateConsSOS1(scip, &conssos1, name, 0, NULL, NULL, TRUE, TRUE, TRUE, FALSE, TRUE,
5183  TRUE, FALSE, FALSE, FALSE) );
5184 
5185  /* add variables to SOS1 constraint */
5186  SCIP_CALL( addVarSOS1(scip, conssos1, conshdlrdata, var1, 1.0) );
5187  SCIP_CALL( addVarSOS1(scip, conssos1, conshdlrdata, var2, 2.0) );
5188 
5189  /* add SOS1 constraint to the branching node */
5190  SCIP_CALL( SCIPaddConsNode(scip, node, conssos1, NULL) );
5191  ++(*naddedconss);
5192 
5193  /* release constraint */
5194  SCIP_CALL( SCIPreleaseCons(scip, &conssos1) );
5195  }
5196 
5197 
5198  /* add bound inequality*/
5199  if ( ! SCIPisFeasZero(scip, solval1) && ! SCIPisFeasZero(scip, solval2) )
5200  {
5201  /* possibly create linear constraint of the form x_i/u_i + x_j/u_j <= t if a bound variable t with x_i <= u_i * t and x_j <= u_j * t exists.
5202  * Otherwise try to create a constraint of the form x_i/u_i + x_j/u_j <= 1. Try the same for the lower bounds. */
5203  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "boundcons_branchnode_%i_no_%i", SCIPnodeGetNumber(node), *naddedconss);
5204  if ( takebound )
5205  {
5206  /* create constraint with right hand side = 0.0 */
5207  SCIP_CALL( SCIPcreateConsLinear(scip, &conssos1, name, 0, NULL, NULL, -SCIPinfinity(scip), 0.0, TRUE, FALSE, TRUE, FALSE, FALSE,
5208  TRUE, FALSE, FALSE, FALSE, FALSE) );
5209 
5210  /* add variables */
5211  SCIP_CALL( getBoundConsFromVertices(scip, conflictgraph, sol, vertex1, vertex2, boundvar1, conshdlrdata->addextendedbds, conssos1, &feas) );
5212  }
5213  else
5214  {
5215  /* create constraint with right hand side = 1.0 */
5216  SCIP_CALL( SCIPcreateConsLinear(scip, &conssos1, name, 0, NULL, NULL, -SCIPinfinity(scip), 1.0, TRUE, FALSE, TRUE, FALSE, FALSE,
5217  TRUE, FALSE, FALSE, FALSE, FALSE) );
5218 
5219  /* add variables */
5220  SCIP_CALL( getBoundConsFromVertices(scip, conflictgraph, sol, vertex1, vertex2, NULL, conshdlrdata->addextendedbds, conssos1, &feas) );
5221  }
5222 
5223  /* add linear constraint to the branching node if usefull */
5224  if ( SCIPisGT(scip, feas, conshdlrdata->addbdsfeas ) )
5225  {
5226  SCIP_CALL( SCIPaddConsNode(scip, node, conssos1, NULL) );
5227  ++(*naddedconss);
5228  }
5229 
5230  /* release constraint */
5231  SCIP_CALL( SCIPreleaseCons(scip, &conssos1) );
5232  }
5233 
5234  /* break if number of added constraints exceeds a predefined value */
5235  if ( conshdlrdata->maxaddcomps >= 0 && *naddedconss > conshdlrdata->maxaddcomps )
5236  break;
5237  }
5238  }
5239  }
5240  }
5241 
5242  /* break if number of added constraints exceeds a predefined value */
5243  if ( conshdlrdata->maxaddcomps >= 0 && *naddedconss > conshdlrdata->maxaddcomps )
5244  break;
5245  }
5246 
5247  /* free buffer array */
5248  SCIPfreeBufferArray(scip, &coverarray);
5249  SCIPfreeBufferArray(scip, &fixingsnode22);
5250  SCIPfreeBufferArray(scip, &fixingsnode21);
5251  SCIPfreeBufferArray(scip, &mark);
5252  SCIPfreeBufferArray(scip, &succarray);
5253  }
5254 
5255  return SCIP_OKAY;
5256 }
5257 
5258 
5259 /** resets local conflict graph to the conflict graph of the root node */
5260 static
5262  SCIP_DIGRAPH* conflictgraph, /**< conflict graph of root node */
5263  SCIP_DIGRAPH* localconflicts, /**< local conflicts that should be removed from conflict graph */
5264  int nsos1vars /**< number of SOS1 variables */
5265  )
5266 {
5267  int j;
5268 
5269  for (j = 0; j < nsos1vars; ++j)
5270  {
5271  int nsuccloc;
5272 
5273  nsuccloc = SCIPdigraphGetNSuccessors(localconflicts, j);
5274  if ( nsuccloc > 0 )
5275  {
5276  int* succloc;
5277  int* succ;
5278  int nsucc;
5279  int k = 0;
5280 
5281  succloc = SCIPdigraphGetSuccessors(localconflicts, j);
5282  succ = SCIPdigraphGetSuccessors(conflictgraph, j);
5283  nsucc = SCIPdigraphGetNSuccessors(conflictgraph, j);
5284 
5285  /* reset number of successors */
5286  SCIP_CALL( SCIPcomputeArraysSetminus(succ, nsucc, succloc, nsuccloc, succ, &k) );
5287  SCIP_CALL( SCIPdigraphSetNSuccessors(conflictgraph, j, k) );
5288  SCIP_CALL( SCIPdigraphSetNSuccessors(localconflicts, j, 0) );
5289  }
5290  }
5291 
5292  return SCIP_OKAY;
5293 }
5294 
5295 
5296 /** Conflict graph enforcement method
5297  *
5298  * The conflict graph can be enforced by different branching rules:
5299  *
5300  * - Branch on the neighborhood of a single variable @p i, i.e., in one branch \f$x_i\f$ is fixed to zero and in the
5301  * other its neighbors from the conflict graph.
5302  *
5303  * - Branch on complete bipartite subgraphs of the conflict graph, i.e., in one branch fix the variables from the first
5304  * bipartite partition and the variables from the second bipartite partition in the other.
5305  *
5306  * - In addition to variable domain fixings, it is sometimes also possible to add new SOS1 constraints to the branching
5307  * nodes. This results in a nonstatic conflict graph, which may change dynamically with every branching node.
5308  *
5309  * We make use of different selection rules that define on which system of SOS1 variables to branch next:
5310  *
5311  * - Most infeasible branching: Branch on the system of SOS1 variables with largest violation.
5312  *
5313  * - Strong branching: Here, the LP-relaxation is partially solved for each branching decision among a candidate list.
5314  * Then the decision with best progress is chosen.
5315  */
5316 static
5318  SCIP* scip, /**< SCIP pointer */
5319  SCIP_CONSHDLRDATA* conshdlrdata, /**< constraint handler data */
5320  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
5321  int nconss, /**< number of constraints */
5322  SCIP_CONS** conss, /**< SOS1 constraints */
5323  SCIP_SOL* sol, /**< solution to be enforced (NULL for LP solution) */
5324  SCIP_RESULT* result /**< result */
5325  )
5326 {
5327  SCIP_DIGRAPH* conflictgraph;
5328  int nsos1vars;
5329 
5330  SCIP_Bool* verticesarefixed = NULL;
5331  int* fixingsnode1 = NULL;
5332  int* fixingsnode2 = NULL;
5333  int nfixingsnode1;
5334  int nfixingsnode2;
5335 
5336  SCIP_Real bestobjval1 = -SCIPinfinity(scip);
5337  SCIP_Real bestobjval2 = -SCIPinfinity(scip);
5338  SCIP_Real lpobjval = -SCIPinfinity(scip);
5339 
5340  SCIP_Bool infeasible;
5341  SCIP_Bool bipbranch = FALSE;
5342  int nstrongrounds;
5343 
5344  int branchvertex;
5345  SCIP_NODE* node1;
5346  SCIP_NODE* node2;
5347  SCIP_Real nodeselest;
5348  SCIP_Real objest;
5349 
5350  int i;
5351  int j;
5352  int c;
5353 
5354  assert( scip != NULL );
5355  assert( conshdlrdata != NULL );
5356  assert( conshdlr != NULL );
5357  assert( conss != NULL );
5358  assert( result != NULL );
5359 
5360  SCIPdebugMsg(scip, "Enforcing SOS1 conflict graph <%s>.\n", SCIPconshdlrGetName(conshdlr) );
5361  *result = SCIP_DIDNOTRUN;
5362 
5363  /* get number of SOS1 variables */
5364  nsos1vars = conshdlrdata->nsos1vars;
5365 
5366  /* get conflict graph */
5367  conflictgraph = conshdlrdata->conflictgraph;
5368  assert( ! conshdlrdata->isconflocal ); /* conflictgraph should be the one of the root node */
5369 
5370  /* check each constraint and update conflict graph if necessary */
5371  for (c = 0; c < nconss; ++c)
5372  {
5373  SCIP_CONSDATA* consdata;
5374  SCIP_CONS* cons;
5375  SCIP_Bool cutoff;int ngen;
5376 
5377  cons = conss[c];
5378  assert( cons != NULL );
5379  consdata = SCIPconsGetData(cons);
5380  assert( consdata != NULL );
5381 
5382  /* do nothing if there are not enough variables - this is usually eliminated by preprocessing */
5383  if ( consdata->nvars < 2 )
5384  continue;
5385 
5386  /* first perform propagation (it might happen that standard propagation is turned off) */
5387  ngen = 0;
5388  SCIP_CALL( propConsSOS1(scip, cons, consdata, &cutoff, &ngen) );
5389  SCIPdebugMsg(scip, "propagating <%s> in enforcing (cutoff: %u, domain reductions: %d).\n", SCIPconsGetName(cons), cutoff, ngen);
5390  if ( cutoff )
5391  {
5392  *result = SCIP_CUTOFF;
5393  break;
5394  }
5395  if ( ngen > 0 )
5396  {
5397  *result = SCIP_REDUCEDDOM;
5398  break;
5399  }
5400  assert( ngen == 0 );
5401 
5402  /* add local conflicts to conflict graph and save them in 'localconflicts' */
5403  if ( consdata->local )
5404  {
5405  SCIP_VAR** vars;
5406  int nvars;
5407  int indi;
5408  int indj;
5409 
5410  if ( conshdlrdata->localconflicts == NULL )
5411  {
5412  SCIP_CALL( SCIPdigraphCreate(&conshdlrdata->localconflicts, nsos1vars ) );
5413  }
5414 
5415  vars = consdata->vars;
5416  nvars = consdata->nvars;
5417  for (i = 0; i < nvars-1; ++i)
5418  {
5419  SCIP_VAR* var;
5420 
5421  var = vars[i];
5422  indi = varGetNodeSOS1(conshdlrdata, var);
5423  assert( indi >= 0 );
5424 
5425  if ( ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) || ! SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) )
5426  {
5427  for (j = i+1; j < nvars; ++j)
5428  {
5429  var = vars[j];
5430  indj = varGetNodeSOS1(conshdlrdata, var);
5431  assert( indj >= 0 );
5432 
5433  if ( ! SCIPisFeasZero(scip, SCIPvarGetUbLocal(var)) || ! SCIPisFeasZero(scip, SCIPvarGetLbLocal(var)) )
5434  {
5435  if ( ! isConnectedSOS1(NULL, conflictgraph, indi, indj) )
5436  {
5437  SCIP_CALL( SCIPdigraphAddArcSafe(conflictgraph, indi, indj, NULL) );
5438  SCIP_CALL( SCIPdigraphAddArcSafe(conflictgraph, indj, indi, NULL) );
5439 
5440  SCIP_CALL( SCIPdigraphAddArcSafe(conshdlrdata->localconflicts, indi, indj, NULL) );
5441  SCIP_CALL( SCIPdigraphAddArcSafe(conshdlrdata->localconflicts, indj, indi, NULL) );
5442 
5443  conshdlrdata->isconflocal = TRUE;
5444  }
5445  }
5446  }
5447  }
5448  }
5449  }
5450  }
5451 
5452  /* sort successor list of conflict graph if necessary */
5453  if ( conshdlrdata->isconflocal )
5454  {
5455  for (j = 0; j < nsos1vars; ++j)
5456  {
5457  int nsuccloc;
5458 
5459  nsuccloc = SCIPdigraphGetNSuccessors(conshdlrdata->localconflicts, j);
5460  if ( nsuccloc > 0 )
5461  {
5462  SCIPsortInt(SCIPdigraphGetSuccessors(conflictgraph, j), SCIPdigraphGetNSuccessors(conflictgraph, j));
5463  SCIPsortInt(SCIPdigraphGetSuccessors(conshdlrdata->localconflicts, j), nsuccloc);
5464  }
5465  }
5466  }
5467 
5468  if ( *result == SCIP_CUTOFF || *result == SCIP_REDUCEDDOM )
5469  {
5470  /* remove local conflicts from conflict graph */
5471  if ( conshdlrdata->isconflocal )
5472  {
5473  SCIP_CALL( resetConflictgraphSOS1(conflictgraph, conshdlrdata->localconflicts, nsos1vars) );
5474  conshdlrdata->isconflocal = FALSE;
5475  }
5476  return SCIP_OKAY;
5477  }
5478 
5479 
5480  /* detect fixed variables */
5481  SCIP_CALL( SCIPallocBufferArray(scip, &verticesarefixed, nsos1vars) );
5482  for (j = 0; j < nsos1vars; ++j)
5483  {
5484  SCIP_VAR* var;
5485  SCIP_Real ub;
5486  SCIP_Real lb;
5487 
5488  var = SCIPnodeGetVarSOS1(conflictgraph, j);
5489  ub = SCIPvarGetUbLocal(var);
5490  lb = SCIPvarGetLbLocal(var);
5491  if ( SCIPisFeasZero(scip, ub) && SCIPisFeasZero(scip, lb) )
5492  verticesarefixed[j] = TRUE;
5493  else
5494  verticesarefixed[j] = FALSE;
5495  }
5496 
5497  /* should bipartite branching be used? */
5498  if ( conshdlrdata->branchingrule == 'b' )
5499  bipbranch = TRUE;
5500 
5501  /* determine number of strong branching iterations */
5502  if ( conshdlrdata->nstrongrounds >= 0 )
5503  nstrongrounds = MIN(conshdlrdata->nstrongrounds, nsos1vars);
5504  else
5505  {
5506  /* determine number depending on depth, based on heuristical considerations */
5507  if ( SCIPgetDepth(scip) <= 10 )
5508  nstrongrounds = MAX(10, (int)SCIPfloor(scip, pow(log((SCIP_Real)nsos1vars), 1.0)));/*lint !e666*/
5509  else if ( SCIPgetDepth(scip) <= 20 )
5510  nstrongrounds = MAX(5, (int)SCIPfloor(scip, pow(log((SCIP_Real)nsos1vars), 0.7)));/*lint !e666*/
5511  else
5512  nstrongrounds = 0;
5513  nstrongrounds = MIN(nsos1vars, nstrongrounds);
5514  }
5515 
5516 
5517  /* allocate buffer arrays */
5518  SCIP_CALL( SCIPallocBufferArray(scip, &fixingsnode1, nsos1vars) );
5519  if ( bipbranch )
5520  SCIP_CALL( SCIPallocBufferArray(scip, &fixingsnode2, nsos1vars) );
5521  else
5522  SCIP_CALL( SCIPallocBufferArray(scip, &fixingsnode2, 1) );
5523 
5524 
5525  /* if strongbranching is turned off: use most infeasible branching */
5526  if ( nstrongrounds == 0 )
5527  {
5528  SCIP_Bool relsolfeas;
5529 
5530  /* get branching vertex using most infeasible branching */
5531  SCIP_CALL( getBranchingPrioritiesSOS1(scip, conshdlrdata, conflictgraph, sol, nsos1vars, verticesarefixed, bipbranch, fixingsnode1, fixingsnode2, NULL, &branchvertex, &relsolfeas) );
5532 
5533  /* if LP relaxation solution is feasible */
5534  if ( relsolfeas )
5535  {
5536  SCIPdebugMsg(scip, "all the SOS1 constraints are feasible.\n");
5537 
5538  /* update result */
5539  *result = SCIP_FEASIBLE;
5540 
5541  /* remove local conflicts from conflict graph */
5542  if ( conshdlrdata->isconflocal )
5543  {
5544  SCIP_CALL( resetConflictgraphSOS1(conflictgraph, conshdlrdata->localconflicts, nsos1vars) );
5545  conshdlrdata->isconflocal = FALSE;
5546  }
5547 
5548  /* free memory */
5549  SCIPfreeBufferArrayNull(scip, &fixingsnode2);
5550  SCIPfreeBufferArrayNull(scip, &fixingsnode1);
5551  SCIPfreeBufferArrayNull(scip, &verticesarefixed);
5552 
5553  return SCIP_OKAY;
5554  }
5555  }
5556  else
5557  {
5558  /* get branching vertex using strong branching */
5559  SCIP_CALL( getBranchingDecisionStrongbranchSOS1(scip, conshdlrdata, conflictgraph, sol, nsos1vars, lpobjval, bipbranch, nstrongrounds, verticesarefixed,
5560  fixingsnode1, fixingsnode2, &branchvertex, &bestobjval1, &bestobjval2, result) );
5561 
5562  if ( *result == SCIP_CUTOFF || *result == SCIP_FEASIBLE || *result == SCIP_REDUCEDDOM )
5563  {
5564  /* remove local conflicts from conflict graph */
5565  if ( conshdlrdata->isconflocal )
5566  {
5567  SCIP_CALL( resetConflictgraphSOS1(conflictgraph, conshdlrdata->localconflicts, nsos1vars) );
5568  conshdlrdata->isconflocal = FALSE;
5569  }
5570 
5571  /* free memory */
5572  SCIPfreeBufferArrayNull(scip, &fixingsnode2);
5573  SCIPfreeBufferArrayNull(scip, &fixingsnode1);
5574  SCIPfreeBufferArrayNull(scip, &verticesarefixed);
5575 
5576  return SCIP_OKAY;
5577  }
5578  }
5579 
5580  /* if we shouldleave branching decision to branching rules */
5581  if ( ! conshdlrdata->branchsos )
5582  {
5583  /* remove local conflicts from conflict graph */
5584  if ( conshdlrdata->isconflocal )
5585  {
5586  SCIP_CALL( resetConflictgraphSOS1(conflictgraph, conshdlrdata->localconflicts, nsos1vars) );
5587  conshdlrdata->isconflocal = FALSE;
5588  }
5589 
5590  if ( SCIPvarIsBinary(SCIPnodeGetVarSOS1(conflictgraph, branchvertex)) )
5591  {
5592  *result = SCIP_INFEASIBLE;
5593  return SCIP_OKAY;
5594  }
5595  else
5596  {
5597  SCIPerrorMessage("Incompatible parameter setting: branchsos can only be set to false if all SOS1 variables are binary.\n");
5598  return SCIP_PARAMETERWRONGVAL;
5599  }
5600  }
5601 
5602  /* create branching nodes */
5603 
5604  /* get vertices of variables that will be fixed to zero for each node */
5605  assert( branchvertex >= 0 && branchvertex < nsos1vars );
5606  assert( ! verticesarefixed[branchvertex] );
5607  SCIP_CALL( getBranchingVerticesSOS1(scip, conflictgraph, sol, verticesarefixed, bipbranch, branchvertex, fixingsnode1, &nfixingsnode1, fixingsnode2, &nfixingsnode2) );
5608 
5609  /* calculate node selection and objective estimate for node 1 */
5610  nodeselest = 0.0;
5611  objest = 0.0;
5612  for (j = 0; j < nfixingsnode1; ++j)
5613  {
5614  SCIP_VAR* var;
5615 
5616  var = SCIPnodeGetVarSOS1(conflictgraph, fixingsnode1[j]);
5617  nodeselest += SCIPcalcNodeselPriority(scip, var, SCIP_BRANCHDIR_DOWNWARDS, 0.0);
5618  objest += SCIPcalcChildEstimate(scip, var, 0.0);
5619  }
5620  /* take the average of the individual estimates */
5621  objest = objest/((SCIP_Real) nfixingsnode1);
5622 
5623  /* create node 1 */
5624  SCIP_CALL( SCIPcreateChild(scip, &node1, nodeselest, objest) );
5625 
5626  /* fix variables for the first node */
5627  if ( conshdlrdata->fixnonzero && nfixingsnode2 == 1 )
5628  {
5629  SCIP_VAR* var;
5630  SCIP_Real lb;
5631  SCIP_Real ub;
5632 
5633  var = SCIPnodeGetVarSOS1(conflictgraph, fixingsnode2[0]);
5634  lb = SCIPvarGetLbLocal(var);
5635  ub = SCIPvarGetUbLocal(var);
5636 
5638  {
5639  if ( SCIPisZero(scip, lb) )
5640  {
5641  /* fix variable to some very small, but positive number or to 1.0 if variable is integral */
5642  if (SCIPvarIsIntegral(var) )
5643  {
5644  SCIP_CALL( SCIPchgVarLbNode(scip, node1, var, 1.0) );
5645  }
5646  else
5647  {
5648  SCIP_CALL( SCIPchgVarLbNode(scip, node1, var, 1.5 * SCIPfeastol(scip)) );
5649  }
5650  }
5651  else if ( SCIPisZero(scip, ub) )
5652  {
5653  if (SCIPvarIsIntegral(var) )
5654  {
5655  /* fix variable to some negative number with small absolute value to -1.0 if variable is integral */
5656  SCIP_CALL( SCIPchgVarUbNode(scip, node1, var, -1.0) );
5657  }
5658  else
5659  {
5660  /* fix variable to some negative number with small absolute value to -1.0 if variable is integral */
5661  SCIP_CALL( SCIPchgVarUbNode(scip, node1, var, -1.5 * SCIPfeastol(scip)) );
5662  }
5663  }
5664  }
5665  }
5666  for (j = 0; j < nfixingsnode1; ++j)
5667  {
5668  /* fix variable to zero */
5669  SCIP_CALL( fixVariableZeroNode(scip, SCIPnodeGetVarSOS1(conflictgraph, fixingsnode1[j]), node1, &infeasible) );
5670  assert( ! infeasible );
5671  }
5672 
5673  /* calculate node selection and objective estimate for node 2 */
5674  nodeselest = 0.0;
5675  objest = 0.0;
5676  for (j = 0; j < nfixingsnode2; ++j)
5677  {
5678  SCIP_VAR* var;
5679 
5680  var = SCIPnodeGetVarSOS1(conflictgraph, fixingsnode2[j]);
5681  nodeselest += SCIPcalcNodeselPriority(scip, var, SCIP_BRANCHDIR_DOWNWARDS, 0.0);
5682  objest += SCIPcalcChildEstimate(scip, var, 0.0);
5683  }
5684 
5685  /* take the average of the individual estimates */
5686  objest = objest/((SCIP_Real) nfixingsnode2);
5687 
5688  /* create node 2 */
5689  SCIP_CALL( SCIPcreateChild(scip, &node2, nodeselest, objest) );
5690 
5691  /* fix variables to zero */
5692  for (j = 0; j < nfixingsnode2; ++j)
5693  {
5694  SCIP_CALL( fixVariableZeroNode(scip, SCIPnodeGetVarSOS1(conflictgraph, fixingsnode2[j]), node2, &infeasible) );
5695  assert( ! infeasible );
5696  }
5697 
5698 
5699  /* add complementarity constraints to the branching nodes */
5700  if ( conshdlrdata->addcomps && ( conshdlrdata->addcompsdepth == -1 || conshdlrdata->addcompsdepth >= SCIPgetDepth(scip) ) )
5701  {
5702  int naddedconss;
5703 
5704  assert( ! conshdlrdata->fixnonzero );
5705 
5706  /* add complementarity constraints to the left branching node */
5707  SCIP_CALL( addBranchingComplementaritiesSOS1(scip, node1, conshdlrdata, conflictgraph, conshdlrdata->localconflicts, sol,
5708  nsos1vars, verticesarefixed, fixingsnode1, nfixingsnode1, fixingsnode2, nfixingsnode2, &naddedconss, TRUE) );
5709 
5710  if ( naddedconss == 0 )
5711  {
5712  /* add complementarity constraints to the right branching node */
5713  SCIP_CALL( addBranchingComplementaritiesSOS1(scip, node2, conshdlrdata, conflictgraph, conshdlrdata->localconflicts, sol,
5714  nsos1vars, verticesarefixed, fixingsnode2, nfixingsnode2, fixingsnode1, nfixingsnode1, &naddedconss, TRUE) );
5715  }
5716  }
5717 
5718  /* sets node's lower bound to the best known value */
5719  if ( nstrongrounds > 0 )
5720  {
5721  SCIP_CALL( SCIPupdateNodeLowerbound(scip, node1, MAX(lpobjval, bestobjval1) ) );
5722  SCIP_CALL( SCIPupdateNodeLowerbound(scip, node2, MAX(lpobjval, bestobjval2) ) );
5723  }
5724 
5725  /* remove local conflicts from conflict graph */
5726  if ( conshdlrdata->isconflocal )
5727  {
5728  SCIP_CALL( resetConflictgraphSOS1(conflictgraph, conshdlrdata->localconflicts, nsos1vars) );
5729  conshdlrdata->isconflocal = FALSE;
5730  }
5731 
5732  /* free buffer arrays */
5733  SCIPfreeBufferArrayNull(scip, &fixingsnode2);
5734  SCIPfreeBufferArrayNull(scip, &fixingsnode1);
5735  SCIPfreeBufferArrayNull(scip, &verticesarefixed );
5736  *result = SCIP_BRANCHED;
5737 
5738  return SCIP_OKAY;
5739 }
5740 
5741 
5742 /** SOS1 branching enforcement method
5743  *
5744  * We check whether the current solution is feasible, i.e., contains at most one nonzero
5745  * variable. If not, we branch along the lines indicated by Beale and Tomlin:
5746  *
5747  * We first compute \f$W = \sum_{j=1}^n |x_i|\f$ and \f$w = \sum_{j=1}^n j\, |x_i|\f$. Then we
5748  * search for the index \f$k\f$ that satisfies
5749  * \f[
5750  * k \leq \frac{w}{W} < k+1.
5751  * \f]
5752  * The branches are then
5753  * \f[
5754  * x_1 = 0, \ldots, x_k = 0 \qquad \mbox{and}\qquad x_{k+1} = 0, \ldots, x_n = 0.
5755  * \f]
5756  *
5757  * If the constraint contains two variables, the branching of course simplifies.
5758  *
5759  * Depending on the parameters (@c branchnonzeros, @c branchweight) there are three ways to choose
5760  * the branching constraint.
5761  *
5762  * <TABLE>
5763  * <TR><TD>@c branchnonzeros</TD><TD>@c branchweight</TD><TD>constraint chosen</TD></TR>
5764  * <TR><TD>@c true </TD><TD> ? </TD><TD>most number of nonzeros</TD></TR>
5765  * <TR><TD>@c false </TD><TD> @c true </TD><TD>maximal weight corresponding to nonzero variable</TD></TR>
5766  * <TR><TD>@c false </TD><TD> @c true </TD><TD>largest sum of variable values</TD></TR>
5767  * </TABLE>
5768  *
5769  * @c branchnonzeros = @c false, @c branchweight = @c true allows the user to specify an order for
5770  * the branching importance of the constraints (setting the weights accordingly).
5771  *
5772  * Constraint branching can also be turned off using parameter @c branchsos.
5773  */
5774 static
5776  SCIP* scip, /**< SCIP pointer */
5777  SCIP_CONSHDLR* conshdlr, /**< constraint handler */
5778  int nconss, /**< number of constraints */
5779  SCIP_CONS** conss, /**< indicator constraints */
5780  SCIP_SOL* sol, /**< solution to be enforced (NULL for LP solution) */
5781  SCIP_RESULT* result /**< result */
5782  )
5783 {
5784  SCIP_CONSHDLRDATA* conshdlrdata;
5785  SCIP_CONSDATA* consdata;
5786  SCIP_NODE* node1;
5787  SCIP_NODE* node2;
5789  SCIP_Real maxWeight;
5790  SCIP_VAR** vars;
5791  int nvars;
5792  int c;
5793 
5794  assert( scip != NULL );
5795  assert( conshdlr != NULL );
5796  assert( conss != NULL );
5797  assert( result != NULL );
5798 
5799  maxWeight = -SCIP_REAL_MAX;
5800  branchCons = NULL;
5801 
5802  SCIPdebugMsg(scip, "Enforcing SOS1 constraints <%s>.\n", SCIPconshdlrGetName(conshdlr) );
5803  *result = SCIP_FEASIBLE;
5804 
5805  /* get constraint handler data */
5806  conshdlrdata = SCIPconshdlrGetData(conshdlr);
5807  assert( conshdlrdata != NULL );
5808 
5809  /* check each constraint */
5810  for (c = 0; c < nconss; ++c)
5811  {
5812  SCIP_CONS* cons;
5813  SCIP_Bool cutoff;
5814  SCIP_Real weight;
5815  int ngen;
5816  int cnt;
5817  int j;
5818 
5819  cons = conss[c];
5820  assert( cons != NULL );
5821  consdata = SCIPconsGetData(cons);
5822  assert( consdata != NULL );
5823 
5824  ngen = 0;
5825  cnt = 0;
5826  nvars = consdata->nvars;
5827  vars = consdata->vars;
5828 
5829  /* do nothing if there are not enough variables - this is usually eliminated by preprocessing */
5830  if ( nvars < 2 )
5831  continue;
5832 
5833  /* first perform propagation (it might happen that standard propagation is turned off) */
5834  SCIP_CALL( propConsSOS1(scip, cons, consdata, &cutoff, &ngen) );
5835  SCIPdebugMsg(scip, "propagating <%s> in enforcing (cutoff: %u, domain reductions: %d).\n", SCIPconsGetName(cons), cutoff, ngen);
5836  if ( cutoff )
5837  {
5838  *result = SCIP_CUTOFF;
5839  return SCIP_OKAY;
5840  }
5841  if ( ngen > 0 )
5842  {
5843  *result = SCIP_REDUCEDDOM;
5844  return SCIP_OKAY;
5845  }
5846  assert( ngen == 0 );
5847 
5848  /* check constraint */
5849  weight = 0.0;
5850  for (j = 0; j < nvars; ++j)
5851  {
5852  SCIP_Real val = REALABS(SCIPgetSolVal(scip, sol, vars[j]));
5853 
5854  if ( ! SCIPisFeasZero(scip, val) )
5855  {
5856  if ( conshdlrdata->branchnonzeros )
5857  weight += 1.0;
5858  else
5859  {
5860  if ( conshdlrdata->branchweight )
5861  {
5862  /* choose maximum nonzero-variable weight */
5863  if ( consdata->weights[j] > weight )
5864  weight = consdata->weights[j];
5865  }
5866  else
5867  weight += val;
5868  }
5869  ++cnt;
5870  }
5871  }
5872  /* if constraint is violated */
5873  if ( cnt > 1 && weight > maxWeight )
5874  {
5875  maxWeight = weight;
5876  branchCons = cons;
5877  }
5878  }
5879 
5880  /* if all constraints are feasible */
5881  if ( branchCons == NULL )
5882  {
5883  SCIPdebugMsg(scip, "All SOS1 constraints are feasible.\n");
5884  return SCIP_OKAY;
5885  }
5886 
5887  /* if we should leave branching decision to branching rules */
5888  if ( ! conshdlrdata->branchsos )
5889  {
5890  int j;
5891 
5892  consdata = SCIPconsGetData(branchCons);
5893  for (j = 0; j < consdata->nvars; ++j)
5894  {
5895  if ( ! SCIPvarIsBinary(consdata->vars[j]) )
5896  break;
5897  }
5898 
5899  if ( j == consdata->nvars )
5900  {
5901  *result = SCIP_INFEASIBLE;
5902  return SCIP_OKAY;
5903  }
5904  else
5905  {
5906  SCIPerrorMessage("Incompatible parameter setting: branchsos can only be set to false if all SOS1 variables are binary.\n");
5907  return SCIP_PARAMETERWRONGVAL;
5908  }
5909  }
5910 
5911  /* otherwise create branches */
5912  SCIPdebugMsg(scip, "Branching on constraint <%s> (weight: %f).\n", SCIPconsGetName(branchCons), maxWeight);
5913  consdata = SCIPconsGetData(branchCons);
5914  assert( consdata != NULL );
5915  nvars = consdata->nvars;
5916  vars = consdata->vars;
5917 
5918  if ( nvars == 2 )
5919  {
5920  SCIP_Bool infeasible;
5921 
5922  /* constraint is infeasible: */
5923  assert( ! SCIPisFeasZero(scip, SCIPgetSolVal(scip, sol, vars[0])) && ! SCIPisFeasZero(scip, SCIPgetSolVal(scip, sol, vars[1])) );
5924 
5925  /* create branches */
5926  SCIPdebugMsg(scip, "Creating two branches.\n");
5927 
5928  SCIP_CALL( SCIPcreateChild(scip, &node1, SCIPcalcNodeselPriority(scip, vars[0], SCIP_BRANCHDIR_DOWNWARDS, 0.0), SCIPcalcChildEstimate(scip, vars[0], 0.0) ) );
5929  SCIP_CALL( fixVariableZeroNode(scip, vars[0], node1, &infeasible) );
5930  assert( ! infeasible );
5931 
5932  SCIP_CALL( SCIPcreateChild(scip, &node2, SCIPcalcNodeselPriority(scip, vars[1], SCIP_BRANCHDIR_DOWNWARDS, 0.0), SCIPcalcChildEstimate(scip, vars[1], 0.0) ) );
5933  SCIP_CALL( fixVariableZeroNode(scip, vars[1], node2, &infeasible) );
5934  assert( ! infeasible );
5935  }
5936  else
5937  {
5938  SCIP_Bool infeasible;
5939  SCIP_Real weight1;
5940  SCIP_Real weight2;
5941  SCIP_Real nodeselest;
5942  SCIP_Real objest;
5943  SCIP_Real w;
5944  int j;
5945  int ind;
5946  int cnt;
5947 
5948  cnt = 0;
5949 
5950  weight1 = 0.0;
5951  weight2 = 0.0;
5952 
5953  /* compute weight */
5954  for (j = 0; j < nvars; ++j)
5955  {
5956  SCIP_Real val = REALABS(SCIPgetSolVal(scip, sol, vars[j]));
5957  weight1 += val * (SCIP_Real) j;
5958  weight2 += val;
5959 
5960  if ( ! SCIPisFeasZero(scip, val) )
5961  ++cnt;
5962  }
5963 
5964  assert( cnt >= 2 );
5965  assert(