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