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