Scippy

SCIP

Solving Constraint Integer Programs

cons_orbitope.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2024 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file cons_orbitope.c
26 * @ingroup DEFPLUGINS_CONS
27 * @brief constraint handler for (partitioning/packing/full) orbitope constraints w.r.t. the full symmetric group
28 * @author Timo Berthold
29 * @author Marc Pfetsch
30 * @author Christopher Hojny
31 *
32 * The type of constraints of this constraint handler is described in cons_orbitope.h.
33 *
34 * The details of the method implemented here are described in the following papers.
35 *
36 * Packing and Partitioning Orbitopes@n
37 * Volker Kaibel and Marc E. Pfetsch,@n
38 * Math. Program. 114, No. 1, 1-36 (2008)
39 *
40 * Among other things, this paper describes so-called shifted column inequalities of the following
41 * form \f$x(S) \leq x(B)\f$, where \f$S\f$ is a so-called shifted column and \f$B\f$ is a so-called
42 * bar. These inequalities can be used to handle symmetry and they are separated in this constraint
43 * handler. We use the linear time separation algorithm of the paper.@par
44 *
45 * Orbitopal Fixing@n
46 * Volker Kaibel, Matthias Peinhardt, and Marc E. Pfetsch,@n
47 * Discrete Optimization 8, No. 4, 595-610 (2011)
48 * (A preliminary version appears in Proc. IPCO 2007.)
49 *
50 * In this paper a linear time propagation algorithm is described, a variant of which is implemented
51 * here. The implemented variant does not run in linear time, but is very fast in practice.
52 *
53 * <table>
54 * <caption>translation table</caption>
55 * <tr><td>here</td><td>paper</td></tr>
56 * <tr><td></td><td></td></tr>
57 * <tr><td>nspcons </td><td>p </td></tr>
58 * <tr><td>nblocks </td><td>q </td></tr>
59 * <tr><td>vars </td><td>x </td></tr>
60 * <tr><td>vals </td><td>A^\\star</td></tr>
61 * <tr><td>weights </td><td>\\omega </td></tr>
62 * <tr><td>cases </td><td>\\tau </td></tr>
63 * <tr><td>fixtriangle </td><td>-- </td></tr>
64 * <tr><td>resolveprop </td><td>-- </td></tr>
65 * <tr><td>firstnonzeros</td><td>\\mu </td></tr>
66 * <tr><td>lastones </td><td>\\alpha </td></tr>
67 * <tr><td>frontiersteps</td><td>\\Gamma </td></tr>
68 * </table>
69 *
70 * Orbitopal fixing for the full (sub-)orbitope and application to the Unit Commitment Problem@n
71 * Pascale Bendotti, Pierre Fouilhoux, and Cecile Rottner,@n
72 * Optimization Online: http://www.optimization-online.org/DB_HTML/2017/10/6301.html
73 *
74 * Two linear time propagation algorithms for full orbitopes are described in this paper, a static
75 * version and a dynamic one. While the static version uses a fixed variable order, the dynamic
76 * version determines the variable order during the solving process via branching descisions.
77 * We implemented the static version as well as a modified version of the dynamic one. The reason
78 * for the latter is to simplify the compatibility with full orbitope cutting planes.
79 *
80 * Note, however, that the dynamic version may lead to conflicts if orbitopes are copied to subSCIPs.
81 * Since the dynamic version is based on branching decisions, which may be different in main SCIP
82 * and subSCIPs, orbitopes using the dynamic algorithm are not allowed to be copied. However, as a
83 * user might use orbitopes to enforce a certain variable ordering in a solution, we distinguish
84 * whether an orbitope is a model constraint or not. If it is a model constraint, we assume that
85 * a variable order has already been fixed and disable the dynamic algorithm. In this case, orbitope
86 * constraints are copied to subSCIPs. If it is not a model constraint, the orbitope was added to
87 * handle symmetries but not to enforce a solution to have a certain structure. In this case, the
88 * dynamic algorithm can be used and we do not copy orbitope constraints to subSCIPs.
89 *
90 * Polytopes associated with symmetry handling@n
91 * Christopher Hojny and Marc E. Pfetsch,@n
92 * Math. Program. (2018)
93 *
94 * In this paper, a linear time separation algorithm for orbisacks (full orbitopes with two columnes)
95 * is described. We use this algorithm for every pair of adjacent columns within the orbitope as well
96 * as a version that is adapted to the reordering based on the dynamic full orbitope propagation
97 * algorithm to ensure validity of binary points via cutting planes.
98 */
99
100/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
101
102#include "blockmemshell/memory.h"
103#include "scip/cons_orbisack.h"
104#include "scip/cons_orbitope.h"
105#include "scip/cons_setppc.h"
106#include "scip/pub_cons.h"
107#include "scip/pub_message.h"
108#include "scip/pub_var.h"
109#include "scip/scip.h"
110#include "scip/scip_branch.h"
111#include "scip/scip_conflict.h"
112#include "scip/scip_cons.h"
113#include "scip/scip_copy.h"
114#include "scip/scip_cut.h"
115#include "scip/scip_general.h"
116#include "scip/scip_lp.h"
117#include "scip/scip_mem.h"
118#include "scip/scip_message.h"
119#include "scip/scip_numerics.h"
120#include "scip/scip_param.h"
121#include "scip/scip_prob.h"
122#include "scip/scip_probing.h"
123#include "scip/scip_sol.h"
124#include "scip/scip_var.h"
125#include "scip/symmetry.h"
127
128/* constraint handler properties */
129#define CONSHDLR_NAME "orbitope"
130#define CONSHDLR_DESC "symmetry breaking constraint handler relying on (partitioning/packing) orbitopes"
131#define CONSHDLR_SEPAPRIORITY +40100 /**< priority of the constraint handler for separation */
132#define CONSHDLR_ENFOPRIORITY -1005200 /**< priority of the constraint handler for constraint enforcing */
133#define CONSHDLR_CHECKPRIORITY -1005200 /**< priority of the constraint handler for checking feasibility */
134#define CONSHDLR_SEPAFREQ -1 /**< frequency for separating cuts; zero means to separate only in the root node */
135#define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
136#define CONSHDLR_EAGERFREQ -1 /**< frequency for using all instead of only the useful constraints in separation,
137 * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
138#define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
139#define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
140#define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
141#define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
142
143#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP /**< propagation timing mask of the constraint handler */
144#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM /**< presolving timing of the constraint handler (fast, medium, or exhaustive) */
145
146#define DEFAULT_PPORBITOPE TRUE /**< whether we check if full orbitopes can be strengthened to packing/partitioning orbitopes */
147#define DEFAULT_SEPAFULLORBITOPE FALSE /**< whether we separate inequalities for full orbitopes */
148#define DEFAULT_FORCECONSCOPY FALSE /**< whether orbitope constraints should be forced to be copied to sub SCIPs */
149
150/*
151 * Data structures
152 */
153
154/** constraint handler data */
155struct SCIP_ConshdlrData
156{
157 SCIP_Bool checkpporbitope; /**< whether we allow upgrading to packing/partitioning orbitopes */
158 SCIP_Bool sepafullorbitope; /**< whether we separate inequalities for full orbitopes orbitopes */
159 SCIP_Bool forceconscopy; /**< whether orbitope constraints should be forced to be copied to sub SCIPs */
160};
161
162/** constraint data for orbitope constraints */
163struct SCIP_ConsData
164{
165 SCIP_VAR*** vars; /**< matrix of variables on which the symmetry acts */
166 SCIP_VAR** tmpvars; /**< temporary storage for variables */
167 SCIP_HASHMAP* rowindexmap; /**< map of variables to row index in orbitope matrix */
168 SCIP_Real** vals; /**< LP-solution for those variables */
169 SCIP_Real* tmpvals; /**< temporary storage for values */
170 SCIP_Real** weights; /**< SC weight table */
171 int** cases; /**< indicator of the SC cases */
172 int nspcons; /**< number of set partitioning/packing constraints <=> p */
173 int nblocks; /**< number of symmetric variable blocks <=> q */
174 SCIP_ORBITOPETYPE orbitopetype; /**< type of orbitope constraint */
175 SCIP_Bool resolveprop; /**< should propagation be resolved? */
176 SCIP_Bool istrianglefixed; /**< has the upper right triangle already globally been fixed to zero? */
177 int* roworder; /**< order of orbitope rows if dynamic propagation for full orbitopes
178 * is used. */
179 SCIP_Bool* rowused; /**< whether a row has been considered in roworder */
180 int nrowsused; /**< number of rows that have already been considered in roworder */
181 SCIP_Bool ismodelcons; /**< whether the orbitope is a model constraint */
182 SCIP_Bool mayinteract; /**< whether symmetries corresponding to orbitope might interact
183 * with symmetries handled by other routines */
184 SCIP_Bool usedynamicprop; /**< whether we use a dynamic version of the propagation routine */
185};
186
187
188/*
189 * Local methods
190 */
191
192/** frees an orbitope constraint data */
193static
195 SCIP* scip, /**< SCIP data structure */
196 SCIP_CONSDATA** consdata /**< pointer to orbitope constraint data */
197 )
198{
199 int i;
200 int j;
201 int p;
202 int q;
203
204 assert( consdata != NULL );
205 assert( *consdata != NULL );
206
207 if ( (*consdata)->usedynamicprop && (*consdata)->rowindexmap != NULL )
208 {
209 SCIPhashmapFree(&((*consdata)->rowindexmap));
210 }
211
212 p = (*consdata)->nspcons;
213 q = (*consdata)->nblocks;
214 for (i = 0; i < p; ++i)
215 {
216 /* release variables in vars array */
217 for (j = 0; j < q; ++j)
218 {
219 assert( (*consdata)->vars[i] != NULL );
220 SCIP_CALL( SCIPreleaseVar(scip, &(*consdata)->vars[i][j]) );
221 }
222
223 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->cases[i]), q); /*lint !e866*/
224 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vars[i]), q); /*lint !e866*/
225 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->weights[i]), q); /*lint !e866*/
226 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vals[i]), q); /*lint !e866*/
227 }
228
229 if ( (*consdata)->usedynamicprop )
230 {
231 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->rowused), p);
232 }
233 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->roworder), p);
234 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->cases), p);
235 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vars), p);
236 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->weights), p);
237 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vals), p);
238
239 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->tmpvals), p + q);
240 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->tmpvars), p + q);
241
242 SCIPfreeBlockMemory(scip, consdata);
243
244 return SCIP_OKAY;
245}
246
247
248/** creates orbitope constraint data */
249static
251 SCIP* scip, /**< SCIP data structure */
252 SCIP_CONSDATA** consdata, /**< pointer to store constraint data */
253 SCIP_VAR*** vars, /**< variables array, must have size nspcons x nblocks */
254 int nspcons, /**< number of set partitioning (packing) constraints <=> p */
255 int nblocks, /**< number of symmetric variable blocks <=> q */
256 SCIP_ORBITOPETYPE orbitopetype, /**< type of orbitope constraint */
257 SCIP_Bool resolveprop, /**< should propagation be resolved? */
258 SCIP_Bool usedynamicprop, /**< whether we use a dynamic version of the propagation routine */
259 SCIP_Bool ismodelcons, /**< whether the orbitope is a model constraint */
260 SCIP_Bool mayinteract /**< whether symmetries corresponding to orbitope might interact
261 * with symmetries handled by other routines */
262 )
263{
264 int i;
265 int j;
266
267 assert(consdata != NULL);
268#ifndef NDEBUG
269 if ( usedynamicprop )
270 {
271 assert( ! mayinteract );
272 }
273#endif
274
275 SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
276
277 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->vals, nspcons) );
278 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->weights, nspcons) );
279 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->vars, nspcons) );
280 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->cases, nspcons) );
281 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->roworder, nspcons) );
282
283 /* if orbitope might interact with other symmetries, we cannot adapt the row order of orbitopes dynamically */
284 if ( usedynamicprop )
285 {
286 SCIP_CALL( SCIPhashmapCreate(&(*consdata)->rowindexmap, SCIPblkmem(scip), nspcons) );
287 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->rowused, nspcons) );
288 }
289
290 for (i = 0; i < nspcons; ++i)
291 {
292 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->vals[i], nblocks) ); /*lint !e866*/
293 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->weights[i], nblocks) ); /*lint !e866*/
294 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars[i], vars[i], nblocks) ); /*lint !e866*/
295 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->cases[i], nblocks) ); /*lint !e866*/
296 (*consdata)->roworder[i] = i;
297
298 if ( usedynamicprop )
299 {
300 (*consdata)->rowused[i] = FALSE;
301 }
302 }
303 (*consdata)->nrowsused = 0;
304
305 (*consdata)->tmpvals = NULL;
306 (*consdata)->tmpvars = NULL;
307 (*consdata)->nspcons = nspcons;
308 (*consdata)->nblocks = nblocks;
309 (*consdata)->orbitopetype = orbitopetype;
310 (*consdata)->resolveprop = resolveprop;
311 (*consdata)->istrianglefixed = FALSE;
312 (*consdata)->ismodelcons = ismodelcons;
313 (*consdata)->mayinteract = mayinteract;
314 (*consdata)->usedynamicprop = usedynamicprop;
315
316 /* get transformed variables, if we are in the transformed problem */
317 if ( SCIPisTransformed(scip) )
318 {
319 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->tmpvals, nspcons + nblocks) );
320 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->tmpvars, nspcons + nblocks) );
321
322 for (i = 0; i < nspcons; ++i)
323 {
324 /* make sure that no variable gets multiaggregated (cannot be handled by cons_orbitope, since one cannot easily
325 * eliminate single variables from an orbitope constraint).
326 */
327 for (j = 0; j < nblocks; ++j)
328 {
329 SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->vars[i][j], &(*consdata)->vars[i][j]) );
330 SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, (*consdata)->vars[i][j]) );
331 if ( usedynamicprop )
332 {
333 SCIP_CALL( SCIPhashmapInsert((*consdata)->rowindexmap, (*consdata)->vars[i][j], (void*) (size_t) i) );
334 }
335 }
336 }
337 }
338
339 /* capture vars contained in vars array */
340 for (i = 0; i < nspcons; ++i)
341 {
342 for (j = 0; j < nblocks; ++j)
343 {
344 assert( (*consdata)->vars[i][j] != NULL );
345 SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->vars[i][j]) );
346 }
347 }
348
349 return SCIP_OKAY;
350}
351
352
353/** strengthen full orbitopes to packing/partitioning orbitopes if possible */
354static
356 SCIP* scip, /**< SCIP data structure */
357 SCIP_VAR*** vars, /**< variable matrix of orbitope constraint */
358 int* nrows, /**< pointer to number of rows of variable matrix */
359 int ncols, /**< number of columns of variable matrix */
360 SCIP_ORBITOPETYPE* type, /**< pointer to store type of orbitope constraint after strengthening */
361 SCIP_Bool mayinteract /**< whether symmetries corresponding to orbitope might interact
362 * with symmetries handled by other routines */
363 )
364{
365 SCIP_Bool* pprows = NULL;
366 int npprows;
367 int nrowsorig;
368
369 assert( scip != NULL );
370 assert( vars != NULL );
371 assert( vars != NULL );
372 assert( *nrows > 0 );
373 assert( ncols > 0 );
374 assert( type != NULL );
375
376 nrowsorig = *nrows;
377 SCIP_CALL( SCIPisPackingPartitioningOrbitope(scip, vars, *nrows, ncols, &pprows, &npprows, type) );
378
379 /* If only some rows are contained in set packing/partitioning constraints, it may still be worth it
380 * to exploit the packing/partitioning structure on these rows, because packing/partitioning orbitopes
381 * or more restrictive than full orbitopes. If at least three rows have this property, we discard
382 * all rows not contained in set packing/partitioning constraints and add the smaller sub packing orbitope.
383 * This is only possible if the orbitope's symmetries do not interact with other symmetry handling
384 * methods (otherwise, dropping rows might change the variable order).
385 */
386 if ( npprows >= 3 && ! mayinteract )
387 {
388 int r = *nrows - 1;
389 int i;
390
391 assert( pprows != NULL );
392
393 while ( r >= 0 )
394 {
395 if ( ! pprows[r] )
396 {
397 for (i = r; i < *nrows - 1; ++i)
398 {
399 SCIP_VAR** row;
400 row = vars[i];
401 vars[i] = vars[i+1];
402 vars[i+1] = row;
403 }
404 *nrows -= 1;
405 }
406 --r;
407 }
409 }
410
411 /* pprows might not have been initialized if there are no setppc conss */
412 if ( pprows != NULL )
413 {
414 SCIPfreeBlockMemoryArray(scip, &pprows, nrowsorig);
415 }
416
417 return SCIP_OKAY;
418}
419
420#ifdef PRINT_MATRIX
421/** debug method, prints variable matrix */
422static
423void printMatrix(
424 SCIP* scip, /**< SCIP data structure */
425 SCIP_CONSDATA* consdata /**< the constraint data */
426 )
427{
428 int i;
429 int j;
430
431 assert( consdata != NULL );
432 assert( consdata->nspcons > 0 );
433 assert( consdata->nblocks > 0 );
434 assert( consdata->vars != NULL );
435
436 for (j = 0; j < consdata->nblocks; ++j)
438
439 SCIPinfoMessage(scip, NULL, "\n");
440 for (i = 0; i < consdata->nspcons; ++i)
441 {
442 for (j = 0; j < consdata->nblocks; ++j)
443 {
444 if ( SCIPvarGetUbLocal(consdata->vars[i][j]) - SCIPvarGetLbLocal(consdata->vars[i][j]) < 0.5 )
445 SCIPinfoMessage(scip, NULL, "%1.0f", REALABS(SCIPvarGetUbLocal(consdata->vars[i][j])));
446 else
448 }
449 SCIPinfoMessage(scip, NULL, "|\n");
450 }
451 for (j = 0; j < consdata->nblocks; ++j)
453 SCIPinfoMessage(scip, NULL, "\n");
454}
455#endif
456
457
458#ifdef SHOW_SCI
459/** Print SCI in nice form for debugging */
460static
461SCIP_RETCODE printSCI(
462 SCIP* scip, /**< SCIP pointer */
463 int p, /**< number of rows */
464 int q, /**< number of columns */
465 int** cases, /**< SCI dynamic programming table */
466 int i, /**< row position of bar */
467 int j /**< column position of bar */
468 )
469{
470 int k;
471 int l;
472 int** M;
473 int p1;
474 int p2;
475
477 for (k = 0; k < p; ++k)
478 {
479 SCIP_CALL( SCIPallocBufferArray(scip, &M[k], q) ); /*lint !e866*/
480 for (l = 0; l < q; ++l)
481 M[k][l] = 0;
482 }
483
484 /* first add bar */
485 for (l = j; l < q; ++l)
486 {
487 assert( M[i][l] == 0 );
488 M[i][l] = 1;
489 }
490
491 /* then add shifted column */
492 p1 = i-1;
493 p2 = j-1;
494 do
495 {
496 assert( cases[p1][p2] != -1 );
497 assert( p1 >= 0 && p1 < i );
498 assert( p2 >= 0 && p2 < j );
499
500 /* if case 1 */
501 if ( cases[p1][p2] == 1 )
502 --p2; /* decrease column */
503 else
504 {
505 /* case 2 or 3: */
506 assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
507 assert( M[p1][p2] == 0 );
508 M[p1][p2] = -1;
509 if ( cases[p1][p2] == 3 )
510 break;
511 }
512 --p1; /* decrease row */
513 }
514 while ( p1 >= 0 ); /* should always be true, i.e. the break should end the loop */
515 assert( cases[p1][p2] == 3 );
516
517 /* now output matrix M */
518 for (l = 0; l < q; ++l)
520 SCIPinfoMessage(scip, NULL, "\n");
521
522 for (k = 0; k < p; ++k)
523 {
524 for (l = 0; l < q; ++l)
525 {
526 if ( l > k )
528 else
529 {
530 switch (M[k][l])
531 {
532 case 1:
534 break;
535 case -1:
537 break;
538 case 0:
540 break;
541 default:
542 SCIPerrorMessage("unexpected matrix entry <%d>: should be -1, 0 or +1\n", M[k][l]);
543 SCIPABORT();
544 }
545 }
546 }
547 SCIPinfoMessage(scip, NULL, "\n");
548 }
549
550 for (l = 0; l < q; ++l)
552 SCIPinfoMessage(scip, NULL, "\n");
553
554 for (k = 0; k < p; ++k)
557
558 return SCIP_OKAY;
559}
560#endif
561
562
563/** copies the variables values from the solution to the constraint data structure */
564static
566 SCIP* scip, /**< the SCIP data structure */
567 SCIP_CONSDATA* consdata, /**< the constraint data */
568 SCIP_SOL* sol /**< a primal solution or NULL for the current LP optimum */
569 )
570{
571 int i;
572 int j;
573
574 assert( scip != NULL );
575 assert( consdata != NULL );
576 assert( consdata->nspcons > 0 );
577 assert( consdata->nblocks > 0 );
578 assert( consdata->vars != NULL );
579 assert( consdata->vals != NULL );
580
581 for (i = 0; i < consdata->nspcons; ++i)
582 {
583 for (j = 0; j < consdata->nblocks; ++j)
584 consdata->vals[i][j] = SCIPgetSolVal(scip, sol, consdata->vars[i][j]);
585 }
586}
587
588
589/** compute the dynamic programming table for SC
590 *
591 * Build up dynamic programming table in order to find SCs with minimum weight.
592 *
593 * The values of the minimal SCIs are stored in @a weights.
594 * The array @a cases[i][j] stores which of the cases were applied to get @a weights[i][j].
595 * Here, 3 means that we have reached the upper limit.
596 *
597 * We assume that the upper right triangle is fixed to 0. Hence we can perform the computation a
598 * bit more efficient.
599 */
600static
602 SCIP* scip, /**< SCIP pointer */
603 int nspcons, /**< number of set partitioning (packing) constraints <=> p */
604 int nblocks, /**< number of symmetric variable blocks <=> q */
605 SCIP_Real** weights, /**< SC weight table */
606 int** cases, /**< indicator of the SC cases */
607 SCIP_Real** vals /**< current solution */
608 )
609{
610 SCIP_Real minvalue;
611 int diagsize;
612 int i;
613 int j;
614
615 assert( weights != NULL );
616 assert( cases != NULL );
617 assert( vals != NULL );
618
619#ifndef NDEBUG
620 /* for debugging */
621 for (i = 0; i < nspcons; ++i)
622 {
623 for (j = 0; j < nblocks; ++j)
624 {
625 if ( i >= j )
626 {
627 weights[i][j] = -1.0;
628 cases[i][j] = -1;
629 }
630 }
631 }
632#endif
633
634 /* initialize diagonal */
635 minvalue = vals[0][0];
636 weights[0][0] = minvalue;
637 cases[0][0] = 3;
638
639 /* get last row of triangle */
640 diagsize = nblocks;
641 if ( nspcons < nblocks )
642 diagsize = nspcons;
643
644 for (j = 1; j < diagsize; ++j)
645 {
646 /* use LT to move entry as far to the left as possible */
647 if ( SCIPisLT(scip, vals[j][j], minvalue) )
648 {
649 minvalue = vals[j][j];
650 cases[j][j] = 3;
651 }
652 else
653 cases[j][j] = 1;
654 weights[j][j] = minvalue;
655 }
656
657 /* initialize first column */
658 for (i = 1; i < nspcons; ++i)
659 {
660 weights[i][0] = weights[i-1][0] + vals[i][0];
661 cases[i][0] = 2; /* second case */
662 }
663
664 /* build the table */
665 for (i = 2; i < nspcons; ++i)
666 {
667 for (j = 1; j < nblocks && j < i; ++j)
668 {
669 SCIP_Real weightleft;
670 SCIP_Real weightright;
671
672 assert( cases[i-1][j] != -1 );
673 assert( cases[i-1][j-1] != -1 );
674
675 weightleft = weights[i-1][j-1];
676 weightright = vals[i][j] + weights[i-1][j];
677
678 /* For first column: cannot take left possibility */
679 if ( SCIPisLT(scip, weightleft, weightright) )
680 {
681 weights[i][j] = weightleft;
682 cases[i][j] = 1;
683 }
684 else
685 {
686 weights[i][j] = weightright;
687 cases[i][j] = 2;
688 }
689 }
690 }
691}
692
693
694/** fix upper right triangle if necessary */
695static
697 SCIP* scip, /**< SCIP data structure */
698 SCIP_CONS* cons, /**< constraint to be processed */
699 SCIP_Bool* infeasible, /**< pointer to store TRUE, if the node can be cut off */
700 int* nfixedvars /**< pointer to add up the number of found domain reductions */
701 )
702{
703 SCIP_CONSDATA* consdata;
704 SCIP_VAR*** vars;
705 SCIP_Bool fixedglobal;
706 SCIP_Bool fixed;
707 int diagsize;
708 int nspcons;
709 int nblocks;
710 int i;
711 int j;
712
713 assert( scip != NULL );
714 assert( cons != NULL );
715 assert( infeasible != NULL );
716 assert( nfixedvars != NULL );
717
718 consdata = SCIPconsGetData(cons);
719 assert( consdata != NULL );
720 assert( consdata->nspcons > 0 );
721 assert( consdata->nblocks > 0 );
722 assert( consdata->vars != NULL );
723
724 *infeasible = FALSE;
725 *nfixedvars = 0;
726
727 if ( consdata->istrianglefixed )
728 return SCIP_OKAY;
729
730 nspcons = consdata->nspcons;
731 nblocks = consdata->nblocks;
732 vars = consdata->vars;
733 fixedglobal = TRUE;
734
735 /* get last row of triangle */
736 diagsize = nblocks;
737 if ( nspcons < nblocks )
738 diagsize = nspcons;
739
740 /* fix variables to 0 */
741 for (i = 0; i < diagsize; ++i)
742 {
743 for (j = i+1; j < nblocks; ++j)
744 {
745 /* fix variable, if not in the root the fixation is local */
746 SCIP_CALL( SCIPfixVar(scip, vars[i][j], 0.0, infeasible, &fixed) );
747
748 if ( *infeasible )
749 {
750 SCIPdebugMsg(scip, "The problem is infeasible: some variable in the upper right triangle is fixed to 1.\n");
751 return SCIP_OKAY;
752 }
753
754 if ( fixed )
755 ++(*nfixedvars);
756
757 if ( SCIPvarGetUbGlobal(vars[i][j]) > 0.5 )
758 fixedglobal = FALSE;
759 }
760 }
761 if ( *nfixedvars > 0 )
762 {
763 SCIPdebugMsg(scip, "<%s>: %s fixed upper right triangle to 0 (fixed vars: %d).\n", SCIPconsGetName(cons), fixedglobal ? "globally" : "locally", *nfixedvars);
764 }
765 else
766 {
767 SCIPdebugMsg(scip, "<%s>: Upper right triangle already fixed to 0.\n", SCIPconsGetName(cons));
768 }
769
770 if ( fixedglobal )
771 consdata->istrianglefixed = TRUE;
772
773 return SCIP_OKAY;
774}
775
776
777/** separates shifted column inequalities according to the solution stored in consdata->vals */
778static
780 SCIP* scip, /**< the SCIP data structure */
781 SCIP_CONSHDLR* conshdlr, /**< constraint handler */
782 SCIP_CONS* cons, /**< constraint */
783 SCIP_CONSDATA* consdata, /**< the constraint data */
784 SCIP_Bool* infeasible, /**< whether we detected infeasibility */
785 int* nfixedvars, /**< pointer to store the number of variables fixed */
786 int* ncuts /**< pointer to store number of separated SCIs */
787 )
788{
789 SCIP_Real** vals;
790 SCIP_Real** weights;
791 SCIP_Real* tmpvals;
792 SCIP_VAR*** vars;
793 SCIP_VAR** tmpvars;
794 int** cases;
795 int nspcons;
796 int nblocks;
797 int i;
798 int j;
799 int l;
800
801 assert( scip != NULL );
802 assert( conshdlr != NULL );
803 assert( cons != NULL );
804 assert( infeasible != NULL);
805 assert( nfixedvars != NULL );
806 assert( ncuts != NULL );
807
808 assert( consdata != NULL );
809 assert( consdata->nspcons > 0 );
810 assert( consdata->nblocks > 0 );
811 assert( consdata->vars != NULL );
812 assert( consdata->vals != NULL );
813 assert( consdata->tmpvars != NULL );
814 assert( consdata->tmpvals != NULL );
815 assert( consdata->weights != NULL );
816 assert( consdata->cases != NULL );
817
818 *infeasible = FALSE;
819 *nfixedvars = 0;
820 *ncuts = 0;
821
822 nspcons = consdata->nspcons;
823 nblocks = consdata->nblocks;
824 vars = consdata->vars;
825 vals = consdata->vals;
826 tmpvars = consdata->tmpvars;
827 tmpvals = consdata->tmpvals;
828 weights = consdata->weights;
829 cases = consdata->cases;
830
831 /* check for upper right triangle */
832 if ( ! consdata->istrianglefixed )
833 {
834 SCIP_CALL( fixTriangle(scip, cons, infeasible, nfixedvars) );
835 if ( *infeasible )
836 return SCIP_OKAY;
837 if ( *nfixedvars > 0 )
838 return SCIP_OKAY;
839 }
840
841 /* compute table if necessary (i.e., not computed before) */
842 computeSCTable(scip, nspcons, nblocks, weights, cases, vals);
843
844 /* loop through rows */
845 for (i = 1; i < nspcons && ! (*infeasible); ++i)
846 {
847 SCIP_Real bar; /* value of bar: */
848 int lastcolumn; /* last column considered as part of the bar */
849
850 bar = 0.0;
851 lastcolumn = nblocks - 1;
852 if ( lastcolumn > i )
853 lastcolumn = i;
854
855 /* traverse row from right to left: */
856 /* j >= 1, since for j = 0, i.e., the bar is a complete row, there does not exist an SCI */
857 for (j = lastcolumn; j > 0; --j)
858 {
859 bar += vals[i][j];
860
861 /* check whether weights[i-1][j-1] < bar (<=> bar - weights[i-1][j-1] > 0), i.e. cut is violated) */
862 if ( SCIPisEfficacious(scip, bar - weights[i-1][j-1]) )
863 {
864#ifndef NDEBUG
865 SCIP_Real weight = 0.0;
866#endif
867 SCIP_ROW* row;
868#ifdef SCIP_DEBUG
869 char name[SCIP_MAXSTRLEN];
870#endif
871 int nvars;
872 int p1;
873 int p2;
874
875 nvars = 0;
876 p1 = i-1;
877 p2 = j-1;
878
879 /* first add bar */
880 for (l = j; l <= lastcolumn; ++l)
881 {
882 tmpvars[nvars] = vars[i][l];
883 tmpvals[nvars] = 1.0;
884 nvars++;
885 }
886
887 /* then add shifted column */
888 do
889 {
890 assert( cases[p1][p2] != -1 );
891 assert( p1 >= 0 && p1 < i );
892 assert( p2 >= 0 && p2 < j );
893
894 /* if case 1 */
895 if (cases[p1][p2] == 1)
896 p2--; /* decrease column */
897 else
898 {
899 /* case 2 or 3: */
900 assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
901 tmpvars[nvars] = vars[p1][p2];
902 tmpvals[nvars] = -1.0;
903 nvars++;
904#ifndef NDEBUG
905 weight += vals[p1][p2];
906#endif
907 if ( cases[p1][p2] == 3 )
908 break;
909 }
910 p1--; /* decrease row */
911 }
912 while ( p1 >= 0 ); /* should always be true, i.e. the break should end the loop */
913 assert( cases[p1][p2] == 3 );
914
915 /* generate cut */
916#ifdef SCIP_DEBUG
917 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "sci_%d_%d", i, j);
918 SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, name, -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
919#else
920 SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, "", -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
921#endif
922 SCIP_CALL( SCIPaddVarsToRow(scip, row, nvars, tmpvars, tmpvals) );
923 /*SCIP_CALL( SCIPprintRow(scip, row, NULL) ); */
924 SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
925 SCIP_CALL( SCIPreleaseRow(scip, &row) );
926 ++(*ncuts);
927
928#ifdef SHOW_SCI
929 SCIP_CALL( printSCI(scip, nspcons, nblocks, cases, i, j) );
930#endif
931
932 assert( SCIPisSumEQ(scip, weights[i-1][j-1], weight) );
933 }
934 }
935 }
936 return SCIP_OKAY;
937}
938
939
940/** propagation method for a single packing or partitioning orbitope constraint */
941static
943 SCIP* scip, /**< SCIP data structure */
944 SCIP_CONS* cons, /**< constraint to be processed */
945 SCIP_Bool* infeasible, /**< pointer to store TRUE, if the node can be cut off */
946 int* nfixedvars /**< pointer to add up the number of found domain reductions */
947 )
948{
949 SCIP_CONSDATA* consdata;
950 SCIP_VAR*** vars;
951 SCIP_ORBITOPETYPE orbitopetype;
952 int* firstnonzeros;
953 int* lastones;
954 int* frontiersteps;
955 int lastoneprevrow;
956 int nspcons;
957 int nblocks;
958 int nsteps;
959 int i;
960 int j;
961
962 assert( scip != NULL );
963 assert( cons != NULL );
964 assert( infeasible != NULL );
965 assert( nfixedvars != NULL );
966
967 *nfixedvars = 0;
968
970 return SCIP_OKAY;
971
972 consdata = SCIPconsGetData(cons);
973 assert( consdata != NULL );
974 assert( consdata->nspcons > 0 );
975 assert( consdata->nblocks > 0 );
976 assert( consdata->vars != NULL );
977
978 nspcons = consdata->nspcons;
979 nblocks = consdata->nblocks;
980 vars = consdata->vars;
981 orbitopetype = consdata->orbitopetype;
982
983 assert( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING );
984
985 /* fix upper right triangle if still necessary */
986 if ( ! consdata->istrianglefixed )
987 {
988 int nfixed = 0;
989 SCIP_CALL( fixTriangle(scip, cons, infeasible, &nfixed) );
990 *nfixedvars += nfixed;
991 }
992
993 /* prepare further propagation */
994 SCIP_CALL( SCIPallocBufferArray(scip, &firstnonzeros, nspcons) );
995 SCIP_CALL( SCIPallocBufferArray(scip, &lastones, nspcons) );
996 SCIP_CALL( SCIPallocBufferArray(scip, &frontiersteps, nblocks) );
997
998#ifdef PRINT_MATRIX
999 SCIPdebugMsg(scip, "Matrix:\n");
1000 printMatrix(scip, consdata);
1001#endif
1002
1003 /* propagate */
1004 lastoneprevrow = 0;
1005 lastones[0] = 0;
1006
1007 if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING )
1008 {
1009 /* packing case: if entry (0,0) is fixed to 0 */
1010 if ( SCIPvarGetUbLocal(vars[0][0]) < 0.5 )
1011 {
1012 lastoneprevrow = -1;
1013 lastones[0] = -1;
1014 }
1015 }
1016 nsteps = 0;
1017
1018 for (i = 1; i < nspcons; ++i)
1019 {
1020 int lastcolumn;
1021 int firstnonzeroinrow;
1022 int lastoneinrow;
1023 SCIP_Bool infrontier;
1024
1025 /* last column considered as part of the bar: */
1026 lastcolumn = nblocks - 1;
1027 if ( lastcolumn > i )
1028 lastcolumn = i;
1029
1030 /* find first position not fixed to 0 (partitioning) or fixed to 1 (packing) */
1031 firstnonzeroinrow = -1;
1032 for (j = 0; j <= lastcolumn; ++j)
1033 {
1034 if ( orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
1035 {
1036 /* partitioning case: if variable is not fixed to 0 */
1037 if ( SCIPvarGetUbLocal(vars[i][j]) > 0.5 )
1038 {
1039 firstnonzeroinrow = j;
1040 break;
1041 }
1042 }
1043 else
1044 {
1045 /* packing case: if variable is fixed to 1 */
1046 if ( SCIPvarGetLbLocal(vars[i][j]) > 0.5 )
1047 {
1048 firstnonzeroinrow = j;
1049 break;
1050 }
1051 }
1052 }
1053 /* if all variables are fixed to 0 in the partitioning case - should not happen */
1054 if ( firstnonzeroinrow == -1 && orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
1055 {
1056 SCIPdebugMsg(scip, " -> Infeasible node: all variables in row %d are fixed to 0.\n", i);
1057 *infeasible = TRUE;
1058 /* conflict should be analyzed by setppc constraint handler */
1059 goto TERMINATE;
1060 }
1061 firstnonzeros[i] = firstnonzeroinrow;
1062 assert( orbitopetype == SCIP_ORBITOPETYPE_PACKING || firstnonzeroinrow >= 0 );
1063 assert( -1 <= firstnonzeroinrow && firstnonzeroinrow <= lastcolumn );
1064
1065 /* compute rightmost possible position for a 1 */
1066 assert( orbitopetype == SCIP_ORBITOPETYPE_PACKING || 0 <= lastoneprevrow );
1067 assert( lastoneprevrow <= lastcolumn );
1068
1069 /* if we are at right border or if entry in column lastoneprevrow+1 is fixed to 0 */
1070 infrontier = FALSE;
1071 assert( lastoneprevrow + 1 >= 0 );
1072 if ( lastoneprevrow == nblocks-1 || SCIPvarGetUbLocal(vars[i][lastoneprevrow+1]) < 0.5 ) /*lint !e679*/
1073 lastoneinrow = lastoneprevrow;
1074 else
1075 {
1076 lastoneinrow = lastoneprevrow + 1;
1077 frontiersteps[nsteps++] = i;
1078 infrontier = TRUE;
1079 }
1080
1081 /* store lastoneinrow */
1082 assert( orbitopetype == SCIP_ORBITOPETYPE_PACKING || 0 <= lastoneinrow );
1083 assert( lastoneinrow <= lastcolumn );
1084 lastones[i] = lastoneinrow;
1085
1086 /* check whether we are infeasible */
1087 if ( firstnonzeroinrow > lastoneinrow )
1088 {
1089 int k;
1090
1091#ifdef SCIP_DEBUG
1092 if ( orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
1093 {
1094 SCIPdebugMsg(scip, " -> Infeasible node: row %d, leftmost nonzero at %d, rightmost 1 at %d\n",
1095 i, firstnonzeroinrow, lastoneinrow);
1096 }
1097 else
1098 {
1099 SCIPdebugMsg(scip, " -> Infeasible node: row %d, 1 at %d, rightmost position for 1 at %d\n",
1100 i, firstnonzeroinrow, lastoneinrow);
1101 }
1102#endif
1103 /* check if conflict analysis is applicable */
1105 {
1106 /* conflict analysis only applicable in SOLVING stage */
1108
1109 /* perform conflict analysis */
1111
1112 if ( orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
1113 {
1114 /* add bounds (variables fixed to 0) that result in the first nonzero entry */
1115 for (j = 0; j <= lastcolumn; ++j)
1116 {
1117 /* add varaibles in row up to the first variable fixed to 0 */
1118 if ( SCIPvarGetUbLocal(vars[i][j]) > 0.5 )
1119 break;
1120
1121 assert( SCIPvarGetUbLocal(vars[i][j]) < 0.5 );
1122 SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i][j]) );
1123 }
1124 }
1125 else
1126 {
1127 /* add bounds that result in the last one - check top left entry for packing case */
1128 if ( lastones[0] == -1 )
1129 {
1130 assert( SCIPvarGetUbLocal(vars[0][0]) < 0.5 );
1131 SCIP_CALL( SCIPaddConflictBinvar(scip, vars[0][0]) );
1132 }
1133
1134 /* mark variable fixed to 1 */
1135 assert( SCIPvarGetLbLocal(vars[i][firstnonzeroinrow]) > 0.5 );
1136 SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i][firstnonzeroinrow]) );
1137 }
1138
1139 /* add bounds that result in the last one - pass through rows */
1140 for (k = 1; k < i; ++k)
1141 {
1142 int l;
1143 l = lastones[k] + 1;
1144
1145 /* if the frontier has not moved and we are not beyond the matrix boundaries */
1146 if ( l <= nblocks-1 && l <= k && lastones[k-1] == lastones[k] )
1147 {
1148 assert( SCIPvarGetUbLocal(vars[k][l]) < 0.5 );
1149 SCIP_CALL( SCIPaddConflictBinvar(scip, vars[k][l]) );
1150 }
1151 }
1153 }
1154
1155 *infeasible = TRUE;
1156 goto TERMINATE;
1157 }
1158
1159 /* fix entries beyond the last possible position for a 1 in the row to 0 (see Lemma 1 in the paper) */
1160 for (j = lastoneinrow+1; j <= lastcolumn; ++j)
1161 {
1162 /* if the entry is not yet fixed to 0 */
1163 if ( SCIPvarGetUbLocal(vars[i][j]) > 0.5 )
1164 {
1165 SCIP_Bool tightened;
1166 int inferInfo;
1167
1168 SCIPdebugMsg(scip, " -> Fixing entry (%d,%d) to 0.\n", i, j);
1169
1170 tightened = FALSE;
1171
1172 /* fix variable to 0 and store position of (i,lastoneinrow+1) for conflict resolution */
1173 inferInfo = i * nblocks + lastoneinrow + 1;
1174 /* correction according to Lemma 1 in the paper (second part): store (i,lastoneinrow+2) */
1175 if ( !infrontier )
1176 ++inferInfo;
1177 SCIP_CALL( SCIPinferBinvarCons(scip, vars[i][j], FALSE, cons, inferInfo, infeasible, &tightened) );
1178
1179 /* if entry is fixed to one -> infeasible node */
1180 if ( *infeasible )
1181 {
1182 SCIPdebugMsg(scip, " -> Infeasible node: row %d, 1 in column %d beyond rightmost position %d\n", i, j, lastoneinrow);
1183 /* check if conflict analysis is applicable */
1185 {
1186 int k;
1187
1188 /* conflict analysis only applicable in SOLVING stage */
1190
1191 /* perform conflict analysis */
1193
1194 /* add current bound */
1195 SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i][j]) );
1196
1197 /* add bounds that result in the last one - check top left entry for packing case */
1198 if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING && lastones[0] == -1 )
1199 {
1200 assert( SCIPvarGetUbLocal(vars[0][0]) < 0.5 );
1201 SCIP_CALL( SCIPaddConflictBinvar(scip, vars[0][0]) );
1202 }
1203
1204 /* add bounds that result in the last one - pass through rows */
1205 for (k = 1; k < i; ++k)
1206 {
1207 int l;
1208 l = lastones[k] + 1;
1209
1210 /* if the frontier has not moved and we are not beyond the matrix boundaries */
1211 if ( l <= nblocks-1 && l <= k && lastones[k-1] == lastones[k] )
1212 {
1213 assert( SCIPvarGetUbLocal(vars[k][l]) < 0.5 );
1214 SCIP_CALL( SCIPaddConflictBinvar(scip, vars[k][l]) );
1215 }
1216 }
1218 }
1219
1220 goto TERMINATE;
1221 }
1222 if ( tightened )
1223 ++(*nfixedvars);
1224 }
1225 }
1226
1227 lastoneprevrow = lastoneinrow;
1228 }
1229
1230 /* check whether fixing any entry to 0 results in a contradiction -> loop through rows in frontiersteps (a.k.a. gamma) */
1231 for (j = 0; j < nsteps; ++j)
1232 {
1233 int s;
1234 int lastoneinrow;
1235
1236 s = frontiersteps[j];
1237 lastoneinrow = lastones[s];
1238 /* note for packing case: if we are in a frontier step then lastoneinrow >= 0 */
1239 assert( 0 <= lastoneinrow && lastoneinrow < nblocks );
1240
1241 /* if entry is not fixed */
1242 if ( SCIPvarGetLbLocal(vars[s][lastoneinrow]) < 0.5 && SCIPvarGetUbLocal(vars[s][lastoneinrow]) > 0.5 )
1243 {
1244 int betaprev;
1245 betaprev = lastoneinrow - 1;
1246
1247 /* loop through rows below s */
1248 for (i = s+1; i < nspcons; ++i)
1249 {
1250 int beta;
1251
1252 assert( betaprev + 1 >= 0 );
1253 if ( betaprev == nblocks-1 || SCIPvarGetUbLocal(vars[i][betaprev+1]) < 0.5 ) /*lint !e679*/
1254 beta = betaprev;
1255 else
1256 beta = betaprev + 1;
1257 assert( -1 <= beta && beta < nblocks );
1258
1259 if ( firstnonzeros[i] > beta )
1260 {
1261 SCIP_Bool tightened;
1262 int inferInfo;
1263
1264 /* can fix (s,lastoneinrow) (a.k.a (s,alpha)) to 1
1265 * (do not need to fix other entries to 0, since they will be
1266 * automatically fixed by SCIPtightenVarLb.)
1267 */
1268 assert( SCIPvarGetLbLocal(vars[s][lastoneinrow]) < 0.5 );
1269 SCIPdebugMsg(scip, " -> Fixing entry (%d,%d) to 1.\n", s, lastoneinrow);
1270
1271 tightened = FALSE;
1272
1273 /* store position (i,firstnonzeros[i]) */
1274 inferInfo = nblocks * nspcons + i * nblocks + firstnonzeros[i];
1275 SCIP_CALL( SCIPinferBinvarCons(scip, vars[s][lastoneinrow], TRUE, cons, inferInfo, infeasible, &tightened) );
1276
1277 assert( !(*infeasible) );
1278 if ( tightened )
1279 ++(*nfixedvars);
1280 break;
1281 }
1282 betaprev = beta;
1283 }
1284 }
1285 }
1286
1287 TERMINATE:
1288 SCIPfreeBufferArray(scip, &frontiersteps);
1289 SCIPfreeBufferArray(scip, &lastones);
1290 SCIPfreeBufferArray(scip, &firstnonzeros);
1291
1292 return SCIP_OKAY;
1293}
1294
1295
1296/* Compute dynamic order of rows based on the branching decisions, i.e., the row of the first branching variable
1297 * determines the first row in the new ordering, the row of the second branching variable determines the second
1298 * row in the new ordering if it differs from the row of the first branching variable, and so on.
1299 *
1300 * The roworder array stores this reordering, where acutally only the first maxrowlabel entries encode the
1301 * reordering.
1302 */
1303static
1305 SCIP* scip, /**< SCIP pointer */
1306 SCIP_HASHMAP* rowindexmap, /**< map of variables to indices in orbitope vars matrix */
1307 SCIP_Bool* rowused, /**< bitset marking whether a row has been considered in the new order */
1308 int* roworder, /**< reordering of the rows w.r.t. branching decisions */
1309 int nrows, /**< number of rows in orbitope */
1310 int ncols, /**< number of columns in orbitope */
1311 int* maxrowlabel /**< maximum row label in ordering */
1312 )
1313{
1314 int i;
1315 SCIP_NODE* node;
1316 int* branchdecisions;
1317 int nbranchdecision;
1318
1319 assert( scip != NULL );
1320 assert( rowindexmap != NULL );
1321 assert( roworder != NULL );
1322 assert( nrows > 0 );
1323 assert( maxrowlabel != NULL );
1324
1325 SCIP_CALL( SCIPallocBufferArray(scip, &branchdecisions, nrows * ncols) );
1326 nbranchdecision = 0;
1327
1328 /* get current node */
1329 node = SCIPgetCurrentNode(scip);
1330
1331 /* follow path to the root (in the root no domains were changed due to branching) */
1332 while ( SCIPnodeGetDepth(node) != 0 )
1333 {
1334 SCIP_BOUNDCHG* boundchg;
1335 SCIP_DOMCHG* domchg;
1336 SCIP_VAR* branchvar;
1337 int nboundchgs;
1338
1339 /* get domain changes of current node */
1340 domchg = SCIPnodeGetDomchg(node);
1341 assert( domchg != NULL );
1342
1343 /* loop through all bound changes */
1344 nboundchgs = SCIPdomchgGetNBoundchgs(domchg);
1345 for (i = 0; i < nboundchgs; ++i)
1346 {
1347 /* get bound change info */
1348 boundchg = SCIPdomchgGetBoundchg(domchg, i);
1349 assert( boundchg != NULL );
1350
1351 /* branching decisions have to be in the beginning of the bound change array */
1353 break;
1354
1355 /* get corresponding branching variable */
1356 branchvar = SCIPboundchgGetVar(boundchg);
1357
1358 /* we only consider binary variables */
1359 if ( SCIPvarGetType(branchvar) == SCIP_VARTYPE_BINARY )
1360 {
1361 int rowidx;
1362
1363 /* make sure that branching variable is present in the orbitope */
1364 if ( ! SCIPhashmapExists(rowindexmap, (void*) branchvar) )
1365 continue;
1366
1367 rowidx = (int) (size_t) SCIPhashmapGetImage(rowindexmap, (void*) branchvar);
1368 branchdecisions[nbranchdecision++] = rowidx;
1369 }
1370 }
1371
1372 node = SCIPnodeGetParent(node);
1373 }
1374
1375 /* Insert branching decisions of current path into global row order.
1376 * Iterate in reverse order over branching decisions to get the path
1377 * from the root to the current node.
1378 */
1379 for (i = nbranchdecision - 1; i >= 0; --i)
1380 {
1381 if ( ! rowused[branchdecisions[i]] )
1382 {
1383 roworder[*maxrowlabel] = branchdecisions[i];
1384 rowused[branchdecisions[i]] = TRUE;
1385 *maxrowlabel += 1;
1386 }
1387 }
1388
1389 SCIPfreeBufferArray(scip, &branchdecisions);
1390
1391 return SCIP_OKAY;
1392}
1393
1394
1395/* Compute lexicographically minimal face of the hypercube w.r.t. some coordinate fixing */
1396static
1398 SCIP_VAR*** vars, /**< variable matrix */
1399 int** lexminfixes, /**< fixings characterzing lex-min face */
1400 int* minfixedrowlexmin, /**< index of minimum fixed row for each column or
1401 * NULL (if in prop) */
1402 SCIP_Bool* infeasible, /**< pointer to store whether infeasibility has been
1403 * detected or NULL (if in resprop) */
1404 int m, /**< number of rows in vars */
1405 int n, /**< number of columns in vars */
1406 int nrowsused, /**< number of rows considered in propagation */
1407 SCIP_Bool resprop /**< whether we are in resprop (TRUE) or prop (FALSE) */
1408 )
1409{
1410 int i;
1411 int j;
1412 *infeasible = FALSE;
1413
1414 assert( vars != NULL );
1415 assert( lexminfixes != NULL );
1416 assert( !resprop || minfixedrowlexmin != NULL );
1417 assert( m > 0 );
1418 assert( n > 0 );
1419 assert( nrowsused > 0 );
1420 assert( nrowsused <= m );
1421 assert( infeasible != NULL );
1422
1423 /* iterate over columns in reverse order and find the lexicographically minimal face
1424 * of the hypercube containing lexminfixes
1425 */
1426 for (j = n - 2; j >= 0; --j)
1427 {
1428 int maxdiscriminating = m;
1429 int minfixed = -1;
1430
1431 /* fix free entries in column j to the corresponding value in column j + 1 and collect some information */
1432 for (i = 0; i < nrowsused; ++i)
1433 {
1434 /* is row i j-discriminating? */
1435 if ( minfixed == -1 && lexminfixes[i][j] != 0 && lexminfixes[i][j + 1] != 1 )
1436 {
1437 assert( lexminfixes[i][j + 1] == 0 );
1438
1439 maxdiscriminating = i;
1440 }
1441
1442 /* is row i j-fixed? */
1443 if ( minfixed == -1 && lexminfixes[i][j] != lexminfixes[i][j + 1] && lexminfixes[i][j] != 2 )
1444 {
1445 assert( lexminfixes[i][j + 1] != 2 );
1446
1447 minfixed = i;
1448
1449 /* detect infeasibility */
1450 if ( maxdiscriminating > minfixed )
1451 {
1452 *infeasible = TRUE;
1453
1454 return SCIP_OKAY;
1455 }
1456 }
1457 }
1458
1459 /* ensure that column j is lexicographically not smaller than column j + 1 */
1460 for (i = 0; i < nrowsused; ++i)
1461 {
1462 if ( lexminfixes[i][j] == 2 )
1463 {
1464 if ( i < maxdiscriminating || minfixed == -1 )
1465 lexminfixes[i][j] = lexminfixes[i][j + 1];
1466 else if ( i == maxdiscriminating )
1467 lexminfixes[i][j] = 1;
1468 else
1469 lexminfixes[i][j] = 0;
1470 }
1471 }
1472
1473 if ( resprop )
1474 {
1475 assert( minfixedrowlexmin != NULL );
1476
1477 /* store minimum fixed row */
1478 if ( minfixed == -1 )
1479 minfixedrowlexmin[j] = nrowsused - 1;
1480 else
1481 minfixedrowlexmin[j] = minfixed;
1482
1483 /* columns 1, ..., n-2 are contained in two columns (take the minimum) and
1484 * the minimum fixed row of column n-1 is determined by column n-2 */
1485 if ( minfixedrowlexmin[j + 1] < minfixedrowlexmin[j] )
1486 minfixedrowlexmin[j + 1] = minfixedrowlexmin[j];
1487 }
1488 }
1489
1490 return SCIP_OKAY;
1491}
1492
1493
1494/* Compute lexicographically maximal face of the hypercube w.r.t. some coordinate fixing */
1495static
1497 SCIP_VAR*** vars, /**< variable matrix */
1498 int** lexmaxfixes, /**< fixings characterzing lex-max face */
1499 int* minfixedrowlexmax, /**< index of minimum fixed row for each column or
1500 * NULL (if in prop) */
1501 SCIP_Bool* infeasible, /**< pointer to store whether infeasibility has been
1502 * detected or NULL (if in resprop) */
1503 int m, /**< number of rows in vars */
1504 int n, /**< number of columns in vars */
1505 int nrowsused, /**< number of rows considered in propagation */
1506 SCIP_Bool resprop /**< whether we are in resprop (TRUE) or prop (FALSE) */
1507 )
1508{
1509 int i;
1510 int j;
1511 *infeasible = FALSE;
1512
1513 assert( vars != NULL );
1514 assert( lexmaxfixes != NULL );
1515 assert( !resprop || minfixedrowlexmax != NULL );
1516 assert( m > 0 );
1517 assert( n > 0 );
1518 assert( nrowsused > 0 );
1519 assert( nrowsused <= m );
1520 assert( infeasible != NULL );
1521
1522 for (j = 1; j < n; ++j)
1523 {
1524 int maxdiscriminating = m;
1525 int minfixed = -1;
1526
1527 /* fix free entries in column j to the corresponding value in column j - 1 and collect some information */
1528 for (i = 0; i < nrowsused; ++i)
1529 {
1530 /* is row i j-discriminating? */
1531 if ( minfixed == -1 && lexmaxfixes[i][j - 1] != 0 && lexmaxfixes[i][j] != 1 )
1532 {
1533 assert( lexmaxfixes[i][j - 1] == 1 );
1534
1535 maxdiscriminating = i;
1536 }
1537
1538 /* is row i j-fixed? */
1539 if ( minfixed == -1 && lexmaxfixes[i][j - 1] != lexmaxfixes[i][j] && lexmaxfixes[i][j] != 2 )
1540 {
1541 assert( lexmaxfixes[i][j - 1] != 2 );
1542
1543 minfixed = i;
1544
1545 /* detect infeasibility */
1546 if ( maxdiscriminating > minfixed )
1547 {
1548 *infeasible = TRUE;
1549
1550 return SCIP_OKAY;
1551 }
1552 }
1553 }
1554
1555 /* ensure that column j is lexicographically not greater than column j - 1 */
1556 for (i = 0; i < nrowsused; ++i)
1557 {
1558 if ( lexmaxfixes[i][j] == 2 )
1559 {
1560 if ( i < maxdiscriminating || minfixed == -1 )
1561 lexmaxfixes[i][j] = lexmaxfixes[i][j - 1];
1562 else if ( i == maxdiscriminating )
1563 lexmaxfixes[i][j] = 0;
1564 else
1565 lexmaxfixes[i][j] = 1;
1566 }
1567 }
1568
1569 if ( resprop )
1570 {
1571 assert( minfixedrowlexmax != NULL );
1572
1573 /* store minimum fixed row */
1574 if ( minfixed == -1 )
1575 minfixedrowlexmax[j] = nrowsused - 1;
1576 else
1577 minfixedrowlexmax[j] = minfixed;
1578
1579 /* columns 1, ..., n-2 are contained in two columns (take the minimum) and
1580 * the minimum fixed row of column 0 is determined by column 1 */
1581 if ( minfixedrowlexmax[j - 1] < minfixedrowlexmax[j] )
1582 minfixedrowlexmax[j - 1] = minfixedrowlexmax[j];
1583 }
1584 }
1585
1586 return SCIP_OKAY;
1587}
1588
1589
1590/** propagation method for a single packing or partitioning orbitope constraint */
1591static
1593 SCIP* scip, /**< SCIP data structure */
1594 SCIP_CONS* cons, /**< constraint to be processed */
1595 SCIP_Bool* infeasible, /**< pointer to store TRUE, if the node can be cut off */
1596 int* nfixedvars, /**< pointer to add up the number of found domain reductions */
1597 SCIP_Bool dynamic /**< whether we use a dynamic propagation routine */
1598 )
1599{
1600 SCIP_CONSDATA* consdata;
1601 SCIP_VAR*** vars;
1602 int** lexminfixes;
1603 int** lexmaxfixes;
1604 int* roworder;
1605 int nrowsused;
1606 int i;
1607 int j;
1608 int m;
1609 int n;
1610
1611 assert( scip != NULL );
1612 assert( cons != NULL );
1613 assert( infeasible != NULL );
1614 assert( nfixedvars != NULL );
1615
1616 *nfixedvars = 0;
1617 *infeasible = FALSE;
1618
1619 /* @todo Can the following be removed? */
1621 return SCIP_OKAY;
1622
1623 /* do nothing if we use dynamic propagation and if we are in a probing node */
1624 if ( dynamic && SCIPinProbing(scip) )
1625 return SCIP_OKAY;
1626
1627 consdata = SCIPconsGetData(cons);
1628 assert( consdata != NULL );
1629 assert( consdata->nspcons > 0 );
1630 assert( consdata->nblocks > 0 );
1631 assert( consdata->vars != NULL );
1632 assert( consdata->orbitopetype == SCIP_ORBITOPETYPE_FULL );
1633
1634 m = consdata->nspcons;
1635 n = consdata->nblocks;
1636 vars = consdata->vars;
1637
1638 /* determine order of orbitope rows dynamically by branching decisions */
1639 if ( dynamic )
1640 {
1641 SCIP_CALL( computeDynamicRowOrder(scip, consdata->rowindexmap, consdata->rowused,
1642 consdata->roworder, m, n, &(consdata->nrowsused)) );
1643
1644 /* if no branching variable is contained in the full orbitope */
1645 if ( consdata->nrowsused == 0 )
1646 return SCIP_OKAY;
1647
1648 nrowsused = consdata->nrowsused;
1649 }
1650 else
1651 nrowsused = m;
1652 roworder = consdata->roworder;
1653
1654 /* Initialize lexicographically minimal matrix by fixed entries at the current node.
1655 * Free entries in the last column are set to 0.
1656 */
1657 SCIP_CALL( SCIPallocBufferArray(scip, &lexminfixes, nrowsused) );
1658 for (i = 0; i < nrowsused; ++i)
1659 {
1660 SCIP_CALL( SCIPallocBufferArray(scip, &lexminfixes[i], n) ); /*lint !e866*/
1661 }
1662
1663 for (i = 0; i < nrowsused; ++i)
1664 {
1665 int origrow;
1666
1667 origrow = roworder[i];
1668
1669 for (j = 0; j < n; ++j)
1670 {
1671 if ( SCIPvarGetLbLocal(vars[origrow][j]) > 0.5 )
1672 lexminfixes[i][j] = 1;
1673 else if ( SCIPvarGetUbLocal(vars[origrow][j]) < 0.5 || j == n - 1 )
1674 lexminfixes[i][j] = 0;
1675 else
1676 lexminfixes[i][j] = 2;
1677 }
1678 }
1679
1680 /* find lexicographically minimal face of hypercube containing lexmin fixes */
1681 SCIP_CALL( findLexMinFace(vars, lexminfixes, NULL, infeasible, m, n, nrowsused, FALSE) );
1682
1683 if ( *infeasible == TRUE )
1684 goto FREELEXMIN;
1685
1686 /* Initialize lexicographically maximal matrix by fixed entries at the current node.
1687 * Free entries in the first column are set to 1.
1688 */
1689 SCIP_CALL( SCIPallocBufferArray(scip, &lexmaxfixes, nrowsused) );
1690 for (i = 0; i < nrowsused; ++i)
1691 {
1692 SCIP_CALL( SCIPallocBufferArray(scip, &lexmaxfixes[i], n) ); /*lint !e866*/
1693 }
1694
1695 for (i = 0; i < nrowsused; ++i)
1696 {
1697 int origrow;
1698
1699 origrow = roworder[i];
1700
1701 for (j = 0; j < n; ++j)
1702 {
1703 if ( SCIPvarGetUbLocal(vars[origrow][j]) < 0.5 )
1704 lexmaxfixes[i][j] = 0;
1705 else if ( SCIPvarGetLbLocal(vars[origrow][j]) > 0.5 || j == 0 )
1706 lexmaxfixes[i][j] = 1;
1707 else
1708 lexmaxfixes[i][j] = 2;
1709 }
1710 }
1711
1712 /* find lexicographically maximal face of hypercube containing lexmax fixes */
1713 SCIP_CALL( findLexMaxFace(vars, lexmaxfixes, NULL, infeasible, m, n, nrowsused, FALSE) );
1714
1715 if ( *infeasible )
1716 goto FREELEXMAX;
1717
1718 /* Find for each column j the minimal row in which lexminfixes and lexmaxfixes differ. Fix all entries above this
1719 * row to the corresponding value in lexminfixes (or lexmaxfixes).
1720 */
1721 for (j = 0; j < n; ++j)
1722 {
1723 for (i = 0; i < nrowsused; ++i)
1724 {
1725 int origrow;
1726
1727 origrow = roworder[i];
1728
1729 if ( lexminfixes[i][j] != lexmaxfixes[i][j] )
1730 break;
1731
1732 if ( SCIPvarGetLbLocal(vars[origrow][j]) < 0.5 && SCIPvarGetUbLocal(vars[origrow][j]) > 0.5 )
1733 {
1734 SCIP_Bool success;
1735
1736 SCIP_CALL( SCIPinferBinvarCons(scip, vars[origrow][j], (SCIP_Bool) lexminfixes[i][j],
1737 cons, 0, infeasible, &success) );
1738
1739 if ( success )
1740 *nfixedvars += 1;
1741 }
1742 }
1743 }
1744
1745 FREELEXMAX:
1746 for (i = 0; i < nrowsused; ++i)
1747 SCIPfreeBufferArray(scip, &lexmaxfixes[i]);
1748 SCIPfreeBufferArray(scip, &lexmaxfixes);
1749
1750 FREELEXMIN:
1751 for (i = 0; i < nrowsused; ++i)
1752 SCIPfreeBufferArray(scip, &lexminfixes[i]);
1753 SCIPfreeBufferArray(scip, &lexminfixes);
1754
1755 return SCIP_OKAY;
1756}
1757
1758
1759/** propagation method for a single orbitope constraint */
1760static
1762 SCIP* scip, /**< SCIP data structure */
1763 SCIP_CONS* cons, /**< constraint to be processed */
1764 SCIP_Bool* infeasible, /**< pointer to store TRUE, if the node can be cut off */
1765 int* nfixedvars /**< pointer to add up the number of found domain reductions */
1766 )
1767{
1768 SCIP_CONSDATA* consdata;
1769 SCIP_ORBITOPETYPE orbitopetype;
1770
1771 assert( scip != NULL );
1772 assert( cons != NULL );
1773 assert( infeasible != NULL );
1774 assert( nfixedvars != NULL );
1775
1776 consdata = SCIPconsGetData(cons);
1777 assert( consdata != NULL );
1778
1779 orbitopetype = consdata->orbitopetype;
1780
1781 if ( orbitopetype == SCIP_ORBITOPETYPE_FULL )
1782 {
1783 SCIP_CALL( propagateFullOrbitopeCons(scip, cons, infeasible, nfixedvars,
1784 consdata->usedynamicprop && !consdata->ismodelcons) );
1785 }
1786 else
1787 {
1788 assert( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING );
1789 SCIP_CALL( propagatePackingPartitioningCons(scip, cons, infeasible, nfixedvars) );
1790 }
1791
1792 return SCIP_OKAY;
1793}
1794
1795
1796/** Propagation conflict resolving method of propagator
1797 *
1798 * In this function we use that all variable reductions that can be found by the propagation algorithm
1799 * are only due to the fixed variables that are in or above the minimum fixed row of each pair of adjacent
1800 * columns of the lexmin and lexmax matrices.
1801 *
1802 * Since the storage of an integer is not enough to store the complete information about the fixing,
1803 * we have to use the linear time algorithm for finding the lexmin and lexmax
1804 * matrices and determine from this the minimum fixed rows.
1805 */
1806static
1808 SCIP* scip, /**< SCIP data structure */
1809 SCIP_CONSHDLR* conshdlr, /**< constraint handler of the corresponding constraint */
1810 SCIP_CONS* cons, /**< constraint that inferred the bound change */
1811 int inferinfo, /**< inference information */
1812 SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
1813 SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
1814 )
1815{ /*lint --e{715}*/
1816 SCIP_CONSDATA* consdata;
1817 SCIP_VAR*** vars;
1818 int** lexminfixes;
1819 int** lexmaxfixes;
1820 int* roworder;
1821 int* minfixedrowlexmin;
1822 int* minfixedrowlexmax;
1823 int i;
1824 int j;
1825 int m;
1826 int n;
1827 int nrowsused;
1828 SCIP_Bool dynamic;
1829 SCIP_Bool terminate;
1830
1831 *result = SCIP_DIDNOTFIND;
1832
1833 assert( scip != NULL );
1834 assert( conshdlr != NULL );
1835 assert( cons != NULL );
1836 assert( result != NULL );
1837
1838 consdata = SCIPconsGetData(cons);
1839 assert( consdata != NULL );
1840 assert( consdata->nspcons > 0 );
1841 assert( consdata->nblocks > 0 );
1842 assert( consdata->vars != NULL );
1843 assert( consdata->orbitopetype == SCIP_ORBITOPETYPE_FULL );
1844
1845 dynamic = consdata->usedynamicprop && !consdata->ismodelcons;
1846 m = consdata->nspcons;
1847 n = consdata->nblocks;
1848 vars = consdata->vars;
1849
1850 if ( dynamic )
1851 {
1852 assert( consdata->roworder != NULL );
1853 assert( consdata->nrowsused > 0 );
1854
1855 nrowsused = consdata->nrowsused;
1856 }
1857 else
1858 nrowsused = m;
1859 roworder = consdata->roworder;
1860
1861 assert( inferinfo <= consdata->nspcons );
1862
1863 /* Initialize lexicographically minimal matrix by fixed entries at the current node.
1864 * Free entries in the last column are set to 0.
1865 */
1866 SCIP_CALL( SCIPallocBufferArray(scip, &lexminfixes, nrowsused) );
1867 for (i = 0; i < nrowsused; ++i)
1868 {
1869 SCIP_CALL( SCIPallocBufferArray(scip, &lexminfixes[i], n) ); /*lint !e866*/
1870 }
1871
1872 /* store minimum fixed row for each column */
1873 SCIP_CALL( SCIPallocBufferArray(scip, &minfixedrowlexmin, n) );
1874 minfixedrowlexmin[n - 1] = -1;
1875
1876 for (i = 0; i < nrowsused; ++i)
1877 {
1878 int origrow;
1879
1880 origrow = roworder[i];
1881
1882 for (j = 0; j < n; ++j)
1883 {
1884 if ( SCIPvarGetLbAtIndex(vars[origrow][j], bdchgidx, FALSE) > 0.5 )
1885 lexminfixes[i][j] = 1;
1886 else if ( SCIPvarGetUbAtIndex(vars[origrow][j], bdchgidx, FALSE) < 0.5 || j == n - 1 )
1887 lexminfixes[i][j] = 0;
1888 else
1889 lexminfixes[i][j] = 2;
1890 }
1891 }
1892
1893 /* find lexicographically minimal face of hypercube containing lexmin fixes */
1894 SCIP_CALL( findLexMinFace(vars, lexminfixes, minfixedrowlexmin, &terminate, m, n, nrowsused, TRUE) );
1895
1896 if ( terminate )
1897 goto FREELEXMIN;
1898
1899 /* Initialize lexicographically maximal matrix by fixed entries at the current node.
1900 * Free entries in the first column are set to 1.
1901 */
1902 SCIP_CALL( SCIPallocBufferArray(scip, &lexmaxfixes, nrowsused) );
1903 for (i = 0; i < nrowsused; ++i)
1904 {
1905 SCIP_CALL( SCIPallocBufferArray(scip, &lexmaxfixes[i], n) ); /*lint !e866*/
1906 }
1907
1908 /* store minimum fixed row for each column */
1909 SCIP_CALL( SCIPallocBufferArray(scip, &minfixedrowlexmax, n) );
1910 minfixedrowlexmax[0] = -1;
1911
1912 for (i = 0; i < nrowsused; ++i)
1913 {
1914 int origrow;
1915
1916 origrow = roworder[i];
1917
1918 for (j = 0; j < n; ++j)
1919 {
1920 if ( SCIPvarGetUbAtIndex(vars[origrow][j], bdchgidx, FALSE) < 0.5 )
1921 lexmaxfixes[i][j] = 0;
1922 else if ( SCIPvarGetLbAtIndex(vars[origrow][j], bdchgidx, FALSE) > 0.5 || j == 0 )
1923 lexmaxfixes[i][j] = 1;
1924 else
1925 lexmaxfixes[i][j] = 2;
1926 }
1927 }
1928
1929 /* find lexicographically maximal face of hypercube containing lexmax fixes */
1930 SCIP_CALL( findLexMaxFace(vars, lexmaxfixes, minfixedrowlexmax, &terminate, m, n, nrowsused, TRUE) );
1931
1932 if ( terminate )
1933 goto FREELEXMAX;
1934
1935 /* Find for each column j the minimal row in which lexminfixes and lexmaxfixes differ. Fix all entries above this
1936 * row to the corresponding value in lexminfixes (or lexmaxfixes).
1937 */
1938 for (j = 0; j < n; ++j)
1939 {
1940 int ub = MAX(minfixedrowlexmin[j], minfixedrowlexmax[j]);
1941
1942 for (i = 0; i <= ub; ++i)
1943 {
1944 int origrow;
1945
1946 origrow = roworder[i];
1947
1948 if ( SCIPvarGetLbAtIndex(vars[origrow][j], bdchgidx, FALSE) > 0.5 ||
1949 SCIPvarGetUbAtIndex(vars[origrow][j], bdchgidx, FALSE) < 0.5 )
1950 {
1951 SCIP_CALL( SCIPaddConflictBinvar(scip, vars[origrow][j]) );
1952 *result = SCIP_SUCCESS;
1953 }
1954 }
1955 }
1956
1957 FREELEXMAX:
1958 SCIPfreeBufferArray(scip, &minfixedrowlexmax);
1959 for (i = 0; i < nrowsused; ++i)
1960 SCIPfreeBufferArray(scip, &lexmaxfixes[i]);
1961 SCIPfreeBufferArray(scip, &lexmaxfixes);
1962
1963 FREELEXMIN:
1964 SCIPfreeBufferArray(scip, &minfixedrowlexmin);
1965 for (i = 0; i < nrowsused; ++i)
1966 SCIPfreeBufferArray(scip, &lexminfixes[i]);
1967 SCIPfreeBufferArray(scip, &lexminfixes);
1968
1969 return SCIP_OKAY;
1970}
1971
1972
1973/** Propagation conflict resolving method of propagator
1974 *
1975 * In this function we use that the propagation method above implicitly propagates SCIs, i.e., every
1976 * fixing can also be gotten via an SCI-fixing.
1977 *
1978 * Since the storage of an integer is not enough to store the complete information about the fixing
1979 * nor a complete shifted column, we have to use the linear time algorithm for SCIs.
1980 *
1981 * The inferinfo integer is set as follows:
1982 *
1983 * - If a shifted column is fixed to 0 and the corresponding bar does not necessarily has value 1
1984 * then we fix these entries to 0 and inferinfo is i * nblocks + j, where (i,j) is the leader of the
1985 * bar. The SCI depends on whether i is in Gamma or not (see Lemma 1 in the paper and the comments
1986 * above).
1987 *
1988 * - If a bar has value 1 and the shifted column has one entry that is not fixed, it can be fixed to
1989 * 1 and inferinfo is (nspcons*nblocks) + i * nblocks + j, where (i,j) is the leader of the bar; see
1990 * Proposition 1 (2c).
1991 */
1992static
1994 SCIP* scip, /**< SCIP data structure */
1995 SCIP_CONS* cons, /**< constraint that inferred the bound change */
1996 int inferinfo, /**< inference information */
1997 SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
1998 SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
1999 )
2000{ /*lint --e{715}*/
2001 SCIP_CONSDATA* consdata;
2002 SCIP_Real** vals;
2003 SCIP_Real** weights;
2004 SCIP_VAR*** vars;
2005 SCIP_ORBITOPETYPE orbitopetype;
2006 int** cases;
2007
2008 int i;
2009 int j;
2010 int nspcons;
2011 int nblocks;
2012
2013 assert( scip != NULL );
2014 assert( cons != NULL );
2015 assert( result != NULL );
2016
2017 consdata = SCIPconsGetData(cons);
2018 assert( consdata != NULL );
2019 assert( consdata->nspcons > 0 );
2020 assert( consdata->nblocks > 0 );
2021 assert( consdata->vars != NULL );
2022 assert( consdata->vals != NULL );
2023 assert( consdata->weights != NULL );
2024 assert( consdata->cases != NULL );
2025 assert( consdata->istrianglefixed );
2026
2027 *result = SCIP_DIDNOTFIND;
2028 if ( ! consdata->resolveprop )
2029 return SCIP_OKAY;
2030
2031 nspcons = consdata->nspcons;
2032 nblocks = consdata->nblocks;
2033 vars = consdata->vars;
2034 vals = consdata->vals;
2035 weights = consdata->weights;
2036 orbitopetype = consdata->orbitopetype;
2037 cases = consdata->cases;
2038
2039 SCIPdebugMsg(scip, "Propagation resolution method of orbitope constraint using orbitopal fixing\n");
2040
2041 /* fill table */
2042 for (i = 0; i < nspcons; ++i)
2043 {
2044 int lastcolumn;
2045
2046 /* last column considered as part of the bar: */
2047 lastcolumn = nblocks - 1;
2048 if ( lastcolumn > i )
2049 lastcolumn = i;
2050 for (j = 0; j <= lastcolumn; ++j)
2051 {
2052 /* if the variable was fixed to zero at conflict time */
2053 if ( SCIPgetVarUbAtIndex(scip, vars[i][j], bdchgidx, FALSE) < 0.5 )
2054 vals[i][j] = 0.0;
2055 else
2056 {
2057 /* if the variable was fixed to one at conflict time */
2058 if ( SCIPgetVarLbAtIndex(scip, vars[i][j], bdchgidx, FALSE) > 0.5 )
2059 vals[i][j] = 2.0;
2060 else
2061 vals[i][j] = 1.0;
2062 }
2063 }
2064 }
2065
2066#ifdef PRINT_MATRIX
2067 SCIPdebugMsg(scip, "Matrix:\n");
2068 printMatrix(scip, consdata);
2069#endif
2070
2071 /* computation of table: this now minimizes the value of the shifted column */
2072 assert( consdata->istrianglefixed );
2073 computeSCTable(scip, nspcons, nblocks, weights, cases, vals);
2074
2075 /* if we fixed variables in the bar to zero */
2076 assert( inferinfo >= 0 && inferinfo < 2 * nspcons * nblocks );
2077 if ( inferinfo < nspcons * nblocks )
2078 {
2079 int p1;
2080 int p2;
2081#ifdef SCIP_DEBUG
2082 char str[SCIP_MAXSTRLEN];
2083 char tmpstr[SCIP_MAXSTRLEN];
2084#endif
2085
2086 i = (int) (inferinfo / nblocks);
2087 j = inferinfo % nblocks;
2088 assert( 0 <= i && i < nspcons );
2089 assert( 0 <= j && j < nblocks );
2090
2091 /* find SCI with value 0 */
2092 assert( weights[i-1][j-1] < 0.5 );
2093
2094 SCIPdebugMsg(scip, " -> reason for x[%d][%d] = ... = x[%d][%d] = 0 was the following SC:\n", i, j, i, MIN(i,nblocks));
2095#ifdef SCIP_DEBUG
2096 str[0] = '\0';
2097#endif
2098
2099 p1 = i-1;
2100 p2 = j-1;
2101 do
2102 {
2103 assert( cases[p1][p2] != -1 );
2104 assert( p1 >= 0 && p1 < i );
2105 assert( p2 >= 0 && p2 < j );
2106
2107 /* if case 1 */
2108 if ( cases[p1][p2] == 1 )
2109 --p2; /* decrease column */
2110 else
2111 {
2112 /* case 2 or 3: */
2113 assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
2114 assert( SCIPgetVarUbAtIndex(scip, vars[p1][p2], bdchgidx, FALSE) < 0.5 );
2115 SCIP_CALL( SCIPaddConflictUb(scip, vars[p1][p2], bdchgidx) );
2116 *result = SCIP_SUCCESS;
2117
2118#ifdef SCIP_DEBUG
2119 (void) SCIPsnprintf(tmpstr, SCIP_MAXSTRLEN, " (%d,%d)", p1, p2);
2120 (void) strncat(str, tmpstr, SCIP_MAXSTRLEN-1);
2121#endif
2122
2123 if ( cases[p1][p2] == 3 )
2124 break;
2125 }
2126 --p1; /* decrease row */
2127 }
2128 while ( p1 >= 0 ); /* should always be true, i.e. the break should end the loop */
2129 assert( cases[p1][p2] == 3 );
2130
2131#ifdef SCIP_DEBUG
2132 SCIPdebugMsg(scip, "%s\n", str);
2133#endif
2134 }
2135 else
2136 {
2137 int k;
2138 int p1;
2139 int p2;
2140#ifndef NDEBUG
2141 int pos1;
2142 int pos2;
2143#endif
2144#ifdef SCIP_DEBUG
2145 char str[SCIP_MAXSTRLEN];
2146 char tmpstr[SCIP_MAXSTRLEN];
2147#endif
2148
2149 /* if we fixed a variable in the SC to 1 */
2150 inferinfo -= nspcons * nblocks;
2151 i = (int) inferinfo / nblocks;
2152 j = inferinfo % nblocks;
2153 assert( 0 <= i && i < nspcons );
2154 assert( 0 <= j && j < nblocks );
2155
2156 /* In rare cases it might happen that we fixed a variable to 1, but the node later becomes infeasible by globally
2157 * fixing variables to 0. In this case, it might happen that we find a SC with value 0 instead of 1. We then
2158 * cannot use this SC to repropagate (and do not know how to reconstruct the original reasoning). */
2159 if ( weights[i-1][j-1] > 0.5 && weights[i-1][j-1] < 1.5 )
2160 {
2161 SCIPdebugMsg(scip, " -> reason for x[%d][%d] = 1 was the following SC:\n", i, j);
2162#ifdef SCIP_DEBUG
2163 (void) SCIPsnprintf(str, SCIP_MAXSTRLEN, "SC:");
2164#endif
2165
2166 p1 = i-1;
2167 p2 = j-1;
2168#ifndef NDEBUG
2169 pos1 = -1;
2170 pos2 = -1;
2171#endif
2172 do
2173 {
2174 assert( cases[p1][p2] != -1 );
2175 assert( p1 >= 0 && p1 < i );
2176 assert( p2 >= 0 && p2 < j );
2177
2178 /* if case 1 */
2179 if ( cases[p1][p2] == 1 )
2180 --p2; /* decrease column */
2181 else
2182 {
2183 /* case 2 or 3: reason are formed by variables in SC fixed to 0 */
2184 assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
2185 if ( SCIPgetVarUbAtIndex(scip, vars[p1][p2], bdchgidx, FALSE) < 0.5 )
2186 {
2187 SCIP_CALL( SCIPaddConflictUb(scip, vars[p1][p2], bdchgidx) );
2188 *result = SCIP_SUCCESS;
2189
2190#ifdef SCIP_DEBUG
2191 (void) SCIPsnprintf(tmpstr, SCIP_MAXSTRLEN, " (%d,%d)", p1, p2);
2192 (void) strncat(str, tmpstr, SCIP_MAXSTRLEN-1);
2193#endif
2194 }
2195#ifndef NDEBUG
2196 else
2197 {
2198 assert( SCIPgetVarLbAtIndex(scip, vars[p1][p2], bdchgidx, FALSE) < 0.5 );
2199 assert( pos1 == -1 && pos2 == -1 );
2200 pos1 = p1;
2201 pos2 = p2;
2202 }
2203#endif
2204 if ( cases[p1][p2] == 3 )
2205 break;
2206 }
2207 --p1; /* decrease row */
2208 }
2209 while ( p1 >= 0 ); /* should always be true, i.e., the break should end the loop */
2210 assert( cases[p1][p2] == 3 );
2211 assert( pos1 >= 0 && pos2 >= 0 );
2212
2213 /* distinguish partitioning/packing */
2214 if ( orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
2215 {
2216 /* partitioning case */
2217#ifdef SCIP_DEBUG
2218 (void) SCIPsnprintf(tmpstr, SCIP_MAXSTRLEN, " before bar: ");
2219 (void) strncat(str, tmpstr, SCIP_MAXSTRLEN-1);
2220#endif
2221 /* add variables before the bar in the partitioning case */
2222 for (k = 0; k < j; ++k)
2223 {
2224 assert( SCIPgetVarUbAtIndex(scip, vars[i][k], bdchgidx, FALSE) < 0.5 );
2225 SCIP_CALL( SCIPaddConflictUb(scip, vars[i][k], bdchgidx) );
2226 *result = SCIP_SUCCESS;
2227#ifdef SCIP_DEBUG
2228 (void) SCIPsnprintf(tmpstr, SCIP_MAXSTRLEN, " (%d,%d)", i, k);
2229 (void) strncat(str, tmpstr, SCIP_MAXSTRLEN-1);
2230#endif
2231 }
2232
2233#ifdef SCIP_DEBUG
2234 SCIPdebugMsg(scip, "%s\n", str);
2235#endif
2236 }
2237 else
2238 {
2239 /* packing case */
2240 int lastcolumn;
2241
2242 /* last column considered as part of the bar: */
2243 lastcolumn = nblocks - 1;
2244 if ( lastcolumn > i )
2245 lastcolumn = i;
2246
2247 /* search for variable in the bar that is fixed to 1 in the packing case */
2248 for (k = j; k <= lastcolumn; ++k)
2249 {
2250 if ( SCIPgetVarLbAtIndex(scip, vars[i][k], bdchgidx, FALSE) > 0.5 )
2251 {
2252 SCIP_CALL( SCIPaddConflictLb(scip, vars[i][k], bdchgidx) );
2253 *result = SCIP_SUCCESS;
2254 SCIPdebugMsg(scip, " and variable x[%d][%d] fixed to 1.\n", i, k);
2255 break;
2256 }
2257 }
2258 }
2259 }
2260 }
2261
2262 return SCIP_OKAY;
2263}
2264
2265
2266/** check packing/partitioning orbitope solution for feasibility */
2267static
2269 SCIP* scip, /**< SCIP data structure */
2270 SCIP_CONS* cons, /**< pointer to orbitope constraint */
2271 SCIP_RESULT* result /**< pointer to store the result of the enforcing call */
2272 )
2273{
2274 SCIP_CONSDATA* consdata;
2275 SCIP_Real** weights;
2276 SCIP_Real** vals;
2277 int** cases;
2278 int nspcons;
2279 int nblocks;
2280 int i;
2281 int j;
2282
2283 assert( cons != NULL );
2284
2285 consdata = SCIPconsGetData(cons);
2286
2287 assert( scip != NULL );
2288 assert( consdata != NULL );
2289 assert( consdata->nspcons > 0 );
2290 assert( consdata->nblocks > 0 );
2291 assert( consdata->vals != NULL );
2292 assert( consdata->weights != NULL );
2293 assert( consdata->cases != NULL );
2294
2295 /* check for upper right triangle */
2296 if ( ! consdata->istrianglefixed )
2297 {
2298 SCIP_Bool infeasible = FALSE;
2299 int nfixedvars = 0;
2300
2301 SCIP_CALL( fixTriangle(scip, cons, &infeasible, &nfixedvars) );
2302 if ( infeasible )
2303 {
2304 *result = SCIP_CUTOFF;
2305 return SCIP_OKAY;
2306 }
2307 if ( nfixedvars > 0 )
2308 {
2309 *result = SCIP_REDUCEDDOM;
2310 return SCIP_OKAY;
2311 }
2312 }
2313
2314 nspcons = consdata->nspcons;
2315 nblocks = consdata->nblocks;
2316 vals = consdata->vals;
2317 weights = consdata->weights;
2318 cases = consdata->cases;
2319
2320 /* get solution */
2321 copyValues(scip, consdata, NULL);
2322 SCIPdebugMsg(scip, "Enforcing (pseudo solutions) for orbitope constraint <%s>\n", SCIPconsGetName(cons));
2323
2324 /* compute table */
2325 assert( consdata->istrianglefixed );
2326 computeSCTable(scip, nspcons, nblocks, weights, cases, vals);
2327
2328 /* loop through rows */
2329 for (i = 1; i < nspcons; ++i)
2330 {
2331 SCIP_Real bar = 0.0;
2332 int lastcolumn;
2333
2334 lastcolumn = nblocks - 1;
2335
2336 /* last column considered as part of the bar: */
2337 if ( lastcolumn > i )
2338 lastcolumn = i;
2339
2340 /* traverse row from right to left */
2341 for (j = lastcolumn; j > 0; --j)
2342 {
2343 bar += vals[i][j];
2344 assert( SCIPisIntegral(scip, vals[i][j]) );
2345
2346 /* check whether weights[i-1][j-1] < bar (<=> bar - weights[i-1][j-1] > 0), i.e. cut is violated) */
2347 if ( SCIPisGT(scip, bar - weights[i-1][j-1], 0.0) )
2348 {
2349 SCIPdebugMsg(scip, "Solution is infeasible.\n");
2350 *result = SCIP_INFEASIBLE;
2351 return SCIP_OKAY;
2352 }
2353 }
2354 }
2355
2356 return SCIP_OKAY;
2357}
2358
2359
2360/** check packing/partitioning orbitope solution for feasibility */
2361static
2363 SCIP* scip, /**< SCIP data structure */
2364 SCIP_CONS* cons, /**< pointer to orbitope constraint */
2365 SCIP_SOL* sol, /**< solution to be checked */
2366 SCIP_RESULT* result, /**< pointer to store the result of the enforcing call */
2367 SCIP_Bool printreason /**< whether reason for infeasibility should be printed */
2368 )
2369{
2370 SCIP_CONSDATA* consdata;
2371 SCIP_VAR*** vars;
2372 SCIP_Real** vals;
2373 SCIP_Real** weights;
2374 int** cases;
2375 int nspcons;
2376 int nblocks;
2377 int i;
2378 int j;
2379
2380 /* get data of constraint */
2381 assert( cons != 0 );
2382 consdata = SCIPconsGetData(cons);
2383
2384 assert( consdata != NULL );
2385 assert( consdata->nspcons > 0 );
2386 assert( consdata->nblocks > 0 );
2387 assert( consdata->vars != NULL );
2388 assert( consdata->vals != NULL );
2389 assert( consdata->weights != NULL );
2390 assert( consdata->cases != NULL );
2391
2392 nspcons = consdata->nspcons;
2393 nblocks = consdata->nblocks;
2394 vars = consdata->vars;
2395 vals = consdata->vals;
2396 weights = consdata->weights;
2397 cases = consdata->cases;
2398
2399 /* get solution */
2400 copyValues(scip, consdata, sol);
2401 SCIPdebugMsg(scip, "Checking orbitope constraint <%s> ...\n", SCIPconsGetName(cons));
2402
2403 /* check upper right triangle (if not yet fixed to zero or in debug mode */
2404#ifdef NDEBUG
2405 if ( ! consdata->istrianglefixed )
2406#endif
2407 {
2408 int diagsize;
2409
2410 /* get last row of triangle */
2411 diagsize = nblocks;
2412 if ( nspcons < nblocks )
2413 diagsize = nspcons;
2414
2415 /* check variables */
2416 for (i = 0; i < diagsize; ++i)
2417 {
2418 for (j = i+1; j < nblocks; ++j)
2419 {
2420 if ( ! SCIPisFeasZero(scip, vals[i][j]) )
2421 {
2422 if ( printreason )
2423 SCIPinfoMessage(scip, NULL, "variable x[%d][%d] = %f on upper right nonzero.\n", i, j, vals[i][j]);
2424 *result = SCIP_INFEASIBLE;
2425 }
2426 }
2427 }
2428 }
2429
2430 /* compute table */
2431 computeSCTable(scip, nspcons, nblocks, weights, cases, vals);
2432
2433 /* loop through rows */
2434 for (i = 1; i < nspcons; ++i)
2435 {
2436 SCIP_Real bar;
2437 int lastcolumn;
2438
2439 lastcolumn = nblocks - 1;
2440 bar = 0.0;
2441 /* last column considered as part of the bar: */
2442 if ( lastcolumn > i )
2443 lastcolumn = i;
2444
2445 /* traverse row from right to left */
2446 for (j = lastcolumn; j > 0; --j)
2447 {
2448 bar += vals[i][j];
2449 assert( SCIPisFeasIntegral(scip, vals[i][j]) );
2450
2451 /* check whether weights[i-1][j-1] < bar (<=> bar - weights[i-1][j-1] > 0), i.e. cut is violated) */
2452 if ( SCIPisGT(scip, bar - weights[i-1][j-1], 0.0) )
2453 {
2454 SCIPdebugMsg(scip, "Solution is infeasible.\n");
2455 *result = SCIP_INFEASIBLE;
2456
2457 if ( printreason )
2458 {
2459 int l;
2460 int p1;
2461 int p2;
2462
2463 SCIPinfoMessage(scip, NULL, "violated SCI: bar(");
2464
2465 /* first output bar */
2466 for (l = j; l < nblocks; ++l)
2467 SCIPinfoMessage(scip, NULL, "<%s> (%f)", SCIPvarGetName(vars[i][l]), consdata->vals[i][l]);
2468
2469 SCIPinfoMessage(scip, NULL, ") SC(");
2470
2471 /* output shifted column */
2472 p1 = i-1;
2473 p2 = j-1;
2474 do
2475 {
2476 assert( cases[p1][p2] != -1 );
2477 assert( p1 >= 0 && p1 < i );
2478 assert( p2 >= 0 && p2 < j );
2479
2480 /* if case 1 */
2481 if (cases[p1][p2] == 1)
2482 --p2; /* decrease column */
2483 else
2484 {
2485 /* case 2 or 3: */
2486 assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
2487 SCIPinfoMessage(scip, NULL, "<%s> (%f)", SCIPvarGetName(vars[p1][p2]), consdata->vals[p1][p2]);
2488 if ( cases[p1][p2] == 3 )
2489 break;
2490 }
2491 --p1; /* decrease row */
2492 }
2493 while ( p1 >= 0 ); /* should always be true, i.e. the break should end the loop */
2494 assert( cases[p1][p2] == 3 );
2495
2496 SCIPinfoMessage(scip, NULL, ")");
2497 }
2498 }
2499 }
2500 }
2501
2502 return SCIP_OKAY;
2503}
2504
2505
2506/** check full orbitope solution for feasibility */
2507static
2509 SCIP* scip, /**< SCIP data structure */
2510 SCIP_CONS* cons, /**< constraint to process */
2511 SCIP_SOL* sol, /**< solution to be checked */
2512 SCIP_Bool printreason, /**< whether reason for infeasibility should be printed */
2513 SCIP_Bool* feasible /**< memory address to store whether solution is feasible */
2514 )
2515{
2516 SCIP_CONSDATA* consdata;
2517 SCIP_VAR*** vars;
2518 SCIP_VAR** vars1;
2519 SCIP_VAR** vars2;
2520 int nrows;
2521 int ncols;
2522 int j;
2523 int i;
2524
2525 assert( scip != NULL );
2526 assert( cons != NULL );
2527 assert( feasible != NULL );
2528
2529 consdata = SCIPconsGetData(cons);
2530
2531 assert( consdata != NULL );
2532 assert( consdata->vars != NULL );
2533 assert( consdata->nspcons > 0 );
2534 assert( consdata->nblocks > 0 );
2535 assert( ! consdata->ismodelcons ); /* non-model constraints are never checked */
2536
2537 vars = consdata->vars;
2538 nrows = consdata->nspcons;
2539 ncols = consdata->nblocks;
2540
2541 SCIP_CALL( SCIPallocBufferArray(scip, &vars1, nrows) );
2542 SCIP_CALL( SCIPallocBufferArray(scip, &vars2, nrows) );
2543
2544 /* iterate over adjacent columns of orbitope and check whether the first column in this
2545 * column pair is lexicographically not smaller than the second column in the pair */
2546 *feasible = TRUE;
2547 for (j = 1; j < ncols && *feasible; ++j)
2548 {
2549 for (i = 0; i < nrows; ++i)
2550 {
2551 vars1[i] = vars[i][j - 1];
2552 vars2[i] = vars[i][j];
2553 }
2554
2555 SCIP_CALL( SCIPcheckSolutionOrbisack(scip, sol, vars1, vars2, nrows, printreason, feasible) );
2556 }
2557
2558 SCIPfreeBufferArray(scip, &vars2);
2559 SCIPfreeBufferArray(scip, &vars1);
2560
2561 return SCIP_OKAY;
2562}
2563
2564
2565/** separate orbisack cover inequalities */
2566static
2568 SCIP* scip, /**< SCIP data structure */
2569 SCIP_CONS* cons, /**< constraint to process */
2570 SCIP_SOL* sol, /**< solution to separate (NULL for the LP solution) */
2571 SCIP_Bool dynamic, /**< whether we use a dynamic row order */
2572 int* ngen, /**< pointer to store number of generated cuts */
2573 SCIP_Bool* infeasible /**< pointer to store whether infeasibility has been detected */
2574 )
2575{
2576 SCIP_CONSDATA* consdata;
2577 SCIP_VAR*** vars;
2578 int* roworder;
2579 int nrowsused;
2580 int nrows;
2581 int ncols;
2582 int i;
2583 int j;
2584 int origrow;
2585 SCIP_Real rhs;
2586 SCIP_Real lhs;
2587 SCIP_Real* coeffs1;
2588 SCIP_Real* coeffs2;
2589
2590 assert( scip != NULL );
2591 assert( cons != NULL );
2592 assert( ngen != NULL );
2593 assert( infeasible != NULL );
2594
2595 *ngen = 0;
2596 *infeasible = FALSE;
2597
2598 /* get basic data */
2599 consdata = SCIPconsGetData(cons);
2600 assert( consdata != NULL );
2601
2602 vars = consdata->vars;
2603 nrows = consdata->nspcons;
2604 ncols = consdata->nblocks;
2605 nrowsused = dynamic ? consdata->nrowsused : nrows;
2606 roworder = consdata->roworder;
2607
2608 /* allocate memory for cover inequalities */
2609 SCIP_CALL( SCIPallocBufferArray(scip, &coeffs1, nrowsused) );
2610 SCIP_CALL( SCIPallocBufferArray(scip, &coeffs2, nrowsused) );
2611
2612 lhs = 0.0;
2613 rhs = 0.0;
2614
2615 /* separate orbisack cover inequalities for adjacent columns */
2616 for (j = 0; j < ncols - 1 && ! *infeasible; ++j)
2617 {
2618 SCIP_Real rowval;
2619
2620 for (i = 0; i < nrowsused; ++i)
2621 {
2622 origrow = roworder[i];
2623
2624 assert( origrow >= 0 );
2625 assert( origrow < nrows );
2626
2627 rowval = SCIPgetSolVal(scip, sol, vars[origrow][j + 1]) - SCIPgetSolVal(scip, sol, vars[origrow][j]);
2628
2629 /* check whether cover inequality is violated */
2630 if ( SCIPisEfficacious(scip, rowval + lhs - rhs) )
2631 {
2632 SCIP_ROW* row;
2633 int k;
2634
2635 /* set coefficients for current inequality */
2636 coeffs1[i] = -1.0;
2637 coeffs2[i] = 1.0;
2638
2639 /* add violated orbisack cover inequality */
2640 SCIP_CALL( SCIPcreateEmptyRowCons(scip, &row, cons, "orbisackcover", -SCIPinfinity(scip), rhs, FALSE, FALSE, TRUE) );
2642
2643 for (k = 0; k <= i; ++k)
2644 {
2645 int origrow2;
2646
2647 origrow2 = roworder[k];
2648
2649 SCIP_CALL( SCIPaddVarToRow(scip, row, vars[origrow2][j], coeffs1[k]) );
2650 SCIP_CALL( SCIPaddVarToRow(scip, row, vars[origrow2][j + 1], coeffs2[k]) );
2651 }
2653
2654 SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
2655#ifdef SCIP_DEBUG
2656 SCIP_CALL( SCIPprintRow(scip, row, NULL) );
2657#endif
2658 SCIP_CALL( SCIPreleaseRow(scip, &row) );
2659
2660 *ngen += 1;
2661 if ( *infeasible )
2662 break;
2663
2664 /* reset coefficients for next inequality */
2665 coeffs1[i] = 0.0;
2666 coeffs2[i] = 0.0;
2667 }
2668
2669 /* add argmax( 1 - vals[i][0], vals[i][1] ) as coefficient and ensure that both vars1[0] and vars2[0] are
2670 * contained in the LIFTED cover inequality */
2671 rowval = SCIPgetSolVal(scip, sol, vars[origrow][j]) + SCIPgetSolVal(scip, sol, vars[origrow][j + 1]);
2672 if ( SCIPisEfficacious(scip, 1.0 - rowval) )
2673 {
2674 coeffs1[i] = -1.0;
2675 coeffs2[i] = 0.0;
2676 lhs -= SCIPgetSolVal(scip, sol, vars[origrow][j]);
2677
2678 /* apply lifting? */
2679 if ( i == 0 )
2680 {
2681 coeffs2[i] = 1.0;
2682 lhs += SCIPgetSolVal(scip, sol, vars[origrow][j + 1]);
2683 }
2684 }
2685 else
2686 {
2687 coeffs1[i] = 0.0;
2688 coeffs2[i] = 1.0;
2689 lhs += SCIPgetSolVal(scip, sol, vars[origrow][j]);
2690 rhs += 1.0;
2691
2692 /* apply lifting? */
2693 if ( i == 0 )
2694 {
2695 coeffs1[i] = -1.0;
2696 lhs -= SCIPgetSolVal(scip, sol, vars[origrow][j]);
2697 rhs -= 1.0;
2698 }
2699 }
2700 }
2701 }
2702
2703 SCIPfreeBufferArray(scip, &coeffs1);
2704 SCIPfreeBufferArray(scip, &coeffs2);
2705
2706 return SCIP_OKAY;
2707}
2708
2709
2710/** separate or enforce constraints */
2711static
2713 SCIP* scip, /**< SCIP data structure */
2714 SCIP_CONSHDLR* conshdlr, /**< constraint handler */
2715 SCIP_CONS** conss, /**< constraints to process */
2716 int nconss, /**< number of constraints */
2717 int nusefulconss, /**< number of useful (non-obsolete) constraints to process */
2718 SCIP_SOL* sol, /**< solution to separate (NULL for the LP solution) */
2719 SCIP_RESULT* result, /**< pointer to store the result (should be initialized) */
2720 SCIP_Bool enforce /**< whether we enforce orbitope constraints */
2721 )
2722{
2723 SCIP_Bool infeasible = FALSE;
2724 int nfixedvars = 0;
2725 int ncuts = 0;
2726 int c;
2727
2728 assert( scip != NULL );
2729 assert( conshdlr != NULL );
2730 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2731 assert( result != NULL );
2732
2733 /* loop through constraints */
2734 for (c = 0; c < nconss && ! infeasible; c++)
2735 {
2736 SCIP_CONSHDLRDATA* conshdlrdata;
2737 SCIP_CONSDATA* consdata;
2738 int nconsfixedvars = 0;
2739 int nconscuts = 0;
2740 SCIP_ORBITOPETYPE orbitopetype;
2741
2742 assert( conss[c] != NULL );
2743
2744 /* get data of constraint */
2745 consdata = SCIPconsGetData(conss[c]);
2746 assert( consdata != NULL );
2747
2748 /* do not enforce non-model constraints */
2749 if ( enforce && !consdata->ismodelcons )
2750 continue;
2751
2752 /* get solution */
2753 copyValues(scip, consdata, sol);
2754
2755 /* separate */
2756 orbitopetype = consdata->orbitopetype;
2757
2758 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2759 if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
2760 {
2761 SCIP_CALL( separateSCIs(scip, conshdlr, conss[c], consdata, &infeasible, &nconsfixedvars, &nconscuts) );
2762 nfixedvars += nconsfixedvars;
2763 }
2764 else if ( conshdlrdata->sepafullorbitope )
2765 {
2766 SCIP_CALL( separateCoversOrbisack(scip, conss[c], sol, consdata->usedynamicprop && !consdata->ismodelcons, &nconscuts, &infeasible) );
2767 }
2768 ncuts += nconscuts;
2769
2770 /* stop after the useful constraints if we found cuts of fixed variables */
2771 if ( c >= nusefulconss && (ncuts > 0 || nfixedvars > 0) )
2772 break;
2773 }
2774
2775 if ( infeasible )
2776 {
2777 SCIPdebugMsg(scip, "Infeasible node.\n");
2778 *result = SCIP_CUTOFF;
2779 }
2780 else if ( nfixedvars > 0 )
2781 {
2782 SCIPdebugMsg(scip, "Fixed %d variables.\n", nfixedvars);
2783 *result = SCIP_REDUCEDDOM;
2784 }
2785 else if ( ncuts > 0 )
2786 {
2787 SCIPdebugMsg(scip, "Separated %dinequalities.\n", ncuts);
2788 *result = SCIP_SEPARATED;
2789 }
2790 else
2791 {
2792 SCIPdebugMsg(scip, "No violated inequality found during separation.\n");
2793 }
2794
2795 return SCIP_OKAY;
2796}
2797
2798
2799/** check whether all variables in an orbitope constraint are fixed */
2800static
2802 SCIP* scip, /**< SCIP data structure */
2803 SCIP_CONS* cons, /**< constraint to be processed */
2804 SCIP_Bool* redundant /**< pointer to store whether constraint is redundant (contains no active vars) */
2805 )
2806{
2807 SCIP_CONSDATA* consdata;
2808 SCIP_VAR*** vars;
2809 int i;
2810 int j;
2811 int nrows;
2812 int ncols;
2813
2814 assert( scip != NULL );
2815 assert( cons != NULL );
2816 assert( redundant != NULL );
2817
2818 *redundant = FALSE;
2819
2820 consdata = SCIPconsGetData(cons);
2821 assert( consdata != NULL );
2822 assert( consdata->vars != NULL );
2823 assert( consdata->nspcons > 0 );
2824 assert( consdata->nblocks > 0 );
2825
2826 vars = consdata->vars;
2827 nrows = consdata->nspcons;
2828 ncols = consdata->nblocks;
2829
2830 /* check whether there exists an active variable in the orbitope */
2831 for (i = 0; i < nrows; ++i)
2832 {
2833 for (j = 0; j < ncols; ++j)
2834 {
2835 if ( SCIPvarIsActive(vars[i][j]) )
2836 return SCIP_OKAY;
2837 }
2838 }
2839
2840 *redundant = TRUE;
2841
2842 return SCIP_OKAY;
2843}
2844
2845
2846/*
2847 * Callback methods of constraint handler
2848 */
2849
2850/** copy method for constraint handler plugins (called when SCIP copies plugins) */
2851static
2852SCIP_DECL_CONSHDLRCOPY(conshdlrCopyOrbitope)
2853{ /*lint --e{715}*/
2854 assert(scip != NULL);
2855 assert(conshdlr != NULL);
2856 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2857
2858 /* call inclusion method of constraint handler */
2860
2861 *valid = TRUE;
2862
2863 return SCIP_OKAY;
2864}
2865
2866/** frees constraint handler */
2867static
2868SCIP_DECL_CONSFREE(consFreeOrbitope)
2869{ /*lint --e{715}*/
2870 SCIP_CONSHDLRDATA* conshdlrdata;
2871
2872 assert( scip != 0 );
2873 assert( conshdlr != 0 );
2874 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2875
2876 conshdlrdata = SCIPconshdlrGetData(conshdlr);
2877 assert( conshdlrdata != NULL );
2878
2879 SCIPfreeBlockMemory(scip, &conshdlrdata);
2880
2881 return SCIP_OKAY;
2882}
2883
2884/** frees specific constraint data */
2885static
2886SCIP_DECL_CONSDELETE(consDeleteOrbitope)
2887{ /*lint --e{715}*/
2888 assert(conshdlr != NULL);
2889 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2890
2891 SCIP_CALL( consdataFree(scip, consdata) );
2892
2893 return SCIP_OKAY;
2894}
2895
2896/** transforms constraint data into data belonging to the transformed problem */
2897static
2898SCIP_DECL_CONSTRANS(consTransOrbitope)
2899{ /*lint --e{715}*/
2900 SCIP_CONSDATA* sourcedata;
2901 SCIP_CONSDATA* targetdata;
2902
2903 assert(conshdlr != NULL);
2904 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
2906 assert(sourcecons != NULL);
2907 assert(targetcons != NULL);
2908
2909 sourcedata = SCIPconsGetData(sourcecons);
2910 assert(sourcedata != NULL);
2911
2912 /* create linear constraint data for target constraint */
2913 SCIP_CALL( consdataCreate(scip, &targetdata, sourcedata->vars, sourcedata->nspcons, sourcedata->nblocks,
2914 sourcedata->orbitopetype, sourcedata->resolveprop, sourcedata->usedynamicprop, sourcedata->ismodelcons,
2915 sourcedata->mayinteract) );
2916
2917 /* create target constraint */
2918 SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
2919 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
2920 SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),
2921 SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons),
2922 SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
2923
2924 return SCIP_OKAY;
2925}
2926
2927/** separation method of constraint handler for LP solutions */
2928static
2929SCIP_DECL_CONSSEPALP(consSepalpOrbitope)
2930{ /*lint --e{715}*/
2931 assert( scip != NULL );
2932 assert( result != NULL );
2933
2934 SCIPdebugMsg(scip, "Separation of orbitope constraint handler <%s> for LP solution.\n", SCIPconshdlrGetName(conshdlr));
2935
2936 *result = SCIP_DIDNOTRUN;
2937
2938 /* if solution is integer, skip separation */
2939 if ( SCIPgetNLPBranchCands(scip) <= 0 )
2940 return SCIP_OKAY;
2941
2942 *result = SCIP_DIDNOTFIND;
2943
2944 /* separate constraints */
2945 SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, NULL, result, FALSE) );
2946
2947 return SCIP_OKAY;
2948}
2949
2950/** separation method of constraint handler for arbitrary primal solutions */
2951static
2952SCIP_DECL_CONSSEPASOL(consSepasolOrbitope)
2953{ /*lint --e{715}*/
2954 assert( scip != NULL );
2955 assert( result != NULL );
2956
2957 SCIPdebugMsg(scip, "Separation of orbitope constraint handler <%s> for primal solution.\n", SCIPconshdlrGetName(conshdlr));
2958
2959 *result = SCIP_DIDNOTFIND;
2960
2961 /* separate constraints */
2962 SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, sol, result, FALSE) );
2963
2964 return SCIP_OKAY;
2965}
2966
2967
2968/** constraint enforcing method of constraint handler for LP solutions */
2969static
2970SCIP_DECL_CONSENFOLP(consEnfolpOrbitope)
2971{ /*lint --e{715}*/
2972 assert( scip != NULL );
2973 assert( result != NULL );
2974
2975 /* we have a negative priority, so we should come after the integrality conshdlr */
2976 assert( SCIPgetNLPBranchCands(scip) == 0 );
2977
2978 SCIPdebugMsg(scip, "Enforcement for orbitope constraint handler <%s> for LP solution.\n", SCIPconshdlrGetName(conshdlr));
2979
2980 *result = SCIP_FEASIBLE;
2981
2982 /* separate constraints */
2983 SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, NULL, result, TRUE) );
2984
2985 return SCIP_OKAY;
2986}
2987
2988
2989/** constraint enforcing method of constraint handler for relaxation solutions */
2990static
2991SCIP_DECL_CONSENFORELAX(consEnforelaxOrbitope)
2992{ /*lint --e{715}*/
2993 assert( result != NULL );
2994 assert( scip != NULL );
2995
2996 SCIPdebugMsg(scip, "Enforcement for orbitope constraint handler <%s> for relaxation solution.\n", SCIPconshdlrGetName(conshdlr));
2997
2998 *result = SCIP_FEASIBLE;
2999
3000 /* separate constraints */
3001 SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, sol, result, TRUE) );
3002
3003 return SCIP_OKAY;
3004}
3005
3006
3007/** constraint enforcing method of constraint handler for pseudo solutions */
3008static
3009SCIP_DECL_CONSENFOPS(consEnfopsOrbitope)
3010{ /*lint --e{715}*/
3011 int c;
3012
3013 assert( scip != NULL );
3014 assert( conshdlr != NULL );
3015 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
3016 assert( result != NULL );
3017
3018 *result = SCIP_FEASIBLE;
3019 if ( objinfeasible || solinfeasible )
3020 return SCIP_OKAY;
3021
3022 /* loop through constraints */
3023 for (c = 0; c < nconss; ++c)
3024 {
3025 SCIP_CONS* cons;
3026 SCIP_CONSDATA* consdata;
3027 SCIP_ORBITOPETYPE orbitopetype;
3028 SCIP_Bool feasible;
3029
3030 /* get data of constraint */
3031 cons = conss[c];
3032 assert( cons != 0 );
3033 consdata = SCIPconsGetData(cons);
3034
3035 assert( consdata != NULL );
3036
3037 /* do not enforce non-model constraints */
3038 if ( !consdata->ismodelcons )
3039 continue;
3040
3041 orbitopetype = consdata->orbitopetype;
3042
3043 if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
3044 {
3046 }
3047 else
3048 {
3049 SCIP_CALL( checkFullOrbitopeSolution(scip, cons, NULL, FALSE, &feasible) );
3050
3051 if ( ! feasible )
3052 *result = SCIP_INFEASIBLE;
3053 }
3054
3055 if ( *result == SCIP_INFEASIBLE )
3056 break;
3057 }
3058
3059 return SCIP_OKAY;
3060}
3061
3062
3063/** feasibility check method of constraint handler for integral solutions */
3064static
3065SCIP_DECL_CONSCHECK(consCheckOrbitope)
3066{ /*lint --e{715}*/
3067 int c;
3068 SCIP_CONSDATA* consdata;
3069 SCIP_ORBITOPETYPE orbitopetype;
3070 SCIP_Bool feasible;
3071
3072 assert( scip != NULL );
3073 assert( conshdlr != NULL );
3074 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
3075 assert( result != NULL );
3076
3077 *result = SCIP_FEASIBLE;
3078
3079 /* loop through constraints */
3080 for( c = 0; c < nconss && (*result == SCIP_FEASIBLE || completely); ++c )
3081 {
3082 assert( conss[c] != 0 );
3083 consdata = SCIPconsGetData(conss[c]);
3084
3085 assert( consdata != NULL );
3086
3087 /* do not check non-model constraints */
3088 if ( !consdata->ismodelcons )
3089 continue;
3090
3091 orbitopetype = consdata->orbitopetype;
3092
3093 if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
3094 {
3095 SCIP_CALL( checkPackingPartitioningOrbitopeSolution(scip, conss[c], sol, result, printreason) );
3096 }
3097 else
3098 {
3099 SCIP_CALL( checkFullOrbitopeSolution(scip, conss[c], sol, printreason, &feasible) );
3100
3101 if ( ! feasible )
3102 *result = SCIP_INFEASIBLE;
3103 }
3104 }
3105 SCIPdebugMsg(scip, "Solution is feasible.\n");
3106
3107 return SCIP_OKAY;
3108}
3109
3110
3111/** domain propagation method of constraint handler */
3112static
3113SCIP_DECL_CONSPROP(consPropOrbitope)
3114{ /*lint --e{715}*/
3115 SCIP_Bool infeasible = FALSE;
3116 int nfixedvars = 0;
3117 int c;
3118
3119 assert( scip != NULL );
3120 assert( conshdlr != NULL );
3121 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
3122 assert( result != NULL );
3123
3124 *result = SCIP_DIDNOTRUN;
3125
3126 /* propagate all useful constraints */
3127 for (c = 0; c < nusefulconss && !infeasible; ++c)
3128 {
3129 assert( conss[c] != 0 );
3130
3131 SCIPdebugMsg(scip, "Propagation of orbitope constraint <%s> ...\n", SCIPconsGetName(conss[c]));
3132
3133 SCIP_CALL( propagateCons(scip, conss[c], &infeasible, &nfixedvars) );
3134 }
3135
3136 /* return the correct result */
3137 if ( infeasible )
3138 {
3139 *result = SCIP_CUTOFF;
3140 SCIPdebugMsg(scip, "Propagation via orbitopal fixing proved node to be infeasible.\n");
3141 }
3142 else if ( nfixedvars > 0 )
3143 {
3144 *result = SCIP_REDUCEDDOM;
3145 SCIPdebugMsg(scip, "Propagated %d variables via orbitopal fixing.\n", nfixedvars);
3146 }
3147 else if ( nusefulconss > 0 )
3148 {
3149 *result = SCIP_DIDNOTFIND;
3150 SCIPdebugMsg(scip, "Propagation via orbitopal fixing did not find anything.\n");
3151 }
3152
3153 return SCIP_OKAY;
3154}
3155
3156
3157/** presolving method of constraint handler */
3158static
3159SCIP_DECL_CONSPRESOL(consPresolOrbitope)
3160{ /*lint --e{715}*/
3161 SCIP_Bool infeasible = FALSE;
3162 int noldfixedvars;
3163 int c;
3164 SCIP_Bool redundant;
3165
3166 assert( scip != NULL );
3167 assert( conshdlr != NULL );
3168 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
3169 assert( result != NULL );
3170
3171 *result = SCIP_DIDNOTRUN;
3172 noldfixedvars = *nfixedvars;
3173
3174 /* propagate all useful constraints
3175 *
3176 * @todo use an event handler to only propagate if a variable in the orbitope has been fixed
3177 */
3178 for (c = 0; c < nconss && !infeasible; ++c)
3179 {
3180 int nfixed = 0;
3181
3182 assert( conss[c] != 0 );
3183
3184 SCIPdebugMsg(scip, "Presolving of orbitope constraint <%s> ...\n", SCIPconsGetName(conss[c]));
3185
3186 /* first propagate */
3187 SCIP_CALL( propagateCons(scip, conss[c], &infeasible, &nfixed) );
3188 *nfixedvars += nfixed;
3189
3190 if ( ! infeasible )
3191 {
3192 SCIP_CALL( checkRedundantCons(scip, conss[c], &redundant) );
3193
3194 if ( redundant )
3195 {
3196 SCIPdebugMsg(scip, "Orbitope constraint <%s> is redundant: it does not contain active variables\n",
3197 SCIPconsGetName(conss[c]));
3198 SCIP_CALL( SCIPdelCons(scip, conss[c]) );
3199 assert( ! SCIPconsIsActive(conss[c]) );
3200 (*ndelconss)++;
3201 continue;
3202 }
3203 }
3204 }
3205
3206 if ( infeasible )
3207 {
3208 *result = SCIP_CUTOFF;
3209 SCIPdebugMsg(scip, "Presolving detected infeasibility.\n");
3210 }
3211 else if ( *nfixedvars > noldfixedvars )
3212 {
3213 *result = SCIP_SUCCESS;
3214 }
3215 else if ( nconss > 0 )
3216 {
3217 *result = SCIP_DIDNOTFIND;
3218 SCIPdebugMsg(scip, "Presolving via orbitopal fixing did not find anything.\n");
3219 }
3220
3221 return SCIP_OKAY;
3222}
3223
3224
3225/** propagation conflict resolving method of constraint handler */
3226static
3227SCIP_DECL_CONSRESPROP(consRespropOrbitope)
3228{ /*lint --e{715}*/
3229 SCIP_CONSDATA* consdata;
3230 SCIP_ORBITOPETYPE orbitopetype;
3231
3232 assert( scip != NULL );
3233 assert( cons != NULL );
3234 assert( infervar != NULL );
3235 assert( bdchgidx != NULL );
3236 assert( result != NULL );
3237
3238 consdata = SCIPconsGetData(cons);
3239 assert( consdata != NULL );
3240
3241 orbitopetype = consdata->orbitopetype;
3242
3243 /* resolution for full orbitopes not availabe yet */
3244 if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
3245 {
3246 SCIP_CALL( resolvePropagation(scip, cons, inferinfo, bdchgidx, result) );
3247 }
3248 else
3249 {
3250 SCIP_CALL( resolvePropagationFullOrbitope(scip, conshdlr, cons, inferinfo, bdchgidx, result) );
3251 }
3252
3253 return SCIP_OKAY;
3254}
3255
3256
3257/** variable rounding lock method of constraint handler */
3258static
3259SCIP_DECL_CONSLOCK(consLockOrbitope)
3260{ /*lint --e{715}*/
3261 SCIP_CONSDATA* consdata;
3262 SCIP_VAR*** vars;
3263 int i;
3264 int j;
3265 int nspcons;
3266 int nblocks;
3267
3268 assert( scip != NULL );
3269 assert( conshdlr != NULL );
3270 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
3271 assert( cons != NULL );
3272 assert( locktype == SCIP_LOCKTYPE_MODEL );
3273
3274 consdata = SCIPconsGetData(cons);
3275 assert( consdata != NULL );
3276 assert( consdata->nspcons > 0 );
3277 assert( consdata->nblocks > 0 );
3278 assert( consdata->vars != NULL );
3279
3280 SCIPdebugMsg(scip, "Locking method for orbitope constraint handler\n");
3281
3282 nspcons = consdata->nspcons;
3283 nblocks = consdata->nblocks;
3284 vars = consdata->vars;
3285
3286 /* add up locks and down locks on each variable */
3287 for (i = 0; i < nspcons; ++i)
3288 {
3289 for (j = 0; j < nblocks; ++j)
3290 SCIP_CALL( SCIPaddVarLocksType(scip, vars[i][j], locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) );
3291 }
3292
3293 return SCIP_OKAY;
3294}
3295
3296
3297/** constraint display method of constraint handler */
3298static
3299SCIP_DECL_CONSPRINT(consPrintOrbitope)
3300{
3301 SCIP_CONSDATA* consdata;
3302 SCIP_VAR*** vars;
3303 int i;
3304 int j;
3305 int nspcons;
3306 int nblocks;
3307 SCIP_ORBITOPETYPE orbitopetype;
3308
3309 assert( scip != NULL );
3310 assert( conshdlr != NULL );
3311 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
3312 assert( cons != NULL );
3313
3314 consdata = SCIPconsGetData(cons);
3315 assert( consdata != NULL );
3316 assert( consdata->nspcons > 0 );
3317 assert( consdata->nblocks > 0 );
3318 assert( consdata->vars != NULL );
3319
3320 nspcons = consdata->nspcons;
3321 nblocks = consdata->nblocks;
3322 vars = consdata->vars;
3323 orbitopetype = consdata->orbitopetype;
3324
3325 SCIPdebugMsg(scip, "Printing method for orbitope constraint handler\n");
3326
3327 switch ( orbitopetype )
3328 {
3330 SCIPinfoMessage(scip, file, "partOrbitope(");
3331 break;
3333 SCIPinfoMessage(scip, file, "packOrbitope(");
3334 break;
3336 SCIPinfoMessage(scip, file, "fullOrbitope(");
3337 break;
3338 default:
3339 SCIPABORT();
3340 }
3341
3342 for (i = 0; i < nspcons; ++i)
3343 {
3344 for (j = 0; j < nblocks; ++j)
3345 {
3346 if ( j > 0 )
3347 SCIPinfoMessage(scip, file, ",");
3348 SCIP_CALL( SCIPwriteVarName(scip, file, vars[i][j], TRUE) );
3349 }
3350 if ( i < nspcons-1 )
3351 SCIPinfoMessage(scip, file, ".");
3352 }
3353 SCIPinfoMessage(scip, file, ")");
3354
3355 return SCIP_OKAY;
3356}
3357
3358
3359/** constraint copying method of constraint handler */
3360static
3361SCIP_DECL_CONSCOPY(consCopyOrbitope)
3362{
3363 SCIP_CONSHDLRDATA* conshdlrdata;
3364 SCIP_CONSDATA* sourcedata;
3365 SCIP_VAR*** sourcevars;
3366 SCIP_VAR*** vars;
3367 int nspcons;
3368 int nblocks;
3369 int i;
3370 int k;
3371 int j;
3372
3373 assert( scip != NULL );
3374 assert( cons != NULL );
3375 assert( sourcescip != NULL );
3376 assert( sourceconshdlr != NULL );
3377 assert( strcmp(SCIPconshdlrGetName(sourceconshdlr), CONSHDLR_NAME) == 0 );
3378 assert( sourcecons != NULL );
3379 assert( varmap != NULL );
3380 assert( valid != NULL );
3381
3382 *valid = TRUE;
3383
3384 SCIPdebugMsg(scip, "Copying method for orbitope constraint handler.\n");
3385
3386 sourcedata = SCIPconsGetData(sourcecons);
3387 assert( sourcedata != NULL );
3388 assert( sourcedata->nspcons > 0 );
3389 assert( sourcedata->nblocks > 0 );
3390 assert( sourcedata->vars != NULL );
3391
3392 conshdlrdata = SCIPconshdlrGetData(sourceconshdlr);
3393 assert( conshdlrdata != NULL );
3394
3395 /* do not copy non-model constraints */
3396 if ( !sourcedata->ismodelcons && !conshdlrdata->forceconscopy )
3397 {
3398 *valid = FALSE;
3399
3400 return SCIP_OKAY;
3401 }
3402
3403 nspcons = sourcedata->nspcons;
3404 nblocks = sourcedata->nblocks;
3405 sourcevars = sourcedata->vars;
3406
3407 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nspcons) );
3408 for (i = 0; i < nspcons && *valid; ++i)
3409 {
3410 SCIP_CALL( SCIPallocBufferArray(scip, &(vars[i]), nblocks) ); /*lint !e866*/
3411
3412 for (j = 0; j < nblocks && *valid; ++j)
3413 {
3414 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[i][j], &(vars[i][j]), varmap, consmap, global, valid) );
3415 assert( !(*valid) || vars[i][j] != NULL );
3416 }
3417 }
3418
3419 /* only create the target constraint, if all variables could be copied */
3420 if ( *valid )
3421 {
3422 /* create copied constraint */
3423 if ( name == NULL )
3424 name = SCIPconsGetName(sourcecons);
3425
3427 vars, sourcedata->orbitopetype, nspcons, nblocks, sourcedata->usedynamicprop,
3428 sourcedata->resolveprop, sourcedata->ismodelcons, sourcedata->mayinteract,
3429 initial, separate, enforce, check, propagate,
3430 local, modifiable, dynamic, removable, stickingatnode) );
3431 }
3432
3433 /* free space; only up to row i if copying failed */
3434 assert( 0 <= i && i <= nspcons );
3435 for (k = i - 1; k >= 0; --k)
3436 SCIPfreeBufferArray(scip, &vars[k]);
3437 SCIPfreeBufferArray(scip, &vars);
3438
3439 return SCIP_OKAY;
3440}
3441
3442
3443/** constraint parsing method of constraint handler */
3444static
3445SCIP_DECL_CONSPARSE(consParseOrbitope)
3446{ /*lint --e{715}*/
3447 const char* s;
3448 char* endptr;
3449 SCIP_ORBITOPETYPE orbitopetype;
3450 SCIP_VAR*** vars;
3451 SCIP_VAR* var;
3452 int nspcons;
3453 int maxnspcons;
3454 int nblocks;
3455 int maxnblocks;
3456 int k;
3457 int j;
3458
3459 assert( success != NULL );
3460
3461 *success = TRUE;
3462 s = str;
3463
3464 /* skip white space */
3465 SCIP_CALL( SCIPskipSpace((char**)&s) );
3466
3467 if( strncmp(s, "partOrbitope(", 13) == 0 )
3468 orbitopetype = SCIP_ORBITOPETYPE_PARTITIONING;
3469 else if( strncmp(s, "packOrbitope(", 13) == 0 )
3470 orbitopetype = SCIP_ORBITOPETYPE_PACKING;
3471 else
3472 {
3473 if( strncmp(s, "fullOrbitope(", 13) != 0 )
3474 {
3475 SCIPerrorMessage("Syntax error - expected \"fullOrbitope(\", \"partOrbitope\" or \"packOrbitope\": %s\n", s);
3476 *success = FALSE;
3477 return SCIP_OKAY;
3478 }
3479 orbitopetype = SCIP_ORBITOPETYPE_FULL;
3480 }
3481 s += 13;
3482
3483 /* loop through string */
3484 nspcons = 0;
3485 nblocks = 0;
3486 maxnspcons = 10;
3487 maxnblocks = 10;
3488
3489 SCIP_CALL( SCIPallocBufferArray(scip, &vars, maxnspcons) );
3490
3491 j = 0;
3492 do
3493 {
3494 /* parse variable name */
3495 SCIP_CALL( SCIPparseVarName(scip, s, &var, &endptr) );
3496
3497 if( var == NULL )
3498 {
3499 endptr = strchr(endptr, ')');
3500
3501 if( endptr == NULL || j > 0 )
3502 {
3503 SCIPerrorMessage("not enough variables.\n");
3504 *success = FALSE;
3505 }
3506
3507 break;
3508 }
3509
3510 s = endptr;
3511 assert( s != NULL );
3512
3513 /* skip white space */
3514 SCIP_CALL( SCIPskipSpace((char**)&s) );
3515
3516 /* begin new row if required */
3517 if( j == 0 )
3518 {
3519 ++nspcons;
3520
3521 if( nspcons > maxnspcons )
3522 {
3523 maxnspcons = SCIPcalcMemGrowSize(scip, nspcons);
3524 SCIP_CALL( SCIPreallocBufferArray(scip, &vars, maxnspcons) );
3525 assert( nspcons <= maxnspcons );
3526 }
3527
3528 SCIP_CALL( SCIPallocBufferArray(scip, &(vars[nspcons-1]), nspcons == 1 ? maxnblocks : nblocks) ); /*lint !e866*/
3529 }
3530
3531 /* determine number of columns */
3532 if( nspcons == 1 )
3533 {
3534 nblocks = j+1;
3535
3536 if( *s == '.' || *s == ')' )
3537 SCIP_CALL( SCIPreallocBufferArray(scip, &(vars[nspcons-1]), nblocks) ); /*lint !e866*/
3538 else if( nblocks > maxnblocks )
3539 {
3540 maxnblocks = SCIPcalcMemGrowSize(scip, nblocks);
3541 SCIP_CALL( SCIPreallocBufferArray(scip, &(vars[nspcons-1]), maxnblocks) ); /*lint !e866*/
3542 assert( nblocks <= maxnblocks );
3543 }
3544 }
3545 else if( ( j < nblocks-1 ) == ( *s == '.' || *s == ')' ) )
3546 {
3547 SCIPerrorMessage("variables per row do not match.\n");
3548 *success = FALSE;
3549 break;
3550 }
3551
3552 vars[nspcons-1][j] = var;
3553
3554 if( *s == '.' )
3555 j = 0;
3556 else
3557 ++j;
3558
3559 /* skip ',' or '.' */
3560 if( *s == ',' || *s == '.' )
3561 ++s;
3562 }
3563 while( *s != ')' );
3564
3565 /* to ensure consistency, we disable dynamic propagation and tell SCIP that the orbitope could potentially
3566 * interact with other symmetry handling constraints
3567 */
3568 if( *success )
3569 SCIP_CALL( SCIPcreateConsOrbitope(scip, cons, name, vars, orbitopetype, nspcons, nblocks, FALSE, TRUE, TRUE, TRUE,
3570 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
3571
3572 for( k = nspcons - 1; k >= 0; --k )
3573 SCIPfreeBufferArray(scip, &vars[k]);
3574 SCIPfreeBufferArray(scip, &vars);
3575
3576 return SCIP_OKAY;
3577}
3578
3579
3580/** constraint method of constraint handler which returns the variables (if possible) */
3581static
3582SCIP_DECL_CONSGETVARS(consGetVarsOrbitope)
3583{ /*lint --e{715}*/
3584 SCIP_CONSDATA* consdata;
3585
3586 assert( cons != NULL );
3587 assert( success != NULL );
3588 assert( vars != NULL );
3589
3590 consdata = SCIPconsGetData(cons);
3591 assert( consdata != NULL );
3592
3593 if ( varssize < consdata->nblocks * consdata->nspcons )
3594 (*success) = FALSE;
3595 else
3596 {
3597 int cnt = 0;
3598 int i;
3599 int j;
3600
3601 for (i = 0; i < consdata->nspcons; ++i)
3602 {
3603 for (j = 0; j < consdata->nblocks; ++j)
3604 vars[cnt++] = consdata->vars[i][j];
3605 }
3606 (*success) = TRUE;
3607 }
3608
3609 return SCIP_OKAY;
3610}
3611
3612
3613/** constraint method of constraint handler which returns the number of variables (if possible) */
3614static
3615SCIP_DECL_CONSGETNVARS(consGetNVarsOrbitope)
3616{ /*lint --e{715}*/
3617 SCIP_CONSDATA* consdata;
3618
3619 assert( cons != NULL );
3620
3621 consdata = SCIPconsGetData(cons);
3622 assert( consdata != NULL );
3623
3624 (*nvars) = consdata->nblocks * consdata->nspcons;
3625 (*success) = TRUE;
3626
3627 return SCIP_OKAY;
3628}
3629
3630
3631/*
3632 * constraint specific interface methods
3633 */
3634
3635/** creates the handler for orbitope constraints and includes it in SCIP */
3637 SCIP* scip /**< SCIP data structure */
3638 )
3639{
3640 SCIP_CONSHDLRDATA* conshdlrdata;
3641 SCIP_CONSHDLR* conshdlr;
3642
3643 /* create orbitope constraint handler data */
3644 SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) );
3645
3646 /* include constraint handler */
3650 consEnfolpOrbitope, consEnfopsOrbitope, consCheckOrbitope, consLockOrbitope,
3651 conshdlrdata) );
3652 assert(conshdlr != NULL);
3653
3654 /* set non-fundamental callbacks via specific setter functions */
3655 SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyOrbitope, consCopyOrbitope) );
3656 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeOrbitope) );
3657 SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteOrbitope) );
3658 SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsOrbitope) );
3659 SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsOrbitope) );
3660 SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseOrbitope) );
3662 SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintOrbitope) );
3665 SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropOrbitope) );
3666 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpOrbitope, consSepasolOrbitope, CONSHDLR_SEPAFREQ,
3668 SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransOrbitope) );
3669 SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxOrbitope) );
3670
3671 SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/checkpporbitope",
3672 "Strengthen orbitope constraints to packing/partioning orbitopes?",
3673 &conshdlrdata->checkpporbitope, TRUE, DEFAULT_PPORBITOPE, NULL, NULL) );
3674
3675 SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/sepafullorbitope",
3676 "Whether we separate inequalities for full orbitopes?",
3677 &conshdlrdata->sepafullorbitope, TRUE, DEFAULT_SEPAFULLORBITOPE, NULL, NULL) );
3678
3679 SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/forceconscopy",
3680 "Whether orbitope constraints should be forced to be copied to sub SCIPs.",
3681 &conshdlrdata->forceconscopy, TRUE, DEFAULT_FORCECONSCOPY, NULL, NULL) );
3682
3683 return SCIP_OKAY;
3684}
3685
3686
3687/** creates and captures a orbitope constraint
3688 *
3689 * @pre If packing/partitioning orbitopes are used, this constraint handler assumes that constraints which enforce
3690 * the packing/partitioning constraints are contained in the problem. It does not implement, e.g., separation and
3691 * propagation of set packing/partitioning constraints, since this would just copy large parts of the code of the
3692 * setppc constraint handler.
3693 *
3694 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
3695 */
3697 SCIP* scip, /**< SCIP data structure */
3698 SCIP_CONS** cons, /**< pointer to hold the created constraint */
3699 const char* name, /**< name of constraint */
3700 SCIP_VAR*** vars, /**< matrix of variables on which the symmetry acts */
3701 SCIP_ORBITOPETYPE orbitopetype, /**< type of orbitope constraint */
3702 int nspcons, /**< number of set partitioning/packing constraints <=> p */
3703 int nblocks, /**< number of symmetric variable blocks <=> q */
3704 SCIP_Bool usedynamicprop, /**< whether dynamic propagation should be used */
3705 SCIP_Bool mayinteract, /**< whether symmetries corresponding to orbitope might interact
3706 * with symmetries handled by other routines */
3707 SCIP_Bool resolveprop, /**< should propagation be resolved? */
3708 SCIP_Bool ismodelcons, /**< whether the orbitope is a model constraint */
3709 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
3710 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
3711 SCIP_Bool separate, /**< should the constraint be separated during LP processing?
3712 * Usually set to TRUE. */
3713 SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
3714 * TRUE for model constraints, FALSE for additional, redundant constraints. */
3715 SCIP_Bool check, /**< should the constraint be checked for feasibility?
3716 * TRUE for model constraints, FALSE for additional, redundant constraints. */
3717 SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
3718 * Usually set to TRUE. */
3719 SCIP_Bool local, /**< is constraint only valid locally?
3720 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
3721 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
3722 * Usually set to FALSE. In column generation applications, set to TRUE if pricing
3723 * adds coefficients to this constraint. */
3724 SCIP_Bool dynamic, /**< is constraint subject to aging?
3725 * Usually set to FALSE. Set to TRUE for own cuts which
3726 * are separated as constraints. */
3727 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
3728 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
3729 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
3730 * if it may be moved to a more global node?
3731 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
3732 )
3733{
3734 SCIP_CONSHDLRDATA* conshdlrdata;
3735 SCIP_CONSHDLR* conshdlr;
3736 SCIP_CONSDATA* consdata;
3737
3738 /* find the orbitope constraint handler */
3739 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
3740 if ( conshdlr == NULL )
3741 {
3742 SCIPerrorMessage("orbitope constraint handler not found\n");
3743 return SCIP_PLUGINNOTFOUND;
3744 }
3745
3746 /* check for consistency */
3747 if ( usedynamicprop && mayinteract )
3748 {
3749 SCIPwarningMessage(scip, "Dynamic propagation is only possible if orbitope does not interact with \
3750 other symmetry handling constraints. Ignore value of <usedynamicprop>.\n");
3751 }
3752
3753 assert( nspcons > 0 );
3754 assert( nblocks > 0 );
3755
3756 /* run some checks */
3757#ifndef NDEBUG
3758 {
3759 SCIP_Real obj;
3760 int i;
3761 int j;
3762 for (i = 0; i < nspcons; ++i)
3763 {
3764 /* initialize obj to infinity */
3765 obj = SCIPinfinity(scip);
3766 for (j = 0; j < nblocks; ++j)
3767 {
3768 SCIP_Bool fixedZero;
3769 SCIP_VAR* var;
3770
3771 var = vars[i][j];
3772 assert(var != NULL);
3773
3774 if ( SCIPvarIsNegated(var) )
3775 var = SCIPvarGetNegatedVar(var);
3776
3777 /* all variables need to be binary */
3778 assert( SCIPvarIsBinary(var) );
3779
3780 /* fixed variables have obj = 0; for variables fixed to 0, we assume that there is no
3781 problem (but we cannot always check it, e.g., when in the original problem
3782 variables were fixed and this problem was copied.) */
3783 fixedZero = ( SCIPisZero(scip, SCIPvarGetLbGlobal(var)) && SCIPisZero(scip, SCIPvarGetUbGlobal(var)) );
3784
3785 /* @todo adapt correctness of the following check for sub-scips */
3786 if ( SCIPgetSubscipDepth(scip) == 0 )
3787 {
3788 /* check whether all variables in a row have the same objective */
3789 if ( ! fixedZero && SCIPisInfinity(scip, obj) )
3790 obj = SCIPvarGetObj(var);
3791 else
3792 {
3793 assert( fixedZero || ! SCIPvarIsActive(var) || SCIPisEQ(scip, obj, SCIPvarGetObj(var)) );
3794 }
3795 }
3796 }
3797 }
3798 }
3799#endif
3800
3801 conshdlrdata = SCIPconshdlrGetData(conshdlr);
3802 if ( conshdlrdata->checkpporbitope && orbitopetype != SCIP_ORBITOPETYPE_PARTITIONING
3803 && orbitopetype != SCIP_ORBITOPETYPE_PACKING )
3804 {
3805 SCIP_CALL( strengthenOrbitopeConstraint(scip, vars, &nspcons, nblocks, &orbitopetype, mayinteract) );
3806 }
3807
3808 /* create constraint data */
3809 SCIP_CALL( consdataCreate(scip, &consdata, vars, nspcons, nblocks, orbitopetype,
3810 resolveprop, usedynamicprop && ! mayinteract, ismodelcons, mayinteract) );
3811
3812 /* create constraint */
3813 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
3814 local, modifiable, dynamic, removable, stickingatnode) );
3815
3816 return SCIP_OKAY;
3817}
3818
3819/** creates and captures an orbitope constraint
3820 * in its most basic variant, i. e., with all constraint flags set to their default values
3821 *
3822 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
3823 */
3825 SCIP* scip, /**< SCIP data structure */
3826 SCIP_CONS** cons, /**< pointer to hold the created constraint */
3827 const char* name, /**< name of constraint */
3828 SCIP_VAR*** vars, /**< matrix of variables on which the symmetry acts */
3829 SCIP_ORBITOPETYPE orbitopetype, /**< type of orbitope constraint */
3830 int nspcons, /**< number of set partitioning/packing constraints <=> p */
3831 int nblocks, /**< number of symmetric variable blocks <=> q */
3832 SCIP_Bool usedynamicprop, /**< whether dynamic propagation should be used */
3833 SCIP_Bool resolveprop, /**< should propagation be resolved? */
3834 SCIP_Bool ismodelcons, /**< whether the orbitope is a model constraint */
3835 SCIP_Bool mayinteract /**< whether symmetries corresponding to orbitope might interact
3836 * with symmetries handled by other routines */
3837 )
3838{
3839 SCIP_CALL( SCIPcreateConsOrbitope(scip, cons, name, vars, orbitopetype, nspcons, nblocks, usedynamicprop,
3840 resolveprop, ismodelcons, mayinteract, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
3841
3842 return SCIP_OKAY;
3843}
SCIP_Real * r
Definition: circlepacking.c:59
constraint handler for orbisack constraints
static SCIP_RETCODE checkRedundantCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *redundant)
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyOrbitope)
#define CONSHDLR_NEEDSCONS
#define CONSHDLR_SEPAFREQ
static SCIP_DECL_CONSPARSE(consParseOrbitope)
static SCIP_RETCODE propagatePackingPartitioningCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible, int *nfixedvars)
static SCIP_RETCODE checkFullOrbitopeSolution(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool printreason, SCIP_Bool *feasible)
#define CONSHDLR_CHECKPRIORITY
static SCIP_DECL_CONSGETNVARS(consGetNVarsOrbitope)
#define CONSHDLR_DESC
static SCIP_RETCODE enfopsPackingPartitioningOrbitopeSolution(SCIP *scip, SCIP_CONS *cons, SCIP_RESULT *result)
static SCIP_DECL_CONSCOPY(consCopyOrbitope)
static SCIP_RETCODE resolvePropagation(SCIP *scip, SCIP_CONS *cons, int inferinfo, SCIP_BDCHGIDX *bdchgidx, SCIP_RESULT *result)
static SCIP_RETCODE separateConstraints(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int nusefulconss, SCIP_SOL *sol, SCIP_RESULT *result, SCIP_Bool enforce)
static SCIP_RETCODE checkPackingPartitioningOrbitopeSolution(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_RESULT *result, SCIP_Bool printreason)
#define CONSHDLR_PROP_TIMING
static SCIP_RETCODE separateSCIs(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_Bool *infeasible, int *nfixedvars, int *ncuts)
#define DEFAULT_FORCECONSCOPY
#define CONSHDLR_MAXPREROUNDS
static SCIP_DECL_CONSPRINT(consPrintOrbitope)
static SCIP_DECL_CONSFREE(consFreeOrbitope)
static SCIP_DECL_CONSPROP(consPropOrbitope)
#define CONSHDLR_SEPAPRIORITY
static SCIP_DECL_CONSSEPALP(consSepalpOrbitope)
static SCIP_DECL_CONSRESPROP(consRespropOrbitope)
static SCIP_DECL_CONSPRESOL(consPresolOrbitope)
static SCIP_RETCODE propagateCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible, int *nfixedvars)
static SCIP_DECL_CONSSEPASOL(consSepasolOrbitope)
static SCIP_RETCODE resolvePropagationFullOrbitope(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, int inferinfo, SCIP_BDCHGIDX *bdchgidx, SCIP_RESULT *result)
static SCIP_DECL_CONSTRANS(consTransOrbitope)
static SCIP_RETCODE findLexMaxFace(SCIP_VAR ***vars, int **lexmaxfixes, int *minfixedrowlexmax, SCIP_Bool *infeasible, int m, int n, int nrowsused, SCIP_Bool resprop)
static SCIP_RETCODE strengthenOrbitopeConstraint(SCIP *scip, SCIP_VAR ***vars, int *nrows, int ncols, SCIP_ORBITOPETYPE *type, SCIP_Bool mayinteract)
static SCIP_DECL_CONSDELETE(consDeleteOrbitope)
static SCIP_DECL_CONSCHECK(consCheckOrbitope)
static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSDATA **consdata, SCIP_VAR ***vars, int nspcons, int nblocks, SCIP_ORBITOPETYPE orbitopetype, SCIP_Bool resolveprop, SCIP_Bool usedynamicprop, SCIP_Bool ismodelcons, SCIP_Bool mayinteract)
static SCIP_RETCODE findLexMinFace(SCIP_VAR ***vars, int **lexminfixes, int *minfixedrowlexmin, SCIP_Bool *infeasible, int m, int n, int nrowsused, SCIP_Bool resprop)
#define CONSHDLR_PROPFREQ
static SCIP_RETCODE separateCoversOrbisack(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_Bool dynamic, int *ngen, SCIP_Bool *infeasible)
#define DEFAULT_PPORBITOPE
static SCIP_DECL_CONSGETVARS(consGetVarsOrbitope)
#define CONSHDLR_PRESOLTIMING
static SCIP_RETCODE propagateFullOrbitopeCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible, int *nfixedvars, SCIP_Bool dynamic)
#define DEFAULT_SEPAFULLORBITOPE
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata)
static SCIP_DECL_CONSENFORELAX(consEnforelaxOrbitope)
#define CONSHDLR_EAGERFREQ
static SCIP_DECL_CONSENFOLP(consEnfolpOrbitope)
#define CONSHDLR_ENFOPRIORITY
static SCIP_RETCODE fixTriangle(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible, int *nfixedvars)
static SCIP_RETCODE computeDynamicRowOrder(SCIP *scip, SCIP_HASHMAP *rowindexmap, SCIP_Bool *rowused, int *roworder, int nrows, int ncols, int *maxrowlabel)
static void computeSCTable(SCIP *scip, int nspcons, int nblocks, SCIP_Real **weights, int **cases, SCIP_Real **vals)
#define CONSHDLR_DELAYSEPA
static void copyValues(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_SOL *sol)
static SCIP_DECL_CONSLOCK(consLockOrbitope)
#define CONSHDLR_NAME
static SCIP_DECL_CONSENFOPS(consEnfopsOrbitope)
#define CONSHDLR_DELAYPROP
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 NULL
Definition: def.h:267
#define SCIP_MAXSTRLEN
Definition: def.h:288
#define SCIP_Bool
Definition: def.h:91
#define MIN(x, y)
Definition: def.h:243
#define SCIP_Real
Definition: def.h:173
#define TRUE
Definition: def.h:93
#define FALSE
Definition: def.h:94
#define MAX(x, y)
Definition: def.h:239
#define SCIPABORT()
Definition: def.h:346
#define REALABS(x)
Definition: def.h:197
#define SCIP_CALL(x)
Definition: def.h:374
SCIP_RETCODE SCIPcheckSolutionOrbisack(SCIP *scip, SCIP_SOL *sol, SCIP_VAR **vars1, SCIP_VAR **vars2, int nrows, SCIP_Bool printreason, SCIP_Bool *feasible)
SCIP_RETCODE SCIPcreateConsBasicOrbitope(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR ***vars, SCIP_ORBITOPETYPE orbitopetype, int nspcons, int nblocks, SCIP_Bool usedynamicprop, SCIP_Bool resolveprop, SCIP_Bool ismodelcons, SCIP_Bool mayinteract)
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 SCIPincludeConshdlrOrbitope(SCIP *scip)
int SCIPgetSubscipDepth(SCIP *scip)
Definition: scip_copy.c:2605
SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success)
Definition: scip_copy.c:711
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition: scip_general.c:596
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition: scip_general.c:380
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition: scip_prob.c:2843
void SCIPhashmapFree(SCIP_HASHMAP **hashmap)
Definition: misc.c:3108
void * SCIPhashmapGetImage(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3261
SCIP_RETCODE SCIPhashmapInsert(SCIP_HASHMAP *hashmap, void *origin, void *image)
Definition: misc.c:3156
SCIP_RETCODE SCIPhashmapCreate(SCIP_HASHMAP **hashmap, BMS_BLKMEM *blkmem, int mapsize)
Definition: misc.c:3074
SCIP_Bool SCIPhashmapExists(SCIP_HASHMAP *hashmap, void *origin)
Definition: misc.c:3423
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition: scip_message.c:208
#define SCIPdebugMsg
Definition: scip_message.h:78
void SCIPwarningMessage(SCIP *scip, const char *formatstr,...)
Definition: scip_message.c:120
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition: scip_param.c:57
int SCIPgetNLPBranchCands(SCIP *scip)
Definition: scip_branch.c:428
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse)))
Definition: scip_cons.c:808
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition: scip_cons.c:540
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars)))
Definition: scip_cons.c:831
SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa)
Definition: scip_cons.c:235
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition: scip_cons.c:281
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition: scip_cons.c:181
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
Definition: scip_cons.c:578
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSFREE((*consfree)))
Definition: scip_cons.c:372
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
Definition: scip_cons.c:323
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4197
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
Definition: scip_cons.c:347
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition: scip_cons.c:941
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition: cons.c:4217
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
Definition: scip_cons.c:601
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
Definition: scip_cons.c:647
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars)))
Definition: scip_cons.c:854
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint)))
Definition: scip_cons.c:785
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition: cons.c:8244
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition: cons.c:8473
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition: cons.c:8383
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition: cons.c:8413
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition: cons.c:8403
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
Definition: cons.c:8275
SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition: scip_cons.c:998
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition: cons.c:8433
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition: cons.c:8453
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition: cons.c:8214
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition: cons.c:8463
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition: cons.c:8493
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition: cons.c:8393
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition: cons.c:8483
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition: scip_cut.c:135
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition: scip_cut.c:250
#define SCIPfreeBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:110
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition: scip_mem.c:139
#define SCIPallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:124
#define SCIPreallocBufferArray(scip, ptr, num)
Definition: scip_mem.h:128
#define SCIPfreeBufferArray(scip, ptr)
Definition: scip_mem.h:136
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition: scip_mem.h:93
#define SCIPfreeBlockMemory(scip, ptr)
Definition: scip_mem.h:108
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition: scip_mem.h:111
#define SCIPallocBlockMemory(scip, ptr)
Definition: scip_mem.h:89
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition: scip_mem.h:105
SCIP_DOMCHG * SCIPnodeGetDomchg(SCIP_NODE *node)
Definition: tree.c:7588
SCIP_NODE * SCIPnodeGetParent(SCIP_NODE *node)
Definition: tree.c:7773
int SCIPnodeGetDepth(SCIP_NODE *node)
Definition: tree.c:7503
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition: scip_probing.c:97
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 SCIPcreateEmptyRowConshdlr(SCIP *scip, SCIP_ROW **row, SCIP_CONSHDLR *conshdlr, const char *name, SCIP_Real lhs, SCIP_Real rhs, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool removable)
Definition: scip_lp.c:1391
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 SCIPaddVarsToRow(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition: scip_lp.c:1727
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition: scip_sol.c:1217
SCIP_RETCODE SCIPisPackingPartitioningOrbitope(SCIP *scip, SCIP_VAR ***vars, int nrows, int ncols, SCIP_Bool **pprows, int *npprows, SCIP_ORBITOPETYPE *type)
Definition: symmetry.c:1178
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisSumEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
SCIP_NODE * SCIPgetCurrentNode(SCIP *scip)
Definition: scip_tree.c:91
SCIP_VAR * SCIPvarGetNegatedVar(SCIP_VAR *var)
Definition: var.c:17894
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition: var.c:17748
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition: var.c:17599
SCIP_VAR * SCIPboundchgGetVar(SCIP_BOUNDCHG *boundchg)
Definition: var.c:17326
SCIP_BOUNDCHG * SCIPdomchgGetBoundchg(SCIP_DOMCHG *domchg, int pos)
Definition: var.c:17374
SCIP_BOUNDCHGTYPE SCIPboundchgGetBoundchgtype(SCIP_BOUNDCHG *boundchg)
Definition: var.c:17336
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition: var.c:18144
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition: var.c:17926
SCIP_RETCODE SCIPparseVarName(SCIP *scip, const char *str, SCIP_VAR **var, char **endptr)
Definition: scip_var.c:533
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
Definition: var.c:17584
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition: var.c:18088
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition: scip_var.c:4259
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:2128
int SCIPdomchgGetNBoundchgs(SCIP_DOMCHG *domchg)
Definition: var.c:17366
const char * SCIPvarGetName(SCIP_VAR *var)
Definition: var.c:17419
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition: scip_var.c:1248
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition: var.c:18134
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition: var.c:17574
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition: var.c:18078
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:8715
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition: scip_var.c:8276
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: scip_var.c:1992
SCIP_Real SCIPvarGetLbAtIndex(SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: var.c:16710
SCIP_RETCODE SCIPinferBinvarCons(SCIP *scip, SCIP_VAR *var, SCIP_Bool fixedval, SCIP_CONS *infercons, int inferinfo, SCIP_Bool *infeasible, SCIP_Bool *tightened)
Definition: scip_var.c:5723
SCIP_RETCODE SCIPwriteVarName(SCIP *scip, FILE *file, SCIP_VAR *var, SCIP_Bool type)
Definition: scip_var.c:230
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition: scip_var.c:1439
SCIP_Real SCIPvarGetUbAtIndex(SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition: var.c:16829
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition: scip_var.c:1214
SCIP_Bool SCIPallowStrongDualReds(SCIP *scip)
Definition: scip_var.c:8629
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition: misc.c:10877
SCIP_RETCODE SCIPskipSpace(char **s)
Definition: misc.c:10866
memory allocation routines
BMS_BLKMEM * SCIPblkmem(SCIP *scip)
Definition: scip_mem.c:57
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 problem copies
public methods for cuts and aggregation rows
general public methods
public methods for the LP relaxation, rows and columns
public methods for memory management
public methods for message handling
public methods for numerical tolerances
public methods for SCIP parameter handling
public methods for global and local (sub)problems
public methods for the probing mode
public methods for solutions
public methods for SCIP variables
methods for handling symmetries
@ SCIP_CONFTYPE_PROPAGATION
Definition: type_conflict.h:60
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition: type_cons.h:64
struct SCIP_ConsData SCIP_CONSDATA
Definition: type_cons.h:65
@ SCIP_DIDNOTRUN
Definition: type_result.h:42
@ SCIP_CUTOFF
Definition: type_result.h:48
@ SCIP_FEASIBLE
Definition: type_result.h:45
@ SCIP_REDUCEDDOM
Definition: type_result.h:51
@ SCIP_DIDNOTFIND
Definition: type_result.h:44
@ SCIP_SEPARATED
Definition: type_result.h:49
@ SCIP_SUCCESS
Definition: type_result.h:58
@ SCIP_INFEASIBLE
Definition: type_result.h:46
enum SCIP_Result SCIP_RESULT
Definition: type_result.h:61
@ SCIP_PLUGINNOTFOUND
Definition: type_retcode.h:54
@ SCIP_OKAY
Definition: type_retcode.h:42
enum SCIP_Retcode SCIP_RETCODE
Definition: type_retcode.h:63
@ SCIP_STAGE_SOLVING
Definition: type_set.h:53
@ SCIP_STAGE_TRANSFORMING
Definition: type_set.h:46
type definitions for symmetry computations
@ SCIP_ORBITOPETYPE_PACKING
@ SCIP_ORBITOPETYPE_FULL
@ SCIP_ORBITOPETYPE_PARTITIONING
enum SCIP_OrbitopeType SCIP_ORBITOPETYPE
@ SCIP_VARTYPE_BINARY
Definition: type_var.h:62
@ SCIP_BOUNDCHGTYPE_BRANCHING
Definition: type_var.h:87
@ SCIP_LOCKTYPE_MODEL
Definition: type_var.h:97