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
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
102
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 */
106
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)
115
116
117
118/*
119 * Data structures
120 */
121
122/** constraint handler data */
123struct 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 */
133struct 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 */
158static
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 */
217static
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 */
471static
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 */
612static
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 */
816static
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 */
937static
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
1113 SCIP_CALL( SCIPaddConflictBinvar(scip, vars[invperm[r]]) );
1114 }
1115
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 */
1162static
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
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 }
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 */
1217static
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 */
1338static
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 */
1447static
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 */
1546static
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 */
1626static
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.
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) */
1791static
1792SCIP_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 */
1808static
1809SCIP_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 */
1823static
1824SCIP_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 */
1842static
1843SCIP_DECL_CONSTRANS(consTransSymresack)
1844{
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) */
1953static
1954SCIP_DECL_CONSINITLP(consInitlpSymresack)
1955{
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) */
1987static
1988SCIP_DECL_CONSINITSOL(consInitsolSymresack)
1989{
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 */
2023static
2024SCIP_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 */
2097static
2098SCIP_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 */
2172static
2173SCIP_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 */
2250static
2251SCIP_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 */
2293static
2294SCIP_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 */
2369static
2370SCIP_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 */
2406static
2407SCIP_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 */
2453static
2454SCIP_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 */
2516static
2517SCIP_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 */
2685static
2686SCIP_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 */
2736static
2737SCIP_DECL_CONSCOPY(consCopySymresack)
2738{
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 */
2805static
2806SCIP_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 */
2986static
2987SCIP_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) */
3034static
3035SCIP_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) */
3063static
3064SCIP_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) );
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().
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().
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}
SCIP_Real * r
Definition: circlepacking.c:59
constraint handler for orbisack constraints
Constraint handler for the set partitioning / packing / covering constraints .
#define CONSHDLR_NEEDSCONS
#define CONSHDLR_SEPAFREQ
static SCIP_DECL_CONSTRANS(consTransSymresack)
#define FIXED0
#define CONSHDLR_CHECKPRIORITY
#define CONSHDLR_DESC
static SCIP_DECL_CONSDELETE(consDeleteSymresack)
#define NOINIT
static SCIP_DECL_CONSINITSOL(consInitsolSymresack)
static SCIP_DECL_CONSPROP(consPropSymresack)
static SCIP_DECL_CONSGETVARS(consGetVarsSymresack)
#define CONSHDLR_PROP_TIMING
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopySymresack)
static SCIP_DECL_CONSLOCK(consLockSymresack)
#define DEFAULT_FORCECONSCOPY
#define CONSHDLR_MAXPREROUNDS
#define DEFAULT_CHECKMONOTONICITY
#define ISFIXED(x, bdchgidx)
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_DECL_CONSENFOPS(consEnfopsSymresack)
static SCIP_RETCODE propVariables(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible, int *ngen)
static SCIP_RETCODE initLP(SCIP *scip, SCIP_CONS *cons, SCIP_Bool checkmonotonicity, SCIP_Bool *infeasible)
#define CONSHDLR_SEPAPRIORITY
#define UNFIXED
static SCIP_DECL_CONSENFOLP(consEnfolpSymresack)
static SCIP_RETCODE checkSymresackSolution(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_RESULT *result, SCIP_Bool printreason)
static SCIP_DECL_CONSCHECK(consCheckSymresack)
static SCIP_DECL_CONSENFORELAX(consEnforelaxSymresack)
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)
static SCIP_DECL_CONSPRINT(consPrintSymresack)
static SCIP_RETCODE maximizeObjectiveSymresackCriticalEntry(SCIP *scip, int nvars, SCIP_Real *objective, int *perm, int *invperm, int crit, int *maxsolu)
static SCIP_RETCODE separateSymresackCovers(SCIP *scip, SCIP_CONS *cons, const SCIP_CONSDATA *consdata, SCIP_Real *vals, int *ngen, SCIP_Bool *infeasible)
#define CONSHDLR_PROPFREQ
static SCIP_DECL_CONSPRESOL(consPresolSymresack)
static SCIP_DECL_CONSINITLP(consInitlpSymresack)
static SCIP_RETCODE addSymresackInequality(SCIP *scip, SCIP_CONS *cons, int nvars, SCIP_VAR **vars, int *coeffs, SCIP_Real rhs, SCIP_Bool *infeasible)
#define CONSHDLR_PRESOLTIMING
static SCIP_RETCODE packingUpgrade(SCIP *scip, SCIP_CONSDATA **consdata, int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool checkmonotonicity, SCIP_Bool *upgrade)
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata)
static SCIP_DECL_CONSSEPALP(consSepalpSymresack)
static SCIP_DECL_CONSPARSE(consParseSymresack)
#define CONSHDLR_EAGERFREQ
static SCIP_DECL_CONSGETNVARS(consGetNVarsSymresack)
#define DEFAULT_PPSYMRESACK
static SCIP_RETCODE maximizeObjectiveSymresackStrict(SCIP *scip, int nvars, SCIP_Real *objective, int *perm, int *invperm, int *maxcrit, SCIP_Real *maxsoluval)
#define CONSHDLR_ENFOPRIORITY
static SCIP_DECL_CONSCOPY(consCopySymresack)
#define FIXED1
#define CONSHDLR_DELAYSEPA
static SCIP_DECL_CONSSEPASOL(consSepasolSymresack)
static SCIP_DECL_CONSFREE(consFreeSymresack)
#define CONSHDLR_NAME
static SCIP_DECL_CONSRESPROP(consRespropSymresack)
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)
#define CONSHDLR_DELAYPROP
constraint handler for symresack constraints
#define SCIP_DEFAULT_INFINITY
Definition: def.h:178
#define NULL
Definition: def.h:267
#define SCIP_MAXSTRLEN
Definition: def.h:288
#define SCIP_Bool
Definition: def.h:91
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define REALABS(x)
Definition: def.h:197
#define SCIP_CALL(x)
Definition: def.h:374
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)
int SCIPgetNVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9545
SCIP_VAR ** SCIPgetVarsSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9568
SCIP_SETPPCTYPE SCIPgetTypeSetppc(SCIP *scip, SCIP_CONS *cons)
Definition: cons_setppc.c:9591
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 SCIPcreateConsBasicSymresack(SCIP *scip, SCIP_CONS **cons, const char *name, int *perm, SCIP_VAR **vars, int nvars, SCIP_Bool ismodelcons)
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_SETPPCTYPE_PARTITIONING
Definition: cons_setppc.h:87
@ SCIP_SETPPCTYPE_COVERING
Definition: cons_setppc.h:89
@ SCIP_SETPPCTYPE_PACKING
Definition: cons_setppc.h:88
SCIP_RETCODE SCIPincludeConshdlrSymresack(SCIP *scip)
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_Bool SCIPisTransformed(SCIP *scip)
Definition: scip_general.c:596
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2843
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
#define SCIPdebugMsg
Definition: scip_message.h:78
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
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip_branch.c:428
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse)))
Definition: scip_cons.c:808
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_cons.c:540
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars)))
Definition: scip_cons.c:831
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
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
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
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:578
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:372
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:323
int SCIPconshdlrGetNConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4636
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4197
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:347
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:941
SCIP_RETCODE SCIPsetConshdlrInitlp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITLP((*consinitlp)))
Definition: scip_cons.c:624
SCIP_RETCODE SCIPsetConshdlrInitsol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSINITSOL((*consinitsol)))
Definition: scip_cons.c:444
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4217
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip_cons.c:601
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
Definition: scip_cons.c:647
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars)))
Definition: scip_cons.c:854
SCIP_CONS ** SCIPconshdlrGetConss(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4593
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint)))
Definition: scip_cons.c:785
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:8244
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8473
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8383
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8413
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8403
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_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8433
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:8453
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8214
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8463
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition: cons.c:8493
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8393
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8483
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip_cut.c:135
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:250
#define SCIPfreeCleanBufferArray(scip, ptr)
Definition: scip_mem.h:146
#define SCIPallocCleanBufferArray(scip, ptr, num)
Definition: scip_mem.h:142
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
#define SCIPallocClearBufferArray(scip, ptr, num)
Definition: scip_mem.h:126
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:128
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
#define SCIPfreeBufferArrayNull(scip, ptr)
Definition: scip_mem.h:137
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:105
SCIP_RETCODE SCIPcacheRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1635
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 SCIPflushRowExtensions(SCIP *scip, SCIP_ROW *row)
Definition: scip_lp.c:1658
SCIP_RETCODE SCIPaddVarToRow(SCIP *scip, SCIP_ROW *row, SCIP_VAR *var, SCIP_Real val)
Definition: scip_lp.c:1701
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition: scip_lp.c:1562
SCIP_RETCODE SCIPaddVarsToRow(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_lp.c:1727
SCIP_RETCODE SCIPgetSolVals(SCIP *scip, SCIP_SOL *sol, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_sol.c:1254
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisGE(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17599
SCIP_RETCODE SCIPgetTransformedVars(SCIP *scip, int nvars, SCIP_VAR **vars, SCIP_VAR **transvars)
Definition: scip_var.c:1480
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
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:5615
SCIP_RETCODE SCIPparseVarName(SCIP *scip, const char *str, SCIP_VAR **var, char **endptr)
Definition: scip_var.c:533
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4259
int SCIPvarGetProbindex(SCIP_VAR *var)
Definition: var.c:17768
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1248
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition: var.c:17574
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:8715
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:5501
SCIP_Real SCIPvarGetLbAtIndex(SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: var.c:16710
SCIP_RETCODE SCIPwriteVarName(SCIP *scip, FILE *file, SCIP_VAR *var, SCIP_Bool type)
Definition: scip_var.c:230
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1439
SCIP_Real SCIPvarGetUbAtIndex(SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: var.c:16829
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1214
void SCIPsortIntInt(int *intarray1, int *intarray2, int len)
SCIP_Bool SCIPstrToIntValue(const char *str, int *value, char **endptr)
Definition: misc.c:10946
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
SCIP_RETCODE SCIPskipSpace(char **s)
Definition: misc.c:10866
memory allocation routines
public methods for managing constraints
public methods for message output
#define SCIPerrorMessage
Definition: pub_message.h:64
public data structures and miscellaneous methods
public methods for problem variables
SCIP callable library.
public methods for branching rule plugins and branching
public methods for conflict handler plugins and conflict analysis
public methods for constraint handler plugins and constraints
public methods for cuts and aggregation rows
general public methods
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for solutions
public methods for SCIP variables
@ SCIP_CONFTYPE_PROPAGATION
Definition: type_conflict.h:60
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:64
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:65
@ SCIP_BOUNDTYPE_LOWER
Definition: type_lp.h:56
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_CUTOFF
Definition: type_result.h:48
@ SCIP_FEASIBLE
Definition: type_result.h:45
@ SCIP_REDUCEDDOM
Definition: type_result.h:51
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_SEPARATED
Definition: type_result.h:49
@ SCIP_SUCCESS
Definition: type_result.h:58
@ SCIP_INFEASIBLE
Definition: type_result.h:46
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
@ SCIP_PLUGINNOTFOUND
Definition: type_retcode.h:54
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63