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