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( SCIPunlockVarCons(scip, vars1[i], cons, TRUE, FALSE) );
1064 SCIP_CALL( SCIPreleaseVar(scip, &vars1[i]) );
1065 vars1[i] = var;
1066 SCIP_CALL( SCIPlockVarCons(scip, vars1[i], cons, TRUE, FALSE) );
1067 SCIP_CALL( SCIPcaptureVar(scip, var) );
1068 }
1069
1070 /* treat second column */
1071 assert( SCIPvarGetStatus(vars2[i]) != SCIP_VARSTATUS_MULTAGGR ); /* variables are marked as not to be multi-aggregated */
1072
1073 SCIP_CALL( SCIPgetBinvarRepresentative(scip, vars2[i], &var, &negated) );
1074 SCIP_UNUSED( negated );
1075 assert( SCIPvarIsActive(var) || SCIPvarGetStatus(var) == SCIP_VARSTATUS_NEGATED || SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED );
1076 if ( var != vars2[i] )
1077 {
1078 SCIP_CALL( SCIPunlockVarCons(scip, vars2[i], cons, FALSE, TRUE) );
1079 SCIP_CALL( SCIPreleaseVar(scip, &vars2[i]) );
1080 vars2[i] = var;
1081 SCIP_CALL( SCIPlockVarCons(scip, vars2[i], cons, FALSE, TRUE) );
1082 SCIP_CALL( SCIPcaptureVar(scip, var) );
1083 }
1084 }
1085
1086 return SCIP_OKAY;
1087}
1088
1089
1090/*--------------------------------------------------------------------------------------------
1091 *--------------------------------- SCIP functions -------------------------------------------
1092 *--------------------------------------------------------------------------------------------*/
1093
1094/** copy method for constraint handler plugins (called when SCIP copies plugins) */
1095static
1096SCIP_DECL_CONSHDLRCOPY(conshdlrCopyOrbisack)
1097{ /*lint --e{715}*/
1098 assert(scip != NULL);
1099 assert(conshdlr != NULL);
1100
1101 SCIP_STRINGEQ( SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
1102
1103 /* call inclusion method of constraint handler */
1104 SCIP_CALL( SCIPincludeConshdlrOrbisack(scip) );
1105
1106 *valid = TRUE;
1107
1108 return SCIP_OKAY;
1109}
1110
1111/** frees specific constraint data */
1112static
1113SCIP_DECL_CONSDELETE(consDeleteOrbisack)
1114{ /*lint --e{715}*/
1115 assert( scip != 0 );
1116 assert( conshdlr != 0 );
1117 assert( consdata != 0 );
1118
1119 SCIP_STRINGEQ( SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
1120
1121 SCIP_CALL( consdataFree(scip, consdata) );
1122
1123 return SCIP_OKAY;
1124}
1125
1126
1127/** frees constraint handler */
1128static
1129SCIP_DECL_CONSFREE(consFreeOrbisack)
1130{ /*lint --e{715}*/
1131 SCIP_CONSHDLRDATA* conshdlrdata;
1132
1133 assert( scip != 0 );
1134 assert( conshdlr != 0 );
1135
1136 SCIP_STRINGEQ( SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
1137
1138 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1139 assert( conshdlrdata != NULL );
1140
1141 SCIPfreeBlockMemory(scip, &conshdlrdata);
1142
1143 return SCIP_OKAY;
1144}
1145
1146
1147/** transforms constraint data into data belonging to the transformed problem */
1148static
1149SCIP_DECL_CONSTRANS(consTransOrbisack)
1150{
1151 SCIP_CONSDATA* sourcedata;
1152 SCIP_CONSDATA* consdata = NULL;
1153
1154 assert( scip != NULL );
1155 assert( conshdlr != NULL );
1156 assert( sourcecons != NULL );
1157 assert( targetcons != NULL );
1158
1159 SCIP_STRINGEQ( SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
1160
1161 SCIPdebugMsg(scip, "Transforming constraint.\n");
1162
1163 /* get data of original constraint */
1164 sourcedata = SCIPconsGetData(sourcecons);
1165
1166 /* create constraint data */
1167 SCIP_CALL( consdataCreate(scip, &consdata, sourcedata->vars1, sourcedata->vars2,
1168 sourcedata->nrows, sourcedata->ismodelcons) );
1169
1170 /* create transformed constraint */
1171 SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, consdata,
1172 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons),
1173 SCIPconsIsEnforced(sourcecons), SCIPconsIsChecked(sourcecons),
1174 SCIPconsIsPropagated(sourcecons), SCIPconsIsLocal(sourcecons),
1175 SCIPconsIsModifiable(sourcecons), SCIPconsIsDynamic(sourcecons),
1176 SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
1177
1178 return SCIP_OKAY;
1179}
1180
1181
1182/** LP initialization method of constraint handler (called before the initial LP relaxation at a node is solved) */
1183static
1184SCIP_DECL_CONSINITLP(consInitlpOrbisack)
1185{
1186 int c;
1187
1188 assert( infeasible != NULL );
1189 *infeasible = FALSE;
1190
1191 assert( scip != 0 );
1192 assert( conshdlr != 0 );
1193
1194 SCIP_STRINGEQ( SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
1195
1196 /* loop through constraints */
1197 for (c = 0; c < nconss; ++c)
1198 {
1199 assert( conss[c] != 0 );
1200
1201 SCIPdebugMsg(scip, "Generating initial orbisack cut for constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1202
1203 SCIP_CALL( initLP(scip, conss[c], infeasible) );
1204 if ( *infeasible )
1205 break;
1206
1207 SCIPdebugMsg(scip, "Generated initial orbisack cut.\n");
1208 }
1209
1210 return SCIP_OKAY;
1211}
1212
1213
1214/** solving process initialization method of constraint handler (called when branch and bound process is about to begin) */
1215static
1216SCIP_DECL_CONSINITSOL(consInitsolOrbisack)
1217{
1218 SCIP_CONSHDLRDATA* conshdlrdata;
1219 int c;
1220
1221 assert( scip != NULL );
1222 assert( conshdlr != NULL );
1223
1224 SCIP_STRINGEQ( SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
1225
1226 /* determine maximum number of rows in an orbisack constraint */
1227 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1228 assert( conshdlrdata != NULL );
1229
1230 conshdlrdata->maxnrows = 0;
1231
1232 /* loop through constraints */
1233 for (c = 0; c < nconss; ++c)
1234 {
1235 SCIP_CONSDATA* consdata;
1236
1237 assert( conss[c] != NULL );
1238
1239 consdata = SCIPconsGetData(conss[c]);
1240 assert( consdata != NULL );
1241
1242 /* update conshdlrdata if necessary */
1243 if ( consdata->nrows > conshdlrdata->maxnrows )
1244 conshdlrdata->maxnrows = consdata->nrows;
1245 }
1246
1247 return SCIP_OKAY;
1248}
1249
1250
1251/** separation method of constraint handler for LP solution */
1252static
1253SCIP_DECL_CONSSEPALP(consSepalpOrbisack)
1254{ /*lint --e{715}*/
1255 SCIP_CONSDATA* consdata;
1256 SCIP_Real* vals1;
1257 SCIP_Real* vals2;
1258 int c;
1259
1260 assert( scip != NULL );
1261 assert( conshdlr != NULL );
1262 assert( result != NULL );
1263
1264 SCIP_STRINGEQ( SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
1265
1266 SCIPdebugMsg(scip, "Separation method for orbisack constraints.\n");
1267
1268 *result = SCIP_DIDNOTRUN;
1269
1270 /* if solution is not integer */
1271 if ( SCIPgetNLPBranchCands(scip) > 0 )
1272 {
1273 SCIP_CONSHDLRDATA* conshdlrdata;
1274 int nvals;
1275
1276 *result = SCIP_DIDNOTFIND;
1277
1278 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1279 assert( conshdlrdata != NULL );
1280
1281 nvals = conshdlrdata->maxnrows;
1282 assert( nvals > 0 );
1283
1284 SCIP_CALL( SCIPallocBufferArray(scip, &vals1, nvals) );
1285 SCIP_CALL( SCIPallocBufferArray(scip, &vals2, nvals) );
1286
1287 /* loop through constraints */
1288 for (c = 0; c < nconss; ++c)
1289 {
1290 /* get data of constraint */
1291 assert( conss[c] != NULL );
1292 consdata = SCIPconsGetData(conss[c]);
1293
1294 /* get solution */
1295 SCIP_CALL( SCIPgetSolVals(scip, NULL, consdata->nrows, consdata->vars1, vals1) );
1296 SCIP_CALL( SCIPgetSolVals(scip, NULL, consdata->nrows, consdata->vars2, vals2) );
1297
1298 SCIPdebugMsg(scip, "Separating orbisack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1299
1300 SCIP_CALL( separateInequalities(scip, result, conss[c], consdata->nrows, consdata->vars1, consdata->vars2, vals1, vals2) );
1301
1302 if ( *result == SCIP_CUTOFF )
1303 break;
1304 }
1305
1306 SCIPfreeBufferArray(scip, &vals2);
1307 SCIPfreeBufferArray(scip, &vals1);
1308 }
1309
1310 return SCIP_OKAY;
1311}
1312
1313
1314/** separation method of constraint handler for arbitrary primal solution */
1315static
1316SCIP_DECL_CONSSEPASOL(consSepasolOrbisack)
1317{ /*lint --e{715}*/
1318 SCIP_CONSDATA* consdata;
1319 SCIP_Real* vals1;
1320 SCIP_Real* vals2;
1321 int c;
1322
1323 assert( scip != NULL );
1324 assert( conshdlr != NULL );
1325 assert( result != NULL );
1326
1327 SCIP_STRINGEQ( SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
1328
1329 SCIPdebugMsg(scip, "Separation method for orbisack constraints\n");
1330
1331 *result = SCIP_DIDNOTFIND;
1332
1333 if ( nconss > 0 )
1334 {
1335 SCIP_CONSHDLRDATA* conshdlrdata;
1336 int nvals;
1337
1338 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1339 assert( conshdlrdata != NULL );
1340
1341 nvals = conshdlrdata->maxnrows;
1342 assert( nvals > 0 );
1343
1344 SCIP_CALL( SCIPallocBufferArray(scip, &vals1, nvals) );
1345 SCIP_CALL( SCIPallocBufferArray(scip, &vals2, nvals) );
1346
1347 /* loop through constraints */
1348 for (c = 0; c < nconss; ++c)
1349 {
1350 /* get data of constraint */
1351 assert( conss[c] != NULL );
1352 consdata = SCIPconsGetData(conss[c]);
1353
1354 /* get solution */
1355 assert( consdata->nrows <= nvals );
1356 SCIP_CALL( SCIPgetSolVals(scip, sol, consdata->nrows, consdata->vars1, vals1) );
1357 SCIP_CALL( SCIPgetSolVals(scip, sol, consdata->nrows, consdata->vars2, vals2) );
1358
1359 SCIPdebugMsg(scip, "Separating orbisack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1360
1361 SCIP_CALL( separateInequalities(scip, result, conss[c], consdata->nrows, consdata->vars1, consdata->vars2, vals1, vals2) );
1362 if ( *result == SCIP_CUTOFF )
1363 break;
1364 }
1365
1366 SCIPfreeBufferArray(scip, &vals2);
1367 SCIPfreeBufferArray(scip, &vals1);
1368 }
1369
1370 return SCIP_OKAY;
1371}
1372
1373
1374/** constraint enforcing method of constraint handler for LP solutions
1375 *
1376 * @pre It is assumed that the solution is integral (this can be ensured by appropriate priorities).
1377 */
1378static
1379SCIP_DECL_CONSENFOLP(consEnfolpOrbisack)
1380{ /*lint --e{715}*/
1381 SCIP_CONSDATA* consdata;
1382 SCIP_Bool infeasible = FALSE;
1383 SCIP_Real* vals1;
1384 SCIP_Real* vals2;
1385 int ngen = 0;
1386 int c;
1387
1388 assert( scip != 0 );
1389 assert( conshdlr != 0 );
1390 assert( result != 0 );
1391
1392 SCIP_STRINGEQ( SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
1393
1394 SCIPdebugMsg(scip, "Enfolp method for orbisack constraints\n");
1395
1396 /* we have a negative priority, so we should come after the integrality conshdlr. */
1397 assert( SCIPgetNLPBranchCands(scip) == 0 );
1398
1399 *result = SCIP_FEASIBLE;
1400
1401 if ( nconss > 0 )
1402 {
1403 SCIP_CONSHDLRDATA* conshdlrdata;
1404 int nvals;
1405
1406 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1407 assert( conshdlrdata != NULL );
1408
1409 nvals = conshdlrdata->maxnrows;
1410 assert( nvals > 0 );
1411
1412 SCIP_CALL( SCIPallocBufferArray(scip, &vals1, nvals) );
1413 SCIP_CALL( SCIPallocBufferArray(scip, &vals2, nvals) );
1414
1415 /* loop through constraints */
1416 for (c = 0; c < nconss; ++c)
1417 {
1418 /* get data of constraint */
1419 assert( conss[c] != 0 );
1420 consdata = SCIPconsGetData(conss[c]);
1421 assert( consdata != NULL );
1422
1423 /* do not enforce non-model constraints */
1424 if ( !consdata->ismodelcons )
1425 continue;
1426
1427 /* get solution */
1428 assert( consdata->nrows <= nvals );
1429 SCIP_CALL( SCIPgetSolVals(scip, NULL, consdata->nrows, consdata->vars1, vals1) );
1430 SCIP_CALL( SCIPgetSolVals(scip, NULL, consdata->nrows, consdata->vars2, vals2) );
1431
1432 SCIPdebugMsg(scip, "Enforcing orbisack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1433
1434 /* Separate only cover inequalities to ensure that enforcing works correctly. */
1435 /* Otherwise, it may happen that infeasible solutions cannot be detected, since */
1436 /* we bound the size of the coefficients for the orbisack inequalities. */
1437 SCIP_CALL( separateOrbisackCovers(scip, conss[c], consdata->nrows, consdata->vars1, consdata->vars2, vals1, vals2, &ngen, &infeasible) );
1438
1439 if ( infeasible )
1440 {
1441 *result = SCIP_CUTOFF;
1442 break;
1443 }
1444
1445 SCIPdebugMsg(scip, "Generated orbisack inequalities for <%s>: %d\n", SCIPconsGetName(conss[c]), ngen);
1446
1447 if ( ngen > 0 )
1448 *result = SCIP_SEPARATED;
1449 }
1450
1451 SCIPfreeBufferArray(scip, &vals2);
1452 SCIPfreeBufferArray(scip, &vals1);
1453 }
1454
1455 return SCIP_OKAY;
1456}
1457
1458
1459/** constraint enforcing method of constraint handler for pseudo solutions */
1460static
1461SCIP_DECL_CONSENFOPS(consEnfopsOrbisack)
1462{ /*lint --e{715}*/
1463 SCIP_Bool feasible = TRUE;
1464 SCIP_CONSDATA* consdata;
1465 int c;
1466
1467 assert( scip != NULL );
1468 assert( conshdlr != NULL );
1469 assert( result != NULL );
1470
1471 SCIP_STRINGEQ( SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
1472
1473 SCIPdebugMsg(scip, "Enforcing method for orbisack constraints (pseudo solutions) ...\n");
1474
1475 *result = SCIP_FEASIBLE;
1476
1477 if ( objinfeasible || solinfeasible )
1478 return SCIP_OKAY;
1479
1480 /* loop through constraints */
1481 for (c = 0; c < nconss; ++c)
1482 {
1483 /* get data of constraint */
1484 assert( conss[c] != NULL );
1485 consdata = SCIPconsGetData(conss[c]);
1486 assert( consdata != NULL);
1487 assert( consdata->nrows > 0 );
1488 assert( consdata->vars1 != NULL );
1489 assert( consdata->vars2 != NULL );
1490
1491 /* do not enforce non-model constraints */
1492 if ( !consdata->ismodelcons )
1493 continue;
1494
1495 SCIP_CALL( SCIPcheckSolutionOrbisack(scip, NULL, consdata->vars1, consdata->vars2, consdata->nrows, FALSE, &feasible) );
1496
1497 if ( ! feasible )
1498 {
1499 *result = SCIP_INFEASIBLE;
1500 break;
1501 }
1502 }
1503
1504 return SCIP_OKAY;
1505}
1506
1507
1508/** constraint enforcing method of constraint handler for relaxation solutions */
1509static
1510SCIP_DECL_CONSENFORELAX(consEnforelaxOrbisack)
1511{ /*lint --e{715}*/
1512 SCIP_CONSDATA* consdata;
1513 SCIP_Bool infeasible = FALSE;
1514 SCIP_Real* vals1;
1515 SCIP_Real* vals2;
1516 int ngen = 0;
1517 int c;
1518
1519 assert( scip != 0 );
1520 assert( conshdlr != 0 );
1521 assert( result != 0 );
1522
1523 SCIP_STRINGEQ( SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
1524
1525 SCIPdebugMsg(scip, "Enforelax method for orbisack constraints.\n");
1526
1527 /* we have a negative priority, so we should come after the integrality conshdlr. */
1528 assert( SCIPgetNLPBranchCands(scip) == 0 );
1529
1530 *result = SCIP_FEASIBLE;
1531
1532 if ( nconss > 0 )
1533 {
1534 SCIP_CONSHDLRDATA* conshdlrdata;
1535 int nvals;
1536
1537 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1538 assert( conshdlrdata != NULL );
1539
1540 nvals = conshdlrdata->maxnrows;
1541 assert( nvals > 0 );
1542
1543 SCIP_CALL( SCIPallocBufferArray(scip, &vals1, nvals) );
1544 SCIP_CALL( SCIPallocBufferArray(scip, &vals2, nvals) );
1545
1546 /* loop through constraints */
1547 for (c = 0; c < nconss; ++c)
1548 {
1549 /* get data of constraint */
1550 assert( conss[c] != 0 );
1551 consdata = SCIPconsGetData(conss[c]);
1552 assert( consdata != NULL );
1553
1554 /* do not enforce non-model constraints */
1555 if ( !consdata->ismodelcons )
1556 continue;
1557
1558 /* get solution */
1559 assert( consdata->nrows <= nvals );
1560 SCIP_CALL( SCIPgetSolVals(scip, sol, consdata->nrows, consdata->vars1, vals1) );
1561 SCIP_CALL( SCIPgetSolVals(scip, sol, consdata->nrows, consdata->vars2, vals2) );
1562
1563 SCIPdebugMsg(scip, "Enforcing orbisack constraint <%s> ...\n", SCIPconsGetName(conss[c]));
1564
1565 /* Separate only cover inequalities to ensure that enforcing works correctly. */
1566 /* Otherwise, it may happen that infeasible solutions cannot be detected, since */
1567 /* we bound the size of the coefficients for the orbisack inequalities. */
1568 SCIP_CALL( separateOrbisackCovers(scip, conss[c], consdata->nrows, consdata->vars1, consdata->vars2, vals1, vals2, &ngen, &infeasible) );
1569
1570 if ( infeasible )
1571 {
1572 *result = SCIP_CUTOFF;
1573 break;
1574 }
1575
1576 SCIPdebugMsg(scip, "Generated orbisack inequalities for <%s>: %d\n", SCIPconsGetName(conss[c]), ngen);
1577
1578 if ( ngen > 0 )
1579 *result = SCIP_SEPARATED;
1580 }
1581
1582 SCIPfreeBufferArray(scip, &vals2);
1583 SCIPfreeBufferArray(scip, &vals1);
1584 }
1585
1586 return SCIP_OKAY;
1587}
1588
1589
1590/** feasibility check method of constraint handler for integral solutions */
1591static
1592SCIP_DECL_CONSCHECK(consCheckOrbisack)
1593{ /*lint --e{715}*/
1594 SCIP_Bool feasible = TRUE;
1595 SCIP_CONSDATA* consdata;
1596 int c;
1597
1598 assert( scip != NULL );
1599 assert( conshdlr != NULL );
1600 assert( result != NULL );
1601
1602 SCIP_STRINGEQ( SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
1603
1604 *result = SCIP_FEASIBLE;
1605
1606 /* loop through constraints */
1607 for (c = 0; c < nconss; ++c)
1608 {
1609 /* get data of constraint */
1610 assert( conss[c] != NULL );
1611 consdata = SCIPconsGetData(conss[c]);
1612 assert( consdata != NULL);
1613 assert( consdata->nrows > 0 );
1614 assert( consdata->vars1 != NULL );
1615 assert( consdata->vars2 != NULL );
1616
1617 SCIPdebugMsg(scip, "Check method for orbisack constraint <%s> (%d rows) ...\n", SCIPconsGetName(conss[c]), consdata->nrows);
1618
1619 /* do not check non-model constraints */
1620 if ( !consdata->ismodelcons )
1621 continue;
1622
1623 SCIP_CALL( SCIPcheckSolutionOrbisack(scip, sol, consdata->vars1, consdata->vars2, consdata->nrows, printreason, &feasible) );
1624
1625 if ( ! feasible )
1626 {
1627 *result = SCIP_INFEASIBLE;
1628 SCIPdebugMsg(scip, "Solution is feasible.\n");
1629 break;
1630 }
1631 }
1632
1633 if ( feasible )
1634 SCIPdebugMsg(scip, "Solution is feasible.\n");
1635
1636 return SCIP_OKAY;
1637}
1638
1639
1640/** domain propagation method of constraint handler */
1641static
1642SCIP_DECL_CONSPROP(consPropOrbisack)
1643{ /*lint --e{715}*/
1644 int c;
1645
1646 assert( scip != NULL );
1647 assert( conshdlr != NULL );
1648 assert( result != NULL );
1649
1650 SCIP_STRINGEQ( SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
1651
1652 *result = SCIP_DIDNOTRUN;
1653
1654 SCIPdebugMsg(scip, "Propagation method of orbisack constraint handler.\n");
1655
1656 /* loop through constraints */
1657 for (c = 0; c < nconss; ++c)
1658 {
1659 SCIP_Bool infeasible = FALSE;
1660 SCIP_Bool found = FALSE;
1661 int ngen = 0;
1662
1663 assert( conss[c] != NULL );
1664
1665 SCIP_CALL( propVariables(scip, conss[c], &infeasible, &found, &ngen) );
1666
1667 if ( infeasible )
1668 {
1669 *result = SCIP_CUTOFF;
1670 return SCIP_OKAY;
1671 }
1672
1673 if ( found )
1674 *result = SCIP_REDUCEDDOM;
1675 }
1676
1677 return SCIP_OKAY;
1678}
1679
1680
1681/** presolving method of constraint handler */
1682static
1683SCIP_DECL_CONSPRESOL(consPresolOrbisack)
1684{ /*lint --e{715}*/
1685 int c;
1686 int ngen = 0;
1687
1688 assert( scip != NULL );
1689 assert( conshdlr != NULL );
1690 assert( result != NULL );
1691
1692 SCIP_STRINGEQ( SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
1693
1694 SCIPdebugMsg(scip, "Presolving method of orbisack constraint handler. Propagating orbisack inequalities.\n");
1695
1696 *result = SCIP_DIDNOTFIND;
1697
1698 /* loop through constraints */
1699 for (c = 0; c < nconss; ++c)
1700 {
1701 SCIP_Bool infeasible = FALSE;
1702 SCIP_Bool found = FALSE;
1703 int curngen = 0;
1704
1705 assert( conss[c] != NULL );
1706 SCIP_CALL( propVariables(scip, conss[c], &infeasible, &found, &curngen) );
1707
1708 if ( infeasible )
1709 {
1710 *result = SCIP_CUTOFF;
1711 break;
1712 }
1713
1714 ngen += curngen;
1715 }
1716
1717 if ( ngen > 0 )
1718 {
1719 *nfixedvars += ngen;
1720 *result = SCIP_SUCCESS;
1721 }
1722
1723 return SCIP_OKAY;
1724}
1725
1726
1727/** Propagation resolution for conflict analysis */
1728static
1729SCIP_DECL_CONSRESPROP(consRespropOrbisack)
1730{ /*lint --e{715}*/
1731 SCIP_CONSDATA* consdata;
1732 SCIP_VAR** vars1;
1733 SCIP_VAR** vars2;
1734 int i;
1735 int varrow;
1736 int infrow;
1737
1738 assert( scip != NULL );
1739 assert( conshdlr != NULL );
1740 assert( cons != NULL );
1741 assert( infervar != NULL );
1742 assert( bdchgidx != NULL );
1743 assert( result != NULL );
1744
1745 SCIP_STRINGEQ( SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
1746
1747 SCIPdebugMsg(scip, "Propagation resolution method of orbisack constraint handler.\n");
1748
1749 *result = SCIP_DIDNOTFIND;
1750
1751 consdata = SCIPconsGetData(cons);
1752 assert( consdata != NULL);
1753 assert( consdata->nrows > 0 );
1754 assert( consdata->vars1 != NULL );
1755 assert( consdata->vars2 != NULL );
1756
1757 vars1 = consdata->vars1;
1758 vars2 = consdata->vars2;
1759
1760 /* inferinfo == varrow + infrow * nrows. infrow is 0 if the fixing is not caused by a lookahead. */
1761 varrow = inferinfo % consdata->nrows;
1762 infrow = inferinfo / consdata->nrows;
1763
1764 assert( varrow >= 0 );
1765 assert( varrow < consdata->nrows );
1766 assert( infrow >= 0 );
1767 assert( infrow < consdata->nrows );
1768
1769 /* In both cases, the rows until "varrow" are constants. */
1770 for (i = 0; i < varrow; ++i)
1771 {
1772 /* Conflict caused by bounds of previous variables */
1773 SCIP_CALL( SCIPaddConflictUb(scip, vars1[i], bdchgidx) );
1774 SCIP_CALL( SCIPaddConflictLb(scip, vars1[i], bdchgidx) );
1775 SCIP_CALL( SCIPaddConflictUb(scip, vars2[i], bdchgidx) );
1776 SCIP_CALL( SCIPaddConflictLb(scip, vars2[i], bdchgidx) );
1777 }
1778
1779 if ( infrow > 0 )
1780 {
1781 /* The fixing of infervar is caused by a lookahead (checkFeasible).
1782 * The rows until "varrow" are constants, and row "varrow" is (_, _), (1, _), (_, 0).
1783 * If we assume "varrow" is constant, then the next rows until infrow are constants, and infrow is (0, 1).
1784 */
1785 for (i = varrow + 1; i < infrow; ++i)
1786 {
1787 /* These rows are one of (0, 0), (1, 1), (0, _), (_, 1), making them constants. */
1788 SCIP_CALL( SCIPaddConflictUb(scip, vars1[i], bdchgidx) );
1789 SCIP_CALL( SCIPaddConflictLb(scip, vars1[i], bdchgidx) );
1790 SCIP_CALL( SCIPaddConflictUb(scip, vars2[i], bdchgidx) );
1791 SCIP_CALL( SCIPaddConflictLb(scip, vars2[i], bdchgidx) );
1792 }
1793
1794 /* And infrow itself is (0, 1). */
1795 assert( SCIPgetVarUbAtIndex(scip, vars1[infrow], bdchgidx, TRUE) < 0.5 );
1796 assert( SCIPgetVarUbAtIndex(scip, vars1[infrow], bdchgidx, FALSE) < 0.5 );
1797 assert( SCIPgetVarLbAtIndex(scip, vars2[infrow], bdchgidx, TRUE) > 0.5 );
1798 assert( SCIPgetVarLbAtIndex(scip, vars2[infrow], bdchgidx, FALSE) > 0.5 );
1799
1800 SCIP_CALL( SCIPaddConflictUb(scip, vars1[infrow], bdchgidx) );
1801 SCIP_CALL( SCIPaddConflictLb(scip, vars2[infrow], bdchgidx) );
1802 }
1803 else
1804 {
1805 /* This is not a fixing caused by lookahead (checkFeasible),
1806 * so row "varrow" was (0, _) or (_, 1) and its previous rows are constants.
1807 */
1808 if ( boundtype == SCIP_BOUNDTYPE_LOWER )
1809 {
1810 /* We changed the lower bound of infervar to 1. This means that this fixing is due to (_, 1) */
1811 assert( infervar == vars1[varrow] );
1812 assert( SCIPgetVarLbAtIndex(scip, vars1[varrow], bdchgidx, FALSE) < 0.5 );
1813 assert( SCIPgetVarLbAtIndex(scip, vars1[varrow], bdchgidx, TRUE) > 0.5 );
1814 assert( SCIPgetVarLbAtIndex(scip, vars2[varrow], bdchgidx, FALSE) > 0.5);
1815 assert( SCIPgetVarUbAtIndex(scip, vars2[varrow], bdchgidx, FALSE) > 0.5);
1816
1817 SCIP_CALL( SCIPaddConflictUb(scip, vars2[varrow], bdchgidx) );
1818 SCIP_CALL( SCIPaddConflictLb(scip, vars2[varrow], bdchgidx) );
1819 }
1820 else
1821 {
1822 /* We changed the upper bound to 0. This means that this fixing is due to (0, _) */
1823 assert( infervar == vars2[varrow] );
1824 assert( SCIPgetVarLbAtIndex(scip, vars1[varrow], bdchgidx, FALSE) < 0.5);
1825 assert( SCIPgetVarUbAtIndex(scip, vars1[varrow], bdchgidx, FALSE) < 0.5);
1826 assert( SCIPgetVarUbAtIndex(scip, vars2[varrow], bdchgidx, FALSE) > 0.5 );
1827 assert( SCIPgetVarUbAtIndex(scip, vars2[varrow], bdchgidx, TRUE) < 0.5 );
1828
1829 SCIP_CALL( SCIPaddConflictUb(scip, vars1[varrow], bdchgidx) );
1830 SCIP_CALL( SCIPaddConflictLb(scip, vars1[varrow], bdchgidx) );
1831 }
1832 }
1833
1834 *result = SCIP_SUCCESS;
1835 return SCIP_OKAY;
1836}
1837
1838
1839/** presolving deinitialization method of constraint handler (called after presolving has been finished) */
1840static
1841SCIP_DECL_CONSEXITPRE(consExitpreOrbisack)
1842{
1843 int c;
1844
1845 assert( scip != NULL );
1846 assert( conshdlr != NULL );
1847
1848 SCIP_STRINGEQ( SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
1849
1850 for (c = 0; c < nconss; ++c)
1851 {
1852 /* replace aggregated variables by active variables */
1853 SCIP_CALL( replaceAggregatedVarsOrbisack(scip, conss[c]) );
1854 }
1855 return SCIP_OKAY;
1856}
1857
1858
1859/** Lock variables
1860 *
1861 * We assume we have only one global (void) constraint and lock all variables.
1862 *
1863 * - Orbisack constraints may get violated if the variables of the first column
1864 * are rounded down, we therefor call SCIPaddVarLocksType(..., nlockspos, nlocksneg).
1865 * - Orbisack constraints may get violated if the variables of the second column
1866 * are rounded up , we therefor call SCIPaddVarLocksType(..., nlocksneg, nlockspo ).
1867 */
1868static
1869SCIP_DECL_CONSLOCK(consLockOrbisack)
1870{ /*lint --e{715}*/
1871 SCIP_CONSDATA* consdata;
1872 SCIP_VAR** vars1;
1873 SCIP_VAR** vars2;
1874 int nrows;
1875 int i;
1876
1877 assert( scip != NULL );
1878 assert( conshdlr != NULL );
1879 assert( cons != NULL );
1880
1881 SCIP_STRINGEQ( SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
1882
1883 SCIPdebugMsg(scip, "Locking method for orbisack constraint handler.\n");
1884
1885 /* get data of original constraint */
1886 consdata = SCIPconsGetData(cons);
1887 assert( consdata != NULL);
1888 assert( consdata->nrows > 0 );
1889 assert( consdata->vars1 != NULL );
1890 assert( consdata->vars2 != NULL );
1891
1892 nrows = consdata->nrows;
1893 vars1 = consdata->vars1;
1894 vars2 = consdata->vars2;
1895
1896 for (i = 0; i < nrows; ++i)
1897 {
1898 SCIP_CALL( SCIPaddVarLocksType(scip, vars1[i], locktype, nlockspos, nlocksneg) );
1899 SCIP_CALL( SCIPaddVarLocksType(scip, vars2[i], locktype, nlocksneg, nlockspos) );
1900 }
1901
1902 return SCIP_OKAY;
1903}
1904
1905
1906/** constraint copying method of constraint handler */
1907static
1908SCIP_DECL_CONSCOPY(consCopyOrbisack)
1909{
1910 SCIP_CONSHDLRDATA* conshdlrdata;
1911 SCIP_CONSDATA* sourcedata;
1912 SCIP_VAR** sourcevars1;
1913 SCIP_VAR** sourcevars2;
1914 SCIP_VAR** vars1;
1915 SCIP_VAR** vars2;
1916 int nrows;
1917 int i;
1918
1919 assert( scip != NULL );
1920 assert( cons != NULL );
1921 assert( sourcescip != NULL );
1922 assert( sourceconshdlr != NULL );
1923 assert( sourcecons != NULL );
1924 assert( varmap != NULL );
1925 assert( valid != NULL );
1926
1927 SCIP_STRINGEQ( SCIPconshdlrGetName(sourceconshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
1928
1929 *valid = TRUE;
1930
1931 SCIPdebugMsg(scip, "Copying method for orbisack constraint handler.\n");
1932
1933 sourcedata = SCIPconsGetData(sourcecons);
1934 assert( sourcedata != NULL );
1935 assert( sourcedata->vars1 != NULL );
1936 assert( sourcedata->vars2 != NULL );
1937 assert( sourcedata->nrows > 0 );
1938
1939 conshdlrdata = SCIPconshdlrGetData(sourceconshdlr);
1940 assert( conshdlrdata != NULL );
1941
1942 /* do not copy non-model constraints */
1943 if ( !sourcedata->ismodelcons && !conshdlrdata->forceconscopy )
1944 {
1945 *valid = FALSE;
1946
1947 return SCIP_OKAY;
1948 }
1949
1950 sourcevars1 = sourcedata->vars1;
1951 sourcevars2 = sourcedata->vars2;
1952 nrows = sourcedata->nrows;
1953
1954 SCIP_CALL( SCIPallocBufferArray(scip, &vars1, nrows) );
1955
1956 for (i = 0; i < nrows && *valid; ++i)
1957 {
1958 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars1[i], &(vars1[i]), varmap, consmap, global, valid) );
1959 assert( !(*valid) || vars1[i] != NULL );
1960 }
1961
1962 /* only create the target constraint, if all variables could be copied */
1963 if ( !(*valid) )
1964 {
1965 SCIPfreeBufferArray(scip, &vars1);
1966
1967 return SCIP_OKAY;
1968 }
1969
1970 SCIP_CALL( SCIPallocBufferArray(scip, &vars2, nrows) );
1971
1972 for (i = 0; i < nrows && *valid; ++i)
1973 {
1974 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars2[i], &(vars2[i]), varmap, consmap, global, valid) );
1975 assert( !(*valid) || vars2[i] != NULL );
1976 }
1977
1978 /* only create the target constraint, if all variables could be copied */
1979 if ( *valid )
1980 {
1981 /* create copied constraint */
1982 if ( name == NULL )
1983 name = SCIPconsGetName(sourcecons);
1984
1985 SCIP_CALL( SCIPcreateConsOrbisack(scip, cons, name, vars1, vars2, nrows, FALSE, FALSE, sourcedata->ismodelcons,
1986 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
1987 }
1988
1989 SCIPfreeBufferArray(scip, &vars2);
1990 SCIPfreeBufferArray(scip, &vars1);
1991
1992 return SCIP_OKAY;
1993}
1994
1995
1996/** constraint parsing method of constraint handler */
1997static
1998SCIP_DECL_CONSPARSE(consParseOrbisack)
1999{ /*lint --e{715}*/
2000 const char* s;
2001 char* endptr;
2002 SCIP_VAR** vars1;
2003 SCIP_VAR** vars2;
2004 SCIP_VAR* var;
2005 int nrows = 0;
2006 int maxnrows = 128;
2007 SCIP_Bool firstcolumn = TRUE;
2008 SCIP_Bool ispporbisack = FALSE;
2009 SCIP_Bool isparttype = FALSE;
2010
2011 assert( success != NULL );
2012
2013 *success = TRUE;
2014 s = str;
2015
2016 /* skip white space */
2017 SCIP_CALL( SCIPskipSpace((char**)&s) );
2018
2019 if( strncmp(s, "partOrbisack(", 13) == 0 )
2020 {
2021 ispporbisack = TRUE;
2022 isparttype = TRUE;
2023 }
2024 else if( strncmp(s, "packOrbisack(", 13) == 0 )
2025 ispporbisack = TRUE;
2026 else
2027 {
2028 if( strncmp(s, "fullOrbisack(", 13) != 0 )
2029 {
2030 SCIPerrorMessage("Syntax error - expected \"fullOrbisack(\", \"partOrbisack\" or \"packOrbisacj\": %s\n", s);
2031 *success = FALSE;
2032 return SCIP_OKAY;
2033 }
2034 }
2035 s += 13;
2036
2037 /* loop through string */
2038 SCIP_CALL( SCIPallocBufferArray(scip, &vars1, maxnrows) );
2039 SCIP_CALL( SCIPallocBufferArray(scip, &vars2, maxnrows) );
2040
2041 do
2042 {
2043 /* parse variable name */
2044 SCIP_CALL( SCIPparseVarName(scip, s, &var, &endptr) );
2045
2046 if( var == NULL )
2047 {
2048 endptr = strchr(endptr, ')');
2049
2050 if( endptr == NULL || !firstcolumn )
2051 {
2052 SCIPerrorMessage("variable is missing.\n");
2053 *success = FALSE;
2054 }
2055
2056 break;
2057 }
2058
2059 s = endptr;
2060 assert( s != NULL );
2061
2062 /* skip white space */
2063 SCIP_CALL( SCIPskipSpace((char**)&s) );
2064
2065 if( firstcolumn == ( *s == '.' || *s == ')' ) )
2066 {
2067 SCIPerrorMessage("there are not two variables per row.\n");
2068 *success = FALSE;
2069 break;
2070 }
2071
2072 /* begin new row if required */
2073 if( firstcolumn )
2074 {
2075 ++nrows;
2076
2077 if( nrows > maxnrows )
2078 {
2079 maxnrows = SCIPcalcMemGrowSize(scip, nrows);
2080 SCIP_CALL( SCIPreallocBufferArray(scip, &vars1, maxnrows) );
2081 SCIP_CALL( SCIPreallocBufferArray(scip, &vars2, maxnrows) );
2082 assert( nrows <= maxnrows );
2083 }
2084
2085 vars1[nrows-1] = var;
2086 }
2087 else
2088 vars2[nrows-1] = var;
2089
2090 firstcolumn = !firstcolumn;
2091
2092 /* skip ',' or '.' */
2093 if( *s == ',' || *s == '.' )
2094 ++s;
2095 }
2096 while( *s != ')' );
2097
2098 if( *success )
2099 SCIP_CALL( SCIPcreateConsBasicOrbisack(scip, cons, name, vars1, vars2, nrows, ispporbisack, isparttype, TRUE) );
2100
2101 SCIPfreeBufferArray(scip, &vars2);
2102 SCIPfreeBufferArray(scip, &vars1);
2103
2104 return SCIP_OKAY;
2105}
2106
2107
2108/** constraint display method of constraint handler
2109 *
2110 * The constraint handler should output a representation of the constraint into the given text file.
2111 */
2112static
2113SCIP_DECL_CONSPRINT(consPrintOrbisack)
2114{ /*lint --e{715}*/
2115 SCIP_CONSDATA* consdata;
2116 SCIP_VAR** vars1;
2117 SCIP_VAR** vars2;
2118 int nrows;
2119 int i;
2120
2121 assert( scip != NULL );
2122 assert( conshdlr != NULL );
2123 assert( cons != NULL );
2124
2125 SCIP_STRINGEQ( SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
2126
2127 consdata = SCIPconsGetData(cons);
2128 assert( consdata != NULL );
2129 assert( consdata->vars1 != NULL );
2130 assert( consdata->vars2 != NULL );
2131 assert( consdata->nrows > 0 );
2132
2133 vars1 = consdata->vars1;
2134 vars2 = consdata->vars2;
2135 nrows = consdata->nrows;
2136
2137 SCIPdebugMsg(scip, "Printing method for orbisack constraint handler\n");
2138
2139 SCIPinfoMessage(scip, file, "fullOrbisack(");
2140
2141 for (i = 0; i < nrows; ++i)
2142 {
2143 SCIP_CALL( SCIPwriteVarName(scip, file, vars1[i], TRUE) );
2144 SCIPinfoMessage(scip, file, ",");
2145 SCIP_CALL( SCIPwriteVarName(scip, file, vars2[i], TRUE) );
2146 if ( i < nrows-1 )
2147 SCIPinfoMessage(scip, file, ".");
2148 }
2149
2150 SCIPinfoMessage(scip, file, ")");
2151
2152 return SCIP_OKAY;
2153}
2154
2155
2156/** checks given solution for feasibility */
2157SCIP_RETCODE SCIPcheckSolutionOrbisack(
2158 SCIP* scip, /**< SCIP data structure */
2159 SCIP_SOL* sol, /**< solution to check for feasibility */
2160 SCIP_VAR** vars1, /**< variables of first column */
2161 SCIP_VAR** vars2, /**< variables of second column */
2162 int nrows, /**< number of rows */
2163 SCIP_Bool printreason, /**< whether reason for infeasibility should be printed */
2164 SCIP_Bool* feasible /**< memory address to store whether sol is feasible */
2165 )
2166{
2167 int i;
2168 int val1;
2169 int val2;
2170
2171 assert( scip != NULL );
2172 assert( vars1 != NULL );
2173 assert( vars2 != NULL );
2174 assert( nrows > 0 );
2175 assert( feasible != NULL );
2176
2177 *feasible = TRUE;
2178
2179 /* find first non-constant row and check for feasibility */
2180 for (i = 0; i < nrows; ++i)
2181 {
2182 assert( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, vars1[i])) );
2183 assert( SCIPisFeasIntegral(scip, SCIPgetSolVal(scip, sol, vars2[i])) );
2184
2185 /* get values of i-th row */
2186 val1 = SCIPgetSolVal(scip, sol, vars1[i]) > 0.5 ? 1 : 0;
2187 val2 = SCIPgetSolVal(scip, sol, vars2[i]) > 0.5 ? 1 : 0;
2188
2189 /* if row i is constrant */
2190 if ( val1 == val2 )
2191 continue;
2192 /* row i has type (1,0) -> feasible */
2193 else if ( val1 == 1 )
2194 {
2195 assert( val2 == 0 );
2196 break;
2197 }
2198 else /* infeasible */
2199 {
2200 if ( printreason )
2201 SCIPinfoMessage(scip, NULL, "First non-constant row %d is fixed to (0,1).\n", i);
2202 *feasible = FALSE;
2203 break;
2204 }
2205 }
2206
2207 return SCIP_OKAY;
2208}
2209
2210
2211/** constraint method of constraint handler which returns the variables (if possible) */
2212static
2213SCIP_DECL_CONSGETVARS(consGetVarsOrbisack)
2214{ /*lint --e{715}*/
2215 SCIP_CONSDATA* consdata;
2216
2217 assert( cons != NULL );
2218 assert( success != NULL );
2219 assert( vars != NULL );
2220
2221 consdata = SCIPconsGetData(cons);
2222 assert( consdata != NULL );
2223
2224 if ( varssize < 2 * consdata->nrows )
2225 (*success) = FALSE;
2226 else
2227 {
2228 int cnt = 0;
2229 int i;
2230
2231 for (i = 0; i < consdata->nrows; ++i)
2232 {
2233 vars[cnt++] = consdata->vars1[i];
2234 vars[cnt++] = consdata->vars2[i];
2235 }
2236 (*success) = TRUE;
2237 }
2238
2239 return SCIP_OKAY;
2240}
2241
2242
2243/** constraint method of constraint handler which returns the number of variables (if possible) */
2244static
2245SCIP_DECL_CONSGETNVARS(consGetNVarsOrbisack)
2246{ /*lint --e{715}*/
2247 SCIP_CONSDATA* consdata;
2248
2249 assert( cons != NULL );
2250
2251 consdata = SCIPconsGetData(cons);
2252 assert( consdata != NULL );
2253
2254 (*nvars) = 2 * consdata->nrows;
2255 (*success) = TRUE;
2256
2257 return SCIP_OKAY;
2258}
2259
2260
2261/** creates the handler for orbisack constraints and includes it in SCIP */
2262SCIP_RETCODE SCIPincludeConshdlrOrbisack(
2263 SCIP* scip /**< SCIP data structure */
2264 )
2265{
2266 SCIP_CONSHDLRDATA* conshdlrdata = NULL;
2267 SCIP_CONSHDLR* conshdlr;
2268
2269 SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) );
2270
2271 /* include constraint handler */
2272 SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC,
2273 CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY,
2274 CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS,
2275 consEnfolpOrbisack, consEnfopsOrbisack, consCheckOrbisack, consLockOrbisack,
2276 conshdlrdata) );
2277 assert( conshdlr != NULL );
2278
2279 /* set non-fundamental callbacks via specific setter functions */
2280 SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyOrbisack, consCopyOrbisack) );
2281 SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxOrbisack) );
2282 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeOrbisack) );
2283 SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteOrbisack) );
2284 SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsOrbisack) );
2285 SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsOrbisack) );
2286 SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseOrbisack) );
2287 SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolOrbisack, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
2288 SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintOrbisack) );
2289 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropOrbisack, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP, CONSHDLR_PROP_TIMING) );
2290 SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropOrbisack) );
2291 SCIP_CALL( SCIPsetConshdlrExitpre(scip, conshdlr, consExitpreOrbisack) );
2292 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpOrbisack, consSepasolOrbisack, CONSHDLR_SEPAFREQ, CONSHDLR_SEPAPRIORITY, CONSHDLR_DELAYSEPA) );
2293 SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransOrbisack) );
2294 SCIP_CALL( SCIPsetConshdlrInitlp(scip, conshdlr, consInitlpOrbisack) );
2295 SCIP_CALL( SCIPsetConshdlrInitsol(scip, conshdlr, consInitsolOrbisack) );
2296
2297 /* separation methods */
2298 SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/coverseparation",
2299 "Separate cover inequalities for orbisacks?",
2300 &conshdlrdata->coverseparation, TRUE, DEFAULT_COVERSEPARATION, NULL, NULL) );
2301
2302 SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/orbiSeparation",
2303 "Separate orbisack inequalities?",
2304 &conshdlrdata->orbiseparation, TRUE, DEFAULT_ORBISEPARATION, NULL, NULL) );
2305
2306 SCIP_CALL( SCIPaddRealParam(scip, "constraints/" CONSHDLR_NAME "/coeffbound",
2307 "Maximum size of coefficients for orbisack inequalities",
2308 &conshdlrdata->coeffbound, TRUE, DEFAULT_COEFFBOUND, 0.0, DBL_MAX, NULL, NULL) );
2309
2310 /* whether we allow upgrading to packing/partioning orbisack constraints*/
2311 SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/checkpporbisack",
2312 "Upgrade orbisack constraints to packing/partioning orbisacks?",
2313 &conshdlrdata->checkpporbisack, TRUE, DEFAULT_PPORBISACK, NULL, NULL) );
2314
2315 SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/forceconscopy",
2316 "Whether orbisack constraints should be forced to be copied to sub SCIPs.",
2317 &conshdlrdata->forceconscopy, TRUE, DEFAULT_FORCECONSCOPY, NULL, NULL) );
2318
2319 return SCIP_OKAY;
2320}
2321
2322
2323/*
2324 * constraint specific interface methods
2325 */
2326
2327/** creates and captures a orbisack constraint
2328 *
2329 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
2330 */
2331SCIP_RETCODE SCIPcreateConsOrbisack(
2332 SCIP* scip, /**< SCIP data structure */
2333 SCIP_CONS** cons, /**< pointer to hold the created constraint */
2334 const char* name, /**< name of constraint */
2335 SCIP_VAR*const* vars1, /**< first column of matrix of variables on which the symmetry acts */
2336 SCIP_VAR*const* vars2, /**< second column of matrix of variables on which the symmetry acts */
2337 int nrows, /**< number of rows in variable matrix */
2338 SCIP_Bool ispporbisack, /**< whether the orbisack is a packing/partitioning orbisack */
2339 SCIP_Bool isparttype, /**< whether the orbisack is a partitioning orbisack */
2340 SCIP_Bool ismodelcons, /**< whether the orbisack is a model constraint */
2341 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
2342 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
2343 SCIP_Bool separate, /**< should the constraint be separated during LP processing?
2344 * Usually set to TRUE. */
2345 SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
2346 * TRUE for model constraints, FALSE for additional, redundant constraints. */
2347 SCIP_Bool check, /**< should the constraint be checked for feasibility?
2348 * TRUE for model constraints, FALSE for additional, redundant constraints. */
2349 SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
2350 * Usually set to TRUE. */
2351 SCIP_Bool local, /**< is constraint only valid locally?
2352 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
2353 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
2354 * Usually set to FALSE. In column generation applications, set to TRUE if pricing
2355 * adds coefficients to this constraint. */
2356 SCIP_Bool dynamic, /**< is constraint subject to aging?
2357 * Usually set to FALSE. Set to TRUE for own cuts which
2358 * are separated as constraints. */
2359 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
2360 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
2361 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
2362 * if it may be moved to a more global node?
2363 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
2364 )
2365{
2366 SCIP_CONSHDLR* conshdlr;
2367 SCIP_CONSHDLRDATA* conshdlrdata;
2368 SCIP_CONSDATA* consdata;
2369 SCIP_VAR*** vars;
2370 SCIP_Bool success;
2371 SCIP_ORBITOPETYPE orbitopetype;
2372 int i;
2373
2374 /* find the orbisack constraint handler */
2375 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2376 if ( conshdlr == NULL )
2377 {
2378 SCIPerrorMessage("orbisack constraint handler not found\n");
2379 return SCIP_PLUGINNOTFOUND;
2380 }
2381
2382 assert( nrows > 0 );
2383
2384 /* check for upgrade to packing/partitioning orbisacks*/
2385 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2386 if ( ! ispporbisack && conshdlrdata->checkpporbisack )
2387 {
2388 SCIP_CALL( packingUpgrade(scip, vars1, vars2, nrows, &success, &isparttype) );
2389
2390 if ( success )
2391 ispporbisack = TRUE;
2392 }
2393
2394 /* create constraint, if it is a packing/partitioning orbisack, add orbitope constraint
2395 * instead of orbitsack constraint */
2396 if ( ispporbisack )
2397 {
2398 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nrows) );
2399 for (i = 0; i < nrows; ++i)
2400 {
2401 SCIP_CALL( SCIPallocBufferArray(scip, &vars[i], 2) ); /*lint !e866*/
2402 vars[i][0] = vars1[i];
2403 vars[i][1] = vars2[i];
2404 }
2405
2406 if ( isparttype )
2407 orbitopetype = SCIP_ORBITOPETYPE_PARTITIONING;
2408 else
2409 orbitopetype = SCIP_ORBITOPETYPE_PACKING;
2410
2411 SCIP_CALL( SCIPcreateConsOrbitope(scip, cons, "pporbisack", vars, orbitopetype, nrows,
2412 2, TRUE, ismodelcons, FALSE, initial, separate, enforce, check, propagate, local,
2413 modifiable, dynamic, removable, stickingatnode) );
2414
2415 for (i = 0; i < nrows; ++i)
2416 SCIPfreeBufferArray(scip, &vars[i]);
2417 SCIPfreeBufferArray(scip, &vars);
2418 }
2419 else
2420 {
2421 /* create constraint data */
2422 SCIP_CALL( consdataCreate(scip, &consdata, vars1, vars2, nrows, ismodelcons) );
2423
2424 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
2425 local, modifiable, dynamic, removable, stickingatnode) );
2426 }
2427
2428 return SCIP_OKAY;
2429}
2430
2431
2432/** creates and captures an orbisack constraint in its most basic variant
2433 *
2434 * All constraint flags set to their default values, which can be set afterwards using SCIPsetConsFLAGNAME() in scip.h.
2435 *
2436 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
2437 */
2438SCIP_RETCODE SCIPcreateConsBasicOrbisack(
2439 SCIP* scip, /**< SCIP data structure */
2440 SCIP_CONS** cons, /**< pointer to hold the created constraint */
2441 const char* name, /**< name of constraint */
2442 SCIP_VAR** vars1, /**< first column of matrix of variables on which the symmetry acts */
2443 SCIP_VAR** vars2, /**< second column of matrix of variables on which the symmetry acts */
2444 int nrows, /**< number of rows in constraint matrix */
2445 SCIP_Bool ispporbisack, /**< whether the orbisack is a packing/partitioning orbisack */
2446 SCIP_Bool isparttype, /**< whether the orbisack is a partitioning orbisack */
2447 SCIP_Bool ismodelcons /**< whether the orbisack is a model constraint */
2448 )
2449{
2450 SCIP_CALL( SCIPcreateConsOrbisack(scip, cons, name, vars1, vars2, nrows, ispporbisack, isparttype, ismodelcons,
2451 TRUE, TRUE, FALSE, FALSE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
2452
2453 return SCIP_OKAY;
2454}
CONSHDLR_NEEDSCONS
#define CONSHDLR_NEEDSCONS
Definition cons_and.c:96
CONSHDLR_SEPAFREQ
#define CONSHDLR_SEPAFREQ
Definition cons_and.c:89
CONSHDLR_CHECKPRIORITY
#define CONSHDLR_CHECKPRIORITY
Definition cons_and.c:88
CONSHDLR_DESC
#define CONSHDLR_DESC
Definition cons_and.c:85
CONSHDLR_PROP_TIMING
#define CONSHDLR_PROP_TIMING
Definition cons_and.c:99
CONSHDLR_MAXPREROUNDS
#define CONSHDLR_MAXPREROUNDS
Definition cons_and.c:93
CONSHDLR_SEPAPRIORITY
#define CONSHDLR_SEPAPRIORITY
Definition cons_and.c:86
CONSHDLR_PROPFREQ
#define CONSHDLR_PROPFREQ
Definition cons_and.c:90
CONSHDLR_PRESOLTIMING
#define CONSHDLR_PRESOLTIMING
Definition cons_and.c:98
CONSHDLR_EAGERFREQ
#define CONSHDLR_EAGERFREQ
Definition cons_and.c:91
CONSHDLR_ENFOPRIORITY
#define CONSHDLR_ENFOPRIORITY
Definition cons_and.c:87
CONSHDLR_DELAYSEPA
#define CONSHDLR_DELAYSEPA
Definition cons_and.c:94
CONSHDLR_NAME
#define CONSHDLR_NAME
Definition cons_and.c:84
CONSHDLR_DELAYPROP
#define CONSHDLR_DELAYPROP
Definition cons_and.c:95
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:257
SCIP_UNUSED
#define SCIP_UNUSED(x)
Definition def.h:418
SCIP_Bool
#define SCIP_Bool
Definition def.h:100
SCIP_STRINGEQ
#define SCIP_STRINGEQ(name, reference, retcode)
Definition def.h:454
SCIP_Real
#define SCIP_Real
Definition def.h:165
TRUE
#define TRUE
Definition def.h:102
FALSE
#define FALSE
Definition def.h:103
SCIP_CALL
#define SCIP_CALL(x)
Definition def.h:364
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:2157
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:2438
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:2331
SCIPincludeConshdlrOrbisack
SCIP_RETCODE SCIPincludeConshdlrOrbisack(SCIP *scip)
Definition cons_orbisack.c:2262
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:655
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:4320
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:4340
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:8423
SCIPconsIsDynamic
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition cons.c:8652
SCIPconsGetHdlr
SCIP_CONSHDLR * SCIPconsGetHdlr(SCIP_CONS *cons)
Definition cons.c:8413
SCIPconsIsInitial
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition cons.c:8562
SCIPconsIsChecked
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition cons.c:8592
SCIPconsIsEnforced
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition cons.c:8582
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:8612
SCIPconsIsLocal
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition cons.c:8632
SCIPconsGetName
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition cons.c:8393
SCIPconsIsModifiable
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition cons.c:8642
SCIPconsIsStickingAtNode
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition cons.c:8672
SCIPconsIsSeparated
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition cons.c:8572
SCIPconsIsRemovable
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition cons.c:8662
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:1844
SCIPgetSolVal
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition scip_sol.c:1763
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
SCIPlockVarCons
SCIP_RETCODE SCIPlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition scip_var.c:5210
SCIPvarIsActive
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition var.c:23674
SCIPvarIsBinary
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition var.c:23510
SCIPvarGetStatus
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition var.c:23418
SCIPvarGetUbLocal
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:24300
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
SCIPunlockVarCons
SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition scip_var.c:5296
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:24266
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:297
SCIP_OKAY
return SCIP_OKAY
Definition heur_actconsdiving.c:237
c
int c
Definition heur_intdiving.c:223
sol
static SCIP_SOL * sol
Definition heur_intshifting.c:696
assert
assert(minobj< SCIPgetCutoffbound(scip))
var
SCIP_VAR * var
Definition heur_objpscostdiving.c:269
propagate
static SCIP_Bool propagate
Definition heur_randrounding.c:468
vars
static SCIP_VAR ** vars
Definition heur_rootsoldiving.c:190
i
int i
Definition heur_rootsoldiving.c:216
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:1219
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:867
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:769
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:506
SCIP_DECL_CONSGETNVARS
#define SCIP_DECL_CONSGETNVARS(x)
Definition type_cons.h:885
SCIP_DECL_CONSRESPROP
#define SCIP_DECL_CONSRESPROP(x)
Definition type_cons.h:612
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:845
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:561
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:676
SCIP_CONSHDLR
struct SCIP_Conshdlr SCIP_CONSHDLR
Definition type_cons.h:62
SCIP_DECL_CONSCOPY
#define SCIP_DECL_CONSCOPY(x)
Definition type_cons.h:810
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_INVALIDCALL
@ SCIP_INVALIDCALL
Definition type_retcode.h:51
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