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