Scippy

SCIP

Solving Constraint Integer Programs

cons_symresack.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-2019 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file cons_symresack.c
17  * @brief constraint handler for symresack constraints
18  * @author Christopher Hojny
19  *
20  * The type of constraints of this constraint handler is described in cons_symresack.h.
21  *
22  * The details of the method implemented here are described in the following papers:
23  *
24  * Fundamental Domains for Integer Programs with Symmetries@n
25  * Eric J. Friedman,@n
26  * Combinatorial Optimization, volume 4616 of LNCS, 146-153 (2007)
27  *
28  * This paper describes an inequality to handle symmetries of a single permutation. This
29  * so-called FD-inequality is the basic for the propagation routine of our implementation.
30  *
31  * Polytopes Associated with Symmetry Handling@n
32  * Christopher Hojny and Marc E. Pfetsch,@n
33  * (2017), preprint available at http://www.optimization-online.org/DB_HTML/2017/01/5835.html
34  *
35  * This paper describes an almost linear time separation routine for so-called cove
36  * inequalities of symresacks. In our implementation, however, we use a separation routine with
37  * quadratic worst case running time.
38  *
39  * Packing, Partitioning, and Covering Symresacks@n
40  * Christopher Hojny,@n
41  * (2017), preprint available at http://www.optimization-online.org/DB_HTML/2017/05/5990.html
42  *
43  * This paper introduces linearly many inequalities with ternary coefficients that suffice to
44  * characterize the binary points contained in a packing and partitioning symresack completely.
45  */
46 
47 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
48 
49 #include "blockmemshell/memory.h"
50 #include "scip/cons_orbisack.h"
51 #include "scip/cons_setppc.h"
52 #include "scip/cons_symresack.h"
53 #include "scip/pub_cons.h"
54 #include "scip/pub_message.h"
55 #include "scip/pub_var.h"
56 #include "scip/scip_branch.h"
57 #include "scip/scip_conflict.h"
58 #include "scip/scip_cons.h"
59 #include "scip/scip_cut.h"
60 #include "scip/scip_general.h"
61 #include "scip/scip_lp.h"
62 #include "scip/scip_mem.h"
63 #include "scip/scip_message.h"
64 #include "scip/scip_numerics.h"
65 #include "scip/scip_param.h"
66 #include "scip/scip_prob.h"
67 #include "scip/scip_sol.h"
68 #include "scip/scip_var.h"
69 #include <string.h>
70 
71 /* constraint handler properties */
72 #define CONSHDLR_NAME "symresack"
73 #define CONSHDLR_DESC "symmetry breaking constraint handler relying on symresacks"
74 #define CONSHDLR_SEPAPRIORITY +40100 /**< priority of the constraint handler for separation */
75 #define CONSHDLR_ENFOPRIORITY -1005200 /**< priority of the constraint handler for constraint enforcing */
76 #define CONSHDLR_CHECKPRIORITY -1005200 /**< priority of the constraint handler for checking feasibility */
77 #define CONSHDLR_SEPAFREQ 5 /**< frequency for separating cuts; zero means to separate only in the root node */
78 #define CONSHDLR_PROPFREQ 5 /**< frequency for propagating domains; zero means only preprocessing propagation */
79 #define CONSHDLR_EAGERFREQ -1 /**< frequency for using all instead of only the useful constraints in separation,
80  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
81 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
82 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
83 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
84 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
85 
86 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
87 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE
88 
89 #define DEFAULT_PPSYMRESACK TRUE /**< whether we allow upgrading to packing/partitioning symresacks */
90 #define DEFAULT_CHECKALWAYSFEAS TRUE /**< whether check routine returns always SCIP_FEASIBLE */
91 
92 /* macros for getting bounds of pseudo solutions in propagation */
93 #define ISFIXED0(x) (SCIPvarGetUbLocal(x) < 0.5 ? TRUE : FALSE)
94 #define ISFIXED1(x) (SCIPvarGetLbLocal(x) > 0.5 ? TRUE : FALSE)
95 
96 
97 /*
98  * Data structures
99  */
100 
101 /** constraint handler data */
102 struct SCIP_ConshdlrData
103 {
104  SCIP_Bool checkppsymresack; /**< whether we allow upgrading to packing/partitioning symresacks */
105  SCIP_Bool checkalwaysfeas; /**< whether check routine returns always SCIP_FEASIBLE */
106  int maxnvars; /**< maximal number of variables in a symresack constraint */
107 };
108 
109 
110 /** constraint data for symresack constraints */
111 struct SCIP_ConsData
112 {
113  SCIP_VAR** vars; /**< variables */
114  int nvars; /**< number of variables */
115  int* perm; /**< permutation associated to the symresack */
116  int* invperm; /**< inverse permutation */
117  SCIP_Bool ppupgrade; /**< whether constraint is upgraded to packing/partitioning symresack */
118 #ifdef SCIP_DEBUG
119  int debugcnt; /**< counter to store number of added cover inequalities */
120 #endif
121 
122  /* data for upgraded symresack constraints */
123  int ncycles; /**< number of cycles in permutation */
124  int** cycledecomposition; /**< cycle decomposition */
125 };
126 
127 
128 /*
129  * Local methods
130  */
131 
132 /** frees a symresack constraint data */
133 static
134 SCIP_RETCODE consdataFree(
135  SCIP* scip, /**< SCIP data structure */
136  SCIP_CONSDATA** consdata /**< pointer to symresack constraint data */
137  )
138 {
139  int nvars;
140  int i;
141 
142  assert( consdata != NULL );
143  assert( *consdata != NULL );
144 
145  nvars = (*consdata)->nvars;
146 
147  if ( nvars == 0 )
148  {
149  SCIPfreeBlockMemory(scip, consdata);
150 
151  return SCIP_OKAY;
152  }
153 
154  if ( (*consdata)->ppupgrade )
155  {
156  for (i = 0; i < (*consdata)->ncycles; ++i)
157  {
158  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->cycledecomposition[i]), nvars + 1);
159  }
160  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->cycledecomposition), (*consdata)->ncycles);
161  }
162 
163  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->invperm), nvars);
164  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->perm), nvars);
165 
166  for (i = 0; i < nvars; ++i)
167  {
168  SCIP_CALL( SCIPreleaseVar(scip, &(*consdata)->vars[i]) );
169  }
170  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vars), nvars);
171 
172  SCIPfreeBlockMemory(scip, consdata);
173 
174  return SCIP_OKAY;
175 }
176 
177 
178 /** check whether constraint can be upgraded to packing/partitioning symresack */
179 static
180 SCIP_RETCODE packingUpgrade(
181  SCIP* scip, /**< SCIP data structure */
182  SCIP_CONSDATA** consdata, /**< pointer to store constraint data */
183  int* perm, /**< permutation */
184  SCIP_VAR** vars, /**< variables affected by permutation */
185  int nvars, /**< length of permutation */
186  SCIP_Bool* upgrade /**< pointer to store whether upgrade was successful */
187  )
188 {
189  SCIP_Bool* covered;
190  SCIP_Bool descent;
191  SCIP_CONSHDLR* setppcconshdlr;
192  SCIP_CONS** setppcconss;
193  SCIP_VAR* var;
194  SCIP_Bool terminated = FALSE;
195  int** cycledecomposition;
196  int* indicesincycle;
197  int nsetppcconss;
198  int curcycle;
199  int maxcyclelength;
200  int ncycles = 0;
201  int c;
202  int i;
203  int j;
204 
205  assert( scip != NULL );
206  assert( perm != NULL );
207  assert( vars != NULL );
208  assert( nvars > 0 );
209  assert( upgrade != NULL );
210 
211  *upgrade = FALSE;
212 
213  SCIP_CALL( SCIPallocBufferArray(scip, &covered, nvars) );
214 
215  for (i = 0; i < nvars; ++i)
216  covered[i] = FALSE;
217 
218  /* check wether permutation is monotone */
219  for (i = 0; i < nvars; ++i)
220  {
221  /* skip checked indices */
222  if ( covered[i] )
223  continue;
224 
225  ++ncycles;
226  j = i;
227  descent = FALSE;
228 
229  do
230  {
231  covered[j] = TRUE;
232 
233  if ( perm[j] < j )
234  {
235  if ( ! descent )
236  descent = TRUE;
237  else
238  break;
239  }
240 
241  j = perm[j];
242  }
243  while ( j != i );
244 
245  /* if cycle is not monotone */
246  if ( j != i )
247  {
248  SCIPfreeBufferArray(scip, &covered);
249 
250  return SCIP_OKAY;
251  }
252  }
253  assert( ncycles <= nvars / 2 );
254 
255  /* each cycle is monotone; check for packing/partitioning type */
256  for (i = 0; i < nvars; ++i)
257  covered[i] = FALSE;
258 
259  /* compute cycle decomposition: row i stores in entry 0 the length of the cycle,
260  * the remaining entries are the coordinates in the cycle */
261  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &cycledecomposition, ncycles) );
262  for (i = 0; i < ncycles; ++i)
263  {
264  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &cycledecomposition[i], nvars + 1) );
265  }
266 
267  curcycle = 0;
268  maxcyclelength = 0;
269  for (i = 0; i < nvars; ++i)
270  {
271  int cyclelength = 0;
272 
273  /* skip checked indices */
274  if ( covered[i] )
275  continue;
276 
277  j = i;
278  do
279  {
280  covered[j] = TRUE;
281  cycledecomposition[curcycle][++cyclelength] = j;
282  j = perm[j];
283  }
284  while ( j != i );
285 
286  cycledecomposition[curcycle][0] = cyclelength;
287  ++curcycle;
288 
289  if ( maxcyclelength < cyclelength )
290  maxcyclelength = cyclelength;
291  }
292 
293  /* permutation can be upgraded -> check whether the symresack is of packing/partitioning type */
294  setppcconshdlr = SCIPfindConshdlr(scip, "setppc");
295  if ( setppcconshdlr == NULL )
296  {
297  SCIPerrorMessage("Setppc constraint handler not found.\n");
298  return SCIP_PLUGINNOTFOUND;
299  }
300  setppcconss = SCIPconshdlrGetConss(setppcconshdlr);
301  nsetppcconss = SCIPconshdlrGetNConss(setppcconshdlr);
302 
303  /* Check whether each cycle of the symresack is contained in a set packing/partitioning constraint.
304  * To this end, we have to guarantee that all affected variables are not negated since permutations
305  * are given w.r.t. original variables. */
306  *upgrade = TRUE;
307 
308  SCIP_CALL( SCIPallocBufferArray(scip, &indicesincycle, maxcyclelength) );
309 
310  for (i = 0; i < ncycles && *upgrade && ! terminated; ++i)
311  {
312  int cyclelength;
313 
314  /* get indices of variables in current cycle */
315  for (j = 0; j < cycledecomposition[i][0]; ++ j)
316  {
317  var = vars[cycledecomposition[i][j + 1]];
318 
319  if ( SCIPvarIsNegated(var) )
320  {
321  terminated = TRUE;
322  break;
323  }
324 
325  indicesincycle[j] = SCIPvarGetProbindex(var);
326  }
327 
328  cyclelength = cycledecomposition[i][0];
329 
330  /* iterate over constraints
331  *
332  * @todo Improve the check by sorting the constraints in the setppcconss array
333  * by type and number of contained variables. */
334  for (c = 0; c < nsetppcconss; ++c)
335  {
336  int nsetppcvars;
337  SCIP_VAR** setppcvars;
338  int varidx;
339  int nfound = 0;
340  int k;
341 
342  /* check type */
343  if ( SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_COVERING )
344  continue;
345  assert( SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_PARTITIONING || SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_PACKING );
346 
347  /* get set packing/partitioning variables */
348  nsetppcvars = SCIPgetNVarsSetppc(scip, setppcconss[c]);
349  assert( nsetppcvars > 0 );
350 
351  setppcvars = SCIPgetVarsSetppc(scip, setppcconss[c]);
352  assert( setppcvars != NULL );
353 
354  /* check whether all variables of the cycle are contained in setppc constraint */
355  for (j = 0; j < nsetppcvars && nfound < cyclelength; ++j)
356  {
357  var = setppcvars[j];
358 
359  if ( SCIPvarIsNegated(var) )
360  continue;
361 
362  varidx = SCIPvarGetProbindex(var);
363 
364  for (k = 0; k < cyclelength; ++k)
365  {
366  if ( varidx == indicesincycle[k] )
367  {
368  ++nfound;
369  break;
370  }
371  }
372  }
373  assert( nfound <= cyclelength );
374 
375  if ( nfound == cyclelength )
376  break;
377  }
378 
379  /* row is not contained in a set packing/partitioning constraint */
380  if ( c >= nsetppcconss )
381  *upgrade = FALSE;
382  }
383 
384  if ( *upgrade )
385  {
386  (*consdata)->ncycles = ncycles;
387  (*consdata)->cycledecomposition = cycledecomposition;
388 
389  SCIPfreeBufferArray(scip, &indicesincycle);
390  SCIPfreeBufferArray(scip, &covered);
391  }
392  else
393  {
394  SCIPfreeBufferArray(scip, &indicesincycle);
395  SCIPfreeBufferArray(scip, &covered);
396  for (i = 0; i < ncycles; ++i)
397  {
398  SCIPfreeBlockMemoryArray(scip, &cycledecomposition[i], nvars + 1);
399  }
400  SCIPfreeBlockMemoryArray(scip, &cycledecomposition, ncycles);
401  }
402 
403  return SCIP_OKAY;
404 }
405 
406 
407 /** creates symresack constraint data
408  *
409  * If the input data contain non-binary variables of fixed
410  * points, we delete these variables in a preprocessing step.
411  */
412 static
413 SCIP_RETCODE consdataCreate(
414  SCIP* scip, /**< SCIP data structure */
415  SCIP_CONSDATA** consdata, /**< pointer to store constraint data */
416  SCIP_VAR*const* inputvars, /**< input variables of the constraint handler */
417  int inputnvars, /**< input number of variables of the constraint handler*/
418  int* inputperm /**< input permutation of the constraint handler */
419  )
420 {
421  SCIP_CONSHDLRDATA* conshdlrdata;
422  SCIP_CONSHDLR* conshdlr;
423  SCIP_VAR** vars;
424  SCIP_Bool upgrade;
425  int* indexcorrection;
426  int* invperm;
427  int* perm;
428  int naffectedvariables;
429  int i;
430  int j = 0;
431 
432  assert( consdata != NULL );
433 
434  SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
435 
436 #ifdef SCI_DEBUG
437  consdata->debugcnt = 0;
438 #endif
439 
440  /* count the number of binary variables which are affected by the permutation */
441  SCIP_CALL( SCIPallocBufferArray(scip, &indexcorrection, inputnvars) );
442  indexcorrection[0] = -1;
443  for (i = 0; i < inputnvars; ++i)
444  {
445  if ( inputperm[i] != i && SCIPvarIsBinary(inputvars[i]) )
446  {
447  if ( i == 0 )
448  indexcorrection[i] = 0;
449  else
450  indexcorrection[i] = indexcorrection[i - 1] + 1;
451  }
452  else
453  {
454  if ( i > 0 )
455  indexcorrection[i] = indexcorrection[i - 1];
456  }
457  }
458  naffectedvariables = indexcorrection[inputnvars - 1] + 1;
459 
460  (*consdata)->nvars = naffectedvariables;
461 
462  /* Stop if we detect that the permutation fixes each binary point. */
463  if ( naffectedvariables == 0 )
464  {
465  SCIPfreeBufferArrayNull(scip, &indexcorrection);
466  return SCIP_OKAY;
467  }
468 
469  /* remove fixed points from permutation representation */
470  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &vars, naffectedvariables) );
471  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &perm, naffectedvariables) );
472  for (i = 0; i < inputnvars; ++i)
473  {
474  if ( i == 0 )
475  {
476  if ( indexcorrection[i] > -1 )
477  {
478  vars[j] = inputvars[i];
479  perm[j++] = indexcorrection[inputperm[i]];
480  }
481  }
482  else
483  {
484  if ( indexcorrection[i] > indexcorrection[i - 1] )
485  {
486  vars[j] = inputvars[i];
487  perm[j++] = indexcorrection[inputperm[i]];
488  }
489  }
490  }
491  SCIPfreeBufferArrayNull(scip, &indexcorrection);
492 
493  (*consdata)->vars = vars;
494  (*consdata)->perm = perm;
495 
496  for (i = 0; i < naffectedvariables; ++i)
497  {
498  SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->vars[i]) );
499  }
500 
501  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &invperm, naffectedvariables) );
502  for (i = 0; i < naffectedvariables; ++i)
503  invperm[perm[i]] = i;
504  (*consdata)->invperm = invperm;
505 
506  /* check for upgrade to packing/partitioning symresacks*/
507  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
508  if ( conshdlr == NULL )
509  {
510  SCIPerrorMessage("symresack constraint handler not found\n");
511  return SCIP_PLUGINNOTFOUND;
512  }
513  conshdlrdata = SCIPconshdlrGetData(conshdlr);
514 
515  upgrade = FALSE;
516  if ( conshdlrdata->checkppsymresack )
517  {
518  SCIP_CALL( packingUpgrade(scip, consdata, perm, vars, naffectedvariables, &upgrade) );
519  }
520 
521  (*consdata)->ppupgrade = upgrade;
522 
523  /* get transformed variables, if we are in the transformed problem */
524  if ( SCIPisTransformed(scip) )
525  {
526  /* Make sure that all variables cannot be multiaggregated (cannot be handled by cons_symresack, since one cannot
527  * easily eliminate single variables from a symresack constraint. */
528  for (i = 0; i < naffectedvariables; ++i)
529  {
530  SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->vars[i], &(*consdata)->vars[i]) );
531  SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, (*consdata)->vars[i]) );
532  }
533  }
534 
535  return SCIP_OKAY;
536 }
537 
538 
539 /** generate initial LP cut
540  *
541  * We generate the ordering inequality for the pair \f$(1, \gamma^{-1}(1))\f$, i.e.,
542  * the inequality \f$-x_{1} + x_{\gamma^{-1}(1)} \leq 0\f$. This inequality is valid,
543  * because we guaranteed in a preprocessing step that all variables are binary.
544  *
545  * Furthermore, we add facet inequalities of packing/partitioning symresacks if
546  * we deal with packing/partitioning symresacks.
547  */
548 static
549 SCIP_RETCODE initLP(
550  SCIP* scip, /**< SCIP pointer */
551  SCIP_CONS* cons, /**< constraint */
552  SCIP_Bool* infeasible /**< pointer to store whether we detected infeasibility */
553  )
554 {
555  SCIP_CONSDATA* consdata;
556  SCIP_VAR** vars;
557  SCIP_ROW* row;
558  int nvars;
559 #ifdef SCIP_DEBUG
560  char name[SCIP_MAXSTRLEN];
561 #endif
562  int i;
563  int j;
564  int k;
565 
566  assert( scip != NULL );
567  assert( cons != NULL );
568  assert( infeasible != NULL );
569 
570  *infeasible = FALSE;
571 
572  consdata = SCIPconsGetData(cons);
573  assert( consdata != NULL );
574 
575  nvars = consdata->nvars;
576 
577  /* avoid stupid problems */
578  if ( nvars <= 1 )
579  return SCIP_OKAY;
580 
581  assert( consdata->vars != NULL );
582  vars = consdata->vars;
583 
584  /* there are no fixed points */
585  assert( consdata->invperm[0] != 0 );
586 
587  /* add ordering inequality */
588 #ifdef SCIP_DEBUG
589  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "symresack_init_%s", SCIPconsGetName(cons));
590  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(cons), name, -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
591 #else
592  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(cons), "", -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
593 #endif
594  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[0], -1.0) );
595  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[consdata->invperm[0]], 1.0) );
596 
597  SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
598 
599  SCIP_CALL( SCIPreleaseRow(scip, &row) );
600 
601  /* check whether we have a packing/partioning symresack */
602  if ( consdata->ppupgrade && ! *infeasible )
603  {
604  SCIP_VAR** varsincons;
605  SCIP_Real* coeffs;
606  int** cycledecomposition;
607  int ncycles;
608  int nvarsincons;
609  int nvarsincycle;
610  int firstelemincycle;
611 
612  ncycles = consdata->ncycles;
613  cycledecomposition = consdata->cycledecomposition;
614 
615  SCIP_CALL( SCIPallocBufferArray(scip, &varsincons, nvars) );
616  SCIP_CALL( SCIPallocBufferArray(scip, &coeffs, nvars) );
617 
618  coeffs[0] = 1.0;
619 
620  /* add packing/partitioning symresack constraints */
621  for (i = 0; i < ncycles; ++i)
622  {
623  assert( cycledecomposition[i][0] > 0 );
624 
625  nvarsincycle = cycledecomposition[i][0];
626  varsincons[0] = vars[cycledecomposition[i][nvarsincycle]];
627  firstelemincycle = cycledecomposition[i][1];
628 
629  assert( firstelemincycle == consdata->perm[cycledecomposition[i][nvarsincycle]] );
630 
631  nvarsincons = 1;
632 
633  /* add variables of other cycles to the constraint */
634  for (j = 0; j < i; ++j)
635  {
636  nvarsincycle = cycledecomposition[j][0];
637  for (k = 1; k <= nvarsincycle; ++k)
638  {
639  if ( cycledecomposition[j][k] < firstelemincycle )
640  {
641  varsincons[nvarsincons] = vars[cycledecomposition[j][k]];
642  coeffs[nvarsincons++] = -1.0;
643  }
644  else
645  continue;
646  }
647  }
648 
649 #ifdef SCIP_DEBUG
650  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "ppSymresack_%d_%s", i, SCIPconsGetName(cons));
651  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(cons), name, -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
652 #else
653  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(cons), "", -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
654 #endif
655  SCIP_CALL( SCIPaddVarsToRow(scip, row, nvarsincons, varsincons, coeffs) );
656 
657  SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
658  SCIP_CALL( SCIPreleaseRow(scip, &row) );
659 
660  if ( *infeasible )
661  break;
662  }
663 
664  SCIPfreeBufferArray(scip, &coeffs);
665  SCIPfreeBufferArray(scip, &varsincons);
666  }
667 
668  return SCIP_OKAY;
669 }
670 
671 
672 /** perform propagation of symresack constraint */
673 static
674 SCIP_RETCODE propVariables(
675  SCIP* scip, /**< SCIP pointer */
676  SCIP_CONS* cons, /**< constraint to be propagated */
677  SCIP_Bool* infeasible, /**< pointer to store whether it was detected that the node is infeasible */
678  int* ngen /**< pointer to store number of generated bound strengthenings */
679  )
680 {
681  SCIP_CONSDATA* consdata;
682  SCIP_VAR** vars;
683  int* invperm;
684  int nvars;
685  int i;
686 
687  assert( scip != NULL );
688  assert( cons != NULL );
689  assert( infeasible != NULL );
690  assert( ngen != NULL );
691 
692  SCIPdebugMsg(scip, "Propagating variables of constraint <%s>.\n", SCIPconsGetName(cons));
693 
694  *ngen = 0;
695  *infeasible = FALSE;
696 
697  /* get data of constraint */
698  consdata = SCIPconsGetData(cons);
699  assert( consdata != NULL );
700  assert( consdata->nvars > 0 );
701  nvars = consdata->nvars;
702 
703  /* avoid trivial problems */
704  if ( nvars < 2 )
705  return SCIP_OKAY;
706 
707  assert( consdata->vars != NULL );
708  assert( consdata->invperm != NULL );
709  vars = consdata->vars;
710  invperm = consdata->invperm;
711 
712  /* loop through all variables */
713  for (i = 0; i < nvars; ++i)
714  {
715  SCIP_VAR* var2;
716  SCIP_VAR* var;
717  int r;
718  SCIP_Bool tightened;
719 
720  /* there are no fixed points */
721  assert( invperm[i] != i );
722 
723  /* get variables of first and second column */
724  var = vars[i];
725  var2 = vars[invperm[i]];
726  assert( var != NULL );
727  assert( var2 != NULL );
728 
729  /* if first part of variable pair fixed to 0 and second part is fixed to 1 */
730  if ( ISFIXED0(var) && ISFIXED1(var2) )
731  {
732  SCIPdebugMsg(scip, "Check variable pair (%d,%d).\n", i, invperm[i]);
733 
734  SCIPdebugMsg(scip, " -> node infeasible (pair was fixed to (0,1) but there was no pair of type (1,0) before) ---> lexicographical order violated, infeasible.\n");
735 
736  /* perform conflict analysis */
737  if ( SCIPisConflictAnalysisApplicable(scip) )
738  {
739  SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) );
740 
741  for (r = 0; r <= i; ++r)
742  {
743  /* there are no fixed points */
744  assert( invperm[r] != r );
745 
746  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[r]) );
747  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[invperm[r]]) );
748  }
749 
750  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
751  }
752 
753  *infeasible = TRUE;
754  break;
755  }
756  /* if first part of the variable pair is fixed to 0 and the second part is free --> fix second part to 0 */
757  else if ( ISFIXED0(var) && ( ! ISFIXED0(var2) ) )
758  {
759  assert( SCIPvarGetUbLocal(var) < 0.5 );
760  assert( SCIPvarGetLbLocal(var2) < 0.5 );
761  assert( SCIPvarGetUbLocal(var2) > 0.5 );
762 
763  SCIPdebugMsg(scip, "Check variable pair (%d,%d).\n", i, invperm[i]);
764 
765  assert( SCIPvarGetLbLocal(var2) < 0.5 );
766  SCIP_CALL( SCIPinferVarUbCons(scip, var2, 0.0, cons, i, FALSE, infeasible, &tightened) ); /*lint !e713*/
767  assert( ! *infeasible );
768 
769  if ( tightened )
770  ++(*ngen);
771  }
772  /* if second part of the variable pair is fixed to 1 and the first part is free --> fix first part to 1 */
773  else if ( ( ! ISFIXED1(var) ) && ISFIXED1(var2) )
774  {
775  assert( SCIPvarGetLbLocal(var) < 0.5 );
776  assert( SCIPvarGetUbLocal(var) > 0.5 );
777  assert( SCIPvarGetLbLocal(var2) > 0.5 );
778 
779  SCIPdebugMsg(scip, "Check variable pair (%d,%d).\n", i, invperm[i]);
780 
781  assert( SCIPvarGetUbLocal(var) > 0.5 );
782  SCIP_CALL( SCIPinferVarLbCons(scip, var, 1.0, cons, i + nvars, FALSE, infeasible, &tightened) ); /*lint !e713*/
783  assert( ! *infeasible );
784 
785  if ( tightened )
786  ++(*ngen);
787  }
788  /* if solution is lexicographically maximal */
789  else if ( ISFIXED1(var) && ISFIXED0(var2) )
790  {
791  assert( SCIPvarGetLbLocal(var) > 0.5 );
792  assert( SCIPvarGetUbLocal(var2) < 0.5 );
793 
794  SCIPdebugMsg(scip, "Check variable pair (%d,%d).\n", i, invperm[i]);
795  SCIPdebugMsg(scip, " -> node is feasible (pair was fixed to (1,0) and every earlier pair is constant).\n");
796 
797  break;
798  }
799  /* cannot apply propagation */
800  else
801  break;
802  }
803 
804  return SCIP_OKAY;
805 }
806 
807 
808 /** add symresack cover inequality */
809 static
810 SCIP_RETCODE addSymresackInequality(
811  SCIP* scip, /**< SCIP pointer */
812  SCIP_CONS* cons, /**< constraint */
813  int nvars, /**< number of variables */
814  SCIP_VAR** vars, /**< variables */
815  int* coeffs, /**< coefficient vector of inequality to be added */
816  SCIP_Real rhs, /**< right-hand side of inequality to be added */
817  SCIP_Bool* infeasible /**< pointer to store whether we detected infeasibility */
818  )
819 {
820  SCIP_ROW* row;
821  int i;
822 #ifdef SCIP_DEBUG
823  SCIP_CONSDATA* consdata;
824  char name[SCIP_MAXSTRLEN];
825 #endif
826 
827  assert( scip != NULL );
828  assert( cons != NULL );
829  assert( nvars > 0 );
830  assert( vars != NULL );
831  assert( coeffs != NULL );
832  assert( infeasible != NULL );
833 
834  *infeasible = FALSE;
835 
836 #ifdef SCIP_DEBUG
837  consdata = SCIPconsGetData(cons);
838  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "symresack_cover_%s_%d", SCIPconsGetName(cons), consdata->debugcnt);
839  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(cons), name, -SCIPinfinity(scip), rhs, FALSE, FALSE, TRUE) );
840  consdata->debugcnt += 1;
841 #else
842  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, SCIPconsGetHdlr(cons), "", -SCIPinfinity(scip), rhs, FALSE, FALSE, TRUE) );
843 #endif
844  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
845 
846  for (i = 0; i < nvars; ++i)
847  {
848  if ( coeffs[i] == 1 || coeffs[i] == -1 )
849  {
850  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[i], (SCIP_Real) coeffs[i]) );
851  }
852  }
853  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
854  SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
855  SCIP_CALL( SCIPreleaseRow(scip, &row) );
856 
857  return SCIP_OKAY;
858 }
859 
860 
861 /** separate symresack cover inequalities
862  *
863  * We currently do NOT enter cuts into the pool.
864  */
865 static
866 SCIP_RETCODE separateSymresackCovers(
867  SCIP* scip, /**< SCIP pointer */
868  SCIP_CONS* cons, /**< constraint */
869  const SCIP_CONSDATA* consdata, /**< constraint data */
870  SCIP_Real* vals, /**< solution values of variables */
871  int* ngen, /**< pointer to store the number of separated covers */
872  SCIP_Bool* infeasible /**< pointer to store whether we detected infeasibility */
873  )
874 {
875  SCIP_Real constobjective;
876  SCIP_Real* sepaobjective;
877  SCIP_Real tmpsoluobj = 0.0;
878  SCIP_Real maxsoluobj = 0.0;
879  int* tmpsolu;
880  int* maxsolu;
881  int* invperm;
882  int* perm;
883  int nvars;
884  int crit;
885  int i;
886 
887  *infeasible = FALSE;
888  *ngen = 0;
889 
890  assert( scip != NULL );
891  assert( consdata != NULL );
892 
893  /* we don't have to take care of trivial constraints */
894  if ( consdata->nvars < 2 )
895  return SCIP_OKAY;
896 
897  assert( consdata->vars != NULL );
898  assert( consdata->perm != NULL );
899  assert( consdata->invperm != NULL );
900  assert( infeasible != NULL );
901  assert( ngen != NULL );
902 
903  nvars = consdata->nvars;
904  perm = consdata->perm;
905  invperm = consdata->invperm;
906 
907  /* initialize objective */
908  SCIP_CALL( SCIPallocBufferArray(scip, &sepaobjective, nvars) );
909 
910  constobjective = 1.0; /* constant part of separation objective */
911  for (i = 0; i < nvars; ++i)
912  {
913  if ( i < perm[i] )
914  {
915  sepaobjective[i] = vals[i];
916  constobjective -= vals[i];
917  }
918  else
919  sepaobjective[i] = vals[i] - 1.0;
920  }
921 
922  /* allocate memory for temporary and global solution */
923  SCIP_CALL( SCIPallocBufferArray(scip, &tmpsolu, nvars) );
924  SCIP_CALL( SCIPallocBufferArray(scip, &maxsolu, nvars) );
925 
926  /* start separation procedure by iterating over critical rows */
927  for (crit = 0; crit < nvars; ++crit)
928  {
929  /* there are no fixed points */
930  assert( perm[crit] != crit );
931 
932  /* initialize temporary solution */
933  for (i = 0; i < nvars; ++i)
934  tmpsolu[i] = 2;
935  tmpsoluobj = 0.0;
936 
937  /* perform fixings implied by the critical row */
938  tmpsolu[crit] = 0;
939  assert( invperm[crit] < nvars );
940 
941  tmpsolu[invperm[crit]] = 1;
942  tmpsoluobj += sepaobjective[invperm[crit]];
943 
944  /* perform 1-fixings */
945  i = invperm[crit];
946  while ( i < crit )
947  {
948  i = invperm[i];
949  tmpsolu[i] = 1;
950  tmpsoluobj += sepaobjective[i];
951  }
952 
953  /* row c cannot be critical */
954  if ( i == crit )
955  continue;
956 
957  assert( tmpsolu[crit] == 0 );
958 
959  /* perform 0-fixing */
960  i = perm[crit];
961  while ( i < crit )
962  {
963  tmpsolu[i] = 0;
964  i = perm[i];
965  }
966 
967  /* iterate over rows above the critical row */
968  for (i = 0; i < crit; ++i)
969  {
970  SCIP_Real objimpact = 0.0;
971  int j;
972 
973  /* skip already fixed entries */
974  if ( tmpsolu[i] != 2 )
975  continue;
976 
977  /* Check effect of fixing entry i to 1 and apply all implied fixing to other entries.
978  *
979  * Observe: Experiments indicate that entries are more often fixed to 1 than to 0.
980  * For this reason, we apply the 1-fixings directly. If it turns out that the 1-fixings
981  * have a negative impact on the objective, we undo these fixings afterwards and apply
982  * 0-fixings instead. */
983 
984  /* check fixings in invperm direction */
985  j = i;
986  do
987  {
988  assert( tmpsolu[j] == 2 );
989  tmpsolu[j] = 1;
990  objimpact += sepaobjective[j];
991  j = invperm[j];
992  }
993  while ( j < crit && j != i );
994 
995  /* if we do not detect a cycle */
996  if ( j != i )
997  {
998  /* fix entry j since this is not done in the above do-while loop */
999  assert( tmpsolu[j] == 2 );
1000  tmpsolu[j] = 1;
1001  objimpact += sepaobjective[j];
1002 
1003  /* check fixings in perm direction */
1004  j = perm[i];
1005  while ( j < crit )
1006  {
1007  assert( j != i );
1008  assert( tmpsolu[j] == 2 );
1009  tmpsolu[j] = 1;
1010  objimpact += sepaobjective[j];
1011  j = perm[j];
1012  }
1013 
1014  assert( j != crit );
1015  }
1016 
1017  /* if fixing entry i has a positive impact -> keep above fixings of entries to 1 */
1018  /* otherwise -> reset entries to 0 */
1019  if ( SCIPisEfficacious(scip, objimpact) )
1020  tmpsoluobj += objimpact;
1021  else
1022  {
1023  j = i;
1024  do
1025  {
1026  assert( tmpsolu[j] == 1 );
1027  tmpsolu[j] = 0;
1028  j = invperm[j];
1029  }
1030  while ( j < crit && j != i );
1031 
1032  /* if we do not detect a cycle */
1033  if ( j != i )
1034  {
1035  /* fix entry j since this is not done in the above do-while loop */
1036  assert( tmpsolu[j] == 1 );
1037  tmpsolu[j] = 0;
1038 
1039  /* check fixings in perm direction */
1040  j = perm[i];
1041  while ( j < crit )
1042  {
1043  assert( j != i );
1044  assert( tmpsolu[j] == 1 );
1045  tmpsolu[j] = 0;
1046  j = perm[j];
1047  }
1048 
1049  assert( j != crit );
1050  }
1051  }
1052  }
1053 
1054  /* iterate over unfixed entries below the critical row */
1055  for (i = crit + 1; i < nvars; ++i)
1056  {
1057  /* skip already fixed entries */
1058  if ( tmpsolu[i] != 2 )
1059  continue;
1060 
1061  if ( SCIPisEfficacious(scip, sepaobjective[i]) )
1062  {
1063  assert( tmpsolu[i] == 2 );
1064  tmpsolu[i] = 1;
1065  tmpsoluobj += sepaobjective[i];
1066  }
1067  else
1068  {
1069  assert( tmpsolu[i] == 2 );
1070  tmpsolu[i] = 0;
1071  }
1072  }
1073 
1074  /* check whether we have found a better solution which has positive separation objective*/
1075  if ( SCIPisEfficacious(scip, tmpsoluobj + constobjective - maxsoluobj) )
1076  {
1077  assert( SCIPisEfficacious(scip, tmpsoluobj + constobjective) );
1078  for (i = 0; i < nvars; ++i)
1079  maxsolu[i] = tmpsolu[i];
1080  maxsoluobj = tmpsoluobj + constobjective;
1081  }
1082  }
1083 
1084  /* Check whether the separation objective is positive, i.e., a violated cover was found. */
1085  if ( SCIPisEfficacious(scip, maxsoluobj) )
1086  {
1087  SCIP_Real rhs = -1.0;
1088  SCIP_Real lhs = 0.0;
1089 
1090  for (i = 0; i < nvars; ++i)
1091  {
1092  if ( i < perm[i] )
1093  {
1094  maxsolu[i] = maxsolu[i] - 1;
1095  lhs += vals[i] * maxsolu[i];
1096  }
1097  else
1098  {
1099  lhs += vals[i] * maxsolu[i];
1100  rhs += maxsolu[i];
1101  }
1102  }
1103 
1104  assert( SCIPisGT(scip, lhs, rhs) );
1105 
1106  /* add cover inequality */
1107  SCIP_CALL( addSymresackInequality(scip, cons, nvars, consdata->vars, maxsolu, rhs, infeasible) );
1108 
1109  if ( ! *infeasible )
1110  ++(*ngen);
1111  }
1112 
1113  SCIPfreeBufferArrayNull(scip, &maxsolu);
1114  SCIPfreeBufferArrayNull(scip, &tmpsolu);
1115  SCIPfreeBufferArrayNull(scip, &sepaobjective);
1116 
1117  return SCIP_OKAY;
1118 }
1119 
1120 
1121 static
1122 SCIP_RETCODE checkSymresackSolution(
1123  SCIP* scip, /**< SCIP pointer */
1124  SCIP_CONS* cons, /**< constrained for which we check the solution */
1125  SCIP_SOL* sol, /**< solution to be checked */
1126  SCIP_RESULT* result, /**< pointer to store whether we detected infeasibility */
1127  SCIP_Bool printreason /**< whether reason for infeasibility should be printed */
1128  )
1129 {
1130  SCIP_CONSDATA* consdata;
1131  SCIP_VAR** vars;
1132  int* invperm;
1133  int nvars;
1134  int i;
1135 
1136  assert( cons != NULL );
1137  consdata = SCIPconsGetData(cons);
1138  assert( consdata != NULL);
1139 
1140  /* we don't have to take care of trivial constraints */
1141  if ( consdata->nvars < 2 )
1142  return SCIP_OKAY;
1143 
1144  assert( consdata->vars != NULL );
1145  assert( consdata->invperm != NULL );
1146 
1147  SCIPdebugMsg(scip, "Check method for symresack constraint <%s> (%d rows) ...\n", SCIPconsGetName(cons), consdata->nvars);
1148 
1149  nvars = consdata->nvars;
1150  vars = consdata->vars;
1151  invperm = consdata->invperm;
1152 
1153  /* detect first non-constant pair of variables */
1154  for (i = 0; i < nvars; ++i)
1155  {
1156  SCIP_Real solval;
1157  int val1;
1158  int val2;
1159 
1160  /* there are no fixed points */
1161  assert( invperm[i] != i );
1162 
1163  /* get value of variable i and its inverse */
1164  solval = SCIPgetSolVal(scip, sol, vars[i]);
1165  assert( SCIPisFeasIntegral(scip, solval) );
1166  if ( solval > 0.5 )
1167  val1 = 1;
1168  else
1169  val1 = 0;
1170 
1171  solval = SCIPgetSolVal(scip, sol, vars[invperm[i]]);
1172  assert( SCIPisFeasIntegral(scip, solval) );
1173  if ( solval > 0.5 )
1174  val2 = 1;
1175  else
1176  val2 = 0;
1177 
1178  /* if we detected a constant pair */
1179  if ( val1 == val2 )
1180  continue;
1181  /* pair is (1,0) --> lexicographically maximal */
1182  else if ( val1 > val2 )
1183  break;
1184 
1185  /* pair is (0,1) --> solution is infeasible */
1186  assert( val2 > val1 );
1187  SCIPdebugMsg(scip, "Solution is infeasible.\n");
1188  *result = SCIP_INFEASIBLE;
1189 
1190  if ( printreason )
1191  SCIPinfoMessage(scip, NULL, "First non-constant pair (%d, %d) of variables has pattern (0,1).\n", i, invperm[i]);
1192 
1193  break;
1194  }
1195 
1196  return SCIP_OKAY;
1197 }
1198 
1199 
1200 /** Upgrade symresack constraints to orbisacks */
1201 static
1202 SCIP_RETCODE orbisackUpgrade(
1203  SCIP* scip, /**< SCIP pointer */
1204  SCIP_CONS** cons, /**< pointer to hold the created constraint */
1205  const char* name, /**< name of constraint */
1206  int* perm, /**< permutation */
1207  SCIP_VAR** inputvars, /**< permuted variables array */
1208  int nvars, /**< size of perm array */
1209  SCIP_Bool* upgrade, /**< whether constraint was upgraded */
1210  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
1211  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
1212  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
1213  * Usually set to TRUE. */
1214  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
1215  * TRUE for model constraints, FALSE for additional, redundant constraints. */
1216  SCIP_Bool check, /**< should the constraint be checked for feasibility?
1217  * TRUE for model constraints, FALSE for additional, redundant constraints. */
1218  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
1219  * Usually set to TRUE. */
1220  SCIP_Bool local, /**< is constraint only valid locally?
1221  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
1222  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
1223  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
1224  * adds coefficients to this constraint. */
1225  SCIP_Bool dynamic, /**< is constraint subject to aging?
1226  * Usually set to FALSE. Set to TRUE for own cuts which
1227  * are separated as constraints. */
1228  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
1229  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
1230  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
1231  * if it may be moved to a more global node?
1232  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
1233  )
1234 {
1235  SCIP_CONSHDLR* conshdlr;
1236  SCIP_VAR** vars1;
1237  SCIP_VAR** vars2;
1238  int nrows = 0;
1239  int i;
1240 
1241  assert( scip != NULL );
1242  assert( perm != NULL );
1243  assert( nvars > 0 );
1244  assert( inputvars != NULL );
1245  assert( upgrade != NULL );
1246 
1247  *upgrade = TRUE;
1248 
1249  /* check whether orbisack conshdlr is available */
1250  conshdlr = SCIPfindConshdlr(scip, "orbisack");
1251  if ( conshdlr == NULL )
1252  {
1253  *upgrade = FALSE;
1254  SCIPdebugMsg(scip, "Cannot check whether symresack constraint can be upgraded to orbisack constraint. ");
1255  SCIPdebugMsg(scip, "---> Orbisack constraint handler not found.\n");
1256 
1257  return SCIP_OKAY;
1258  }
1259 
1260  SCIP_CALL( SCIPallocBufferArray(scip, &vars1, nvars) );
1261  SCIP_CALL( SCIPallocBufferArray(scip, &vars2, nvars) );
1262 
1263  /* check whether permutation is a composition of 2-cycles */
1264  for (i = 0; i < nvars; ++i)
1265  {
1266  /* ignore non-binary variables */
1267  if ( ! SCIPvarIsBinary(inputvars[i]) )
1268  continue;
1269 
1270  if ( perm[perm[i]] != i )
1271  {
1272  *upgrade = FALSE;
1273  break;
1274  }
1275 
1276  if ( perm[i] > i )
1277  {
1278  vars1[nrows] = inputvars[i];
1279  vars2[nrows++] = inputvars[perm[i]];
1280 
1281  assert( nrows <= nvars );
1282  }
1283  }
1284 
1285  /* if permutation can be upgraded to an orbisack */
1286  if ( nrows == 0 )
1287  *upgrade = FALSE;
1288  else if ( *upgrade )
1289  {
1290  SCIP_CALL( SCIPcreateConsOrbisack(scip, cons, name, vars1, vars2, nrows, FALSE, FALSE,
1291  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
1292  }
1293 
1294  SCIPfreeBufferArray(scip, &vars2);
1295  SCIPfreeBufferArray(scip, &vars1);
1296 
1297  return SCIP_OKAY;
1298 }
1299 
1300 
1301 /** creates a symmetry breaking constraint
1302  *
1303  * Depending on the given permutation, either an orbisack or symresack constraint
1304  * is created.
1305  */
1306 SCIP_RETCODE SCIPcreateSymbreakCons(
1307  SCIP* scip, /**< SCIP data structure */
1308  SCIP_CONS** cons, /**< pointer to hold the created constraint */
1309  const char* name, /**< name of constraint */
1310  int* perm, /**< permutation */
1311  SCIP_VAR** vars, /**< variables */
1312  int nvars, /**< number of variables in vars array */
1313  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
1314  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
1315  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
1316  * Usually set to TRUE. */
1317  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
1318  * TRUE for model constraints, FALSE for additional, redundant constraints. */
1319  SCIP_Bool check, /**< should the constraint be checked for feasibility?
1320  * TRUE for model constraints, FALSE for additional, redundant constraints. */
1321  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
1322  * Usually set to TRUE. */
1323  SCIP_Bool local, /**< is constraint only valid locally?
1324  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
1325  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
1326  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
1327  * adds coefficients to this constraint. */
1328  SCIP_Bool dynamic, /**< is constraint subject to aging?
1329  * Usually set to FALSE. Set to TRUE for own cuts which
1330  * are separated as constraints. */
1331  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
1332  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
1333  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
1334  * if it may be moved to a more global node?
1335  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
1336  )
1337 {
1338  SCIP_Bool upgrade = FALSE;
1339 
1340  assert( scip != NULL );
1341  assert( cons != NULL );
1342  assert( perm != NULL );
1343  assert( vars != NULL );
1344  assert( nvars > 0 );
1345 
1346  SCIP_CALL( orbisackUpgrade(scip, cons, name, perm, vars, nvars, &upgrade,
1347  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
1348 
1349  if ( ! upgrade )
1350  {
1351  SCIP_CALL( SCIPcreateConsSymresack(scip, cons, name, perm, vars, nvars,
1352  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
1353  }
1354 
1355  return SCIP_OKAY;
1356 }
1357 
1358 
1359 /*--------------------------------------------------------------------------------------------
1360  *--------------------------------- SCIP functions -------------------------------------------
1361  *--------------------------------------------------------------------------------------------*/
1362 
1363 /** frees specific constraint data */
1364 static
1365 SCIP_DECL_CONSDELETE(consDeleteSymresack)
1366 { /*lint --e{715}*/
1367  assert( scip != NULL );
1368  assert( conshdlr != NULL );
1369  assert( consdata != NULL );
1370  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1371 
1372  SCIP_CALL( consdataFree(scip, consdata) );
1373 
1374  return SCIP_OKAY;
1375 }
1376 
1377 
1378 /** frees constraint handler */
1379 static
1380 SCIP_DECL_CONSFREE(consFreeSymresack)
1381 { /*lint --e{715}*/
1382  SCIP_CONSHDLRDATA* conshdlrdata;
1383 
1384  assert( scip != NULL );
1385  assert( conshdlr != NULL );
1386  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1387 
1388  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1389  assert( conshdlrdata != NULL );
1390 
1391  SCIPfreeBlockMemory(scip, &conshdlrdata);
1392 
1393  return SCIP_OKAY;
1394 }
1395 
1396 
1397 /** transforms constraint data into data belonging to the transformed problem */
1398 static
1399 SCIP_DECL_CONSTRANS(consTransSymresack)
1400 {
1401  SCIP_CONSDATA* sourcedata;
1402  SCIP_CONSDATA* consdata = NULL;
1403  int nvars;
1404  int i;
1405 
1406  assert( scip != NULL );
1407  assert( conshdlr != NULL );
1408  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1409  assert( sourcecons != NULL );
1410  assert( targetcons != NULL );
1411 
1412  SCIPdebugMsg(scip, "Transforming constraint.\n");
1413 
1414  /* get data of original constraint */
1415  sourcedata = SCIPconsGetData(sourcecons);
1416  assert( sourcedata != NULL);
1417  assert( sourcedata->nvars != 0 );
1418  assert( sourcedata->vars != NULL );
1419  assert( sourcedata->perm != NULL );
1420  assert( sourcedata->invperm != NULL );
1421 #ifndef NDEBUG
1422  if ( sourcedata->ppupgrade )
1423  {
1424  assert( sourcedata->ncycles != 0 );
1425  assert( sourcedata->cycledecomposition != NULL );
1426  for (i = 0; i < sourcedata->ncycles; ++i)
1427  {
1428  assert( sourcedata->cycledecomposition[i] != NULL );
1429  assert( sourcedata->cycledecomposition[i][0] != 0 );
1430  }
1431  }
1432 #endif
1433 
1434  /* create transformed constraint data (copy data where necessary) */
1435  nvars = sourcedata->nvars;
1436 
1437  SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) );
1438 
1439 #ifdef SCIP_DEBUG
1440  consdata->debugcnt = sourcedata->debugcnt;
1441 #endif
1442  consdata->nvars = nvars;
1443 
1444  if ( nvars > 0 )
1445  {
1446  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->vars, nvars) );
1447  SCIP_CALL( SCIPgetTransformedVars(scip, nvars, sourcedata->vars, consdata->vars) );
1448  for (i = 0; i < nvars; ++i)
1449  {
1450  SCIP_CALL( SCIPcaptureVar(scip, consdata->vars[i]) );
1451  }
1452 
1453  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->perm, sourcedata->perm, nvars) );
1454  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->invperm, sourcedata->invperm, nvars) );
1455 
1456  consdata->ppupgrade = sourcedata->ppupgrade;
1457 
1458  if ( sourcedata->ppupgrade )
1459  {
1460  consdata->ncycles = sourcedata->ncycles;
1461  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->cycledecomposition, sourcedata->cycledecomposition, sourcedata->ncycles) );
1462  for (i = 0; i < sourcedata->ncycles; ++i)
1463  {
1464  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->cycledecomposition[i], sourcedata->cycledecomposition[i], nvars + 1) ); /*lint !e866*/
1465  }
1466  }
1467  }
1468 
1469  /* create transformed constraint */
1470  SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, consdata,
1471  SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons),
1472  SCIPconsIsEnforced(sourcecons), SCIPconsIsChecked(sourcecons),
1473  SCIPconsIsPropagated(sourcecons), SCIPconsIsLocal(sourcecons),
1474  SCIPconsIsModifiable(sourcecons), SCIPconsIsDynamic(sourcecons),
1475  SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
1476 
1477  return SCIP_OKAY;
1478 }
1479 
1480 
1481 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
1482 static
1483 SCIP_DECL_CONSINITLP(consInitlpSymresack)
1484 {
1485  int c;
1486 
1487  assert( infeasible != NULL );
1488  *infeasible = FALSE;
1489 
1490  assert( scip != NULL );
1491  assert( conshdlr != NULL );
1492  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1493 
1494  /* loop through constraints */
1495  for (c = 0; c < nconss; ++c)
1496  {
1497  assert( conss[c] != NULL );
1498 
1499  SCIPdebugMsg(scip, "Generating initial symresack cut for constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1500 
1501  SCIP_CALL( initLP(scip, conss[c], infeasible) );
1502  if ( *infeasible )
1503  break;
1504  }
1505  SCIPdebugMsg(scip, "Generated initial symresack cuts.\n");
1506 
1507  return SCIP_OKAY;
1508 }
1509 
1510 
1511 /** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */
1512 static
1513 SCIP_DECL_CONSINITSOL(consInitsolSymresack)
1514 {
1515  SCIP_CONSHDLRDATA* conshdlrdata;
1516  int c;
1517 
1518  assert( scip != NULL );
1519  assert( conshdlr != NULL );
1520  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1521 
1522  /* determine maximum number of vars in a symresack constraint */
1523  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1524  assert( conshdlrdata != NULL );
1525 
1526  conshdlrdata->maxnvars = 0;
1527 
1528  /* loop through constraints */
1529  for (c = 0; c < nconss; ++c)
1530  {
1531  SCIP_CONSDATA* consdata;
1532 
1533  assert( conss[c] != NULL );
1534 
1535  consdata = SCIPconsGetData(conss[c]);
1536  assert( consdata != NULL );
1537 
1538  /* update conshdlrdata if necessary */
1539  if ( consdata->nvars > conshdlrdata->maxnvars )
1540  conshdlrdata->maxnvars = consdata->nvars;
1541  }
1542 
1543  return SCIP_OKAY;
1544 }
1545 
1546 
1547 /** separation method of constraint handler for LP solution */
1548 static
1549 SCIP_DECL_CONSSEPALP(consSepalpSymresack)
1550 { /*lint --e{715}*/
1551  SCIP_CONSHDLRDATA* conshdlrdata;
1552  SCIP_CONSDATA* consdata;
1553  SCIP_Real* vals;
1554  int maxnvars;
1555  int c;
1556 
1557  assert( scip != NULL );
1558  assert( conshdlr != NULL );
1559  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1560  assert( result != NULL );
1561 
1562  SCIPdebugMsg(scip, "Separation method for symresack constraints\n");
1563 
1564  *result = SCIP_DIDNOTRUN;
1565 
1566  /* if solution is not integer */
1567  if ( SCIPgetNLPBranchCands(scip) == 0 )
1568  return SCIP_OKAY;
1569 
1570  if ( nconss == 0 )
1571  return SCIP_OKAY;
1572 
1573  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1574  assert( conshdlrdata != NULL );
1575 
1576  maxnvars = conshdlrdata->maxnvars;
1577  assert( maxnvars > 0 );
1578 
1579  SCIP_CALL( SCIPallocBufferArray(scip, &vals, maxnvars) );
1580 
1581  /* loop through constraints */
1582  for (c = 0; c < nconss; ++c)
1583  {
1584  SCIP_Bool infeasible = FALSE;
1585  int ngen = 0;
1586 
1587  SCIPdebugMsg(scip, "Separating symresack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1588 
1589  /* get data of constraint */
1590  assert( conss[c] != NULL );
1591  consdata = SCIPconsGetData(conss[c]);
1592 
1593  /* get solution */
1594  assert( consdata->nvars <= maxnvars );
1595  SCIP_CALL( SCIPgetSolVals(scip, NULL, consdata->nvars, consdata->vars, vals) );
1596  SCIP_CALL( separateSymresackCovers(scip, conss[c], consdata, vals, &ngen, &infeasible) );
1597 
1598  if ( infeasible )
1599  {
1600  *result = SCIP_CUTOFF;
1601  SCIPfreeBufferArray(scip, &vals);
1602 
1603  return SCIP_OKAY;
1604  }
1605 
1606  if ( ngen > 0 )
1607  *result = SCIP_SEPARATED;
1608 
1609  if ( *result == SCIP_DIDNOTRUN )
1610  *result = SCIP_DIDNOTFIND;
1611  }
1612  SCIPfreeBufferArray(scip, &vals);
1613 
1614  return SCIP_OKAY;
1615 }
1616 
1617 
1618 /** separation method of constraint handler for arbitrary primal solution */
1619 static
1620 SCIP_DECL_CONSSEPASOL(consSepasolSymresack)
1621 { /*lint --e{715}*/
1622  SCIP_CONSHDLRDATA* conshdlrdata;
1623  SCIP_CONSDATA* consdata;
1624  SCIP_Real* vals;
1625  int maxnvars;
1626  int c;
1627 
1628  assert( scip != NULL );
1629  assert( conshdlr != NULL );
1630  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1631  assert( result != NULL );
1632 
1633  SCIPdebugMsg(scip, "Separation method for symresack constraints\n");
1634 
1635  *result = SCIP_DIDNOTRUN;
1636 
1637  if ( nconss == 0 )
1638  return SCIP_OKAY;
1639 
1640  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1641  assert( conshdlrdata != NULL );
1642 
1643  maxnvars = conshdlrdata->maxnvars;
1644  assert( maxnvars > 0 );
1645 
1646  SCIP_CALL( SCIPallocBufferArray(scip, &vals, maxnvars) );
1647 
1648  /* loop through constraints */
1649  for (c = 0; c < nconss; ++c)
1650  {
1651  SCIP_Bool infeasible = FALSE;
1652  int ngen = 0;
1653 
1654  SCIPdebugMsg(scip, "Separating symresack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1655 
1656  /* get data of constraint */
1657  assert( conss[c] != NULL );
1658  consdata = SCIPconsGetData(conss[c]);
1659 
1660  /* get solution */
1661  assert( consdata->nvars <= maxnvars );
1662  SCIP_CALL( SCIPgetSolVals(scip, sol, consdata->nvars, consdata->vars, vals) );
1663  SCIP_CALL( separateSymresackCovers(scip, conss[c], consdata, vals, &ngen, &infeasible) );
1664 
1665  if ( infeasible )
1666  {
1667  *result = SCIP_CUTOFF;
1668  SCIPfreeBufferArray(scip, &vals);
1669 
1670  return SCIP_OKAY;
1671  }
1672 
1673  if ( ngen > 0 )
1674  *result = SCIP_SEPARATED;
1675 
1676  if ( *result == SCIP_DIDNOTRUN )
1677  *result = SCIP_DIDNOTFIND;
1678  }
1679  SCIPfreeBufferArray(scip, &vals);
1680 
1681  return SCIP_OKAY;
1682 }
1683 
1684 
1685 /** constraint enforcing method of constraint handler for LP solutions.
1686  *
1687  * To check feasibility, we separate cover inequalities.
1688  *
1689  * @pre It is assumed that the solution is integral (this can be ensured by appropriate priorities).
1690  */
1691 static
1692 SCIP_DECL_CONSENFOLP(consEnfolpSymresack)
1693 { /*lint --e{715}*/
1694  SCIP_CONSDATA* consdata;
1695  int c;
1696 
1697  assert( scip != NULL );
1698  assert( conshdlr != NULL );
1699  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1700  assert( result != NULL );
1701 
1702  SCIPdebugMsg(scip, "Enforcing method for symresack constraints (lp solutions) ...\n");
1703 
1704  /* we have a negative priority, so we should come after the integrality conshdlr. */
1705  assert( SCIPgetNLPBranchCands(scip) == 0 );
1706 
1707  *result = SCIP_FEASIBLE;
1708 
1709  if ( nconss > 0 )
1710  {
1711  SCIP_CONSHDLRDATA* conshdlrdata;
1712  SCIP_Real* vals;
1713  int maxnvars;
1714 
1715  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1716  assert( conshdlrdata != NULL );
1717 
1718  maxnvars = conshdlrdata->maxnvars;
1719  assert( maxnvars > 0 );
1720 
1721  SCIP_CALL( SCIPallocBufferArray(scip, &vals, maxnvars) );
1722 
1723  /* loop through constraints */
1724  for (c = 0; c < nconss; ++c)
1725  {
1726  SCIP_Bool infeasible = FALSE;
1727  int ngen = 0;
1728 
1729  SCIPdebugMsg(scip, "Enforcing symresack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1730 
1731  /* get data of constraint */
1732  assert( conss[c] != NULL );
1733  consdata = SCIPconsGetData(conss[c]);
1734 
1735  /* get solution */
1736  assert( consdata->nvars <= maxnvars );
1737  SCIP_CALL( SCIPgetSolVals(scip, NULL, consdata->nvars, consdata->vars, vals) );
1738  SCIP_CALL( separateSymresackCovers(scip, conss[c], consdata, vals, &ngen, &infeasible) );
1739 
1740  if ( infeasible )
1741  {
1742  *result = SCIP_CUTOFF;
1743  SCIPfreeBufferArray(scip, &vals);
1744 
1745  return SCIP_OKAY;
1746  }
1747 
1748  /* SCIPdebugMsg(scip, "Generated symresack inequalities for <%s>: %d\n", SCIPconsGetName(conss[c]), ngen); */
1749 
1750  if ( ngen > 0 )
1751  *result = SCIP_SEPARATED;
1752  }
1753  SCIPfreeBufferArray(scip, &vals);
1754  }
1755 
1756  return SCIP_OKAY;
1757 }
1758 
1759 
1760 /** constraint enforcing method of constraint handler for pseudo solutions */
1761 static
1762 SCIP_DECL_CONSENFOPS(consEnfopsSymresack)
1763 { /*lint --e{715}*/
1764  int c;
1765 
1766  assert( scip != NULL );
1767  assert( conshdlr != NULL );
1768  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1769  assert( result != NULL );
1770 
1771  SCIPdebugMsg(scip, "Enforcing method for symresack constraints (pseudo solutions) ...\n");
1772 
1773  *result = SCIP_FEASIBLE;
1774 
1775  if ( objinfeasible || solinfeasible )
1776  return SCIP_OKAY;
1777 
1778  /* loop through constraints */
1779  for (c = 0; c < nconss; ++c)
1780  {
1781  SCIP_CALL( checkSymresackSolution(scip, conss[c], NULL, result, FALSE) );
1782 
1783  if ( *result == SCIP_INFEASIBLE )
1784  break;
1785  }
1786 
1787  return SCIP_OKAY;
1788 }
1789 
1790 
1791 /** constraint enforcing method of constraint handler for relaxation solutions
1792  *
1793  * To check feasibility, we separate cover inequalities.
1794  *
1795  */
1796 static
1797 SCIP_DECL_CONSENFORELAX(consEnforelaxSymresack)
1798 { /*lint --e{715}*/
1799  SCIP_CONSDATA* consdata;
1800  int c;
1801 
1802  assert( scip != NULL );
1803  assert( conshdlr != NULL );
1804  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1805  assert( result != NULL );
1806 
1807  SCIPdebugMsg(scip, "Enforcing method for symresack constraints (relaxation solutions) ...\n");
1808 
1809  /* we have a negative priority, so we should come after the integrality conshdlr. */
1810  assert( SCIPgetNLPBranchCands(scip) == 0 );
1811 
1812  *result = SCIP_FEASIBLE;
1813 
1814  if ( nconss > 0 )
1815  {
1816  SCIP_CONSHDLRDATA* conshdlrdata;
1817  SCIP_Real* vals;
1818  int maxnvars;
1819 
1820  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1821  assert( conshdlrdata != NULL );
1822 
1823  maxnvars = conshdlrdata->maxnvars;
1824  assert( maxnvars > 0 );
1825 
1826  SCIP_CALL( SCIPallocBufferArray(scip, &vals, maxnvars) );
1827 
1828  /* loop through constraints */
1829  for (c = 0; c < nconss; ++c)
1830  {
1831  SCIP_Bool infeasible = FALSE;
1832  int ngen = 0;
1833 
1834  SCIPdebugMsg(scip, "Enforcing symresack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1835 
1836  /* get data of constraint */
1837  assert( conss[c] != NULL );
1838  consdata = SCIPconsGetData(conss[c]);
1839 
1840  /* get solution */
1841  assert( consdata->nvars <= maxnvars );
1842  SCIP_CALL( SCIPgetSolVals(scip, sol, consdata->nvars, consdata->vars, vals) );
1843  SCIP_CALL( separateSymresackCovers(scip, conss[c], consdata, vals, &ngen, &infeasible) );
1844 
1845  if ( infeasible )
1846  {
1847  *result = SCIP_CUTOFF;
1848  SCIPfreeBufferArray(scip, &vals);
1849 
1850  return SCIP_OKAY;
1851  }
1852 
1853  if ( ngen > 0 )
1854  *result = SCIP_SEPARATED;
1855  }
1856  SCIPfreeBufferArray(scip, &vals);
1857  }
1858 
1859  return SCIP_OKAY;
1860 }
1861 
1862 
1863 /** feasibility check method of constraint handler for integral solutions */
1864 static
1865 SCIP_DECL_CONSCHECK(consCheckSymresack)
1866 { /*lint --e{715}*/
1867  int c;
1868  SCIP_CONSHDLRDATA* conshdlrdata;
1869 
1870  assert( scip != NULL );
1871  assert( conshdlr != NULL );
1872  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1873  assert( result != NULL );
1874 
1875  *result = SCIP_FEASIBLE;
1876 
1877  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1878  assert( conshdlrdata != NULL );
1879 
1880  if ( conshdlrdata->checkalwaysfeas )
1881  return SCIP_OKAY;
1882 
1883  /* loop through constraints */
1884  for (c = 0; c < nconss; ++c)
1885  {
1886  SCIP_CALL( checkSymresackSolution(scip, conss[c], sol, result, printreason) );
1887 
1888  if ( *result == SCIP_INFEASIBLE )
1889  break;
1890  }
1891 
1892  if ( *result == SCIP_FEASIBLE )
1893  SCIPdebugMsg(scip, "Solution is feasible.\n");
1894 
1895  return SCIP_OKAY;
1896 }
1897 
1898 
1899 /** domain propagation method of constraint handler */
1900 static
1901 SCIP_DECL_CONSPROP(consPropSymresack)
1902 { /*lint --e{715}*/
1903  int c;
1904  SCIP_Bool success = FALSE;
1905 
1906  assert( scip != NULL );
1907  assert( conshdlr != NULL );
1908  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1909  assert( result != NULL );
1910 
1911  *result = SCIP_DIDNOTRUN;
1912 
1913  SCIPdebugMsg(scip, "Propagation method of symresack constraint handler.\n");
1914 
1915  /* loop through constraints */
1916  for (c = 0; c < nconss; ++c)
1917  {
1918  SCIP_Bool infeasible = FALSE;
1919  int ngen = 0;
1920 
1921  assert( conss[c] != NULL );
1922 
1923  SCIP_CALL( propVariables(scip, conss[c], &infeasible, &ngen) );
1924 
1925  if ( infeasible )
1926  {
1927  *result = SCIP_CUTOFF;
1928  return SCIP_OKAY;
1929  }
1930 
1931  success = success || ( ngen > 0 );
1932 
1933  *result = SCIP_DIDNOTFIND;
1934  }
1935 
1936  if ( success )
1937  {
1938  *result = SCIP_REDUCEDDOM;
1939  return SCIP_OKAY;
1940  }
1941 
1942  return SCIP_OKAY;
1943 }
1944 
1945 
1946 /** presolving method of constraint handler */
1947 static
1948 SCIP_DECL_CONSPRESOL(consPresolSymresack)
1949 { /*lint --e{715}*/
1950  int c;
1951  SCIP_Bool success = FALSE;
1952  int oldndelconss;
1953 
1954  assert( scip != NULL );
1955  assert( conshdlr != NULL );
1956  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1957  assert( result != NULL );
1958 
1959  oldndelconss = *ndelconss;
1960 
1961  SCIPdebugMsg(scip, "Presolving method of symresack constraint handler. Propagating symresack inequalities.\n");
1962  *result = SCIP_DIDNOTRUN;
1963 
1964  /* loop through constraints */
1965  for (c = 0; c < nconss; ++c)
1966  {
1967  SCIP_Bool infeasible = FALSE;
1968  SCIP_CONSDATA* consdata;
1969  int ngen = 0;
1970 
1971  assert( conss[c] != NULL );
1972 
1973  consdata = SCIPconsGetData(conss[c]);
1974  assert( consdata != NULL );
1975 
1976  /* avoid trivial problems */
1977  if ( consdata->nvars == 0 )
1978  {
1979  SCIP_CALL( SCIPdelCons(scip, conss[c]) );
1980  (*ndelconss)++;
1981  }
1982  else
1983  {
1984  SCIP_CALL( propVariables(scip, conss[c], &infeasible, &ngen) );
1985  }
1986 
1987  if ( infeasible )
1988  {
1989  *result = SCIP_CUTOFF;
1990  break;
1991  }
1992 
1993  if ( ngen > 0 )
1994  {
1995  *nfixedvars += ngen;
1996  success = TRUE;
1997  }
1998 
1999  *result = SCIP_DIDNOTFIND;
2000  }
2001 
2002  if ( *ndelconss > oldndelconss || success )
2003  *result = SCIP_SUCCESS;
2004 
2005  return SCIP_OKAY;
2006 }
2007 
2008 
2009 /** Propagation resolution for conflict analysis */
2010 static
2011 SCIP_DECL_CONSRESPROP(consRespropSymresack)
2012 { /*lint --e{715}*/
2013  SCIP_CONSDATA* consdata;
2014  SCIP_VAR** vars;
2015  int* invperm;
2016  int nvars;
2017  int i;
2018 
2019  assert( scip != NULL );
2020  assert( conshdlr != NULL );
2021  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2022  assert( cons != NULL );
2023  assert( infervar != NULL );
2024  assert( bdchgidx != NULL );
2025  assert( result != NULL );
2026 
2027  SCIPdebugMsg(scip, "Propagation resolution method of symresack constraint handler.\n");
2028 
2029  *result = SCIP_DIDNOTFIND;
2030 
2031  consdata = SCIPconsGetData(cons);
2032  assert( consdata != NULL );
2033 
2034  /* we don't have to take care of trivial constraints */
2035  if ( consdata->nvars < 2 )
2036  return SCIP_OKAY;
2037 
2038  assert( consdata->vars != NULL );
2039  assert( consdata->invperm != NULL );
2040 
2041  vars = consdata->vars;
2042  nvars = consdata->nvars;
2043  invperm = consdata->invperm;
2044 
2045  assert( 0 <= inferinfo && inferinfo < (2 * nvars - 1) );
2046 
2047  /* if first part of variable pair was fixed to 0 */
2048  if ( inferinfo < nvars )
2049  {
2050  assert( vars[invperm[inferinfo]] == infervar );
2051  assert( SCIPvarGetUbAtIndex(vars[invperm[inferinfo]], bdchgidx, FALSE) > 0.5
2052  && SCIPvarGetUbAtIndex(vars[invperm[inferinfo]], bdchgidx, TRUE) < 0.5 );
2053 
2054  if ( SCIPvarGetUbAtIndex(vars[invperm[inferinfo]], bdchgidx, FALSE) > 0.5
2055  && SCIPvarGetUbAtIndex(vars[invperm[inferinfo]], bdchgidx, TRUE) < 0.5 )
2056  {
2057  SCIPdebugMsg(scip, " -> reason for setting x[%d] = 0 was fixing x[%d] to 0 ", invperm[inferinfo], inferinfo);
2058  SCIPdebugMsg(scip, "and each pair of binary variables before (%d,%d) which are not fixed points is constant.\n",
2059  inferinfo, invperm[inferinfo]);
2060 
2061  SCIP_CALL( SCIPaddConflictUb(scip, vars[inferinfo], bdchgidx) );
2062 
2063  for (i = 0; i < inferinfo; ++i)
2064  {
2065  /* there are no fixed points */
2066  assert( invperm[i] != i );
2067 
2068  SCIP_CALL( SCIPaddConflictUb(scip, vars[i], bdchgidx) );
2069  SCIP_CALL( SCIPaddConflictLb(scip, vars[i], bdchgidx) );
2070  SCIP_CALL( SCIPaddConflictUb(scip, vars[invperm[i]], bdchgidx) );
2071  SCIP_CALL( SCIPaddConflictLb(scip, vars[invperm[i]], bdchgidx) );
2072  }
2073  }
2074  }
2075  /* if second part of variable pair was fixed to 1 */
2076  else
2077  {
2078  int inferinfo2;
2079 
2080  inferinfo2 = inferinfo - nvars;
2081  assert( vars[inferinfo2] == infervar );
2082  assert( SCIPvarGetLbAtIndex(vars[inferinfo2], bdchgidx, FALSE) < 0.5
2083  && SCIPvarGetLbAtIndex(vars[inferinfo2], bdchgidx, TRUE) > 0.5 );
2084 
2085  if ( SCIPvarGetLbAtIndex(vars[inferinfo2], bdchgidx, FALSE) < 0.5
2086  && SCIPvarGetLbAtIndex(vars[inferinfo2], bdchgidx, TRUE) > 0.5 )
2087  {
2088  SCIPdebugMsg(scip, " -> reason for setting x[%d] = 1 was fixing x[%d] to 1 ", inferinfo2, invperm[inferinfo2]);
2089  SCIPdebugMsg(scip, "and each pair of binary variables before (%d,%d) which are not fixed points is constant.\n",
2090  inferinfo2, invperm[inferinfo2]);
2091 
2092  SCIP_CALL( SCIPaddConflictLb(scip, vars[invperm[inferinfo2]], bdchgidx) );
2093 
2094  for (i = 0; i < inferinfo2; ++i)
2095  {
2096  /* there are no fixed points */
2097  assert( invperm[i] != i );
2098 
2099  SCIP_CALL( SCIPaddConflictUb(scip, vars[i], bdchgidx) );
2100  SCIP_CALL( SCIPaddConflictLb(scip, vars[i], bdchgidx) );
2101  SCIP_CALL( SCIPaddConflictUb(scip, vars[invperm[i]], bdchgidx) );
2102  SCIP_CALL( SCIPaddConflictLb(scip, vars[invperm[i]], bdchgidx) );
2103  }
2104  }
2105  }
2106 
2107  *result = SCIP_SUCCESS;
2108 
2109  return SCIP_OKAY;
2110 }
2111 
2112 
2113 /** lock variables
2114  *
2115  * We assume we have only one global (void) constraint and lock all binary variables
2116  * which do not correspond to fixed points of the permutation.
2117  *
2118  * - Symresack constraints may get violated if the variables with a negative coefficient
2119  * in the FD inequality are rounded down, we therefor call
2120  * SCIPaddVarLocksType(..., nlockspos, nlocksneg).
2121  * - Symresack constraints may get violated if the variables with a positive coefficient
2122  * in the FD inequality are rounded up, we therefor call
2123  * SCIPaddVarLocksType(..., nlocksneg, nlockspo ).
2124  */
2125 static
2126 SCIP_DECL_CONSLOCK(consLockSymresack)
2127 { /*lint --e{715}*/
2128  SCIP_CONSDATA* consdata;
2129  SCIP_VAR** vars;
2130  int* perm;
2131  int nvars;
2132  int i;
2133 
2134  assert( scip != NULL );
2135  assert( conshdlr != NULL );
2136  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2137  assert( cons != NULL );
2138 
2139  SCIPdebugMsg(scip, "Locking method for symresack constraint handler.\n");
2140 
2141  /* get data of original constraint */
2142  consdata = SCIPconsGetData(cons);
2143  assert( consdata != NULL );
2144 
2145  /* we don't have to take care of trivial constraints */
2146  if ( consdata->nvars < 2 )
2147  return SCIP_OKAY;
2148 
2149  assert( consdata->vars != NULL );
2150  assert( consdata->perm != NULL );
2151 
2152  nvars = consdata->nvars;
2153  vars = consdata->vars;
2154  perm = consdata->perm;
2155 
2156  for (i = 0; i < nvars; ++i)
2157  {
2158  /* due to clean-up in consdataCreate, there are no fixed points */
2159  assert( perm[i] != i );
2160 
2161  if ( perm[i] > i )
2162  {
2163  SCIP_CALL( SCIPaddVarLocksType(scip, vars[i], locktype, nlockspos, nlocksneg) );
2164  }
2165  else
2166  {
2167  SCIP_CALL( SCIPaddVarLocksType(scip, vars[i], locktype, nlocksneg, nlockspos) );
2168  }
2169  }
2170 
2171  return SCIP_OKAY;
2172 }
2173 
2174 
2175 /** constraint display method of constraint handler
2176  *
2177  * The constraint handler should output a representation of the constraint into the given text file.
2178  */
2179 static
2180 SCIP_DECL_CONSPRINT(consPrintSymresack)
2181 { /*lint --e{715}*/
2182  SCIP_CONSDATA* consdata;
2183  SCIP_VAR** vars;
2184  SCIP_Bool* covered;
2185  int* perm;
2186  int nvars;
2187  int i;
2188  int j;
2189 
2190  assert( scip != NULL );
2191  assert( conshdlr != NULL );
2192  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2193  assert( cons != NULL );
2194 
2195  consdata = SCIPconsGetData(cons);
2196  assert( consdata != NULL );
2197 
2198  SCIPdebugMsg(scip, "Printing method for symresack constraint handler\n");
2199 
2200  /* we don't have to take care of trivial constraints */
2201  if ( consdata->nvars < 2 )
2202  {
2203  SCIPinfoMessage(scip, file, "symresack()");
2204  return SCIP_OKAY;
2205  }
2206 
2207  assert( consdata->vars != NULL );
2208  assert( consdata->perm != NULL );
2209 
2210  vars = consdata->vars;
2211  nvars = consdata->nvars;
2212  perm = consdata->perm;
2213 
2214  SCIP_CALL( SCIPallocBufferArray(scip, &covered, nvars) );
2215  for (i = 0; i < nvars; ++i)
2216  covered[i] = FALSE;
2217 
2218  if ( consdata->ppupgrade )
2219  SCIPinfoMessage(scip, file, "ppSymresack(");
2220  else
2221  SCIPinfoMessage(scip, file, "symresack(");
2222 
2223  for (i = 0; i < nvars; ++i)
2224  {
2225  if ( covered[i] )
2226  continue;
2227 
2228  /* print cycle of perm containing i */
2229  SCIPinfoMessage(scip, file, "[%s", SCIPvarGetName(vars[i]));
2230  covered[i] = TRUE;
2231  j = perm[i];
2232  while ( j != i )
2233  {
2234  SCIPinfoMessage(scip, file, ",%s", SCIPvarGetName(vars[j]));
2235  covered[j] = TRUE;
2236  j = perm[j];
2237  }
2238  SCIPinfoMessage(scip, file, "]");
2239  }
2240  SCIPinfoMessage(scip, file, ")");
2241 
2242  SCIPfreeBufferArray(scip, &covered);
2243 
2244  return SCIP_OKAY;
2245 }
2246 
2247 
2248 /** constraint method of constraint handler which returns the variables (if possible) */
2249 static
2250 SCIP_DECL_CONSGETVARS(consGetVarsSymresack)
2251 { /*lint --e{715}*/
2252  SCIP_CONSDATA* consdata;
2253 
2254  assert( cons != NULL );
2255  assert( success != NULL );
2256  assert( vars != NULL );
2257 
2258  consdata = SCIPconsGetData(cons);
2259  assert( consdata != NULL );
2260 
2261  if ( varssize < consdata->nvars )
2262  (*success) = FALSE;
2263  else
2264  {
2265  int cnt = 0;
2266  int i;
2267 
2268  for (i = 0; i < consdata->nvars; ++i)
2269  vars[cnt++] = consdata->vars[i];
2270  (*success) = TRUE;
2271  }
2272 
2273  return SCIP_OKAY;
2274 }
2275 
2276 
2277 /** constraint method of constraint handler which returns the number of variables (if possible) */
2278 static
2279 SCIP_DECL_CONSGETNVARS(consGetNVarsSymresack)
2280 { /*lint --e{715}*/
2281  SCIP_CONSDATA* consdata;
2282 
2283  assert( cons != NULL );
2284  assert( success != NULL );
2285  assert( nvars != NULL );
2286 
2287  consdata = SCIPconsGetData(cons);
2288  assert( consdata != NULL );
2289 
2290  (*nvars) = consdata->nvars;
2291  (*success) = TRUE;
2292 
2293  return SCIP_OKAY;
2294 }
2295 
2296 
2297 /** creates the handler for symresack constraints and includes it in SCIP */
2298 SCIP_RETCODE SCIPincludeConshdlrSymresack(
2299  SCIP* scip /**< SCIP data structure */
2300  )
2301 {
2302  SCIP_CONSHDLRDATA* conshdlrdata = NULL;
2303  SCIP_CONSHDLR* conshdlr;
2304 
2305  SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) );
2306 
2307  /* include constraint handler */
2308  SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC,
2309  CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY, CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS,
2310  consEnfolpSymresack, consEnfopsSymresack, consCheckSymresack, consLockSymresack,
2311  conshdlrdata) );
2312  assert( conshdlr != NULL );
2313 
2314  /* set non-fundamental callbacks via specific setter functions */
2315  SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxSymresack) );
2316  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeSymresack) );
2317  SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteSymresack) );
2318  SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsSymresack) );
2319  SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsSymresack) );
2320  SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolSymresack, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
2321  SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintSymresack) );
2322  SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropSymresack, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP, CONSHDLR_PROP_TIMING) );
2323  SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropSymresack) );
2324  SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpSymresack, consSepasolSymresack, CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, CONSHDLR_DELAYSEPA) );
2325  SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransSymresack) );
2326  SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpSymresack) );
2327  SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolSymresack) );
2328 
2329  /* whether we allow upgrading to packing/partioning symresack constraints*/
2330  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/ppsymresack",
2331  "Upgrade symresack constraints to packing/partioning symresacks?",
2332  &conshdlrdata->checkppsymresack, TRUE, DEFAULT_PPSYMRESACK, NULL, NULL) );
2333 
2334  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/checkalwaysfeas",
2335  "Whether check routine returns always SCIP_FEASIBLE.",
2336  &conshdlrdata->checkalwaysfeas, TRUE, DEFAULT_CHECKALWAYSFEAS, NULL, NULL) );
2337 
2338  return SCIP_OKAY;
2339 }
2340 
2341 
2342 /*
2343  * constraint specific interface methods
2344  */
2345 
2346 /** creates and captures a symresack constraint
2347  *
2348  * In a presolving step, we check whether the permutation acts only on binary points. Otherwise, we eliminate
2349  * the non-binary variables from the permutation.
2350  *
2351  * @note The constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons().
2352  */
2353 SCIP_RETCODE SCIPcreateConsSymresack(
2354  SCIP* scip, /**< SCIP data structure */
2355  SCIP_CONS** cons, /**< pointer to hold the created constraint */
2356  const char* name, /**< name of constraint */
2357  int* perm, /**< permutation */
2358  SCIP_VAR** vars, /**< variables */
2359  int nvars, /**< number of variables in vars array */
2360  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
2361  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
2362  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
2363  * Usually set to TRUE. */
2364  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
2365  * TRUE for model constraints, FALSE for additional, redundant constraints. */
2366  SCIP_Bool check, /**< should the constraint be checked for feasibility?
2367  * TRUE for model constraints, FALSE for additional, redundant constraints. */
2368  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
2369  * Usually set to TRUE. */
2370  SCIP_Bool local, /**< is constraint only valid locally?
2371  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
2372  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
2373  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
2374  * adds coefficients to this constraint. */
2375  SCIP_Bool dynamic, /**< is constraint subject to aging?
2376  * Usually set to FALSE. Set to TRUE for own cuts which
2377  * are separated as constraints. */
2378  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
2379  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
2380  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
2381  * if it may be moved to a more global node?
2382  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
2383  )
2384 {
2385  SCIP_CONSHDLR* conshdlr;
2386  SCIP_CONSDATA* consdata;
2387 
2388  assert( cons != NULL );
2389  assert( nvars > 0 );
2390 
2391  /* find the symresack constraint handler */
2392  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2393  if ( conshdlr == NULL )
2394  {
2395  SCIPerrorMessage("Symresack constraint handler not found.\n");
2396  return SCIP_PLUGINNOTFOUND;
2397  }
2398 
2399  /* create constraint data */
2400  SCIP_CALL( consdataCreate(scip, &consdata, vars, nvars, perm) );
2401 
2402  /* create constraint */
2403  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate && (! consdata->ppupgrade), enforce, check, propagate,
2404  local, modifiable, dynamic, removable, stickingatnode) );
2405 
2406  return SCIP_OKAY;
2407 }
2408 
2409 
2410 /** creates and captures a symresack constraint
2411  * in its most basic variant, i.e., with all constraint flags set to their default values
2412  *
2413  * In a presolving step, we remove all fixed points and cycles that act on non-binary variables of the permutation
2414  *
2415  * @note The constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons().
2416  */
2417 SCIP_RETCODE SCIPcreateConsBasicSymresack(
2418  SCIP* scip, /**< SCIP data structure */
2419  SCIP_CONS** cons, /**< pointer to hold the created constraint */
2420  const char* name, /**< name of constraint */
2421  int* perm, /**< permutation */
2422  SCIP_VAR** vars, /**< variables */
2423  int nvars /**< number of variables in vars array */
2424  )
2425 {
2426  SCIP_CALL( SCIPcreateConsSymresack(scip, cons, name, perm, vars, nvars,
2427  TRUE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
2428 
2429  return SCIP_OKAY;
2430 }
SCIP_RESULT
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:52
SCIPfreeBlockMemoryArray
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:116
SCIPsetConshdlrDelete
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:640
SCIP_DIDNOTRUN
Definition: type_result.h:33
CONSHDLR_ENFOPRIORITY
#define CONSHDLR_ENFOPRIORITY
Definition: cons_symresack.c:75
SCIP_INFEASIBLE
Definition: type_result.h:37
NULL
#define NULL
Definition: def.h:246
CONSHDLR_PRESOLTIMING
#define CONSHDLR_PRESOLTIMING
Definition: cons_symresack.c:88
SCIPcreateConsBasicSymresack
SCIP_RETCODE SCIPcreateConsBasicSymresack(SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **vars, int nvars)
Definition: cons_symresack.c:2418
SCIPallocBlockMemoryArray
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:99
SCIP_DECL_CONSPROP
static SCIP_DECL_CONSPROP(consPropSymresack)
Definition: cons_symresack.c:1902
SCIPcacheRowExtensions
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1547
scip_param.h
public methods for SCIP parameter handling
SCIPconsIsDynamic
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8335
SCIPsetConshdlrTrans
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip_cons.c:663
SCIPcreateSymbreakCons
SCIP_RETCODE SCIPcreateSymbreakCons(SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_symresack.c:1307
scip_mem.h
public methods for memory management
SCIP_CONFTYPE_PROPAGATION
Definition: type_conflict.h:50
SCIP_DECL_CONSFREE
static SCIP_DECL_CONSFREE(consFreeSymresack)
Definition: cons_symresack.c:1381
SCIPfindConshdlr
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:954
SCIPflushRowExtensions
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1570
SCIPgetNVarsSetppc
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9252
CONSHDLR_NAME
#define CONSHDLR_NAME
Definition: cons_symresack.c:72
consdataFree
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata)
Definition: cons_symresack.c:135
SCIPsetConshdlrGetVars
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars)))
Definition: scip_cons.c:893
SCIP_MAXSTRLEN
#define SCIP_MAXSTRLEN
Definition: def.h:267
scip_conflict.h
public methods for conflict handler plugins and conflict analysis
SCIPsetConshdlrEnforelax
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:385
SCIP_SUCCESS
Definition: type_result.h:49
SCIPdelCons
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2895
SCIPaddVarToRow
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1607
SCIP_SETPPCTYPE_COVERING
Definition: cons_setppc.h:80
SCIPvarGetLbLocal
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:17400
SCIP_DECL_CONSENFORELAX
static SCIP_DECL_CONSENFORELAX(consEnforelaxSymresack)
Definition: cons_symresack.c:1798
SCIPaddConflictBinvar
SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var)
Definition: scip_conflict.c:625
SCIP_Var
Definition: struct_var.h:198
SCIPgetTransformedVar
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1442
SCIPreleaseVar
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1251
SCIPvarIsBinary
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:16910
SCIPconshdlrGetConss
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4563
FALSE
#define FALSE
Definition: def.h:72
CONSHDLR_PROPFREQ
#define CONSHDLR_PROPFREQ
Definition: cons_symresack.c:78
SCIPincludeConshdlrBasic
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition: scip_cons.c:243
cons_orbisack.h
constraint handler for orbisack constraints
SCIPinfinity
SCIP_Real SCIPinfinity(SCIP *scip)
Definition: scip_numerics.c:581
SCIPsnprintf
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10253
TRUE
#define TRUE
Definition: def.h:71
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:53
SCIPaddConflictUb
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
Definition: scip_conflict.c:488
SCIPconsIsStickingAtNode
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition: cons.c:8355
checkSymresackSolution
static SCIP_RETCODE checkSymresackSolution(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_RESULT *result, SCIP_Bool printreason)
Definition: cons_symresack.c:1123
SCIPvarGetProbindex
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17037
CONSHDLR_MAXPREROUNDS
#define CONSHDLR_MAXPREROUNDS
Definition: cons_symresack.c:82
SCIP_SETPPCTYPE_PACKING
Definition: cons_setppc.h:79
pub_var.h
public methods for problem variables
SCIPinitConflictAnalysis
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
Definition: scip_conflict.c:392
SCIPfreeBlockMemory
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:114
SCIPsetConshdlrSepa
SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa)
Definition: scip_cons.c:297
SCIP_SEPARATED
Definition: type_result.h:40
SCIPfreeBufferArray
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:142
SCIP_DECL_CONSPRESOL
static SCIP_DECL_CONSPRESOL(consPresolSymresack)
Definition: cons_symresack.c:1949
cons_setppc.h
Constraint handler for the set partitioning / packing / covering constraints .
SCIPallocBlockMemory
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:97
SCIPisTransformed
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip_general.c:610
SCIPgetNLPBranchCands
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip_branch.c:417
DEFAULT_CHECKALWAYSFEAS
#define DEFAULT_CHECKALWAYSFEAS
Definition: cons_symresack.c:91
scip_var.h
public methods for SCIP variables
SCIP_DECL_CONSGETNVARS
static SCIP_DECL_CONSGETNVARS(consGetNVarsSymresack)
Definition: cons_symresack.c:2280
SCIPconsIsRemovable
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8345
SCIPsetConshdlrInitlp
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp)))
Definition: scip_cons.c:686
SCIPdebugMsg
#define SCIPdebugMsg
Definition: scip_message.h:88
SCIPgetTransformedVars
SCIP_RETCODE SCIPgetTransformedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
Definition: scip_var.c:1483
separateSymresackCovers
static SCIP_RETCODE separateSymresackCovers(SCIP *scip, SCIP_CONS *cons, const SCIP_CONSDATA *consdata, SCIP_Real *vals, int *ngen, SCIP_Bool *infeasible)
Definition: cons_symresack.c:867
SCIP_DECL_CONSINITLP
static SCIP_DECL_CONSINITLP(consInitlpSymresack)
Definition: cons_symresack.c:1484
SCIPinfoMessage
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:279
SCIPcreateCons
SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: scip_cons.c:1011
SCIPaddConflictLb
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
Definition: scip_conflict.c:421
SCIPcreateConsOrbisack
SCIP_RETCODE SCIPcreateConsOrbisack(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR *const *vars1, SCIP_VAR *const *vars2, int nrows, SCIP_Bool ispporbisack, SCIP_Bool isparttype, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_orbisack.c:2045
scip_numerics.h
public methods for numerical tolerances
SCIP_DECL_CONSPRINT
static SCIP_DECL_CONSPRINT(consPrintSymresack)
Definition: cons_symresack.c:2181
SCIP_Sol
Definition: struct_sol.h:63
CONSHDLR_NEEDSCONS
#define CONSHDLR_NEEDSCONS
Definition: cons_symresack.c:85
SCIPcreateConsSymresack
SCIP_RETCODE SCIPcreateConsSymresack(SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_symresack.c:2354
SCIPaddVarLocksType
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4198
SCIPisConflictAnalysisApplicable
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
Definition: scip_conflict.c:370
cons_symresack.h
constraint handler for symresack constraints
SCIPsetConshdlrInitsol
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol)))
Definition: scip_cons.c:506
SCIPduplicateBlockMemoryArray
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:111
pub_cons.h
public methods for managing constraints
addSymresackInequality
static SCIP_RETCODE addSymresackInequality(SCIP *scip, SCIP_CONS *cons, int nvars, SCIP_VAR **vars, int *coeffs, SCIP_Real rhs, SCIP_Bool *infeasible)
Definition: cons_symresack.c:811
SCIP_DECL_CONSSEPALP
static SCIP_DECL_CONSSEPALP(consSepalpSymresack)
Definition: cons_symresack.c:1550
CONSHDLR_EAGERFREQ
#define CONSHDLR_EAGERFREQ
Definition: cons_symresack.c:79
SCIP_DIDNOTFIND
Definition: type_result.h:35
SCIPincludeConshdlrSymresack
SCIP_RETCODE SCIPincludeConshdlrSymresack(SCIP *scip)
Definition: cons_symresack.c:2299
SCIP_Cons
Definition: struct_cons.h:37
SCIPerrorMessage
#define SCIPerrorMessage
Definition: pub_message.h:45
SCIPconshdlrGetName
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4191
SCIP_Conshdlr
Definition: struct_cons.h:117
SCIPgetSolVals
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1447
SCIP_DECL_CONSENFOLP
static SCIP_DECL_CONSENFOLP(consEnfolpSymresack)
Definition: cons_symresack.c:1693
SCIPfreeBufferArrayNull
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:143
SCIP_FEASIBLE
Definition: type_result.h:36
SCIPisEfficacious
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip_cut.c:179
SCIPvarGetUbAtIndex
SCIP_Real SCIPvarGetUbAtIndex(SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: var.c:16142
SCIPconsGetName
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8076
SCIP_DECL_CONSLOCK
static SCIP_DECL_CONSLOCK(consLockSymresack)
Definition: cons_symresack.c:2127
SCIPmarkDoNotMultaggrVar
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:8524
SCIPconsIsPropagated
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8295
SCIPvarGetName
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:16730
SCIPsetConshdlrFree
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:434
SCIPconshdlrGetData
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4211
SCIP_DECL_CONSDELETE
static SCIP_DECL_CONSDELETE(consDeleteSymresack)
Definition: cons_symresack.c:1366
CONSHDLR_SEPAFREQ
#define CONSHDLR_SEPAFREQ
Definition: cons_symresack.c:77
SCIP_OKAY
Definition: type_retcode.h:33
SCIP_SETPPCTYPE_PARTITIONING
Definition: cons_setppc.h:78
SCIP_CALL
#define SCIP_CALL(x)
Definition: def.h:358
SCIP_REDUCEDDOM
Definition: type_result.h:42
SCIPanalyzeConflictCons
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
Definition: scip_conflict.c:772
SCIPconsIsLocal
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:8315
SCIP_DECL_CONSSEPASOL
static SCIP_DECL_CONSSEPASOL(consSepasolSymresack)
Definition: cons_symresack.c:1621
SCIPaddRow
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:294
SCIPsetConshdlrResprop
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
Definition: scip_cons.c:709
SCIP_CONSDATA
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:51
SCIPconshdlrGetNConss
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4593
scip_cons.h
public methods for constraint handler plugins and constraints
packingUpgrade
static SCIP_RETCODE packingUpgrade(SCIP *scip, SCIP_CONSDATA **consdata, int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool *upgrade)
Definition: cons_symresack.c:181
SCIPallocBufferArray
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:130
SCIP_Bool
#define SCIP_Bool
Definition: def.h:69
SCIPcreateEmptyRowCons
SCIP_RETCODE SCIPcreateEmptyRowCons(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1336
SCIPgetTypeSetppc
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9294
SCIPvarGetLbAtIndex
SCIP_Real SCIPvarGetLbAtIndex(SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: var.c:16023
SCIP_Row
Definition: struct_lp.h:192
SCIPconsGetHdlr
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition: cons.c:8096
SCIP_DECL_CONSRESPROP
static SCIP_DECL_CONSRESPROP(consRespropSymresack)
Definition: cons_symresack.c:2012
scip_cut.h
public methods for cuts and aggregation rows
SCIPconsIsChecked
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8275
SCIPconsIsInitial
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8245
SCIP_DECL_CONSCHECK
static SCIP_DECL_CONSCHECK(consCheckSymresack)
Definition: cons_symresack.c:1866
initLP
static SCIP_RETCODE initLP(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible)
Definition: cons_symresack.c:550
SCIPsetConshdlrPrint
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint)))
Definition: scip_cons.c:847
SCIPinferVarLbCons
SCIP_RETCODE SCIPinferVarLbCons(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_CONS *infercons, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5415
consdataCreate
static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSDATA **consdata, SCIP_VAR *const *inputvars, int inputnvars, int *inputperm)
Definition: cons_symresack.c:414
scip_lp.h
public methods for the LP relaxation, rows and columns
SCIPgetVarsSetppc
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9273
CONSHDLR_DELAYSEPA
#define CONSHDLR_DELAYSEPA
Definition: cons_symresack.c:83
r
SCIP_Real * r
Definition: circlepacking.c:50
scip_branch.h
public methods for branching rule plugins and branching
SCIPreleaseRow
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1474
scip_general.h
general public methods
SCIPisGT
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition: scip_numerics.c:555
CONSHDLR_PROP_TIMING
#define CONSHDLR_PROP_TIMING
Definition: cons_symresack.c:87
scip_sol.h
public methods for solutions
SCIPconsGetData
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:8106
SCIPinferVarUbCons
SCIP_RETCODE SCIPinferVarUbCons(SCIP *scip, SCIP_VAR *var, SCIP_Real newbound, SCIP_CONS *infercons, int inferinfo, SCIP_Bool force, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5528
orbisackUpgrade
static SCIP_RETCODE orbisackUpgrade(SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **inputvars, int nvars, SCIP_Bool *upgrade, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: cons_symresack.c:1203
SCIP_DECL_CONSGETVARS
static SCIP_DECL_CONSGETVARS(consGetVarsSymresack)
Definition: cons_symresack.c:2251
DEFAULT_PPSYMRESACK
#define DEFAULT_PPSYMRESACK
Definition: cons_symresack.c:90
SCIPsetConshdlrPresol
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_cons.c:602
pub_message.h
public methods for message output
SCIPcaptureVar
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1217
SCIP_Real
#define SCIP_Real
Definition: def.h:157
SCIPconsIsModifiable
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8325
SCIPaddVarsToRow
SCIP_RETCODE SCIPaddVarsToRow(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_lp.c:1633
CONSHDLR_CHECKPRIORITY
#define CONSHDLR_CHECKPRIORITY
Definition: cons_symresack.c:76
SCIPsetConshdlrGetNVars
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars)))
Definition: scip_cons.c:916
scip_message.h
public methods for message handling
SCIPconsIsEnforced
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8265
SCIPconsIsSeparated
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8255
SCIP_PLUGINNOTFOUND
Definition: type_retcode.h:45
CONSHDLR_DESC
#define CONSHDLR_DESC
Definition: cons_symresack.c:73
SCIP_DECL_CONSENFOPS
static SCIP_DECL_CONSENFOPS(consEnfopsSymresack)
Definition: cons_symresack.c:1763
CONSHDLR_SEPAPRIORITY
#define CONSHDLR_SEPAPRIORITY
Definition: cons_symresack.c:74
SCIP_CONSHDLRDATA
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:50
SCIPvarGetUbLocal
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:17410
SCIPfreeBlockMemoryArrayNull
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:117
SCIPisFeasIntegral
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition: scip_numerics.c:952
CONSHDLR_DELAYPROP
#define CONSHDLR_DELAYPROP
Definition: cons_symresack.c:84
propVariables
static SCIP_RETCODE propVariables(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible, int *ngen)
Definition: cons_symresack.c:675
ISFIXED0
#define ISFIXED0(x)
Definition: cons_symresack.c:94
scip_prob.h
public methods for global and local (sub)problems
SCIP_DECL_CONSINITSOL
static SCIP_DECL_CONSINITSOL(consInitsolSymresack)
Definition: cons_symresack.c:1514
SCIP_DECL_CONSTRANS
static SCIP_DECL_CONSTRANS(consTransSymresack)
Definition: cons_symresack.c:1400
SCIPgetSolVal
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1410
ISFIXED1
#define ISFIXED1(x)
Definition: cons_symresack.c:95
SCIP_CUTOFF
Definition: type_result.h:39
SCIPaddBoolParam
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:129
SCIPvarIsNegated
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition: var.c:16885
SCIPsetConshdlrProp
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip_cons.c:343
memory.h
memory allocation routines