Scippy

SCIP

Solving Constraint Integer Programs

sepa_impliedbounds.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-2023 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 sepa_impliedbounds.c
26  * @ingroup DEFPLUGINS_SEPA
27  * @brief implied bounds separator
28  * @author Kati Wolter
29  * @author Tobias Achterberg
30  */
31 
32 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
33 
34 #include "blockmemshell/memory.h"
35 #include "scip/pub_implics.h"
36 #include "scip/pub_lp.h"
37 #include "scip/pub_message.h"
38 #include "scip/pub_misc.h"
39 #include "scip/pub_sepa.h"
40 #include "scip/pub_var.h"
41 #include "scip/scip_branch.h"
42 #include "scip/scip_cut.h"
43 #include "scip/scip_lp.h"
44 #include "scip/scip_mem.h"
45 #include "scip/scip_message.h"
46 #include "scip/scip_numerics.h"
47 #include "scip/scip_param.h"
48 #include "scip/scip_prob.h"
49 #include "scip/scip_sepa.h"
50 #include "scip/scip_sol.h"
51 #include "scip/scip_solvingstats.h"
52 #include "scip/scip_var.h"
54 #include <string.h>
55 
56 
57 #define SEPA_NAME "impliedbounds"
58 #define SEPA_DESC "implied bounds separator"
59 #define SEPA_PRIORITY -50
60 #define SEPA_FREQ 10
61 #define SEPA_MAXBOUNDDIST 1.0
62 #define SEPA_USESSUBSCIP FALSE /**< does the separator use a secondary SCIP instance? */
63 #define SEPA_DELAY FALSE /**< should separation method be delayed, if other separators found cuts? */
64 
65 #define RELCUTCOEFMAXRANGE 1.0 /**< maximal allowed range of cut coefficients, relative to 1/feastol */
66 #define DEFAULT_USETWOSIZECLIQUES TRUE /**< should violated inequalities for cliques with 2 variables be separated? */
67 
68 /** separator-specific data for the implied bounds separator */
69 struct SCIP_SepaData
70 {
71  SCIP_Bool usetwosizecliques; /**< should violated inequalities for cliques with 2 variables be separated? */
72 };
73 
74 /*
75  * Local methods
76  */
77 
78 /** adds given cut with two variables, if it is violated */
79 static
81  SCIP* scip, /**< SCIP data structure */
82  SCIP_SEPA* sepa, /**< separator */
83  SCIP_Real val1, /**< given coefficient of first variable */
84  SCIP_VAR* var1, /**< given first variable */
85  SCIP_Real solval1, /**< current LP solution value of first variable */
86  SCIP_Real val2, /**< given coefficient of second variable */
87  SCIP_VAR* var2, /**< given second variable */
88  SCIP_Real solval2, /**< current LP solution value of second variable */
89  SCIP_Real rhs, /**< given right hand side of the cut to add */
90  SCIP_Bool* cutoff, /**< whether a cutoff has been detected */
91  int* ncuts /**< pointer to update number of cuts added */
92  )
93 {
94  SCIP_Real activity;
95 
96  assert(ncuts != NULL);
97  assert(cutoff != NULL);
98  *cutoff = FALSE;
99 
100  /* calculate activity of cut */
101  activity = val1 * solval1 + val2 * solval2;
102  /*SCIPdebugMsg(scip, " -> %g<%s>[%g] + %g<%s>[%g] <= %g (act: %g)\n",
103  val1, SCIPvarGetName(var1), solval1, val2, SCIPvarGetName(var2), solval2, rhs, activity);*/
104 
105  /* check, if cut is violated */
106  if( SCIPisEfficacious(scip, activity - rhs) )
107  {
108  SCIP_ROW* cut;
109  char cutname[SCIP_MAXSTRLEN];
110 
111  /* create cut */
112  (void) SCIPsnprintf(cutname, SCIP_MAXSTRLEN, "implbd%" SCIP_LONGINT_FORMAT "_%d", SCIPgetNLPs(scip), *ncuts);
113  SCIP_CALL( SCIPcreateEmptyRowSepa(scip, &cut, sepa, cutname, -SCIPinfinity(scip), rhs, FALSE, FALSE, TRUE) );
114  SCIP_CALL( SCIPcacheRowExtensions(scip, cut) );
115  SCIP_CALL( SCIPaddVarToRow(scip, cut, var1, val1) );
116  SCIP_CALL( SCIPaddVarToRow(scip, cut, var2, val2) );
117  SCIP_CALL( SCIPflushRowExtensions(scip, cut) );
118  /* set cut rank: for implied bounds we always set to 1 */
119  SCIProwChgRank(cut, 1);
120 
121 #ifdef SCIP_DEBUG
122  SCIPdebugMsg(scip, " -> found cut (activity = %g): ", activity);
123  SCIP_CALL( SCIPprintRow(scip, cut, NULL) );
124 #endif
125 
126  SCIP_CALL( SCIPaddPoolCut(scip, cut) );
127  (*ncuts)++;
128 
129  /* release cut */
130  SCIP_CALL( SCIPreleaseRow(scip, &cut) );
131  }
132 
133  return SCIP_OKAY;
134 }
135 
136 /** searches and adds implied bound cuts that are violated by the given solution value array */
137 static
139  SCIP* scip, /**< SCIP data structure */
140  SCIP_SEPA* sepa, /**< separator */
141  SCIP_SOL* sol, /**< the solution that should be separated, or NULL for LP solution */
142  SCIP_Real* solvals, /**< array with solution values of all problem variables */
143  SCIP_VAR** fracvars, /**< array of fractional variables */
144  SCIP_Real* fracvals, /**< solution values of fractional variables */
145  int nfracs, /**< number of fractional variables */
146  SCIP_Bool* cutoff, /**< whether a cutoff has been detected */
147  int* ncuts /**< pointer to store the number of generated cuts */
148  )
149 {
150  SCIP_CLIQUE** cliques;
151  SCIP_SEPADATA* sepadata;
152  int ncliques;
153  int i;
154 
155  assert(solvals != NULL);
156  assert(fracvars != NULL || nfracs == 0);
157  assert(fracvals != NULL || nfracs == 0);
158  assert(cutoff != NULL);
159  assert(ncuts != NULL);
160 
161  *cutoff = FALSE;
162  *ncuts = 0;
163  sepadata = SCIPsepaGetData(sepa);
164  assert(sepadata != NULL);
165 
166  SCIPdebugMsg(scip, "searching for implied bound cuts\n");
167 
168  /* search binary variables for violated implications */
169  for( i = 0; i < nfracs; i++ )
170  {
171  SCIP_BOUNDTYPE* impltypes;
172  SCIP_Real* implbounds;
173  SCIP_VAR** implvars;
174  int nimpl;
175  int j;
176 
177  assert(fracvars != NULL);
178  assert(fracvals != NULL);
179 
180  /* only process binary variables */
181  if( SCIPvarGetType(fracvars[i]) != SCIP_VARTYPE_BINARY )
182  continue;
183 
184  /* get implications of x == 1 */
185  nimpl = SCIPvarGetNImpls(fracvars[i], TRUE);
186  implvars = SCIPvarGetImplVars(fracvars[i], TRUE);
187  impltypes = SCIPvarGetImplTypes(fracvars[i], TRUE);
188  implbounds = SCIPvarGetImplBounds(fracvars[i], TRUE);
189 
190  /*SCIPdebugMsg(scip, "%d implications for <%s>[%g] == 1\n", nimpl, SCIPvarGetName(fracvars[i]), fracvals[i]);*/
191 
192  /* try to add cuts for implications of x == 1
193  * x == 1 -> y <= p: y <= ub + x * (p - ub) <==> y + (ub - p) * x <= ub
194  * x == 1 -> y >= p: y >= lb + x * (p - lb) <==> -y + (p - lb) * x <= -lb
195  * with lb (ub) global lower (upper) bound of y
196  */
197  for( j = 0; j < nimpl; j++ )
198  {
199  SCIP_Real solval;
200 
201  assert(implvars != NULL);
202  assert(impltypes != NULL);
203  assert(implbounds != NULL);
204 
205  /* consider only implications with active implvar */
206  if( SCIPvarGetProbindex(implvars[j]) < 0 )
207  continue;
208 
209  solval = solvals[SCIPvarGetProbindex(implvars[j])];
210  if( impltypes[j] == SCIP_BOUNDTYPE_UPPER )
211  {
212  SCIP_Real ub;
213 
214  /* implication x == 1 -> y <= p */
215  ub = SCIPvarGetUbGlobal(implvars[j]);
216 
217  /* consider only nonredundant and numerical harmless implications */
218  if( SCIPisLE(scip, implbounds[j], ub) && (ub - implbounds[j]) * SCIPfeastol(scip) <= RELCUTCOEFMAXRANGE )
219  {
220  /* add cut if violated */
221  SCIP_CALL( addCut(scip, sepa, 1.0, implvars[j], solval, (ub - implbounds[j]), fracvars[i], fracvals[i],
222  ub, cutoff, ncuts) );
223  if ( *cutoff )
224  return SCIP_OKAY;
225  }
226  }
227  else
228  {
229  SCIP_Real lb;
230 
231  /* implication x == 1 -> y >= p */
232  lb = SCIPvarGetLbGlobal(implvars[j]);
233  assert(impltypes[j] == SCIP_BOUNDTYPE_LOWER);
234 
235  /* consider only nonredundant and numerical harmless implications */
236  if( SCIPisGE(scip, implbounds[j], lb) && (implbounds[j] - lb) * SCIPfeastol(scip) <= RELCUTCOEFMAXRANGE )
237  {
238  /* add cut if violated */
239  SCIP_CALL( addCut(scip, sepa, -1.0, implvars[j], solval, (implbounds[j] - lb), fracvars[i], fracvals[i],
240  -lb, cutoff, ncuts) );
241  if ( *cutoff )
242  return SCIP_OKAY;
243  }
244  }
245  }
246 
247  /* get implications of x == 0 */
248  nimpl = SCIPvarGetNImpls(fracvars[i], FALSE);
249  implvars = SCIPvarGetImplVars(fracvars[i], FALSE);
250  impltypes = SCIPvarGetImplTypes(fracvars[i], FALSE);
251  implbounds = SCIPvarGetImplBounds(fracvars[i], FALSE);
252 
253  /*SCIPdebugMsg(scip, "%d implications for <%s>[%g] == 0\n", nimpl, SCIPvarGetName(fracvars[i]), fracvals[i]);*/
254 
255  /* try to add cuts for implications of x == 0
256  * x == 0 -> y <= p: y <= p + x * (ub - p) <==> y + (p - ub) * x <= p
257  * x == 0 -> y >= p: y >= p + x * (lb - p) <==> -y + (lb - p) * x <= -p
258  * with lb (ub) global lower (upper) bound of y
259  */
260  for( j = 0; j < nimpl; j++ )
261  {
262  SCIP_Real solval;
263 
264  /* consider only implications with active implvar */
265  if( SCIPvarGetProbindex(implvars[j]) < 0 )
266  continue;
267 
268  solval = solvals[SCIPvarGetProbindex(implvars[j])];
269  if( impltypes[j] == SCIP_BOUNDTYPE_UPPER )
270  {
271  SCIP_Real ub;
272 
273  /* implication x == 0 -> y <= p */
274  ub = SCIPvarGetUbGlobal(implvars[j]);
275 
276  /* consider only nonredundant and numerical harmless implications */
277  if( SCIPisLE(scip, implbounds[j], ub) && (ub - implbounds[j]) * SCIPfeastol(scip) < RELCUTCOEFMAXRANGE )
278  {
279  /* add cut if violated */
280  SCIP_CALL( addCut(scip, sepa, 1.0, implvars[j], solval, (implbounds[j] - ub), fracvars[i], fracvals[i],
281  implbounds[j], cutoff, ncuts) );
282  if ( *cutoff )
283  return SCIP_OKAY;
284  }
285  }
286  else
287  {
288  SCIP_Real lb;
289 
290  /* implication x == 0 -> y >= p */
291  lb = SCIPvarGetLbGlobal(implvars[j]);
292  assert(impltypes[j] == SCIP_BOUNDTYPE_LOWER);
293 
294  /* consider only nonredundant and numerical harmless implications */
295  if( SCIPisGE(scip, implbounds[j], lb) && (implbounds[j] - lb) * SCIPfeastol(scip) < RELCUTCOEFMAXRANGE )
296  {
297  /* add cut if violated */
298  SCIP_CALL( addCut(scip, sepa, -1.0, implvars[j], solval, (lb - implbounds[j]), fracvars[i], fracvals[i],
299  -implbounds[j], cutoff, ncuts) );
300  if ( *cutoff )
301  return SCIP_OKAY;
302  }
303  }
304  }
305  }
306 
307  /* stop separation here if cliques should not be separated */
308  if( ! sepadata->usetwosizecliques )
309  return SCIP_OKAY;
310 
311  /* prepare clean clique data */
312  SCIP_CALL( SCIPcleanupCliques(scip, cutoff) );
313 
314  if( *cutoff )
315  return SCIP_OKAY;
316 
317  cliques = SCIPgetCliques(scip);
318  ncliques = SCIPgetNCliques(scip);
319 
320  /* loop over cliques of size 2 which are essentially implications and add cuts if they are violated */
321  for( i = 0; i < ncliques; ++i )
322  {
323  SCIP_CLIQUE* clique;
324  SCIP_VAR** clqvars;
325  SCIP_Bool* clqvals;
326  SCIP_Real rhs;
327 
328  clique = cliques[i];
329  /* only consider inequality cliques of size 2 */
330  if( SCIPcliqueGetNVars(clique) != 2 || SCIPcliqueIsEquation(clique) )
331  continue;
332 
333  /* get variables and values of the clique */
334  clqvars = SCIPcliqueGetVars(clique);
335  clqvals = SCIPcliqueGetValues(clique);
336 
337  /* clique variables should never be equal after clean up */
338  assert(clqvars[0] != clqvars[1]);
339 
340  /* calculate right hand side of clique inequality, which is initially 1 and decreased by 1 for every occurence of
341  * a negated variable in the clique
342  */
343  rhs = 1.0;
344  if( ! clqvals[0] )
345  rhs -= 1.0;
346  if( ! clqvals[1] )
347  rhs -= 1.0;
348 
349  /* Basic clique inequality is
350  *
351  * cx * x + (1-cx) (1-x) + cy * y + (1-cy) * (1-y) <= 1,
352  *
353  * where x and y are the two binary variables in the clique and cx and cy are their clique values, where a
354  * clique value of 0 means that the negation of the variable should be part of the inequality.
355  * Hence, exactly one of the two possible terms for x and y has a nonzero coefficient
356  */
357  SCIP_CALL( addCut(scip, sepa,
358  clqvals[0] ? 1.0 : -1.0, clqvars[0], SCIPgetSolVal(scip, sol, clqvars[0]),
359  clqvals[1] ? 1.0 : -1.0, clqvars[1], SCIPgetSolVal(scip, sol, clqvars[1]),
360  rhs, cutoff, ncuts) );
361 
362  /* terminate if cutoff was found */
363  if( *cutoff )
364  return SCIP_OKAY;
365  }
366 
367  return SCIP_OKAY;
368 }
369 
370 
371 /*
372  * Callback methods of separator
373  */
374 
375 /** copy method for separator plugins (called when SCIP copies plugins) */
376 static
377 SCIP_DECL_SEPACOPY(sepaCopyImpliedbounds)
378 { /*lint --e{715}*/
379  assert(scip != NULL);
380  assert(sepa != NULL);
381  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
382 
383  /* call inclusion method of constraint handler */
385 
386  return SCIP_OKAY;
387 }
388 
389 /** destructor of separator to free user data (called when SCIP is exiting) */
390 static
391 SCIP_DECL_SEPAFREE(sepaFreeImpliedbounds)
392 { /*lint --e{715}*/
393  SCIP_SEPADATA* sepadata;
394 
395  assert(scip != NULL);
396  assert(sepa != NULL);
397  assert(strcmp(SCIPsepaGetName(sepa), SEPA_NAME) == 0);
398 
399  /* get separation data and free it */
400  sepadata = SCIPsepaGetData(sepa);
401  assert(sepadata != NULL);
402  SCIPfreeBlockMemory(scip, &sepadata);
403 
404  /* reset data pointer to NULL */
405  SCIPsepaSetData(sepa, NULL);
406 
407  return SCIP_OKAY;
408 }
409 
410 
411 /** LP solution separation method of separator */
412 static
413 SCIP_DECL_SEPAEXECLP(sepaExeclpImpliedbounds)
414 { /*lint --e{715}*/
415  SCIP_VAR** vars;
416  SCIP_VAR** fracvars;
417  SCIP_Real* solvals;
418  SCIP_Real* fracvals;
419  SCIP_Bool cutoff;
420  int nvars;
421  int nbinvars;
422  int nfracs;
423  int ncuts;
424 
425  assert(sepa != NULL);
426  assert(scip != NULL);
427 
428  *result = SCIP_DIDNOTRUN;
429 
430  /* gets active problem variables */
431  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, NULL, NULL, NULL) );
432  if( nbinvars == 0 )
433  return SCIP_OKAY;
434 
435  /* get fractional problem variables */
436  /* todo try out also separating fractional implicit integer variables */
437  SCIP_CALL( SCIPgetLPBranchCands(scip, &fracvars, &fracvals, NULL, &nfracs, NULL, NULL) );
438  if( nfracs == 0 )
439  return SCIP_OKAY;
440 
441  /* get solution values for all variables */
442  SCIP_CALL( SCIPallocBufferArray(scip, &solvals, nvars) );
443  SCIP_CALL( SCIPgetVarSols(scip, nvars, vars, solvals) );
444 
445  /* call the cut separation */
446  SCIP_CALL( separateCuts(scip, sepa, NULL, solvals, fracvars, fracvals, nfracs, &cutoff, &ncuts) );
447 
448  /* adjust result code */
449  if ( cutoff )
450  *result = SCIP_CUTOFF;
451  else if ( ncuts > 0 )
452  *result = SCIP_SEPARATED;
453  else
454  *result = SCIP_DIDNOTFIND;
455 
456  /* free temporary memory */
457  SCIPfreeBufferArray(scip, &solvals);
458 
459  return SCIP_OKAY;
460 }
461 
462 
463 /** arbitrary primal solution separation method of separator */
464 static
465 SCIP_DECL_SEPAEXECSOL(sepaExecsolImpliedbounds)
466 { /*lint --e{715}*/
467  SCIP_VAR** vars;
468  SCIP_VAR** fracvars;
469  SCIP_Real* solvals;
470  SCIP_Real* fracvals;
471  SCIP_Bool cutoff;
472  int nvars;
473  int nbinvars;
474  int nfracs;
475  int ncuts;
476  int i;
477 
478  assert(sepa != NULL);
479  assert(scip != NULL);
480 
481  *result = SCIP_DIDNOTRUN;
482 
483  /* gets active problem variables */
484  SCIP_CALL( SCIPgetVarsData(scip, &vars, &nvars, &nbinvars, NULL, NULL, NULL) );
485  if( nbinvars == 0 )
486  return SCIP_OKAY;
487 
488  /* get solution values for all variables */
489  SCIP_CALL( SCIPallocBufferArray(scip, &solvals, nvars) );
490  SCIP_CALL( SCIPgetSolVals(scip, sol, nvars, vars, solvals) );
491 
492  /* get binary problem variables that are fractional in given solution */
493  SCIP_CALL( SCIPallocBufferArray(scip, &fracvars, nbinvars) );
494  SCIP_CALL( SCIPallocBufferArray(scip, &fracvals, nbinvars) );
495  nfracs = 0;
496  for( i = 0; i < nbinvars; ++i )
497  {
498  if( !SCIPisFeasIntegral(scip, solvals[i]) )
499  {
500  fracvars[nfracs] = vars[i];
501  fracvals[nfracs] = solvals[i];
502  nfracs++;
503  }
504  }
505 
506  /* call the cut separation */
507  ncuts = 0;
508  cutoff = FALSE;
509 
510  if( nfracs > 0 )
511  {
512  SCIP_CALL( separateCuts(scip, sepa, sol, solvals, fracvars, fracvals, nfracs, &cutoff, &ncuts) );
513  }
514 
515  /* adjust result code */
516  if ( cutoff )
517  *result = SCIP_CUTOFF;
518  else if ( ncuts > 0 )
519  *result = SCIP_SEPARATED;
520  else
521  *result = SCIP_DIDNOTFIND;
522 
523  /* free temporary memory */
524  SCIPfreeBufferArray(scip, &fracvals);
525  SCIPfreeBufferArray(scip, &fracvars);
526  SCIPfreeBufferArray(scip, &solvals);
527 
528  return SCIP_OKAY;
529 }
530 
531 
532 /*
533  * separator specific interface methods
534  */
535 
536 /** creates the impliedbounds separator and includes it in SCIP */
538  SCIP* scip /**< SCIP data structure */
539  )
540 {
541  SCIP_SEPADATA* sepadata;
542  SCIP_SEPA* sepa;
543 
544  /* create impliedbounds separator data */
545  SCIP_CALL( SCIPallocBlockMemory(scip, &sepadata) );
546  assert(sepadata != NULL);
547 
548  /* include separator */
551  sepaExeclpImpliedbounds, sepaExecsolImpliedbounds,
552  sepadata) );
553  assert(sepa != NULL);
554 
555  /* set non-NULL pointers to callback methods */
556  SCIP_CALL( SCIPsetSepaCopy(scip, sepa, sepaCopyImpliedbounds) );
557  SCIP_CALL( SCIPsetSepaFree(scip, sepa, sepaFreeImpliedbounds) );
558 
559  /* add separator parameters */
560  SCIP_CALL( SCIPaddBoolParam(scip, "separating/impliedbounds/usetwosizecliques",
561  "should violated inequalities for cliques with 2 variables be separated?",
562  &sepadata->usetwosizecliques, TRUE, DEFAULT_USETWOSIZECLIQUES, NULL, NULL) );
563 
564  return SCIP_OKAY;
565 }
SCIP_RETCODE SCIPgetLPBranchCands(SCIP *scip, SCIP_VAR ***lpcands, SCIP_Real **lpcandssol, SCIP_Real **lpcandsfrac, int *nlpcands, int *npriolpcands, int *nfracimplvars)
Definition: scip_branch.c:395
enum SCIP_BoundType SCIP_BOUNDTYPE
Definition: type_lp.h:59
static SCIP_DECL_SEPAEXECLP(sepaExeclpImpliedbounds)
SCIP_Real SCIPfeastol(SCIP *scip)
SCIP_VAR ** SCIPcliqueGetVars(SCIP_CLIQUE *clique)
Definition: implics.c:3380
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1635
public methods for SCIP parameter handling
public methods for memory management
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1658
static SCIP_DECL_SEPAFREE(sepaFreeImpliedbounds)
public methods for implications, variable bounds, and cliques
#define SEPA_MAXBOUNDDIST
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:17901
#define SCIP_MAXSTRLEN
Definition: def.h:302
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1701
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define SEPA_PRIORITY
SCIP_RETCODE SCIPgetVarsData(SCIP *scip, SCIP_VAR ***vars, int *nvars, int *nbinvars, int *nintvars, int *nimplvars, int *ncontvars)
Definition: scip_prob.c:1866
#define FALSE
Definition: def.h:96
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10788
#define SEPA_DELAY
#define TRUE
Definition: def.h:95
const char * SCIPsepaGetName(SCIP_SEPA *sepa)
Definition: sepa.c:743
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_Bool SCIPcliqueIsEquation(SCIP_CLIQUE *clique)
Definition: implics.c:3436
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17591
public methods for problem variables
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
static SCIP_RETCODE addCut(SCIP *scip, SCIP_SEPA *sepa, SCIP_Real val1, SCIP_VAR *var1, SCIP_Real solval1, SCIP_Real val2, SCIP_VAR *var2, SCIP_Real solval2, SCIP_Real rhs, SCIP_Bool *cutoff, int *ncuts)
#define SEPA_USESSUBSCIP
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
public methods for SCIP variables
SCIP_RETCODE SCIPsetSepaCopy(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPACOPY((*sepacopy)))
Definition: scip_sepa.c:151
#define SCIPdebugMsg
Definition: scip_message.h:78
public methods for separator plugins
#define DEFAULT_USETWOSIZECLIQUES
public methods for numerical tolerances
SCIP_SEPADATA * SCIPsepaGetData(SCIP_SEPA *sepa)
Definition: sepa.c:633
public methods for querying solving statistics
#define SEPA_FREQ
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:17911
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1398
SCIP_RETCODE SCIPincludeSepaImpliedbounds(SCIP *scip)
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip_cut.c:135
void SCIPsepaSetData(SCIP_SEPA *sepa, SCIP_SEPADATA *sepadata)
Definition: sepa.c:643
#define NULL
Definition: lpi_spx1.cpp:164
#define SCIP_CALL(x)
Definition: def.h:394
#define RELCUTCOEFMAXRANGE
static SCIP_DECL_SEPAEXECSOL(sepaExecsolImpliedbounds)
SCIP_RETCODE SCIPincludeSepaBasic(SCIP *scip, SCIP_SEPA **sepa, const char *name, const char *desc, int priority, int freq, SCIP_Real maxbounddist, SCIP_Bool usessubscip, SCIP_Bool delay, SCIP_DECL_SEPAEXECLP((*sepaexeclp)), SCIP_DECL_SEPAEXECSOL((*sepaexecsol)), SCIP_SEPADATA *sepadata)
Definition: scip_sepa.c:109
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
public data structures and miscellaneous methods
SCIP_BOUNDTYPE * SCIPvarGetImplTypes(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18211
#define SCIP_Bool
Definition: def.h:93
#define SEPA_DESC
int SCIPvarGetNImpls(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18179
SCIP_RETCODE SCIPaddPoolCut(SCIP *scip, SCIP_ROW *row)
Definition: scip_cut.c:361
SCIP_Bool * SCIPcliqueGetValues(SCIP_CLIQUE *clique)
Definition: implics.c:3392
public methods for LP management
SCIP_RETCODE SCIPcreateEmptyRowSepa(SCIP *scip, SCIP_ROW **row, SCIP_SEPA *sepa, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1453
public methods for cuts and aggregation rows
SCIP_Real * SCIPvarGetImplBounds(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18225
public methods for the LP relaxation, rows and columns
SCIP_VAR ** SCIPvarGetImplVars(SCIP_VAR *var, SCIP_Bool varfixing)
Definition: var.c:18196
SCIP_CLIQUE ** SCIPgetCliques(SCIP *scip)
Definition: scip_var.c:7629
implied bounds separator
public methods for branching rule plugins and branching
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1562
SCIP_RETCODE SCIPsetSepaFree(SCIP *scip, SCIP_SEPA *sepa, SCIP_DECL_SEPAFREE((*sepafree)))
Definition: scip_sepa.c:167
public methods for solutions
SCIP_RETCODE SCIPgetVarSols(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_var.c:2327
void SCIProwChgRank(SCIP_ROW *row, int rank)
Definition: lp.c:17534
public methods for message output
static SCIP_DECL_SEPACOPY(sepaCopyImpliedbounds)
int SCIPgetNCliques(SCIP *scip)
Definition: scip_var.c:7575
#define SCIP_Real
Definition: def.h:186
public methods for message handling
SCIP_RETCODE SCIPprintRow(SCIP *scip, SCIP_ROW *row, FILE *file)
Definition: scip_lp.c:2212
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17407
SCIP_Bool SCIPisLE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
int SCIPcliqueGetNVars(SCIP_CLIQUE *clique)
Definition: implics.c:3370
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
#define SEPA_NAME
public methods for separators
SCIP_RETCODE SCIPcleanupCliques(SCIP *scip, SCIP_Bool *infeasible)
Definition: scip_var.c:7532
SCIP_Longint SCIPgetNLPs(SCIP *scip)
public methods for global and local (sub)problems
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1361
struct SCIP_SepaData SCIP_SEPADATA
Definition: type_sepa.h:52
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
static SCIP_RETCODE separateCuts(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_Real *solvals, SCIP_VAR **fracvars, SCIP_Real *fracvals, int nfracs, SCIP_Bool *cutoff, int *ncuts)
memory allocation routines