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