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-2024 Zuse Institute Berlin (ZIB) */
7 /* */
8 /* Licensed under the Apache License, Version 2.0 (the "License"); */
9 /* you may not use this file except in compliance with the License. */
10 /* You may obtain a copy of the License at */
11 /* */
12 /* http://www.apache.org/licenses/LICENSE-2.0 */
13 /* */
14 /* Unless required by applicable law or agreed to in writing, software */
15 /* distributed under the License is distributed on an "AS IS" BASIS, */
16 /* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17 /* See the License for the specific language governing permissions and */
18 /* limitations under the License. */
19 /* */
20 /* You should have received a copy of the Apache-2.0 license */
21 /* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22 /* */
23 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24 
25 /**@file cons_symresack.c
26  * @ingroup DEFPLUGINS_CONS
27  * @brief constraint handler for symresack constraints
28  * @author Christopher Hojny
29  * @author Jasper van Doornmalen
30  *
31  * The type of constraints of this constraint handler is described in cons_symresack.h.
32  *
33  * The details of the method implemented here are described in the following papers:
34  *
35  * Fundamental Domains for Integer Programs with Symmetries@n
36  * Eric J. Friedman,@n
37  * Combinatorial Optimization, volume 4616 of LNCS, 146-153 (2007)
38  *
39  * This paper describes an inequality to handle symmetries of a single permutation. This
40  * so-called FD-inequality is the basic for the propagation routine of our implementation.
41  *
42  * Polytopes Associated with Symmetry Handling@n
43  * Christopher Hojny and Marc E. Pfetsch,@n
44  * Mathematical Programming 175, No. 1, 197-240, 2019
45  *
46  * This paper describes an almost linear time separation routine for so-called cover
47  * inequalities of symresacks. A slight modification of this algorithm allows for a linear
48  * running time, which is used in this implementation.
49  *
50  * Packing, Partitioning, and Covering Symresacks@n
51  * Christopher Hojny,@n
52  * (2020), available at https://doi.org/10.1016/j.dam.2020.03.002
53  * Discrete Applied Mathematics, volume 283, 689-717 (2020)
54  *
55  * This paper introduces linearly many inequalities with ternary coefficients that suffice to
56  * characterize the binary points contained in a packing and partitioning symresack completely.
57  */
58 
59 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
60 
61 #include "blockmemshell/memory.h"
62 #include "scip/cons_orbisack.h"
63 #include "scip/cons_setppc.h"
64 #include "scip/cons_symresack.h"
65 #include "scip/pub_cons.h"
66 #include "scip/pub_message.h"
67 #include "scip/pub_misc.h"
68 #include "scip/pub_var.h"
69 #include "scip/scip.h"
70 #include "scip/scip_branch.h"
71 #include "scip/scip_conflict.h"
72 #include "scip/scip_cons.h"
73 #include "scip/scip_cut.h"
74 #include "scip/scip_general.h"
75 #include "scip/scip_lp.h"
76 #include "scip/scip_mem.h"
77 #include "scip/scip_message.h"
78 #include "scip/scip_numerics.h"
79 #include "scip/scip_param.h"
80 #include "scip/scip_prob.h"
81 #include "scip/scip_sol.h"
82 #include "scip/scip_var.h"
83 
84 
85 /* constraint handler properties */
86 #define CONSHDLR_NAME "symresack"
87 #define CONSHDLR_DESC "symmetry breaking constraint handler relying on symresacks"
88 #define CONSHDLR_SEPAPRIORITY +40100 /**< priority of the constraint handler for separation */
89 #define CONSHDLR_ENFOPRIORITY -1005200 /**< priority of the constraint handler for constraint enforcing */
90 #define CONSHDLR_CHECKPRIORITY -1005200 /**< priority of the constraint handler for checking feasibility */
91 #define CONSHDLR_SEPAFREQ 5 /**< frequency for separating cuts; zero means to separate only in the root node */
92 #define CONSHDLR_PROPFREQ 5 /**< frequency for propagating domains; zero means only preprocessing propagation */
93 #define CONSHDLR_EAGERFREQ -1 /**< frequency for using all instead of only the useful constraints in separation,
94  * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
95 #define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
96 #define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
97 #define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
98 #define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
99 
100 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP
101 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_EXHAUSTIVE
103 #define DEFAULT_PPSYMRESACK TRUE /**< whether we allow upgrading to packing/partitioning symresacks */
104 #define DEFAULT_CHECKMONOTONICITY TRUE /**< check whether permutation is monotone when upgrading to packing/partitioning symresacks */
105 #define DEFAULT_FORCECONSCOPY FALSE /**< whether symresack constraints should be forced to be copied to sub SCIPs */
107 /* Constants to store fixings */
108 #define FIXED0 1 /* When a variable is fixed to 0. */
109 #define FIXED1 2 /* When a variable is fixed to 1. */
110 #define UNFIXED 3 /* When a variable is neither fixed to 0 or to 1. */
111 #define NOINIT 0 /* A dummy entry for non-initialized variables.
112  * Must have value 0 because of SCIPallocCleanBufferArray. */
113 /* A macro for checking if a variable was fixed during a bound change */
114 #define ISFIXED(x, bdchgidx) (SCIPvarGetUbAtIndex(x, bdchgidx, FALSE) - SCIPvarGetLbAtIndex(x, bdchgidx, FALSE) < 0.5)
116 
117 
118 /*
119  * Data structures
120  */
121 
122 /** constraint handler data */
123 struct SCIP_ConshdlrData
124 {
125  SCIP_Bool checkppsymresack; /**< whether we allow upgrading to packing/partitioning symresacks */
126  SCIP_Bool checkmonotonicity; /**< check whether permutation is monotone when upgrading to packing/partitioning symresacks */
127  int maxnvars; /**< maximal number of variables in a symresack constraint */
128  SCIP_Bool forceconscopy; /**< whether symresack constraints should be forced to be copied to sub SCIPs */
129 };
130 
131 
132 /** constraint data for symresack constraints */
133 struct SCIP_ConsData
134 {
135  SCIP_VAR** vars; /**< variables */
136  int nvars; /**< number of variables */
137  int* perm; /**< permutation associated to the symresack */
138  int* invperm; /**< inverse permutation */
139  SCIP_Bool ppupgrade; /**< whether constraint is upgraded to packing/partitioning symresack */
140  SCIP_Bool ismodelcons; /**< whether the symresack is a model constraint */
141 #ifdef SCIP_DEBUG
142  int debugcnt; /**< counter to store number of added cover inequalities */
143 #endif
144 
145  /* data for upgraded symresack constraints */
146  int ncycles; /**< number of cycles in permutation */
147  int** cycledecomposition; /**< cycle decomposition */
148  int ndescentpoints; /**< number of descent points in perm (only used if perm is not monotone) */
149  int* descentpoints; /**< descent points in perm (only used if perm is not monotone) */
150 };
151 
152 
153 /*
154  * Local methods
155  */
156 
157 /** frees a symresack constraint data */
158 static
160  SCIP* scip, /**< SCIP data structure */
161  SCIP_CONSDATA** consdata /**< pointer to symresack constraint data */
162  )
163 {
164  int nvars;
165  int i;
166 
167  assert( consdata != NULL );
168  assert( *consdata != NULL );
169 
170  nvars = (*consdata)->nvars;
171 
172  if ( nvars == 0 )
173  {
174  assert( (*consdata)->vars == NULL );
175  assert( (*consdata)->perm == NULL );
176  assert( (*consdata)->invperm == NULL );
177  assert( (*consdata)->ncycles == 0 );
178  assert( (*consdata)->cycledecomposition == NULL );
179 
180  SCIPfreeBlockMemory(scip, consdata);
181 
182  return SCIP_OKAY;
183  }
184 
185  if ( (*consdata)->ndescentpoints > 0 )
186  {
187  assert( (*consdata)->descentpoints != NULL );
188 
189  SCIPfreeBlockMemoryArray(scip, &((*consdata)->descentpoints), (*consdata)->ndescentpoints);
190  }
191 
192  if ( (*consdata)->ppupgrade )
193  {
194  for (i = 0; i < (*consdata)->ncycles; ++i)
195  {
196  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->cycledecomposition[i]), nvars + 1);
197  }
198  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->cycledecomposition), (*consdata)->ncycles);
199  }
200 
201  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->invperm), nvars);
202  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->perm), nvars);
203 
204  for (i = 0; i < nvars; ++i)
205  {
206  SCIP_CALL( SCIPreleaseVar(scip, &(*consdata)->vars[i]) );
207  }
208  SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vars), nvars);
209 
210  SCIPfreeBlockMemory(scip, consdata);
211 
212  return SCIP_OKAY;
213 }
214 
215 
216 /** check whether constraint can be upgraded to packing/partitioning symresack */
217 static
219  SCIP* scip, /**< SCIP data structure */
220  SCIP_CONSDATA** consdata, /**< pointer to store constraint data */
221  int* perm, /**< permutation */
222  SCIP_VAR** vars, /**< variables affected by permutation */
223  int nvars, /**< length of permutation */
224  SCIP_Bool checkmonotonicity, /**< check whether permutation is monotone */
225  SCIP_Bool* upgrade /**< pointer to store whether upgrade was successful */
226  )
227 {
228  SCIP_Bool* covered;
229  SCIP_Bool descent;
230  SCIP_CONSHDLR* setppcconshdlr;
231  SCIP_CONS** setppcconss;
232  SCIP_VAR* var;
233  SCIP_Bool terminated = FALSE;
234  int** cycledecomposition;
235  int* indicesincycle;
236  int nsetppcconss;
237  int curcycle;
238  int maxcyclelength;
239  int ncycles = 0;
240  int c;
241  int i;
242  int j;
243  int ndescentpoints = 0;
244  int* descentpoints;
245 
246  assert( scip != NULL );
247  assert( perm != NULL );
248  assert( vars != NULL );
249  assert( nvars > 0 );
250  assert( upgrade != NULL );
251 
252  *upgrade = FALSE;
253 
254  SCIP_CALL( SCIPallocBufferArray(scip, &covered, nvars) );
255 
256  for (i = 0; i < nvars; ++i)
257  covered[i] = FALSE;
258 
259  /* get number of cycles in permutation */
260  for (i = 0; i < nvars; ++i)
261  {
262  /* skip checked indices */
263  if ( covered[i] )
264  continue;
265 
266  ++ncycles;
267  j = i;
268  descent = FALSE;
269 
270  do
271  {
272  covered[j] = TRUE;
273 
274  if ( perm[j] < j )
275  {
276  ++ndescentpoints;
277 
278  if ( ! descent )
279  descent = TRUE;
280  else if ( checkmonotonicity )
281  break;
282  }
283 
284  j = perm[j];
285  }
286  while ( j != i );
287 
288  /* if cycle is not monotone and we require the cycle to be monotone */
289  if ( j != i )
290  {
291  assert( checkmonotonicity );
292  SCIPfreeBufferArray(scip, &covered);
293 
294  return SCIP_OKAY;
295  }
296  }
297  assert( ncycles <= nvars / 2 );
298 
299  /* check for packing/partitioning type */
300  for (i = 0; i < nvars; ++i)
301  covered[i] = FALSE;
302 
303  /* compute cycle decomposition: row i stores in entry 0 the length of the cycle,
304  * the remaining entries are the coordinates in the cycle;
305  * store descent points as well if permutation is not monotone */
306  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &cycledecomposition, ncycles) );
307  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &descentpoints, ndescentpoints) );
308  for (i = 0; i < ncycles; ++i)
309  {
310  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &cycledecomposition[i], nvars + 1) );
311  }
312 
313  curcycle = 0;
314  maxcyclelength = 0;
315  c = 0;
316  for (i = 0; i < nvars; ++i)
317  {
318  int cyclelength = 0;
319 
320  /* skip checked indices */
321  if ( covered[i] )
322  continue;
323 
324  j = i;
325  do
326  {
327  if ( perm[j] < j )
328  descentpoints[c++] = j;
329 
330  covered[j] = TRUE;
331  cycledecomposition[curcycle][++cyclelength] = j;
332  j = perm[j];
333  }
334  while ( j != i );
335 
336  cycledecomposition[curcycle][0] = cyclelength;
337  ++curcycle;
338 
339  if ( maxcyclelength < cyclelength )
340  maxcyclelength = cyclelength;
341  }
342  assert( c == ndescentpoints );
343 
344  /* permutation can be upgraded -> check whether the symresack is of packing/partitioning type */
345  setppcconshdlr = SCIPfindConshdlr(scip, "setppc");
346  if ( setppcconshdlr == NULL )
347  {
348  SCIPerrorMessage("Setppc constraint handler not found.\n");
349  return SCIP_PLUGINNOTFOUND;
350  }
351  setppcconss = SCIPconshdlrGetConss(setppcconshdlr);
352  nsetppcconss = SCIPconshdlrGetNConss(setppcconshdlr);
353 
354  /* Check whether each cycle of the symresack is contained in a set packing/partitioning constraint.
355  * To this end, we have to guarantee that all affected variables are not negated since permutations
356  * are given w.r.t. original variables. */
357  *upgrade = TRUE;
358 
359  SCIP_CALL( SCIPallocBufferArray(scip, &indicesincycle, maxcyclelength) );
360 
361  for (i = 0; i < ncycles && *upgrade && ! terminated; ++i)
362  {
363  int cyclelength;
364 
365  /* get indices of variables in current cycle */
366  for (j = 0; j < cycledecomposition[i][0]; ++ j)
367  {
368  var = vars[cycledecomposition[i][j + 1]];
369 
370  if ( SCIPvarIsNegated(var) )
371  {
372  terminated = TRUE;
373  break;
374  }
375 
376  indicesincycle[j] = SCIPvarGetProbindex(var);
377  }
378 
379  cyclelength = cycledecomposition[i][0];
380 
381  /* iterate over constraints
382  *
383  * @todo Improve the check by sorting the constraints in the setppcconss array
384  * by type and number of contained variables. */
385  for (c = 0; c < nsetppcconss; ++c)
386  {
387  int nsetppcvars;
388  SCIP_VAR** setppcvars;
389  int varidx;
390  int nfound = 0;
391  int k;
392 
393  /* check type */
394  if ( SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_COVERING )
395  continue;
396  assert( SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_PARTITIONING || SCIPgetTypeSetppc(scip, setppcconss[c]) == SCIP_SETPPCTYPE_PACKING );
397 
398  /* get set packing/partitioning variables */
399  nsetppcvars = SCIPgetNVarsSetppc(scip, setppcconss[c]);
400 
401  /* skip empty constraints (might not have been removed by presolving yet) */
402  if ( nsetppcvars == 0 )
403  continue;
404  assert( nsetppcvars > 0 );
405 
406  setppcvars = SCIPgetVarsSetppc(scip, setppcconss[c]);
407  assert( setppcvars != NULL );
408 
409  /* check whether all variables of the cycle are contained in setppc constraint */
410  for (j = 0; j < nsetppcvars && nfound < cyclelength; ++j)
411  {
412  var = setppcvars[j];
413 
414  if ( SCIPvarIsNegated(var) )
415  continue;
416 
417  varidx = SCIPvarGetProbindex(var);
418 
419  for (k = 0; k < cyclelength; ++k)
420  {
421  if ( varidx == indicesincycle[k] )
422  {
423  ++nfound;
424  break;
425  }
426  }
427  }
428  assert( nfound <= cyclelength );
429 
430  if ( nfound == cyclelength )
431  break;
432  }
433 
434  /* row is not contained in a set packing/partitioning constraint */
435  if ( c >= nsetppcconss )
436  *upgrade = FALSE;
437  }
438 
439  if ( *upgrade )
440  {
441  (*consdata)->ncycles = ncycles;
442  (*consdata)->cycledecomposition = cycledecomposition;
443  (*consdata)->ndescentpoints = ndescentpoints;
444  (*consdata)->descentpoints = descentpoints;
445  SCIPdebugMsg(scip, "added monotone PP symresack.\n");
446 
447  SCIPfreeBufferArray(scip, &indicesincycle);
448  SCIPfreeBufferArray(scip, &covered);
449  }
450  else
451  {
452  SCIPfreeBlockMemoryArray(scip, &descentpoints, ndescentpoints);
453  SCIPfreeBufferArray(scip, &indicesincycle);
454  SCIPfreeBufferArray(scip, &covered);
455  for (i = 0; i < ncycles; ++i)
456  {
457  SCIPfreeBlockMemoryArray(scip, &cycledecomposition[i], nvars + 1);
458  }
459  SCIPfreeBlockMemoryArray(scip, &cycledecomposition, ncycles);
460  }
461 
462  return SCIP_OKAY;
463 }
464 
465 
466 /** creates symresack constraint data
467  *
468  * If the input data contains non-binary variables or fixed
469  * points, we delete these variables in a preprocessing step.
470  */
471 static
473  SCIP* scip, /**< SCIP data structure */
474  SCIP_CONSHDLR* conshdlr, /**< symresack constraint handler */
475  SCIP_CONSDATA** consdata, /**< pointer to store constraint data */
476  SCIP_VAR*const* inputvars, /**< input variables of the constraint handler */
477  int inputnvars, /**< input number of variables of the constraint handler*/
478  int* inputperm, /**< input permutation of the constraint handler */
479  SCIP_Bool ismodelcons /**< whether the symresack is a model constraint */
480  )
481 {
482  SCIP_CONSHDLRDATA* conshdlrdata;
483  SCIP_VAR** vars;
484  SCIP_Bool upgrade;
485  int* indexcorrection;
486  int* invperm;
487  int* perm;
488  int naffectedvariables;
489  int i;
490  int j = 0;
491 
492  assert( consdata != NULL );
493  assert( conshdlr != NULL );
494  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
495 
496  SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
497 
498 #ifdef SCIP_DEBUG
499  (*consdata)->debugcnt = 0;
500 #endif
501 
502  (*consdata)->ndescentpoints = 0;
503  (*consdata)->descentpoints = NULL;
504  (*consdata)->ismodelcons = ismodelcons;
505 
506  /* count the number of binary variables which are affected by the permutation */
507  SCIP_CALL( SCIPallocBufferArray(scip, &indexcorrection, inputnvars) );
508  indexcorrection[0] = -1;
509  for (i = 0; i < inputnvars; ++i)
510  {
511  if ( inputperm[i] != i && SCIPvarIsBinary(inputvars[i]) )
512  {
513  if ( i == 0 )
514  indexcorrection[i] = 0;
515  else
516  indexcorrection[i] = indexcorrection[i - 1] + 1;
517  }
518  else
519  {
520  if ( i > 0 )
521  indexcorrection[i] = indexcorrection[i - 1];
522  }
523  }
524  naffectedvariables = indexcorrection[inputnvars - 1] + 1;
525 
526  (*consdata)->nvars = naffectedvariables;
527 
528  /* Stop if we detect that the permutation fixes each binary point. */
529  if ( naffectedvariables == 0 )
530  {
531  SCIPfreeBufferArrayNull(scip, &indexcorrection);
532 
533  (*consdata)->vars = NULL;
534  (*consdata)->perm = NULL;
535  (*consdata)->invperm = NULL;
536  (*consdata)->ppupgrade = FALSE;
537  (*consdata)->ncycles = 0;
538  (*consdata)->cycledecomposition = NULL;
539  return SCIP_OKAY;
540  }
541 
542  /* remove fixed points from permutation representation */
543  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &vars, naffectedvariables) );
544  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &perm, naffectedvariables) );
545  for (i = 0; i < inputnvars; ++i)
546  {
547  if ( i == 0 )
548  {
549  if ( indexcorrection[i] > -1 )
550  {
551  vars[j] = inputvars[i];
552  perm[j++] = indexcorrection[inputperm[i]];
553  }
554  }
555  else
556  {
557  if ( indexcorrection[i] > indexcorrection[i - 1] )
558  {
559  vars[j] = inputvars[i];
560  perm[j++] = indexcorrection[inputperm[i]];
561  }
562  }
563  }
564  SCIPfreeBufferArrayNull(scip, &indexcorrection);
565 
566  (*consdata)->vars = vars;
567  (*consdata)->perm = perm;
568 
569  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &invperm, naffectedvariables) );
570  for (i = 0; i < naffectedvariables; ++i)
571  {
572  SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->vars[i]) );
573  invperm[perm[i]] = i;
574  }
575  (*consdata)->invperm = invperm;
576 
577  /* check for upgrade to packing/partitioning symresacks*/
578  conshdlrdata = SCIPconshdlrGetData(conshdlr);
579  upgrade = FALSE;
580  if ( conshdlrdata->checkppsymresack )
581  {
582  SCIP_CALL( packingUpgrade(scip, consdata, perm, vars, naffectedvariables, conshdlrdata->checkmonotonicity, &upgrade) );
583  }
584 
585  (*consdata)->ppupgrade = upgrade;
586 
587  /* get transformed variables, if we are in the transformed problem */
588  if ( SCIPisTransformed(scip) )
589  {
590  /* Make sure that all variables cannot be multiaggregated (cannot be handled by cons_symresack, since one cannot
591  * easily eliminate single variables from a symresack constraint. */
592  for (i = 0; i < naffectedvariables; ++i)
593  {
594  SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->vars[i], &(*consdata)->vars[i]) );
595  SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, (*consdata)->vars[i]) );
596  }
597  }
598 
599  return SCIP_OKAY;
600 }
601 
602 
603 /** generate initial LP cut
604  *
605  * We generate the ordering inequality for the pair \f$(1, \gamma^{-1}(1))\f$, i.e.,
606  * the inequality \f$-x_{1} + x_{\gamma^{-1}(1)} \leq 0\f$. This inequality is valid,
607  * because we guaranteed in a preprocessing step that all variables are binary.
608  *
609  * Furthermore, we add facet inequalities of packing/partitioning symresacks if
610  * we deal with packing/partitioning symresacks.
611  */
612 static
614  SCIP* scip, /**< SCIP pointer */
615  SCIP_CONS* cons, /**< constraint */
616  SCIP_Bool checkmonotonicity, /**< has it been checked whether permutation is monotone for packing/partitioning symresacks? */
617  SCIP_Bool* infeasible /**< pointer to store whether we detected infeasibility */
618  )
619 {
620  SCIP_CONSDATA* consdata;
621  SCIP_VAR** vars;
622  SCIP_ROW* row;
623  int nvars;
624 #ifdef SCIP_DEBUG
625  char name[SCIP_MAXSTRLEN];
626 #endif
627  int i;
628  int j;
629  int k;
630 
631  assert( scip != NULL );
632  assert( cons != NULL );
633  assert( infeasible != NULL );
634 
635  *infeasible = FALSE;
636 
637  consdata = SCIPconsGetData(cons);
638  assert( consdata != NULL );
639 
640  nvars = consdata->nvars;
641 
642  /* avoid stupid problems */
643  if ( nvars <= 1 )
644  return SCIP_OKAY;
645 
646  assert( consdata->vars != NULL );
647  vars = consdata->vars;
648 
649  /* there are no fixed points */
650  assert( consdata->invperm[0] != 0 );
651 
652  /* add ordering inequality */
653 #ifdef SCIP_DEBUG
654  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "symresack_init_%s", SCIPconsGetName(cons));
655  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
656 #else
657  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, "", -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
658 #endif
659  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[0], -1.0) );
660  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[consdata->invperm[0]], 1.0) );
661 
662  SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
663 
664  SCIP_CALL( SCIPreleaseRow(scip, &row) );
665 
666  /* check whether we have a packing/partioning symresack */
667  if ( consdata->ppupgrade && ! *infeasible )
668  {
669  if ( checkmonotonicity )
670  {
671  SCIP_VAR** varsincons;
672  SCIP_Real* coeffs;
673  int** cycledecomposition;
674  int ncycles;
675  int nvarsincons;
676  int nvarsincycle;
677  int firstelemincycle;
678 
679  ncycles = consdata->ncycles;
680  cycledecomposition = consdata->cycledecomposition;
681 
682  SCIP_CALL( SCIPallocBufferArray(scip, &varsincons, nvars) );
683  SCIP_CALL( SCIPallocBufferArray(scip, &coeffs, nvars) );
684 
685  coeffs[0] = 1.0;
686 
687  /* add packing/partitioning symresack constraints */
688  for (i = 0; i < ncycles; ++i)
689  {
690  assert( cycledecomposition[i][0] > 0 );
691 
692  nvarsincycle = cycledecomposition[i][0];
693  varsincons[0] = vars[cycledecomposition[i][nvarsincycle]];
694  firstelemincycle = cycledecomposition[i][1];
695 
696  assert( firstelemincycle == consdata->perm[cycledecomposition[i][nvarsincycle]] );
697 
698  nvarsincons = 1;
699 
700  /* add variables of other cycles to the constraint */
701  for (j = 0; j < i; ++j)
702  {
703  nvarsincycle = cycledecomposition[j][0];
704  for (k = 1; k <= nvarsincycle; ++k)
705  {
706  if ( cycledecomposition[j][k] < firstelemincycle )
707  {
708  varsincons[nvarsincons] = vars[cycledecomposition[j][k]];
709  coeffs[nvarsincons++] = -1.0;
710  }
711  else
712  continue;
713  }
714  }
715 
716 #ifdef SCIP_DEBUG
717  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "ppSymresack_%d_%s", i, SCIPconsGetName(cons));
718  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
719 #else
720  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, "", -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
721 #endif
722  SCIP_CALL( SCIPaddVarsToRow(scip, row, nvarsincons, varsincons, coeffs) );
723 
724  SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
725  SCIP_CALL( SCIPreleaseRow(scip, &row) );
726 
727  if ( *infeasible )
728  break;
729  }
730 
731  SCIPfreeBufferArray(scip, &coeffs);
732  SCIPfreeBufferArray(scip, &varsincons);
733  }
734  else
735  {
736  SCIP_Real* coeffs;
737  SCIP_VAR** varsincons;
738  int* imgdescentpoints;
739  int* descentpoints;
740  int* perm;
741  int ndescentpoints;
742  int lastascent = 0;
743  int newlastascent = 0;
744  int nvarsincons = 1;
745 
746  descentpoints = consdata->descentpoints;
747  ndescentpoints = consdata->ndescentpoints;
748  perm = consdata->perm;
749 
750  assert( descentpoints != NULL );
751  assert( ndescentpoints > 0 );
752  assert( perm != NULL );
753  assert( vars != NULL );
754  assert( nvars > 0 );
755 
756  SCIP_CALL( SCIPallocBufferArray(scip, &imgdescentpoints, ndescentpoints) );
757 
758  /* get images of descentpoints */
759  for (j = 0; j < ndescentpoints; ++j)
760  imgdescentpoints[j] = perm[descentpoints[j]];
761 
762  /* sort descent points increasingly w.r.t. the corresponding image */
763  SCIPsortIntInt(imgdescentpoints, descentpoints, ndescentpoints);
764 
765  /* iteratively generate coefficient vector: the first entry is the descent point j and the remaining entries
766  * are the corresponding ascent points less than perm[j]
767  */
768  SCIP_CALL( SCIPallocClearBufferArray(scip, &coeffs, nvars) );
769  SCIP_CALL( SCIPallocClearBufferArray(scip, &varsincons, nvars) );
770  coeffs[0] = 1.0;
771  for (j = 0; j < ndescentpoints; ++j)
772  {
773  varsincons[0] = vars[descentpoints[j]];
774  for (i = lastascent; i < imgdescentpoints[j]; ++i)
775  {
776  if ( perm[i] > i )
777  {
778  coeffs[nvarsincons] = -1.0;
779  varsincons[nvarsincons++] = vars[i];
780  newlastascent = i;
781  }
782  }
783  lastascent = newlastascent;
784 
785 #ifdef SCIP_DEBUG
786  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "ppSymresack_%d_%s", j, SCIPconsGetName(cons));
787  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
788 #else
789  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, "", -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
790 #endif
791  SCIP_CALL( SCIPaddVarsToRow(scip, row, nvarsincons, varsincons, coeffs) );
792 
793  SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
794  SCIP_CALL( SCIPreleaseRow(scip, &row) );
795 
796  if ( *infeasible )
797  break;
798  }
799 
800  SCIPfreeBufferArray(scip, &varsincons);
801  SCIPfreeBufferArray(scip, &coeffs);
802  SCIPfreeBufferArray(scip, &imgdescentpoints);
803  }
804  }
805 
806  return SCIP_OKAY;
807 }
808 
809 
810 /** Determines if a vector with additional fixings could exist that is lexicographically larger than its image.
811  *
812  * Given a vector of variables, a permutation, and a set of additional (virtual) fixings.
813  * If a vector adhering to the local variable bounds (local fixings) and to the virtual fixings exists,
814  * then infeasible is FALSE, otherwise TRUE.
815  */
816 static
818  SCIP* scip, /**< SCIP pointer */
819  SCIP_VAR** vars, /**< array of variables affected by permutation */
820  int* invperm, /**< inverse of permutation */
821  int nvars, /**< number of variables */
822  int start, /**< at which position to start (assuming previous positions are equal) */
823  int* tempfixings, /**< array with at entry i the virtual fixing of variable vars[i] */
824  int* tempfixentries, /**< the entries i that are virtually fixed until numfixentriesinit */
825  int numfixentriesinit, /**< the number of virtually fixed entries */
826  SCIP_Bool* infeasible, /**< pointer to store whether infeasibility is detected in these fixings */
827  int* infeasibleentry /**< pointer to store at which entry a (0, 1) pattern is found */
828  )
829 {
830  SCIP_VAR* var1;
831  SCIP_VAR* var2;
832  int var1fix;
833  int var2fix;
834 
835  int i;
836  int numfixentries;
837 
838  /* avoid trivial problems */
839  if ( nvars < 2 )
840  return SCIP_OKAY;
841 
842  assert( scip != NULL );
843  assert( vars != NULL );
844  assert( invperm != NULL );
845  assert( tempfixings != NULL );
846  assert( tempfixentries != NULL );
847  assert( infeasible != NULL );
848 
849  /* A counter for how many virtual fixings we have. */
850  numfixentries = numfixentriesinit;
851 
852  *infeasible = FALSE;
853 
854  for (i = start; i < nvars; ++i)
855  {
856  /* there are no fixed points */
857  assert( invperm[i] != i );
858 
859  /* get variables of first and second column */
860  var1 = vars[i];
861  var2 = vars[invperm[i]];
862 
863  assert( var1 != NULL );
864  assert( var2 != NULL );
865 
866  /* Get virtual fixing of variable in left column */
867  var1fix = tempfixings[i];
868  if ( var1fix == NOINIT )
869  {
870  if ( SCIPvarGetUbLocal(var1) < 0.5 )
871  {
872  var1fix = FIXED0;
873  assert( SCIPvarGetLbLocal(var1) <= 0.5 );
874  }
875  else if ( SCIPvarGetLbLocal(var1) > 0.5 )
876  var1fix = FIXED1;
877  else
878  var1fix = UNFIXED;
879  }
880  assert( var1fix != NOINIT );
881 
882  /* Get virtual fixing of variable in right column */
883  var2fix = tempfixings[invperm[i]];
884  if ( var2fix == NOINIT )
885  {
886  if ( SCIPvarGetUbLocal(var2) < 0.5 )
887  {
888  var2fix = FIXED0;
889  assert( SCIPvarGetLbLocal(var2) <= 0.5 );
890  }
891  else if ( SCIPvarGetLbLocal(var2) > 0.5 )
892  var2fix = FIXED1;
893  else
894  var2fix = UNFIXED;
895  }
896  assert( var2fix != NOINIT );
897 
898  /* Encounter one of (_, _), (_, 0), (1, _), (1, 0). In all cases (1, 0) can be constructed. Thus feasible. */
899  if ( var1fix != FIXED0 && var2fix != FIXED1 )
900  break;
901  /* Encounter (0, 1). Infeasible. */
902  else if ( var1fix == FIXED0 && var2fix == FIXED1 )
903  {
904  *infeasible = TRUE;
905  *infeasibleentry = i;
906  break;
907  }
908  /* Encounter (0, _). Virtually fix var2 to 0. */
909  else if ( var1fix == FIXED0 && var2fix == UNFIXED )
910  {
911  tempfixings[invperm[i]] = FIXED0;
912  /* Mark that we have fixed invperm[i]. */
913  tempfixentries[numfixentries++] = invperm[i];
914  }
915  /* Encounter (_, 1). Virtually fix var1 to 1. */
916  else if(var1fix == UNFIXED && var2fix == FIXED1 )
917  {
918  tempfixings[i] = FIXED0;
919  /* Mark that we have fixed invperm[i]. */
920  tempfixentries[numfixentries++] = i;
921  }
922  /* Remaining cases are (0, 0) and (1, 1). In both cases: continue. */
923  }
924 
925  /* Undo virtual fixings made in this function */
926  for (i = numfixentriesinit; i < numfixentries; ++i)
927  {
928  tempfixings[tempfixentries[i]] = NOINIT;
929  tempfixentries[i] = 0;
930  }
931 
932  return SCIP_OKAY;
933 }
934 
935 
936 /** perform propagation of symresack constraint */
937 static
939  SCIP* scip, /**< SCIP pointer */
940  SCIP_CONS* cons, /**< constraint to be propagated */
941  SCIP_Bool* infeasible, /**< pointer to store whether it was detected that the node is infeasible */
942  int* ngen /**< pointer to store number of generated bound strengthenings */
943  )
944 {
945  SCIP_CONSDATA* consdata;
946  SCIP_VAR** vars;
947  int* invperm;
948  int nvars;
949  int i;
950  int r;
951  SCIP_VAR* var1;
952  SCIP_VAR* var2;
953  int var1fix;
954  int var2fix;
955  SCIP_Bool tightened;
956  SCIP_Bool peekinfeasible;
957  int peekinfeasibleentry;
958  int* tempfixings;
959  int* tempfixentries;
960 
961  assert( scip != NULL );
962  assert( cons != NULL );
963  assert( infeasible != NULL );
964  assert( ngen != NULL );
965 
966  SCIPdebugMsg(scip, "Propagating variables of constraint <%s>.\n", SCIPconsGetName(cons));
967 
968  *ngen = 0;
969  *infeasible = FALSE;
970 
971  /* get data of constraint */
972  consdata = SCIPconsGetData(cons);
973  assert( consdata != NULL );
974  nvars = consdata->nvars;
975 
976  /* avoid trivial problems */
977  if ( nvars < 2 )
978  return SCIP_OKAY;
979 
980  assert( consdata->vars != NULL );
981  assert( consdata->invperm != NULL );
982  vars = consdata->vars;
983  invperm = consdata->invperm;
984 
985  /* loop through all variables */
986  for (i = 0; i < nvars; ++i)
987  {
988  /* there are no fixed points */
989  assert( invperm[i] != i );
990 
991  /* get variables of first and second column */
992  var1 = vars[i];
993  var2 = vars[invperm[i]];
994  assert( var1 != NULL );
995  assert( var2 != NULL );
996 
997  /* Get the fixing status of the left column variable var1 */
998  if ( SCIPvarGetUbLocal(var1) < 0.5 )
999  {
1000  var1fix = FIXED0;
1001  assert( SCIPvarGetLbLocal(var1) <= 0.5 );
1002  }
1003  else if ( SCIPvarGetLbLocal(var1) > 0.5 )
1004  var1fix = FIXED1;
1005  else
1006  var1fix = UNFIXED;
1007 
1008  /* Get the fixing status of the right column variable var2 */
1009  if ( SCIPvarGetUbLocal(var2) < 0.5 )
1010  {
1011  var2fix = FIXED0;
1012  assert( SCIPvarGetLbLocal(var2) <= 0.5 );
1013  }
1014  else if ( SCIPvarGetLbLocal(var2) > 0.5 )
1015  var2fix = FIXED1;
1016  else
1017  var2fix = UNFIXED;
1018 
1019  /* Encounter one of (_, _), (_, 0), (1, _), (1, 0). Check if (1, 1) or (0, 0) are possible, otherwise fix. */
1020  if ( var1fix != FIXED0 && var2fix != FIXED1 )
1021  {
1022  assert( SCIPvarGetUbLocal(var1) > 0.5 );
1023  assert( SCIPvarGetLbLocal(var2) < 0.5 );
1024 
1025  SCIPdebugMsg(scip, "Check variable pair (%d,%d).\n", i, invperm[i]);
1026  SCIPdebugMsg(scip, " -> node is feasible (could set pair to (1,0) and every earlier pair is constant).\n");
1027 
1028  if ( var1fix == UNFIXED || var2fix == UNFIXED )
1029  {
1030  /* Create arrays tempfixings and tempfixentries to store virtual fixings. */
1031  SCIP_CALL( SCIPallocCleanBufferArray(scip, &tempfixings, nvars) );
1032  SCIP_CALL( SCIPallocCleanBufferArray(scip, &tempfixentries, nvars) );
1033 
1034  if ( var1fix == UNFIXED )
1035  {
1036  assert( SCIPvarGetLbLocal(var1) < 0.5 );
1037 
1038  /* Peek whether a lexicographical larger-or-equal vector can be created with var1 fixed to 0 */
1039  SCIPdebugMsg(scip, " -> First entry is not fixed. Check if 0 is feasible.\n");
1040  tempfixings[i] = FIXED0;
1041  tempfixentries[0] = i;
1042  SCIP_CALL( checkFeasible(scip, vars, invperm, nvars, i, tempfixings, tempfixentries, 1,
1043  &peekinfeasible, &peekinfeasibleentry) );
1044 
1045  if ( peekinfeasible )
1046  {
1047  /* No feasible vector exists with var1 set to 0, so it must be a 1-fixing. */
1048  SCIPdebugMsg(scip, " -> First entry is not fixed. 0 is not feasible. Fixing to 1.\n");
1049  SCIP_CALL( SCIPinferVarLbCons(scip, var1, 1.0, cons, i + nvars * peekinfeasibleentry,
1050  FALSE, infeasible, &tightened) ); /*lint !e713*/
1051  assert( ! *infeasible );
1052 
1053  if ( tightened )
1054  ++(*ngen);
1055  }
1056 
1057  tempfixings[i] = NOINIT;
1058  tempfixentries[0] = 0;
1059  }
1060 
1061  if ( var2fix == UNFIXED )
1062  {
1063  assert( SCIPvarGetUbLocal(var2) > 0.5 );
1064 
1065  /* Peek whether a lexicographical larger-or-equal vector can be created with var2 fixed to 1 */
1066  SCIPdebugMsg(scip, " -> Second entry is not fixed. Check if 1 is feasible.\n");
1067  tempfixings[invperm[i]] = FIXED1;
1068  tempfixentries[0] = invperm[i];
1069  SCIP_CALL( checkFeasible(scip, vars, invperm, nvars, i, tempfixings, tempfixentries, 1,
1070  &peekinfeasible, &peekinfeasibleentry) );
1071 
1072  if ( peekinfeasible )
1073  {
1074  /* No feasible vector exists with var2 set to 1, so it must be a 1-fixing. */
1075  SCIPdebugMsg(scip, " -> Second entry is not fixed. 1 is not feasible. Fixing to 0.\n");
1076  SCIP_CALL( SCIPinferVarUbCons(scip, var2, 0.0, cons, i + nvars * peekinfeasibleentry,
1077  FALSE, infeasible, &tightened) ); /*lint !e713*/
1078  assert( ! *infeasible );
1079 
1080  if ( tightened )
1081  ++(*ngen);
1082  }
1083 
1084  tempfixings[invperm[i]] = NOINIT;
1085  tempfixentries[0] = 0;
1086  }
1087 
1088  SCIPfreeCleanBufferArray(scip, &tempfixentries);
1089  SCIPfreeCleanBufferArray(scip, &tempfixings);
1090  }
1091 
1092  /* Can stop here, because this row can become (1, 0). Therefore all next rows can take arbitrary values. */
1093  break;
1094  }
1095  /* Encounter (0, 1): If first part of variable pair fixed to 0 and second part is fixed to 1 */
1096  else if ( var1fix == FIXED0 && var2fix == FIXED1 )
1097  {
1098  SCIPdebugMsg(scip, "Check variable pair (%d,%d).\n", i, invperm[i]);
1099 
1100  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");
1101 
1102  /* perform conflict analysis */
1104  {
1106 
1107  for (r = 0; r <= i; ++r)
1108  {
1109  /* there are no fixed points */
1110  assert( invperm[r] != r );
1111 
1112  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[r]) );
1113  SCIP_CALL( SCIPaddConflictBinvar(scip, vars[invperm[r]]) );
1114  }
1115 
1116  SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
1117  }
1118 
1119  *infeasible = TRUE;
1120  break;
1121  }
1122  /* Encounter (0, _): Fix second part to 0 */
1123  else if ( var1fix == FIXED0 && var2fix != FIXED0 )
1124  {
1125  assert( SCIPvarGetUbLocal(var1) < 0.5 );
1126  assert( SCIPvarGetLbLocal(var2) < 0.5 );
1127  assert( SCIPvarGetUbLocal(var2) > 0.5 );
1128 
1129  SCIPdebugMsg(scip, "Check variable pair (%d,%d).\n", i, invperm[i]);
1130 
1131  assert( SCIPvarGetLbLocal(var2) < 0.5 );
1132  SCIP_CALL( SCIPinferVarUbCons(scip, var2, 0.0, cons, i, FALSE, infeasible, &tightened) ); /*lint !e713*/
1133  assert( ! *infeasible );
1134 
1135  if ( tightened )
1136  ++(*ngen);
1137  }
1138  /* Encounter (_, 1): fix first part to 1 */
1139  else if ( var1fix != FIXED1 && var2fix == FIXED1 )
1140  {
1141  assert( SCIPvarGetLbLocal(var1) < 0.5 );
1142  assert( SCIPvarGetUbLocal(var1) > 0.5 );
1143  assert( SCIPvarGetLbLocal(var2) > 0.5 );
1144 
1145  SCIPdebugMsg(scip, "Check variable pair (%d,%d).\n", i, invperm[i]);
1146 
1147  assert( SCIPvarGetUbLocal(var1) > 0.5 );
1148  SCIP_CALL( SCIPinferVarLbCons(scip, var1, 1.0, cons, i, FALSE, infeasible, &tightened) ); /*lint !e713*/
1149  assert( ! *infeasible );
1150 
1151  if ( tightened )
1152  ++(*ngen);
1153  }
1154  /* Remaining cases are (0, 0) and (1, 1). In these cases we can continue! */
1155  }
1156 
1157  return SCIP_OKAY;
1158 }
1159 
1160 
1161 /** add symresack cover inequality */
1162 static
1164  SCIP* scip, /**< SCIP pointer */
1165  SCIP_CONS* cons, /**< constraint */
1166  int nvars, /**< number of variables */
1167  SCIP_VAR** vars, /**< variables */
1168  int* coeffs, /**< coefficient vector of inequality to be added */
1169  SCIP_Real rhs, /**< right-hand side of inequality to be added */
1170  SCIP_Bool* infeasible /**< pointer to store whether we detected infeasibility */
1171  )
1172 {
1173  SCIP_ROW* row;
1174  int i;
1175 #ifdef SCIP_DEBUG
1176  SCIP_CONSDATA* consdata;
1177  char name[SCIP_MAXSTRLEN];
1178 #endif
1179 
1180  assert( scip != NULL );
1181  assert( cons != NULL );
1182  assert( nvars > 0 );
1183  assert( vars != NULL );
1184  assert( coeffs != NULL );
1185  assert( infeasible != NULL );
1186 
1187  *infeasible = FALSE;
1188 
1189 #ifdef SCIP_DEBUG
1190  consdata = SCIPconsGetData(cons);
1191  (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "symresack_cover_%s_%d", SCIPconsGetName(cons), consdata->debugcnt);
1192  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, name, -SCIPinfinity(scip), rhs, FALSE, FALSE, TRUE) );
1193  ++consdata->debugcnt;
1194 #else
1195  SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, "", -SCIPinfinity(scip), rhs, FALSE, FALSE, TRUE) );
1196 #endif
1197  SCIP_CALL( SCIPcacheRowExtensions(scip, row) );
1198 
1199  for (i = 0; i < nvars; ++i)
1200  {
1201  if ( coeffs[i] == 1 || coeffs[i] == -1 )
1202  {
1203  SCIP_CALL( SCIPaddVarToRow(scip, row, vars[i], (SCIP_Real) coeffs[i]) );
1204  }
1205  }
1206  SCIP_CALL( SCIPflushRowExtensions(scip, row) );
1207  SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
1208  SCIP_CALL( SCIPreleaseRow(scip, &row) );
1209 
1210  return SCIP_OKAY;
1211 }
1212 
1213 
1214 /** Maximize a linear function on a "strict" symresack,
1215  * that is a symresack where we do not allow the solution x = gamma(x).
1216  */
1217 static
1219  SCIP* scip, /**< SCIP pointer */
1220  int nvars, /**< number of variables in symresack */
1221  SCIP_Real* objective, /**< the objective vector */
1222  int* perm, /**< the permutation (without fixed points) as an array */
1223  int* invperm, /**< the inverse permutation as an array */
1224  int* maxcrit, /**< pointer to the critical entry where optimality is found at */
1225  SCIP_Real* maxsoluval /**< pointer to store the optimal objective value */
1226  )
1227 {
1228  /* The maximal objective in every iteration. */
1229  SCIP_Real tmpobj;
1230  /* The new value of componentobj when combining two components. */
1231  SCIP_Real tmpnewcompobj;
1232  /* helperobj is the sum of all positive objective-sums for all components. */
1233  SCIP_Real helperobj = 0.0;
1234 
1235  int crit;
1236  int critinv;
1237  int i;
1238 
1239  /* For every vertex of degree < 2 we maintain componentends and componentobj. */
1240  int* componentends;
1241  SCIP_Real* componentobj;
1242 
1243  assert( scip != NULL );
1244  assert( nvars > 0 );
1245  assert( objective != NULL );
1246  assert( perm != NULL );
1247  assert( invperm != NULL );
1248  assert( maxcrit != NULL );
1249  assert( maxsoluval != NULL );
1250 
1251  /* The current best known critical entry and objective */
1252  *maxcrit = -1;
1253  *maxsoluval = -SCIP_DEFAULT_INFINITY;
1254 
1255  SCIP_CALL( SCIPallocBufferArray(scip, &componentends, nvars) );
1256  SCIP_CALL( SCIPallocBufferArray(scip, &componentobj, nvars) );
1257 
1258  /* Initialization: Every entry is a component in the graph,
1259  * having the corresponding objective
1260  */
1261  for (i = 0; i < nvars; ++i)
1262  {
1263  componentends[i] = i;
1264  componentobj[i] = objective[i];
1265  if ( SCIPisGT(scip, objective[i], 0.0) )
1266  helperobj += objective[i];
1267  }
1268 
1269  /* Iterate over all critical rows, and of the graph maintain the components on the vertices of degree < 2. */
1270  for (crit = 0; crit < nvars; ++crit)
1271  {
1272  critinv = invperm[crit];
1273 
1274  /* Do not allow fixed points. */
1275  assert( crit != critinv );
1276 
1277  /* If the other end of the component of crit is critinv, then crit cannot be a critical entry. */
1278  if ( componentends[crit] == critinv )
1279  continue;
1280 
1281  /* Compute objective for crit as critical entry. Update if it is better than the best found objective */
1282  tmpobj = helperobj;
1283  if ( SCIPisLT(scip, componentobj[crit], 0.0) )
1284  tmpobj += componentobj[crit];
1285  if ( SCIPisGT(scip, componentobj[critinv], 0.0) )
1286  tmpobj -= componentobj[critinv];
1287  if ( SCIPisGT(scip, tmpobj, *maxsoluval) )
1288  {
1289  *maxsoluval = tmpobj;
1290  *maxcrit = crit;
1291  }
1292 
1293  /* Update helperobj */
1294  tmpnewcompobj = componentobj[crit] + componentobj[critinv];
1295  if ( SCIPisGT(scip, componentobj[crit], 0.0) )
1296  helperobj -= componentobj[crit];
1297  if ( SCIPisGT(scip, componentobj[critinv], 0.0) )
1298  helperobj -= componentobj[critinv];
1299  if ( SCIPisGT(scip, tmpnewcompobj, 0.0) )
1300  helperobj += tmpnewcompobj;
1301 
1302  /* Update the objective of a component */
1303  componentobj[componentends[crit]] = tmpnewcompobj;
1304  componentobj[componentends[critinv]] = tmpnewcompobj;
1305 
1306  /* Connect the endpoints of the newly created path */
1307  if ( componentends[crit] == crit )
1308  {
1309  componentends[crit] = componentends[critinv];
1310  componentends[componentends[critinv]] = crit;
1311  }
1312  else
1313  {
1314  componentends[componentends[crit]] = componentends[critinv];
1315  componentends[componentends[critinv]] = componentends[crit];
1316  }
1317 
1318  /* Early termination criterion. helperobj is upper bound to tmpobj for every next iteration,
1319  * so if helperobj <= maxsoluval then we can terminate earlier.
1320  */
1321  if ( SCIPisGE(scip, *maxsoluval, helperobj) )
1322  break;
1323  }
1324 
1325  /* It is always possible to make the first entry critical. */
1326  assert( *maxcrit >= 0 );
1327 
1328  SCIPfreeBufferArray(scip, &componentobj);
1329  SCIPfreeBufferArray(scip, &componentends);
1330 
1331  return SCIP_OKAY;
1332 }
1333 
1334 
1335 /** For a symresack, determine a maximizer for optimizing linear function
1336  * over a symresack, where the critical entry is fixed.
1337  */
1338 static
1340  SCIP* scip, /**< SCIP pointer */
1341  int nvars, /**< number of variables in symresack */
1342  SCIP_Real* objective, /**< the objective vector */
1343  int* perm, /**< the permutation (without fixed points) as an array */
1344  int* invperm, /**< the inverse permutation as an array */
1345  int crit, /**< critical entry where optimality is found at */
1346  int* maxsolu /**< pointer to the optimal objective array */
1347  )
1348 {
1349  /* Compute to which components all entries belong. */
1350  int* entrycomponent;
1351  SCIP_Real* componentobjective;
1352 
1353  int i;
1354  int c;
1355 
1356  assert( scip != NULL );
1357  assert( nvars > 0 );
1358  assert( objective != NULL );
1359  assert( perm != NULL );
1360  assert( invperm != NULL );
1361  assert( maxsolu != NULL );
1362  assert( crit >= 0 );
1363  assert( crit <= nvars );
1364 
1365  SCIP_CALL( SCIPallocBufferArray(scip, &entrycomponent, nvars) );
1366  SCIP_CALL( SCIPallocBufferArray(scip, &componentobjective, nvars) );
1367 
1368  /* Initially: Everything forms its own component */
1369  for (i = 0; i < nvars; ++i)
1370  {
1371  entrycomponent[i] = i;
1372  componentobjective[i] = objective[i];
1373  }
1374  for (i = 0; i < crit; ++i)
1375  {
1376  /* The graph with arcs {i, invperm[i]} if i < c is a collection of paths, cycles and singletons.
1377  * Label the vertices to the lowest entry in the component, and store the value of that in this component.
1378  * Every inner while-loop labels one new vertex per iteration, and a vertex is relabeled exactly once.
1379  */
1380  if ( entrycomponent[i] < i )
1381  {
1382  /* This entry is already included in a component. */
1383  continue;
1384  }
1385 
1386  /* Follow the path forward: Take edges {c, invperm[c]} until c >= crit, or a cycle is found. */
1387  c = i;
1388  while( c < crit )
1389  {
1390  /* c < crit, so edge {c, invperm[c]} exists. Label invperm[c] as part of component of i */
1391  c = invperm[c];
1392 
1393  /* Stop if we find a cycle. */
1394  if ( entrycomponent[c] != c )
1395  break;
1396 
1397  entrycomponent[c] = i;
1398  componentobjective[i] += objective[c];
1399  }
1400 
1401  /* Follow the path backward: Take edges {c, perm[c]} until perm[c] >= crit, or a cycle is found. */
1402  c = perm[i];
1403  while( c < crit )
1404  {
1405  /* c < crit, so edge {c, invperm[c]} exists. Label c as part of component of i */
1406 
1407  /* Stop if we find a cycle. */
1408  if ( entrycomponent[c] != c )
1409  break;
1410 
1411  entrycomponent[c] = i;
1412  componentobjective[i] += objective[c];
1413  /* For next iteration: We do another step back */
1414  c = perm[c];
1415  }
1416  }
1417 
1418  /* Now fill the objective vector.
1419  * For the component containing crit, set the value to 1.
1420  * For the component contraining invperm[crit], set the value to 0.
1421  * For the other components, set the value to 1 if the objective sum is positive.
1422  * Otherwise to 0.
1423  */
1424  for (i = 0; i < nvars; ++i)
1425  {
1426  if ( entrycomponent[i] == entrycomponent[crit] )
1427  maxsolu[i] = 1;
1428  else if ( entrycomponent[i] == entrycomponent[invperm[crit]] )
1429  maxsolu[i] = 0;
1430  else if ( SCIPisGT(scip, componentobjective[entrycomponent[i]], 0.0) )
1431  maxsolu[i] = 1;
1432  else
1433  maxsolu[i] = 0;
1434  }
1435 
1436  SCIPfreeBufferArray(scip, &componentobjective);
1437  SCIPfreeBufferArray(scip, &entrycomponent);
1438 
1439  return SCIP_OKAY;
1440 }
1441 
1442 
1443 /** separate symresack cover inequalities
1444  *
1445  * We currently do NOT enter cuts into the pool.
1446  */
1447 static
1449  SCIP* scip, /**< SCIP pointer */
1450  SCIP_CONS* cons, /**< constraint */
1451  const SCIP_CONSDATA* consdata, /**< constraint data */
1452  SCIP_Real* vals, /**< solution values of variables */
1453  int* ngen, /**< pointer to store the number of separated covers */
1454  SCIP_Bool* infeasible /**< pointer to store whether we detected infeasibility */
1455  )
1456 {
1457  SCIP_Real constobjective;
1458  SCIP_Real* sepaobjective;
1459  SCIP_Real maxsoluobj = 0.0;
1460  int* maxsolu;
1461  int* invperm;
1462  int* perm;
1463  int nvars;
1464  int maxcrit;
1465  int i;
1466 
1467  *infeasible = FALSE;
1468  *ngen = 0;
1469 
1470  assert( scip != NULL );
1471  assert( consdata != NULL );
1472 
1473  /* we do not have to take care of trivial constraints */
1474  if ( consdata->nvars < 2 )
1475  return SCIP_OKAY;
1476 
1477  assert( consdata->vars != NULL );
1478  assert( consdata->perm != NULL );
1479  assert( consdata->invperm != NULL );
1480  assert( infeasible != NULL );
1481  assert( ngen != NULL );
1482 
1483  nvars = consdata->nvars;
1484  perm = consdata->perm;
1485  invperm = consdata->invperm;
1486 
1487  /* initialize objective */
1488  SCIP_CALL( SCIPallocBufferArray(scip, &sepaobjective, nvars) );
1489 
1490  constobjective = 1.0; /* constant part of separation objective */
1491  for (i = 0; i < nvars; ++i)
1492  {
1493  if ( i < perm[i] )
1494  sepaobjective[i] = - vals[i];
1495  else
1496  {
1497  sepaobjective[i] = 1.0 - vals[i];
1498  constobjective += vals[i] - 1.0;
1499  }
1500  }
1501 
1502  /* allocate memory for temporary and global solution */
1503  SCIP_CALL( SCIPallocBufferArray(scip, &maxsolu, nvars) );
1504 
1505  /* Find critical row of a maximally violated cover */
1506  SCIP_CALL( maximizeObjectiveSymresackStrict(scip, nvars, sepaobjective, perm, invperm, &maxcrit, &maxsoluobj) );
1507  assert( maxcrit >= 0 );
1508  SCIPdebugMsg(scip, "Critical row %d found; Computing maximally violated cover.\n", maxcrit);
1509  SCIP_CALL( maximizeObjectiveSymresackCriticalEntry(scip, nvars, sepaobjective, perm, invperm, maxcrit, maxsolu) );
1510 
1511  /* Add constant to maxsoluobj to get the real objective */
1512  maxsoluobj += constobjective;
1513 
1514  /* Check whether the separation objective is positive, i.e., a violated cover was found. */
1515  if ( SCIPisEfficacious(scip, maxsoluobj) )
1516  {
1517  /* Now add the cut. Reuse array maxsolu as coefficient vector for the constraint. */
1518  SCIP_Real rhs = -1.0;
1519  for (i = 0; i < nvars; ++i)
1520  {
1521  if ( i < perm[i] )
1522  maxsolu[i] = -maxsolu[i];
1523  else
1524  {
1525  if ( maxsolu[i] == 0 )
1526  rhs += 1.0;
1527  maxsolu[i] = 1 - maxsolu[i];
1528  }
1529  }
1530 
1531  /* add cover inequality */
1532  SCIP_CALL( addSymresackInequality(scip, cons, nvars, consdata->vars, maxsolu, rhs, infeasible) );
1533 
1534  if ( ! *infeasible )
1535  ++(*ngen);
1536  }
1537 
1538  SCIPfreeBufferArrayNull(scip, &maxsolu);
1539  SCIPfreeBufferArrayNull(scip, &sepaobjective);
1540 
1541  return SCIP_OKAY;
1542 }
1543 
1544 
1545 /** check whether solution is feasible for symresacks */
1546 static
1548  SCIP* scip, /**< SCIP pointer */
1549  SCIP_CONS* cons, /**< constrained for which we check the solution */
1550  SCIP_SOL* sol, /**< solution to be checked */
1551  SCIP_RESULT* result, /**< pointer to store whether we detected infeasibility */
1552  SCIP_Bool printreason /**< whether reason for infeasibility should be printed */
1553  )
1554 {
1555  SCIP_CONSDATA* consdata;
1556  SCIP_VAR** vars;
1557  int* invperm;
1558  int nvars;
1559  int i;
1560 
1561  assert( cons != NULL );
1562  consdata = SCIPconsGetData(cons);
1563  assert( consdata != NULL);
1564 
1565  /* we do not have to take care of trivial constraints */
1566  if ( consdata->nvars < 2 )
1567  return SCIP_OKAY;
1568 
1569  assert( consdata->vars != NULL );
1570  assert( consdata->invperm != NULL );
1571 
1572  SCIPdebugMsg(scip, "Check method for symresack constraint <%s> (%d rows) ...\n", SCIPconsGetName(cons), consdata->nvars);
1573 
1574  nvars = consdata->nvars;
1575  vars = consdata->vars;
1576  invperm = consdata->invperm;
1577 
1578  /* detect first non-constant pair of variables */
1579  for (i = 0; i < nvars; ++i)
1580  {
1581  SCIP_Real solval;
1582  int val1;
1583  int val2;
1584 
1585  /* there are no fixed points */
1586  assert( invperm[i] != i );
1587 
1588  /* get value of variable i and its inverse */
1589  solval = SCIPgetSolVal(scip, sol, vars[i]);
1590  assert( SCIPisFeasIntegral(scip, solval) );
1591  if ( solval > 0.5 )
1592  val1 = 1;
1593  else
1594  val1 = 0;
1595 
1596  solval = SCIPgetSolVal(scip, sol, vars[invperm[i]]);
1597  assert( SCIPisFeasIntegral(scip, solval) );
1598  if ( solval > 0.5 )
1599  val2 = 1;
1600  else
1601  val2 = 0;
1602 
1603  /* if we detected a constant pair */
1604  if ( val1 == val2 )
1605  continue;
1606  /* pair is (1,0) --> lexicographically maximal */
1607  else if ( val1 > val2 )
1608  break;
1609 
1610  /* pair is (0,1) --> solution is infeasible */
1611  assert( val2 > val1 );
1612  SCIPdebugMsg(scip, "Solution is infeasible.\n");
1613  *result = SCIP_INFEASIBLE;
1614 
1615  if ( printreason )
1616  SCIPinfoMessage(scip, NULL, "First non-constant pair (%d, %d) of variables has pattern (0,1).\n", i, invperm[i]);
1617 
1618  break;
1619  }
1620 
1621  return SCIP_OKAY;
1622 }
1623 
1624 
1625 /** Upgrade symresack constraints to orbisacks */
1626 static
1628  SCIP* scip, /**< SCIP pointer */
1629  SCIP_CONS** cons, /**< pointer to hold the created constraint */
1630  const char* name, /**< name of constraint */
1631  int* perm, /**< permutation */
1632  SCIP_VAR** inputvars, /**< permuted variables array */
1633  int nvars, /**< size of perm array */
1634  SCIP_Bool* upgrade, /**< whether constraint was upgraded */
1635  SCIP_Bool ismodelcons, /**< whether the symresack is a model constraint */
1636  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
1637  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
1638  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
1639  * Usually set to TRUE. */
1640  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
1641  * TRUE for model constraints, FALSE for additional, redundant constraints. */
1642  SCIP_Bool check, /**< should the constraint be checked for feasibility?
1643  * TRUE for model constraints, FALSE for additional, redundant constraints. */
1644  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
1645  * Usually set to TRUE. */
1646  SCIP_Bool local, /**< is constraint only valid locally?
1647  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
1648  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
1649  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
1650  * adds coefficients to this constraint. */
1651  SCIP_Bool dynamic, /**< is constraint subject to aging?
1652  * Usually set to FALSE. Set to TRUE for own cuts which
1653  * are separated as constraints. */
1654  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
1655  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
1656  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
1657  * if it may be moved to a more global node?
1658  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
1659  )
1660 {
1661  SCIP_CONSHDLR* conshdlr;
1662  SCIP_VAR** vars1;
1663  SCIP_VAR** vars2;
1664  int nrows = 0;
1665  int i;
1666 
1667  assert( scip != NULL );
1668  assert( perm != NULL );
1669  assert( nvars > 0 );
1670  assert( inputvars != NULL );
1671  assert( upgrade != NULL );
1672 
1673  *upgrade = TRUE;
1674 
1675  /* check whether orbisack conshdlr is available */
1676  conshdlr = SCIPfindConshdlr(scip, "orbisack");
1677  if ( conshdlr == NULL )
1678  {
1679  *upgrade = FALSE;
1680  SCIPdebugMsg(scip, "Cannot check whether symresack constraint can be upgraded to orbisack constraint. ");
1681  SCIPdebugMsg(scip, "---> Orbisack constraint handler not found.\n");
1682 
1683  return SCIP_OKAY;
1684  }
1685 
1686  SCIP_CALL( SCIPallocBufferArray(scip, &vars1, nvars) );
1687  SCIP_CALL( SCIPallocBufferArray(scip, &vars2, nvars) );
1688 
1689  /* check whether permutation is a composition of 2-cycles */
1690  for (i = 0; i < nvars; ++i)
1691  {
1692  /* ignore non-binary variables */
1693  if ( ! SCIPvarIsBinary(inputvars[i]) )
1694  continue;
1695 
1696  if ( perm[perm[i]] != i )
1697  {
1698  *upgrade = FALSE;
1699  break;
1700  }
1701 
1702  if ( perm[i] > i )
1703  {
1704  vars1[nrows] = inputvars[i];
1705  vars2[nrows++] = inputvars[perm[i]];
1706 
1707  assert( nrows <= nvars );
1708  }
1709  }
1710 
1711  /* if permutation can be upgraded to an orbisack */
1712  if ( nrows == 0 )
1713  *upgrade = FALSE;
1714  else if ( *upgrade )
1715  {
1716  SCIP_CALL( SCIPcreateConsOrbisack(scip, cons, name, vars1, vars2, nrows, FALSE, FALSE, ismodelcons,
1717  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
1718  }
1719 
1720  SCIPfreeBufferArray(scip, &vars2);
1721  SCIPfreeBufferArray(scip, &vars1);
1722 
1723  return SCIP_OKAY;
1724 }
1725 
1726 
1727 /** creates a symmetry breaking constraint
1728  *
1729  * Depending on the given permutation, either an orbisack or symresack constraint
1730  * is created.
1731  */
1733  SCIP* scip, /**< SCIP data structure */
1734  SCIP_CONS** cons, /**< pointer to hold the created constraint */
1735  const char* name, /**< name of constraint */
1736  int* perm, /**< permutation */
1737  SCIP_VAR** vars, /**< variables */
1738  int nvars, /**< number of variables in vars array */
1739  SCIP_Bool ismodelcons, /**< whether the added constraint is a model constraint */
1740  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
1741  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
1742  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
1743  * Usually set to TRUE. */
1744  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
1745  * TRUE for model constraints, FALSE for additional, redundant constraints. */
1746  SCIP_Bool check, /**< should the constraint be checked for feasibility?
1747  * TRUE for model constraints, FALSE for additional, redundant constraints. */
1748  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
1749  * Usually set to TRUE. */
1750  SCIP_Bool local, /**< is constraint only valid locally?
1751  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
1752  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
1753  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
1754  * adds coefficients to this constraint. */
1755  SCIP_Bool dynamic, /**< is constraint subject to aging?
1756  * Usually set to FALSE. Set to TRUE for own cuts which
1757  * are separated as constraints. */
1758  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
1759  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
1760  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
1761  * if it may be moved to a more global node?
1762  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
1763  )
1764 {
1765  SCIP_Bool upgrade = FALSE;
1766 
1767  assert( scip != NULL );
1768  assert( cons != NULL );
1769  assert( perm != NULL );
1770  assert( vars != NULL );
1771  assert( nvars > 0 );
1772 
1773  SCIP_CALL( orbisackUpgrade(scip, cons, name, perm, vars, nvars, &upgrade, ismodelcons,
1774  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
1775 
1776  if ( ! upgrade )
1777  {
1778  SCIP_CALL( SCIPcreateConsSymresack(scip, cons, name, perm, vars, nvars, ismodelcons,
1779  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
1780  }
1781 
1782  return SCIP_OKAY;
1783 }
1784 
1785 
1786 /*--------------------------------------------------------------------------------------------
1787  *--------------------------------- SCIP functions -------------------------------------------
1788  *--------------------------------------------------------------------------------------------*/
1789 
1790 /** copy method for constraint handler plugins (called when SCIP copies plugins) */
1791 static
1792 SCIP_DECL_CONSHDLRCOPY(conshdlrCopySymresack)
1793 { /*lint --e{715}*/
1794  assert(scip != NULL);
1795  assert(conshdlr != NULL);
1796  assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1797 
1798  /* call inclusion method of constraint handler */
1800 
1801  *valid = TRUE;
1802 
1803  return SCIP_OKAY;
1804 }
1805 
1806 
1807 /** frees specific constraint data */
1808 static
1809 SCIP_DECL_CONSDELETE(consDeleteSymresack)
1810 { /*lint --e{715}*/
1811  assert( scip != NULL );
1812  assert( conshdlr != NULL );
1813  assert( consdata != NULL );
1814  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1815 
1816  SCIP_CALL( consdataFree(scip, consdata) );
1817 
1818  return SCIP_OKAY;
1819 }
1820 
1821 
1822 /** frees constraint handler */
1823 static
1824 SCIP_DECL_CONSFREE(consFreeSymresack)
1825 { /*lint --e{715}*/
1826  SCIP_CONSHDLRDATA* conshdlrdata;
1827 
1828  assert( scip != NULL );
1829  assert( conshdlr != NULL );
1830  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1831 
1832  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1833  assert( conshdlrdata != NULL );
1834 
1835  SCIPfreeBlockMemory(scip, &conshdlrdata);
1836 
1837  return SCIP_OKAY;
1838 }
1839 
1840 
1841 /** transforms constraint data into data belonging to the transformed problem */
1842 static
1843 SCIP_DECL_CONSTRANS(consTransSymresack)
1845  SCIP_CONSDATA* sourcedata;
1846  SCIP_CONSDATA* consdata = NULL;
1847  int nvars;
1848  int i;
1849 
1850  assert( scip != NULL );
1851  assert( conshdlr != NULL );
1852  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1853  assert( sourcecons != NULL );
1854  assert( targetcons != NULL );
1855 
1856  SCIPdebugMsg(scip, "Transforming constraint.\n");
1857 
1858  /* get data of original constraint */
1859  sourcedata = SCIPconsGetData(sourcecons);
1860  assert( sourcedata != NULL);
1861 
1862  /* constraint might be empty and not deleted if no presolving took place */
1863  assert( sourcedata->nvars == 0 || sourcedata->vars != NULL );
1864  assert( sourcedata->nvars == 0 || sourcedata->perm != NULL );
1865  assert( sourcedata->nvars == 0 || sourcedata->invperm != NULL );
1866 #ifndef NDEBUG
1867  if ( sourcedata->ppupgrade )
1868  {
1869  assert( sourcedata->nvars > 0 );
1870  assert( sourcedata->ncycles != 0 );
1871  assert( sourcedata->cycledecomposition != NULL );
1872  for (i = 0; i < sourcedata->ncycles; ++i)
1873  {
1874  assert( sourcedata->cycledecomposition[i] != NULL );
1875  assert( sourcedata->cycledecomposition[i][0] != 0 );
1876  }
1877  }
1878 #endif
1879 
1880  /* create transformed constraint data
1881  *
1882  * do NOT call consdataCreate() again to avoid doing the packing-upgrade check twice
1883  */
1884  nvars = sourcedata->nvars;
1885 
1886  SCIP_CALL( SCIPallocBlockMemory(scip, &consdata) );
1887 
1888  consdata->vars = NULL;
1889  consdata->nvars = nvars;
1890  consdata->perm = NULL;
1891  consdata->invperm = NULL;
1892  consdata->ppupgrade = sourcedata->ppupgrade;
1893  consdata->ismodelcons = sourcedata->ismodelcons;
1894 #ifdef SCIP_DEBUG
1895  consdata->debugcnt = 0;
1896 #endif
1897  consdata->ncycles = 0;
1898  consdata->cycledecomposition = NULL;
1899  consdata->ndescentpoints = 0;
1900  consdata->descentpoints = NULL;
1901 
1902  if ( nvars > 0 )
1903  {
1904  SCIP_CALL( SCIPallocBlockMemoryArray(scip, &consdata->vars, nvars) );
1905  SCIP_CALL( SCIPgetTransformedVars(scip, nvars, sourcedata->vars, consdata->vars) );
1906  for (i = 0; i < nvars; ++i)
1907  {
1908  SCIP_CALL( SCIPcaptureVar(scip, consdata->vars[i]) );
1909  }
1910 
1911  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->perm, sourcedata->perm, nvars) );
1912  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->invperm, sourcedata->invperm, nvars) );
1913 
1914  if ( sourcedata->ppupgrade )
1915  {
1916  consdata->ncycles = sourcedata->ncycles;
1917  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->cycledecomposition, sourcedata->cycledecomposition, sourcedata->ncycles) );
1918  for (i = 0; i < sourcedata->ncycles; ++i)
1919  {
1920  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->cycledecomposition[i], sourcedata->cycledecomposition[i], nvars + 1) ); /*lint !e866*/
1921  }
1922 
1923  consdata->ndescentpoints = sourcedata->ndescentpoints;
1924  SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &consdata->descentpoints, sourcedata->descentpoints, sourcedata->ndescentpoints) );
1925  }
1926 
1927  /* Make sure that all variables cannot be multiaggregated (this cannot be handled by cons_symresack, since one cannot
1928  * easily eliminate single variables from a symresack constraint).
1929  *
1930  * We need to call this again to ensure that multiaggregation is forbidden also if the constraint was part
1931  * of the original problem.
1932  */
1933  for (i = 0; i < sourcedata->nvars; ++i)
1934  {
1935  SCIP_CALL( SCIPgetTransformedVar(scip, consdata->vars[i], &consdata->vars[i]) );
1936  SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, consdata->vars[i]) );
1937  }
1938  }
1939 
1940  /* create transformed constraint */
1941  SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, consdata,
1942  SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons),
1943  SCIPconsIsEnforced(sourcecons), SCIPconsIsChecked(sourcecons),
1944  SCIPconsIsPropagated(sourcecons), SCIPconsIsLocal(sourcecons),
1945  SCIPconsIsModifiable(sourcecons), SCIPconsIsDynamic(sourcecons),
1946  SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
1947 
1948  return SCIP_OKAY;
1949 }
1950 
1951 
1952 /** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
1953 static
1954 SCIP_DECL_CONSINITLP(consInitlpSymresack)
1956  int c;
1957  SCIP_CONSHDLRDATA* conshdlrdata;
1958 
1959  assert( infeasible != NULL );
1960  *infeasible = FALSE;
1961 
1962  assert( scip != NULL );
1963  assert( conshdlr != NULL );
1964  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1965 
1966  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1967  assert( conshdlrdata != NULL );
1968 
1969  /* loop through constraints */
1970  for (c = 0; c < nconss; ++c)
1971  {
1972  assert( conss[c] != NULL );
1973 
1974  SCIPdebugMsg(scip, "Generating initial symresack cut for constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1975 
1976  SCIP_CALL( initLP(scip, conss[c], conshdlrdata->checkmonotonicity, infeasible) );
1977  if ( *infeasible )
1978  break;
1979  }
1980  SCIPdebugMsg(scip, "Generated initial symresack cuts.\n");
1981 
1982  return SCIP_OKAY;
1983 }
1984 
1985 
1986 /** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */
1987 static
1988 SCIP_DECL_CONSINITSOL(consInitsolSymresack)
1990  SCIP_CONSHDLRDATA* conshdlrdata;
1991  int c;
1992 
1993  assert( scip != NULL );
1994  assert( conshdlr != NULL );
1995  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1996 
1997  /* determine maximum number of vars in a symresack constraint */
1998  conshdlrdata = SCIPconshdlrGetData(conshdlr);
1999  assert( conshdlrdata != NULL );
2000 
2001  conshdlrdata->maxnvars = 0;
2002 
2003  /* loop through constraints */
2004  for (c = 0; c < nconss; ++c)
2005  {
2006  SCIP_CONSDATA* consdata;
2007 
2008  assert( conss[c] != NULL );
2009 
2010  consdata = SCIPconsGetData(conss[c]);
2011  assert( consdata != NULL );
2012 
2013  /* update conshdlrdata if necessary */
2014  if ( consdata->nvars > conshdlrdata->maxnvars )
2015  conshdlrdata->maxnvars = consdata->nvars;
2016  }
2017 
2018  return SCIP_OKAY;
2019 }
2020 
2021 
2022 /** separation method of constraint handler for LP solution */
2023 static
2024 SCIP_DECL_CONSSEPALP(consSepalpSymresack)
2025 { /*lint --e{715}*/
2026  SCIP_CONSHDLRDATA* conshdlrdata;
2027  SCIP_CONSDATA* consdata;
2028  SCIP_Real* vals;
2029  int maxnvars;
2030  int c;
2031 
2032  assert( scip != NULL );
2033  assert( conshdlr != NULL );
2034  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2035  assert( result != NULL );
2036 
2037  SCIPdebugMsg(scip, "Separation method for symresack constraints\n");
2038 
2039  *result = SCIP_DIDNOTRUN;
2040 
2041  /* if solution is not integer */
2042  if ( SCIPgetNLPBranchCands(scip) == 0 )
2043  return SCIP_OKAY;
2044 
2045  if ( nconss == 0 )
2046  return SCIP_OKAY;
2047 
2048  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2049  assert( conshdlrdata != NULL );
2050 
2051  maxnvars = conshdlrdata->maxnvars;
2052  assert( maxnvars > 0 );
2053 
2054  SCIP_CALL( SCIPallocBufferArray(scip, &vals, maxnvars) );
2055 
2056  /* loop through constraints */
2057  for (c = 0; c < nconss; ++c)
2058  {
2059  SCIP_Bool infeasible = FALSE;
2060  int ngen = 0;
2061 
2062  SCIPdebugMsg(scip, "Separating symresack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
2063 
2064  /* get data of constraint */
2065  assert( conss[c] != NULL );
2066  consdata = SCIPconsGetData(conss[c]);
2067 
2068  if ( consdata->nvars == 0 )
2069  continue;
2070 
2071  /* get solution */
2072  assert( consdata->nvars <= maxnvars );
2073  SCIP_CALL( SCIPgetSolVals(scip, NULL, consdata->nvars, consdata->vars, vals) );
2074  SCIP_CALL( separateSymresackCovers(scip, conss[c], consdata, vals, &ngen, &infeasible) );
2075 
2076  if ( infeasible )
2077  {
2078  *result = SCIP_CUTOFF;
2079  SCIPfreeBufferArray(scip, &vals);
2080 
2081  return SCIP_OKAY;
2082  }
2083 
2084  if ( ngen > 0 )
2085  *result = SCIP_SEPARATED;
2086 
2087  if ( *result == SCIP_DIDNOTRUN )
2088  *result = SCIP_DIDNOTFIND;
2089  }
2090  SCIPfreeBufferArray(scip, &vals);
2091 
2092  return SCIP_OKAY;
2093 }
2094 
2095 
2096 /** separation method of constraint handler for arbitrary primal solution */
2097 static
2098 SCIP_DECL_CONSSEPASOL(consSepasolSymresack)
2099 { /*lint --e{715}*/
2100  SCIP_CONSHDLRDATA* conshdlrdata;
2101  SCIP_CONSDATA* consdata;
2102  SCIP_Real* vals;
2103  int maxnvars;
2104  int c;
2105 
2106  assert( scip != NULL );
2107  assert( conshdlr != NULL );
2108  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2109  assert( result != NULL );
2110 
2111  SCIPdebugMsg(scip, "Separation method for symresack constraints\n");
2112 
2113  *result = SCIP_DIDNOTRUN;
2114 
2115  if ( nconss == 0 )
2116  return SCIP_OKAY;
2117 
2118  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2119  assert( conshdlrdata != NULL );
2120 
2121  maxnvars = conshdlrdata->maxnvars;
2122  assert( maxnvars > 0 );
2123 
2124  SCIP_CALL( SCIPallocBufferArray(scip, &vals, maxnvars) );
2125 
2126  /* loop through constraints */
2127  for (c = 0; c < nconss; ++c)
2128  {
2129  SCIP_Bool infeasible = FALSE;
2130  int ngen = 0;
2131 
2132  SCIPdebugMsg(scip, "Separating symresack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
2133 
2134  /* get data of constraint */
2135  assert( conss[c] != NULL );
2136  consdata = SCIPconsGetData(conss[c]);
2137 
2138  if ( consdata->nvars == 0 )
2139  continue;
2140 
2141  /* get solution */
2142  assert( consdata->nvars <= maxnvars );
2143  SCIP_CALL( SCIPgetSolVals(scip, sol, consdata->nvars, consdata->vars, vals) );
2144  SCIP_CALL( separateSymresackCovers(scip, conss[c], consdata, vals, &ngen, &infeasible) );
2145 
2146  if ( infeasible )
2147  {
2148  *result = SCIP_CUTOFF;
2149  SCIPfreeBufferArray(scip, &vals);
2150 
2151  return SCIP_OKAY;
2152  }
2153 
2154  if ( ngen > 0 )
2155  *result = SCIP_SEPARATED;
2156 
2157  if ( *result == SCIP_DIDNOTRUN )
2158  *result = SCIP_DIDNOTFIND;
2159  }
2160  SCIPfreeBufferArray(scip, &vals);
2161 
2162  return SCIP_OKAY;
2163 }
2164 
2165 
2166 /** constraint enforcing method of constraint handler for LP solutions.
2167  *
2168  * To check feasibility, we separate cover inequalities.
2169  *
2170  * @pre It is assumed that the solution is integral (this can be ensured by appropriate priorities).
2171  */
2172 static
2173 SCIP_DECL_CONSENFOLP(consEnfolpSymresack)
2174 { /*lint --e{715}*/
2175  SCIP_CONSDATA* consdata;
2176  int c;
2177 
2178  assert( scip != NULL );
2179  assert( conshdlr != NULL );
2180  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2181  assert( result != NULL );
2182 
2183  SCIPdebugMsg(scip, "Enforcing method for symresack constraints (lp solutions) ...\n");
2184 
2185  /* we have a negative priority, so we should come after the integrality conshdlr. */
2186  assert( SCIPgetNLPBranchCands(scip) == 0 );
2187 
2188  *result = SCIP_FEASIBLE;
2189 
2190  if ( nconss > 0 )
2191  {
2192  SCIP_CONSHDLRDATA* conshdlrdata;
2193  SCIP_Real* vals;
2194  int maxnvars;
2195 
2196  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2197  assert( conshdlrdata != NULL );
2198 
2199  maxnvars = conshdlrdata->maxnvars;
2200  assert( maxnvars > 0 );
2201 
2202  SCIP_CALL( SCIPallocBufferArray(scip, &vals, maxnvars) );
2203 
2204  /* loop through constraints */
2205  for (c = 0; c < nconss; ++c)
2206  {
2207  SCIP_Bool infeasible = FALSE;
2208  int ngen = 0;
2209 
2210  SCIPdebugMsg(scip, "Enforcing symresack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
2211 
2212  /* get data of constraint */
2213  assert( conss[c] != NULL );
2214  consdata = SCIPconsGetData(conss[c]);
2215  assert( consdata != NULL );
2216 
2217  /* do not enforce non-model constraints */
2218  if ( !consdata->ismodelcons )
2219  continue;
2220 
2221  if ( consdata->nvars == 0 )
2222  continue;
2223 
2224  /* get solution */
2225  assert( consdata->nvars <= maxnvars );
2226  SCIP_CALL( SCIPgetSolVals(scip, NULL, consdata->nvars, consdata->vars, vals) );
2227  SCIP_CALL( separateSymresackCovers(scip, conss[c], consdata, vals, &ngen, &infeasible) );
2228 
2229  if ( infeasible )
2230  {
2231  *result = SCIP_CUTOFF;
2232  SCIPfreeBufferArray(scip, &vals);
2233 
2234  return SCIP_OKAY;
2235  }
2236 
2237  /* SCIPdebugMsg(scip, "Generated symresack inequalities for <%s>: %d\n", SCIPconsGetName(conss[c]), ngen); */
2238 
2239  if ( ngen > 0 )
2240  *result = SCIP_SEPARATED;
2241  }
2242  SCIPfreeBufferArray(scip, &vals);
2243  }
2244 
2245  return SCIP_OKAY;
2246 }
2247 
2248 
2249 /** constraint enforcing method of constraint handler for pseudo solutions */
2250 static
2251 SCIP_DECL_CONSENFOPS(consEnfopsSymresack)
2252 { /*lint --e{715}*/
2253  SCIP_CONSDATA* consdata;
2254  int c;
2255 
2256  assert( scip != NULL );
2257  assert( conshdlr != NULL );
2258  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2259  assert( result != NULL );
2260 
2261  SCIPdebugMsg(scip, "Enforcing method for symresack constraints (pseudo solutions) ...\n");
2262 
2263  *result = SCIP_FEASIBLE;
2264 
2265  if ( objinfeasible || solinfeasible )
2266  return SCIP_OKAY;
2267 
2268  /* loop through constraints */
2269  for (c = 0; c < nconss; ++c)
2270  {
2271  consdata = SCIPconsGetData(conss[c]);
2272  assert( consdata != NULL );
2273 
2274  /* do not enforce non-model constraints */
2275  if ( !consdata->ismodelcons )
2276  continue;
2277 
2278  SCIP_CALL( checkSymresackSolution(scip, conss[c], NULL, result, FALSE) );
2279 
2280  if ( *result == SCIP_INFEASIBLE )
2281  break;
2282  }
2283 
2284  return SCIP_OKAY;
2285 }
2286 
2287 
2288 /** constraint enforcing method of constraint handler for relaxation solutions
2289  *
2290  * To check feasibility, we separate cover inequalities.
2291  *
2292  */
2293 static
2294 SCIP_DECL_CONSENFORELAX(consEnforelaxSymresack)
2295 { /*lint --e{715}*/
2296  SCIP_CONSDATA* consdata;
2297  int c;
2298 
2299  assert( scip != NULL );
2300  assert( conshdlr != NULL );
2301  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2302  assert( result != NULL );
2303 
2304  SCIPdebugMsg(scip, "Enforcing method for symresack constraints (relaxation solutions) ...\n");
2305 
2306  /* we have a negative priority, so we should come after the integrality conshdlr. */
2307  assert( SCIPgetNLPBranchCands(scip) == 0 );
2308 
2309  *result = SCIP_FEASIBLE;
2310 
2311  if ( nconss > 0 )
2312  {
2313  SCIP_CONSHDLRDATA* conshdlrdata;
2314  SCIP_Real* vals;
2315  int maxnvars;
2316 
2317  conshdlrdata = SCIPconshdlrGetData(conshdlr);
2318  assert( conshdlrdata != NULL );
2319 
2320  maxnvars = conshdlrdata->maxnvars;
2321  assert( maxnvars > 0 );
2322 
2323  SCIP_CALL( SCIPallocBufferArray(scip, &vals, maxnvars) );
2324 
2325  /* loop through constraints */
2326  for (c = 0; c < nconss; ++c)
2327  {
2328  SCIP_Bool infeasible = FALSE;
2329  int ngen = 0;
2330 
2331  SCIPdebugMsg(scip, "Enforcing symresack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
2332 
2333  /* get data of constraint */
2334  assert( conss[c] != NULL );
2335  consdata = SCIPconsGetData(conss[c]);
2336  assert( consdata != NULL );
2337 
2338  /* do not enforce non-model constraints */
2339  if ( !consdata->ismodelcons )
2340  continue;
2341 
2342  if ( consdata->nvars == 0 )
2343  continue;
2344 
2345  /* get solution */
2346  assert( consdata->nvars <= maxnvars );
2347  SCIP_CALL( SCIPgetSolVals(scip, sol, consdata->nvars, consdata->vars, vals) );
2348  SCIP_CALL( separateSymresackCovers(scip, conss[c], consdata, vals, &ngen, &infeasible) );
2349 
2350  if ( infeasible )
2351  {
2352  *result = SCIP_CUTOFF;
2353  SCIPfreeBufferArray(scip, &vals);
2354 
2355  return SCIP_OKAY;
2356  }
2357 
2358  if ( ngen > 0 )
2359  *result = SCIP_SEPARATED;
2360  }
2361  SCIPfreeBufferArray(scip, &vals);
2362  }
2363 
2364  return SCIP_OKAY;
2365 }
2366 
2367 
2368 /** feasibility check method of constraint handler for integral solutions */
2369 static
2370 SCIP_DECL_CONSCHECK(consCheckSymresack)
2371 { /*lint --e{715}*/
2372  SCIP_CONSDATA* consdata;
2373  int c;
2374 
2375  assert( scip != NULL );
2376  assert( conshdlr != NULL );
2377  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2378  assert( result != NULL );
2379 
2380  *result = SCIP_FEASIBLE;
2381 
2382  /* loop through constraints */
2383  for (c = 0; c < nconss; ++c)
2384  {
2385  consdata = SCIPconsGetData(conss[c]);
2386  assert( consdata != NULL );
2387 
2388  /* do not check non-model constraints */
2389  if ( !consdata->ismodelcons )
2390  continue;
2391 
2392  SCIP_CALL( checkSymresackSolution(scip, conss[c], sol, result, printreason) );
2393 
2394  if ( *result == SCIP_INFEASIBLE )
2395  break;
2396  }
2397 
2398  if ( *result == SCIP_FEASIBLE )
2399  SCIPdebugMsg(scip, "Solution is feasible.\n");
2400 
2401  return SCIP_OKAY;
2402 }
2403 
2404 
2405 /** domain propagation method of constraint handler */
2406 static
2407 SCIP_DECL_CONSPROP(consPropSymresack)
2408 { /*lint --e{715}*/
2409  int c;
2410  SCIP_Bool success = FALSE;
2411 
2412  assert( scip != NULL );
2413  assert( conshdlr != NULL );
2414  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2415  assert( result != NULL );
2416 
2417  *result = SCIP_DIDNOTRUN;
2418 
2419  SCIPdebugMsg(scip, "Propagation method of symresack constraint handler.\n");
2420 
2421  /* loop through constraints */
2422  for (c = 0; c < nconss; ++c)
2423  {
2424  SCIP_Bool infeasible = FALSE;
2425  int ngen = 0;
2426 
2427  assert( conss[c] != NULL );
2428 
2429  SCIP_CALL( propVariables(scip, conss[c], &infeasible, &ngen) );
2430 
2431  if ( infeasible )
2432  {
2433  *result = SCIP_CUTOFF;
2434  return SCIP_OKAY;
2435  }
2436 
2437  success = success || ( ngen > 0 );
2438 
2439  *result = SCIP_DIDNOTFIND;
2440  }
2441 
2442  if ( success )
2443  {
2444  *result = SCIP_REDUCEDDOM;
2445  return SCIP_OKAY;
2446  }
2447 
2448  return SCIP_OKAY;
2449 }
2450 
2451 
2452 /** presolving method of constraint handler */
2453 static
2454 SCIP_DECL_CONSPRESOL(consPresolSymresack)
2455 { /*lint --e{715}*/
2456  int c;
2457  SCIP_Bool success = FALSE;
2458  int oldndelconss;
2459 
2460  assert( scip != NULL );
2461  assert( conshdlr != NULL );
2462  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2463  assert( result != NULL );
2464 
2465  oldndelconss = *ndelconss;
2466 
2467  SCIPdebugMsg(scip, "Presolving method of symresack constraint handler. Propagating symresack inequalities.\n");
2468  *result = SCIP_DIDNOTRUN;
2469 
2470  /* loop through constraints */
2471  for (c = 0; c < nconss; ++c)
2472  {
2473  SCIP_Bool infeasible = FALSE;
2474  SCIP_CONSDATA* consdata;
2475  int ngen = 0;
2476 
2477  assert( conss[c] != NULL );
2478 
2479  consdata = SCIPconsGetData(conss[c]);
2480  assert( consdata != NULL );
2481 
2482  /* avoid trivial problems */
2483  if ( consdata->nvars == 0 )
2484  {
2485  SCIP_CALL( SCIPdelCons(scip, conss[c]) );
2486  (*ndelconss)++;
2487  }
2488  else
2489  {
2490  SCIP_CALL( propVariables(scip, conss[c], &infeasible, &ngen) );
2491  }
2492 
2493  if ( infeasible )
2494  {
2495  *result = SCIP_CUTOFF;
2496  break;
2497  }
2498 
2499  if ( ngen > 0 )
2500  {
2501  *nfixedvars += ngen;
2502  success = TRUE;
2503  }
2504 
2505  *result = SCIP_DIDNOTFIND;
2506  }
2507 
2508  if ( *ndelconss > oldndelconss || success )
2509  *result = SCIP_SUCCESS;
2510 
2511  return SCIP_OKAY;
2512 }
2513 
2514 
2515 /** Propagation resolution for conflict analysis */
2516 static
2517 SCIP_DECL_CONSRESPROP(consRespropSymresack)
2518 { /*lint --e{715}*/
2519  SCIP_CONSDATA* consdata;
2520  SCIP_VAR** vars;
2521  int* perm;
2522  int* invperm;
2523  int nvars;
2524  int i;
2525  int varrow;
2526  int infrow;
2527 
2528  assert( scip != NULL );
2529  assert( conshdlr != NULL );
2530  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2531  assert( cons != NULL );
2532  assert( infervar != NULL );
2533  assert( bdchgidx != NULL );
2534  assert( result != NULL );
2535 
2536  SCIPdebugMsg(scip, "Propagation resolution method of symresack constraint handler.\n");
2537 
2538  *result = SCIP_DIDNOTFIND;
2539 
2540  consdata = SCIPconsGetData(cons);
2541  assert( consdata != NULL );
2542 
2543  /* we do not have to take care of trivial constraints */
2544  if ( consdata->nvars < 2 )
2545  return SCIP_OKAY;
2546 
2547  assert( consdata->vars != NULL );
2548  assert( consdata->invperm != NULL );
2549 
2550  vars = consdata->vars;
2551  nvars = consdata->nvars;
2552  perm = consdata->perm;
2553  invperm = consdata->invperm;
2554 
2555  /* inferinfo == varrow + infrow * nvars.
2556  * infrow is 0 if the fixing is not caused by a lookahead.
2557  */
2558  varrow = inferinfo % nvars;
2559  infrow = inferinfo / nvars;
2560 
2561  assert( varrow >= 0 );
2562  assert( varrow < nvars );
2563  assert( infrow >= 0 );
2564  assert( infrow < nvars );
2565  assert( vars[varrow] == infervar || vars[invperm[varrow]] == infervar );
2566 
2567  /* Up to entry varrow the vectors x and perm[x] are equal. */
2568  for (i = 0; i < varrow; ++i)
2569  {
2570  /* Conflict caused by bounds of x[i] and perm(x)[i] = x[invperm[i]]. */
2571 
2572  /* No fixed points in the permutation. */
2573  assert( i != invperm[i] );
2574 
2575  /* Up to entry varrow the vectors x and perm[x] are fixed to the same value. */
2576  assert( ISFIXED(vars[i], bdchgidx) );
2577  assert( ISFIXED(vars[invperm[i]], bdchgidx) );
2578  assert( REALABS(SCIPvarGetUbAtIndex(vars[i], bdchgidx, FALSE) -
2579  SCIPvarGetUbAtIndex(vars[invperm[i]], bdchgidx, FALSE)) < 0.5 );
2580  assert( REALABS(SCIPvarGetLbAtIndex(vars[i], bdchgidx, FALSE) -
2581  SCIPvarGetLbAtIndex(vars[invperm[i]], bdchgidx, FALSE)) < 0.5 );
2582 
2583  /* At iteration i the vars x[i] and x[invperm[i]] are fixed.
2584  * So only new information is received if i < perm[i] (i.e. there is no j < i with j = invperm[i])
2585  * Or if invperm[i] > i.
2586  */
2587  if ( i < perm[i] )
2588  {
2589  assert( vars[i] != infervar );
2590  SCIP_CALL( SCIPaddConflictUb(scip, vars[i], bdchgidx) );
2591  SCIP_CALL( SCIPaddConflictLb(scip, vars[i], bdchgidx) );
2592  }
2593  if ( invperm[i] > i )
2594  {
2595  assert( vars[invperm[i]] != infervar );
2596  SCIP_CALL( SCIPaddConflictUb(scip, vars[invperm[i]], bdchgidx) );
2597  SCIP_CALL( SCIPaddConflictLb(scip, vars[invperm[i]], bdchgidx) );
2598  }
2599  }
2600 
2601  /* Case distinction: Fixing due to propagation or due to lookahead */
2602  if ( infrow > 0 )
2603  {
2604  /* The fixing of infervar is caused by a lookahead (checkFeasible)
2605  * Up to row "varrow" the entries x[i] and perm(x)[i] are forced to be equal
2606  * If x[varrow] = perm(x)[varrow] is assumed, then until infrow we find x[i] = perm(x)[i] ( = x[invperm[i]] )
2607  * and (x[infrow], perm(x)[infrow]) = (0, 1).
2608  */
2609 
2610  /* Everything after varrow to infrow is forced to a constant, and row infrow is (0, 1) */
2611  for (i = varrow + 1; i <= infrow; ++i)
2612  {
2613  /* Conflict caused by bounds of x[i] and perm(x)[i] = x[invperm[i]]. */
2614 
2615  /* No fixed points in the permutation. */
2616  assert( i != invperm[i] );
2617 
2618  /* The fixing are applied 'virtually', i.e. if varrow is considered constant, then fixings will follow.
2619  * Thus, between entries varrow and infrow of vectorx x and gamma(x) the entries do not have to be fixed.
2620  * For conflict analysis, only the fixed entries matter.
2621  */
2622  if ( ( i < perm[i] || i == invperm[varrow] ) && ISFIXED(vars[i], bdchgidx) )
2623  {
2624  assert( vars[i] != infervar );
2625  SCIP_CALL( SCIPaddConflictUb(scip, vars[i], bdchgidx) );
2626  SCIP_CALL( SCIPaddConflictLb(scip, vars[i], bdchgidx) );
2627  }
2628  if ( ( invperm[i] > i || invperm[i] == varrow ) && ISFIXED(vars[invperm[i]], bdchgidx) )
2629  {
2630  assert( vars[invperm[i]] != infervar );
2631  SCIP_CALL( SCIPaddConflictUb(scip, vars[invperm[i]], bdchgidx) );
2632  SCIP_CALL( SCIPaddConflictLb(scip, vars[invperm[i]], bdchgidx) );
2633  }
2634  }
2635  }
2636  else
2637  {
2638  /* This is not a fixing caused by lookahead (checkFeasible),
2639  * so row "varrow" was (0, _) or (_, 1) and for i < varrow x[i] = perm(x)[i].
2640  */
2641  if ( boundtype == SCIP_BOUNDTYPE_LOWER )
2642  {
2643  /* Changed the lower bound of infervar to 1. That means that this fixing is due to (_, 1) */
2644  assert( infervar == vars[varrow] );
2645  assert( ISFIXED(vars[invperm[varrow]], bdchgidx) );
2646 
2647  if ( invperm[varrow] > varrow )
2648  {
2649  SCIP_CALL( SCIPaddConflictUb(scip, vars[invperm[varrow]], bdchgidx) );
2650  SCIP_CALL( SCIPaddConflictLb(scip, vars[invperm[varrow]], bdchgidx) );
2651  }
2652  }
2653  else
2654  {
2655  /* Changed the lower bound of infervar to 0. That means that this fixing is due to (0, _) */
2656  assert( infervar == vars[invperm[varrow]] );
2657  assert( ISFIXED(vars[varrow], bdchgidx) );
2658 
2659  if ( varrow < perm[varrow] )
2660  {
2661  SCIP_CALL( SCIPaddConflictUb(scip, vars[varrow], bdchgidx) );
2662  SCIP_CALL( SCIPaddConflictLb(scip, vars[varrow], bdchgidx) );
2663  }
2664  }
2665  }
2666 
2667  *result = SCIP_SUCCESS;
2668 
2669  return SCIP_OKAY;
2670 }
2671 
2672 
2673 /** lock variables
2674  *
2675  * We assume we have only one global (void) constraint and lock all binary variables
2676  * which do not correspond to fixed points of the permutation.
2677  *
2678  * - Symresack constraints may get violated if the variables with a negative coefficient
2679  * in the FD inequality are rounded down, we therefor call
2680  * SCIPaddVarLocksType(..., nlockspos, nlocksneg).
2681  * - Symresack constraints may get violated if the variables with a positive coefficient
2682  * in the FD inequality are rounded up, we therefor call
2683  * SCIPaddVarLocksType(..., nlocksneg, nlockspo ).
2684  */
2685 static
2686 SCIP_DECL_CONSLOCK(consLockSymresack)
2687 { /*lint --e{715}*/
2688  SCIP_CONSDATA* consdata;
2689  SCIP_VAR** vars;
2690  int* perm;
2691  int nvars;
2692  int i;
2693 
2694  assert( scip != NULL );
2695  assert( conshdlr != NULL );
2696  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2697  assert( cons != NULL );
2698 
2699  SCIPdebugMsg(scip, "Locking method for symresack constraint handler.\n");
2700 
2701  /* get data of original constraint */
2702  consdata = SCIPconsGetData(cons);
2703  assert( consdata != NULL );
2704 
2705  /* we do not have to take care of trivial constraints */
2706  if ( consdata->nvars < 2 )
2707  return SCIP_OKAY;
2708 
2709  assert( consdata->vars != NULL );
2710  assert( consdata->perm != NULL );
2711 
2712  nvars = consdata->nvars;
2713  vars = consdata->vars;
2714  perm = consdata->perm;
2715 
2716  for (i = 0; i < nvars; ++i)
2717  {
2718  /* due to clean-up in consdataCreate, there are no fixed points */
2719  assert( perm[i] != i );
2720 
2721  if ( perm[i] > i )
2722  {
2723  SCIP_CALL( SCIPaddVarLocksType(scip, vars[i], locktype, nlockspos, nlocksneg) );
2724  }
2725  else
2726  {
2727  SCIP_CALL( SCIPaddVarLocksType(scip, vars[i], locktype, nlocksneg, nlockspos) );
2728  }
2729  }
2730 
2731  return SCIP_OKAY;
2732 }
2733 
2734 
2735 /** constraint copying method of constraint handler */
2736 static
2737 SCIP_DECL_CONSCOPY(consCopySymresack)
2739  SCIP_CONSHDLRDATA* conshdlrdata;
2740  SCIP_CONSDATA* sourcedata;
2741  SCIP_VAR** sourcevars;
2742  SCIP_VAR** vars;
2743  int nvars;
2744  int i;
2745 
2746  assert( scip != NULL );
2747  assert( cons != NULL );
2748  assert( sourcescip != NULL );
2749  assert( sourceconshdlr != NULL );
2750  assert( strcmp(SCIPconshdlrGetName(sourceconshdlr), CONSHDLR_NAME) == 0 );
2751  assert( sourcecons != NULL );
2752  assert( varmap != NULL );
2753  assert( valid != NULL );
2754 
2755  *valid = TRUE;
2756 
2757  SCIPdebugMsg(scip, "Copying method for symresack constraint handler.\n");
2758 
2759  sourcedata = SCIPconsGetData(sourcecons);
2760  assert( sourcedata != NULL );
2761  assert( sourcedata->vars != NULL );
2762  assert( sourcedata->perm != NULL );
2763  assert( sourcedata->nvars > 0 );
2764 
2765  conshdlrdata = SCIPconshdlrGetData(sourceconshdlr);
2766  assert( conshdlrdata != NULL );
2767 
2768  /* do not copy non-model constraints */
2769  if ( !sourcedata->ismodelcons && !conshdlrdata->forceconscopy )
2770  {
2771  *valid = FALSE;
2772 
2773  return SCIP_OKAY;
2774  }
2775 
2776  sourcevars = sourcedata->vars;
2777  nvars = sourcedata->nvars;
2778 
2779  SCIP_CALL( SCIPallocBufferArray(scip, &vars, nvars) );
2780 
2781  for (i = 0; i < nvars && *valid; ++i)
2782  {
2783  SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[i], &(vars[i]), varmap, consmap, global, valid) );
2784  assert( !(*valid) || vars[i] != NULL );
2785  }
2786 
2787  /* only create the target constraint, if all variables could be copied */
2788  if ( *valid )
2789  {
2790  /* create copied constraint */
2791  if ( name == NULL )
2792  name = SCIPconsGetName(sourcecons);
2793 
2794  SCIP_CALL( SCIPcreateConsSymresack(scip, cons, name, sourcedata->perm, vars, nvars, sourcedata->ismodelcons,
2795  initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
2796  }
2797 
2798  SCIPfreeBufferArray(scip, &vars);
2799 
2800  return SCIP_OKAY;
2801 }
2802 
2803 
2804 /** constraint parsing method of constraint handler */
2805 static
2806 SCIP_DECL_CONSPARSE(consParseSymresack)
2807 { /*lint --e{715}*/
2808  const char* s;
2809  char* endptr;
2810  SCIP_VAR** vars;
2811  SCIP_VAR* var;
2812  int* perm;
2813  int val;
2814  int nvars = 0;
2815  int cnt = 0;
2816  int nfoundpermidx = 0;
2817  int maxnvars = 128;
2818 
2819  assert( success != NULL );
2820 
2821  *success = TRUE;
2822  s = str;
2823 
2824  /* skip white space */
2825  SCIP_CALL( SCIPskipSpace((char**)&s) );
2826 
2827  if( strncmp(s, "symresack(", 10) != 0 )
2828  {
2829  SCIPerrorMessage("Syntax error - expected \"symresack(\", but got '%s'", s);
2830  *success = FALSE;
2831  return SCIP_OKAY;
2832  }
2833  s += 10;
2834 
2835  /* loop through string */
2836  SCIP_CALL( SCIPallocBufferArray(scip, &vars, maxnvars) );
2837  SCIP_CALL( SCIPallocBufferArray(scip, &perm, maxnvars) );
2838 
2839  do
2840  {
2841  if( cnt > 1 )
2842  {
2843  SCIPerrorMessage("expected two arrays, but got more\n");
2844  *success = FALSE;
2845  break;
2846  }
2847 
2848  /* skip whitespace */
2849  SCIP_CALL( SCIPskipSpace((char**)&s) );
2850 
2851  /* skip ',' */
2852  if( *s == ',' )
2853  ++s;
2854 
2855  /* skip whitespace */
2856  SCIP_CALL( SCIPskipSpace((char**)&s) );
2857 
2858  /* if we could not find starting indicator of array */
2859  if( *s != '[' )
2860  {
2861  SCIPerrorMessage("expected '[' to start new array\n");
2862  *success = FALSE;
2863  break;
2864  }
2865  ++s;
2866 
2867  /* read array, cnt = 0: variables; cnt = 1: permutation*/
2868  if( cnt == 0 )
2869  {
2870  do
2871  {
2872  /* parse variable name */
2873  SCIP_CALL( SCIPparseVarName(scip, s, &var, &endptr) );
2874 
2875  if( var == NULL )
2876  {
2877  endptr = strchr(endptr, ']');
2878 
2879  if( endptr == NULL )
2880  {
2881  SCIPerrorMessage("closing ']' missing\n");
2882  *success = FALSE;
2883  }
2884  else
2885  s = endptr;
2886 
2887  break;
2888  }
2889 
2890  s = endptr;
2891  assert( s != NULL );
2892  ++nvars;
2893 
2894  if( nvars > maxnvars )
2895  {
2896  maxnvars = SCIPcalcMemGrowSize(scip, nvars);
2897  SCIP_CALL( SCIPreallocBufferArray(scip, &vars, maxnvars) );
2898  SCIP_CALL( SCIPreallocBufferArray(scip, &perm, maxnvars) );
2899  assert( nvars <= maxnvars );
2900  }
2901 
2902  vars[nvars-1] = var;
2903 
2904  /* skip white space */
2905  SCIP_CALL( SCIPskipSpace((char**)&s) );
2906 
2907  /* skip ',' */
2908  if( *s == ',' )
2909  ++s;
2910  }
2911  while( *s != ']' );
2912  }
2913  else
2914  {
2915  do
2916  {
2917  /* skip whitespace */
2918  SCIP_CALL( SCIPskipSpace((char**)&s) );
2919 
2920  /* parse integer value */
2921  if( !SCIPstrToIntValue(s, &val, &endptr) )
2922  {
2923  SCIPerrorMessage("could not extract int from string '%s'\n", str);
2924  *success = FALSE;
2925  break;
2926  }
2927 
2928  s = endptr;
2929  assert( s != NULL );
2930  ++nfoundpermidx;
2931 
2932  if( nfoundpermidx > nvars )
2933  {
2934  SCIPerrorMessage("permutation is longer than vars array\n");
2935  *success = FALSE;
2936  break;
2937  }
2938 
2939  perm[nfoundpermidx-1] = val;
2940 
2941  /* skip whitespace */
2942  SCIP_CALL( SCIPskipSpace((char**)&s) );
2943 
2944  /* skip ',' */
2945  if( *s == ',' )
2946  ++s;
2947  }
2948  while( *s != ']' );
2949 
2950  if( nfoundpermidx != nvars )
2951  {
2952  SCIPerrorMessage("length of permutation is not equal to number of given variables.\n");
2953  *success = FALSE;
2954  break;
2955  }
2956  }
2957 
2958  if( !*success )
2959  break;
2960 
2961  ++s;
2962  ++cnt;
2963  }
2964  while( *s != ')' );
2965 
2966  if( *success && cnt < 2 )
2967  {
2968  SCIPerrorMessage("permutation is missing.\n");
2969  *success = FALSE;
2970  }
2971 
2972  if( *success )
2973  SCIP_CALL( SCIPcreateConsBasicSymresack(scip, cons, name, perm, vars, nvars, TRUE) );
2974 
2975  SCIPfreeBufferArray(scip, &perm);
2976  SCIPfreeBufferArray(scip, &vars);
2977 
2978  return SCIP_OKAY;
2979 }
2980 
2981 
2982 /** constraint display method of constraint handler
2983  *
2984  * The constraint handler should output a representation of the constraint into the given text file.
2985  */
2986 static
2987 SCIP_DECL_CONSPRINT(consPrintSymresack)
2988 { /*lint --e{715}*/
2989  SCIP_CONSDATA* consdata;
2990  SCIP_VAR** vars;
2991  int* perm;
2992  int nvars;
2993  int i;
2994 
2995  assert( scip != NULL );
2996  assert( conshdlr != NULL );
2997  assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2998  assert( cons != NULL );
2999 
3000  consdata = SCIPconsGetData(cons);
3001  assert( consdata != NULL );
3002 
3003  SCIPdebugMsg(scip, "Printing method for symresack constraint handler\n");
3004 
3005  /* we do not have to take care of trivial constraints */
3006  if ( consdata->nvars < 2 )
3007  return SCIP_OKAY;
3008 
3009  assert( consdata->vars != NULL );
3010  assert( consdata->perm != NULL );
3011 
3012  vars = consdata->vars;
3013  nvars = consdata->nvars;
3014  perm = consdata->perm;
3015 
3016  SCIPinfoMessage(scip, file, "symresack([");
3017  SCIP_CALL( SCIPwriteVarName(scip, file, vars[0], TRUE) );
3018 
3019  for (i = 1; i < nvars; ++i)
3020  {
3021  SCIPinfoMessage(scip, file, ",");
3022  SCIP_CALL( SCIPwriteVarName(scip, file, vars[i], TRUE) );
3023  }
3024  SCIPinfoMessage(scip, file, "],[%d", perm[0]);
3025  for (i = 1; i < nvars; ++i)
3026  SCIPinfoMessage(scip, file, ",%d", perm[i]);
3027  SCIPinfoMessage(scip, file, "])");
3028 
3029  return SCIP_OKAY;
3030 }
3031 
3032 
3033 /** constraint method of constraint handler which returns the variables (if possible) */
3034 static
3035 SCIP_DECL_CONSGETVARS(consGetVarsSymresack)
3036 { /*lint --e{715}*/
3037  SCIP_CONSDATA* consdata;
3038 
3039  assert( cons != NULL );
3040  assert( success != NULL );
3041  assert( vars != NULL );
3042 
3043  consdata = SCIPconsGetData(cons);
3044  assert( consdata != NULL );
3045 
3046  if ( varssize < consdata->nvars )
3047  (*success) = FALSE;
3048  else
3049  {
3050  int cnt = 0;
3051  int i;
3052 
3053  for (i = 0; i < consdata->nvars; ++i)
3054  vars[cnt++] = consdata->vars[i];
3055  (*success) = TRUE;
3056  }
3057 
3058  return SCIP_OKAY;
3059 }
3060 
3061 
3062 /** constraint method of constraint handler which returns the number of variables (if possible) */
3063 static
3064 SCIP_DECL_CONSGETNVARS(consGetNVarsSymresack)
3065 { /*lint --e{715}*/
3066  SCIP_CONSDATA* consdata;
3067 
3068  assert( cons != NULL );
3069  assert( success != NULL );
3070  assert( nvars != NULL );
3071 
3072  consdata = SCIPconsGetData(cons);
3073  assert( consdata != NULL );
3074 
3075  (*nvars) = consdata->nvars;
3076  (*success) = TRUE;
3077 
3078  return SCIP_OKAY;
3079 }
3080 
3081 
3082 /** creates the handler for symresack constraints and includes it in SCIP */
3084  SCIP* scip /**< SCIP data structure */
3085  )
3086 {
3087  SCIP_CONSHDLRDATA* conshdlrdata = NULL;
3088  SCIP_CONSHDLR* conshdlr;
3089 
3090  SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) );
3091 
3092  /* include constraint handler */
3095  consEnfolpSymresack, consEnfopsSymresack, consCheckSymresack, consLockSymresack,
3096  conshdlrdata) );
3097  assert( conshdlr != NULL );
3098 
3099  /* set non-fundamental callbacks via specific setter functions */
3100  SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopySymresack, consCopySymresack) );
3101  SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxSymresack) );
3102  SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeSymresack) );
3103  SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteSymresack) );
3104  SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsSymresack) );
3105  SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsSymresack) );
3106  SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseSymresack) );
3107  SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolSymresack, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
3108  SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintSymresack) );
3110  SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropSymresack) );
3111  SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpSymresack, consSepasolSymresack, CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, CONSHDLR_DELAYSEPA) );
3112  SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransSymresack) );
3113  SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpSymresack) );
3114  SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolSymresack) );
3115 
3116  /* whether we allow upgrading to packing/partioning symresack constraints*/
3117  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/ppsymresack",
3118  "Upgrade symresack constraints to packing/partioning symresacks?",
3119  &conshdlrdata->checkppsymresack, TRUE, DEFAULT_PPSYMRESACK, NULL, NULL) );
3120 
3121  /* whether we check for monotonicity of perm when upgrading to packing/partioning symresacks */
3122  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/checkmonotonicity",
3123  "Check whether permutation is monotone when upgrading to packing/partioning symresacks?",
3124  &conshdlrdata->checkmonotonicity, TRUE, DEFAULT_CHECKMONOTONICITY, NULL, NULL) );
3125 
3126  SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/forceconscopy",
3127  "Whether symresack constraints should be forced to be copied to sub SCIPs.",
3128  &conshdlrdata->forceconscopy, TRUE, DEFAULT_FORCECONSCOPY, NULL, NULL) );
3129 
3130  return SCIP_OKAY;
3131 }
3132 
3133 
3134 /*
3135  * constraint specific interface methods
3136  */
3137 
3138 /** creates and captures a symresack constraint
3139  *
3140  * In a presolving step, we check whether the permutation acts only on binary points. Otherwise, we eliminate
3141  * the non-binary variables from the permutation.
3142  *
3143  * @note The constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons().
3144  */
3146  SCIP* scip, /**< SCIP data structure */
3147  SCIP_CONS** cons, /**< pointer to hold the created constraint */
3148  const char* name, /**< name of constraint */
3149  int* perm, /**< permutation */
3150  SCIP_VAR** vars, /**< variables */
3151  int nvars, /**< number of variables in vars array */
3152  SCIP_Bool ismodelcons, /**< whether the symresack is a model constraint */
3153  SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
3154  * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
3155  SCIP_Bool separate, /**< should the constraint be separated during LP processing?
3156  * Usually set to TRUE. */
3157  SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
3158  * TRUE for model constraints, FALSE for additional, redundant constraints. */
3159  SCIP_Bool check, /**< should the constraint be checked for feasibility?
3160  * TRUE for model constraints, FALSE for additional, redundant constraints. */
3161  SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
3162  * Usually set to TRUE. */
3163  SCIP_Bool local, /**< is constraint only valid locally?
3164  * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
3165  SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
3166  * Usually set to FALSE. In column generation applications, set to TRUE if pricing
3167  * adds coefficients to this constraint. */
3168  SCIP_Bool dynamic, /**< is constraint subject to aging?
3169  * Usually set to FALSE. Set to TRUE for own cuts which
3170  * are separated as constraints. */
3171  SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
3172  * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
3173  SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
3174  * if it may be moved to a more global node?
3175  * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
3176  )
3177 {
3178  SCIP_CONSHDLR* conshdlr;
3179  SCIP_CONSDATA* consdata;
3180 
3181  assert( cons != NULL );
3182  assert( nvars > 0 );
3183 
3184  /* find the symresack constraint handler */
3185  conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
3186  if ( conshdlr == NULL )
3187  {
3188  SCIPerrorMessage("Symresack constraint handler not found.\n");
3189  return SCIP_PLUGINNOTFOUND;
3190  }
3191 
3192  /* create constraint data */
3193  SCIP_CALL( consdataCreate(scip, conshdlr, &consdata, vars, nvars, perm, ismodelcons) );
3194 
3195  /* create constraint */
3196  SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate && (! consdata->ppupgrade), enforce, check, propagate,
3197  local, modifiable, dynamic, removable, stickingatnode) );
3198 
3199  return SCIP_OKAY;
3200 }
3201 
3202 
3203 /** creates and captures a symresack constraint
3204  * in its most basic variant, i.e., with all constraint flags set to their default values
3205  *
3206  * In a presolving step, we remove all fixed points and cycles that act on non-binary variables of the permutation
3207  *
3208  * @note The constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons().
3209  */
3211  SCIP* scip, /**< SCIP data structure */
3212  SCIP_CONS** cons, /**< pointer to hold the created constraint */
3213  const char* name, /**< name of constraint */
3214  int* perm, /**< permutation */
3215  SCIP_VAR** vars, /**< variables */
3216  int nvars, /**< number of variables in vars array */
3217  SCIP_Bool ismodelcons /**< whether the symresack is a model constraint */
3218  )
3219 {
3220  SCIP_CALL( SCIPcreateConsSymresack(scip, cons, name, perm, vars, nvars, ismodelcons,
3222 
3223  return SCIP_OKAY;
3224 }
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
SCIP_RETCODE SCIPcreateEmptyRowCons(SCIP *scip, SCIP_ROW **row, SCIP_CONS *cons, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1422
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:578
#define CONSHDLR_ENFOPRIORITY
#define NULL
Definition: def.h:267
#define CONSHDLR_PRESOLTIMING
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
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 ismodelcons, 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)
SCIP_RETCODE SCIPskipSpace(char **s)
Definition: misc.c:10866
static SCIP_DECL_CONSPROP(consPropSymresack)
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1635
public methods for SCIP parameter handling
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8475
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip_cons.c:601
public methods for memory management
static SCIP_DECL_CONSFREE(consFreeSymresack)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:941
SCIP_RETCODE SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1658
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9553
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:126
#define CONSHDLR_NAME
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata)
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars)))
Definition: scip_cons.c:831
#define SCIP_MAXSTRLEN
Definition: def.h:288
SCIP_RETCODE SCIPcreateSymbreakCons(SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool ismodelcons, 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)
public methods for conflict handler plugins and conflict analysis
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:323
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2843
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1701
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18135
static SCIP_DECL_CONSENFORELAX(consEnforelaxSymresack)
SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPcreateConsBasicSymresack(SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool ismodelcons)
#define ISFIXED(x, bdchgidx)
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1441
SCIP_RETCODE SCIPparseVarName(SCIP *scip, const char *str, SCIP_VAR **var, char **endptr)
Definition: scip_var.c:533
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1250
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17600
static SCIP_DECL_CONSCOPY(consCopySymresack)
static SCIP_DECL_CONSPARSE(consParseSymresack)
static SCIP_RETCODE initLP(SCIP *scip, SCIP_CONS *cons, SCIP_Bool checkmonotonicity, SCIP_Bool *infeasible)
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4595
#define FALSE
Definition: def.h:94
#define CONSHDLR_PROPFREQ
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:181
constraint handler for orbisack constraints
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
#define TRUE
Definition: def.h:93
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition: cons.c:8495
static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA **consdata, SCIP_VAR *const *inputvars, int inputnvars, int *inputperm, SCIP_Bool ismodelcons)
static SCIP_RETCODE checkSymresackSolution(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_RESULT *result, SCIP_Bool printreason)
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17769
#define CONSHDLR_MAXPREROUNDS
public methods for problem variables
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
SCIP_Bool SCIPstrToIntValue(const char *str, int *value, char **endptr)
Definition: misc.c:10946
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:235
#define FIXED0
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
static SCIP_DECL_CONSPRESOL(consPresolSymresack)
Constraint handler for the set partitioning / packing / covering constraints .
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip_general.c:590
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip_branch.c:428
public methods for SCIP variables
static SCIP_DECL_CONSGETNVARS(consGetNVarsSymresack)
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8485
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp)))
Definition: scip_cons.c:624
#define SCIPdebugMsg
Definition: scip_message.h:78
SCIP_RETCODE SCIPgetTransformedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
Definition: scip_var.c:1482
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse)))
Definition: scip_cons.c:808
static SCIP_RETCODE separateSymresackCovers(SCIP *scip, SCIP_CONS *cons, const SCIP_CONSDATA *consdata, SCIP_Real *vals, int *ngen, SCIP_Bool *infeasible)
static SCIP_DECL_CONSINITLP(consInitlpSymresack)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
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:998
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
static SCIP_RETCODE maximizeObjectiveSymresackStrict(SCIP *scip, int nvars, SCIP_Real *objective, int *perm, int *invperm, int *maxcrit, SCIP_Real *maxsoluval)
public methods for numerical tolerances
static SCIP_DECL_CONSPRINT(consPrintSymresack)
#define CONSHDLR_NEEDSCONS
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4261
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
constraint handler for symresack constraints
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:142
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol)))
Definition: scip_cons.c:444
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:105
public methods for managing constraints
static SCIP_RETCODE addSymresackInequality(SCIP *scip, SCIP_CONS *cons, int nvars, SCIP_VAR **vars, int *coeffs, SCIP_Real rhs, SCIP_Bool *infeasible)
static SCIP_RETCODE orbisackUpgrade(SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **inputvars, int nvars, SCIP_Bool *upgrade, SCIP_Bool ismodelcons, 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)
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:347
static SCIP_DECL_CONSSEPALP(consSepalpSymresack)
#define CONSHDLR_EAGERFREQ
SCIP_RETCODE SCIPincludeConshdlrSymresack(SCIP *scip)
#define SCIPerrorMessage
Definition: pub_message.h:64
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4199
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_RETCODE SCIPcreateConsSymresack(SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool ismodelcons, 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)
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1254
static SCIP_DECL_CONSENFOLP(consEnfolpSymresack)
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:137
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip_cut.c:135
SCIP_Real SCIPvarGetUbAtIndex(SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: var.c:16830
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8216
static SCIP_DECL_CONSLOCK(consLockSymresack)
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:8717
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8435
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:372
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4219
static SCIP_DECL_CONSDELETE(consDeleteSymresack)
#define REALABS(x)
Definition: def.h:197
#define CONSHDLR_SEPAFREQ
static SCIP_RETCODE maximizeObjectiveSymresackCriticalEntry(SCIP *scip, int nvars, SCIP_Real *objective, int *perm, int *invperm, int crit, int *maxsolu)
#define SCIP_CALL(x)
Definition: def.h:380
#define FIXED1
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:8455
static SCIP_DECL_CONSSEPASOL(consSepasolSymresack)
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:250
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
Definition: scip_cons.c:647
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:65
#define UNFIXED
static SCIP_RETCODE packingUpgrade(SCIP *scip, SCIP_CONSDATA **consdata, int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool checkmonotonicity, SCIP_Bool *upgrade)
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4638
public methods for constraint handler plugins and constraints
#define DEFAULT_CHECKMONOTONICITY
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
public data structures and miscellaneous methods
#define SCIP_Bool
Definition: def.h:91
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9599
SCIP_Real SCIPvarGetLbAtIndex(SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: var.c:16711
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopySymresack)
static SCIP_DECL_CONSRESPROP(consRespropSymresack)
public methods for cuts and aggregation rows
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8415
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8385
static SCIP_DECL_CONSCHECK(consCheckSymresack)
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint)))
Definition: scip_cons.c:785
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:5503
public methods for the LP relaxation, rows and columns
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9576
#define CONSHDLR_DELAYSEPA
SCIP_Real * r
Definition: circlepacking.c:59
public methods for branching rule plugins and branching
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1562
general public methods
#define SCIP_DEFAULT_INFINITY
Definition: def.h:178
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define CONSHDLR_PROP_TIMING
public methods for solutions
SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success)
Definition: scip_copy.c:711
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:8246
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:5617
static SCIP_DECL_CONSGETVARS(consGetVarsSymresack)
#define DEFAULT_PPSYMRESACK
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_cons.c:540
static SCIP_RETCODE checkFeasible(SCIP *scip, SCIP_VAR **vars, int *invperm, int nvars, int start, int *tempfixings, int *tempfixentries, int numfixentriesinit, SCIP_Bool *infeasible, int *infeasibleentry)
#define DEFAULT_FORCECONSCOPY
public methods for message output
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1216
#define SCIP_Real
Definition: def.h:173
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8465
SCIP_RETCODE SCIPaddVarsToRow(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_lp.c:1727
#define SCIPfreeCleanBufferArray(scip, ptr)
Definition: scip_mem.h:146
#define CONSHDLR_CHECKPRIORITY
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars)))
Definition: scip_cons.c:854
public methods for message handling
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8405
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8395
#define NOINIT
#define CONSHDLR_DESC
static SCIP_DECL_CONSENFOPS(consEnfopsSymresack)
#define CONSHDLR_SEPAPRIORITY
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:64
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18145
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
#define CONSHDLR_DELAYPROP
static SCIP_RETCODE propVariables(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible, int *ngen)
SCIP_RETCODE SCIPwriteVarName(SCIP *scip, FILE *file, SCIP_VAR *var, SCIP_Bool type)
Definition: scip_var.c:230
public methods for global and local (sub)problems
static SCIP_DECL_CONSINITSOL(consInitsolSymresack)
static SCIP_DECL_CONSTRANS(consTransSymresack)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
SCIP callable library.
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition: var.c:17575
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:128
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip_cons.c:281
memory allocation routines