SCIP Doxygen Documentation
Loading...
Searching...
No Matches
cons_orbitope_pp.c
Go to the documentation of this file.
1/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2/* */
3/* This file is part of the program and library */
4/* SCIP --- Solving Constraint Integer Programs */
5/* */
6/* Copyright (c) 2002-2026 Zuse Institute Berlin (ZIB) */
7/* */
8/* Licensed under the Apache License, Version 2.0 (the "License"); */
9/* you may not use this file except in compliance with the License. */
10/* You may obtain a copy of the License at */
11/* */
12/* http://www.apache.org/licenses/LICENSE-2.0 */
13/* */
14/* Unless required by applicable law or agreed to in writing, software */
15/* distributed under the License is distributed on an "AS IS" BASIS, */
16/* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. */
17/* See the License for the specific language governing permissions and */
18/* limitations under the License. */
19/* */
20/* You should have received a copy of the Apache-2.0 license */
21/* along with SCIP; see the file LICENSE. If not visit scipopt.org. */
22/* */
23/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
24
25/**@file cons_orbitope_pp.c
26 * @ingroup DEFPLUGINS_CONS
27 * @brief constraint handler for partitioning/packing 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_pp.h.
33 * When creating the constraint, users can decide whether it is a constraint defining the model
34 * or "just" use to handle symmetries. In the latter case, symmetry reductions are only performed
35 * by the constraint handler if strong dual reductions are permitted.
36 *
37 * The details of the method implemented here are described in the following papers.
38 *
39 * Packing and Partitioning Orbitopes@n
40 * Volker Kaibel and Marc E. Pfetsch,@n
41 * Math. Program. 114, No. 1, 1-36 (2008)
42 *
43 * Among other things, this paper describes so-called shifted column inequalities of the following
44 * 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
45 * bar. These inequalities can be used to handle symmetry and they are separated in this constraint
46 * handler. We use the linear time separation algorithm of the paper.@par
47 *
48 * Orbitopal Fixing@n
49 * Volker Kaibel, Matthias Peinhardt, and Marc E. Pfetsch,@n
50 * Discrete Optimization 8, No. 4, 595-610 (2011)
51 * (A preliminary version appears in Proc. IPCO 2007.)
52 *
53 * In this paper a linear time propagation algorithm is described, a variant of which is implemented
54 * here. The implemented variant does not run in linear time, but is very fast in practice.
55 *
56 * <table>
57 * <caption>translation table</caption>
58 * <tr><td>here</td><td>paper</td></tr>
59 * <tr><td></td><td></td></tr>
60 * <tr><td>nrows </td><td>p </td></tr>
61 * <tr><td>ncols </td><td>q </td></tr>
62 * <tr><td>vars </td><td>x </td></tr>
63 * <tr><td>vals </td><td>A^\\star</td></tr>
64 * <tr><td>weights </td><td>\\omega </td></tr>
65 * <tr><td>cases </td><td>\\tau </td></tr>
66 * <tr><td>fixtriangle </td><td>-- </td></tr>
67 * <tr><td>resolveprop </td><td>-- </td></tr>
68 * <tr><td>firstnonzeros</td><td>\\mu </td></tr>
69 * <tr><td>lastones </td><td>\\alpha </td></tr>
70 * <tr><td>frontiersteps</td><td>\\Gamma </td></tr>
71 * </table>
72 *
73 */
74
75/*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
76
77#include "blockmemshell/memory.h"
78#include "scip/cons_orbitope_pp.h"
79#include "scip/cons_setppc.h"
80#include "scip/pub_cons.h"
81#include "scip/pub_message.h"
82#include "scip/pub_var.h"
83#include "scip/scip.h"
84#include "scip/scip_branch.h"
85#include "scip/scip_conflict.h"
86#include "scip/scip_cons.h"
87#include "scip/scip_copy.h"
88#include "scip/scip_cut.h"
89#include "scip/scip_general.h"
90#include "scip/scip_lp.h"
91#include "scip/scip_mem.h"
92#include "scip/scip_message.h"
93#include "scip/scip_numerics.h"
94#include "scip/scip_param.h"
95#include "scip/scip_prob.h"
96#include "scip/scip_probing.h"
97#include "scip/scip_sol.h"
98#include "scip/scip_var.h"
99#include "scip/symmetry.h"
100#include <symmetry/type_symmetry.h>
101
102/* constraint handler properties */
103#define CONSHDLR_NAME "orbitope_pp"
104#define CONSHDLR_DESC "symmetry breaking constraint handler relying on partitioning/packing orbitopes"
105#define CONSHDLR_SEPAPRIORITY +40100 /**< priority of the constraint handler for separation */
106#define CONSHDLR_ENFOPRIORITY -1005200 /**< priority of the constraint handler for constraint enforcing */
107#define CONSHDLR_CHECKPRIORITY -1005200 /**< priority of the constraint handler for checking feasibility */
108#define CONSHDLR_SEPAFREQ -1 /**< frequency for separating cuts; zero means to separate only in the root node */
109#define CONSHDLR_PROPFREQ 1 /**< frequency for propagating domains; zero means only preprocessing propagation */
110#define CONSHDLR_EAGERFREQ -1 /**< frequency for using all instead of only the useful constraints in separation,
111 * propagation and enforcement, -1 for no eager evaluations, 0 for first only */
112#define CONSHDLR_MAXPREROUNDS -1 /**< maximal number of presolving rounds the constraint handler participates in (-1: no limit) */
113#define CONSHDLR_DELAYSEPA FALSE /**< should separation method be delayed, if other separators found cuts? */
114#define CONSHDLR_DELAYPROP FALSE /**< should propagation method be delayed, if other propagators found reductions? */
115#define CONSHDLR_NEEDSCONS TRUE /**< should the constraint handler be skipped, if no constraints are available? */
116
117#define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP /**< propagation timing mask of the constraint handler */
118#define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM /**< presolving timing of the constraint handler (fast, medium, or exhaustive) */
119
120#define DEFAULT_FORCECONSCOPY FALSE /**< whether orbitope constraints should be forced to be copied to sub SCIPs */
121
122/*
123 * Data structures
124 */
125
126/** constraint handler data */
127struct SCIP_ConshdlrData
128{
129 SCIP_Bool forceconscopy; /**< whether orbitope constraints should be forced to be copied to sub SCIPs */
130};
131
132/** constraint data for orbitope constraints */
133struct SCIP_ConsData
134{
135 SCIP_VAR*** vars; /**< matrix of variables on which the symmetry acts */
136 SCIP_VAR** tmpvars; /**< temporary storage for variables */
137 SCIP_Real** vals; /**< LP-solution for those variables */
138 SCIP_Real* tmpvals; /**< temporary storage for values */
139 SCIP_Real** weights; /**< SC weight table */
140 int** cases; /**< indicator of the SC cases */
141 int nrows; /**< number of rows in orbitope matrix <=> p */
142 int ncols; /**< number of columns in orbitope matrix <=> q */
143 SCIP_ORBITOPETYPE orbitopetype; /**< type of orbitope constraint */
144 SCIP_Bool resolveprop; /**< should propagation be resolved? */
145 SCIP_Bool istrianglefixed; /**< has the upper right triangle already globally been fixed to zero? */
146 SCIP_Bool ismodelcons; /**< whether the orbitope is a model constraint */
147};
148
149
150/*
151 * Local methods
152 */
153
154/** frees an orbitope constraint data */
155static
156SCIP_RETCODE consdataFree(
157 SCIP* scip, /**< SCIP data structure */
158 SCIP_CONSDATA** consdata /**< pointer to orbitope constraint data */
159 )
160{
161 int i;
162 int j;
163 int nrows;
164 int ncols;
165
166 assert( consdata != NULL );
167 assert( *consdata != NULL );
168
169 nrows = (*consdata)->nrows;
170 ncols = (*consdata)->ncols;
171 for (i = 0; i < nrows; ++i)
172 {
173 /* release variables in vars array */
174 for (j = 0; j < ncols; ++j)
175 {
176 assert( (*consdata)->vars[i] != NULL );
177 SCIP_CALL( SCIPreleaseVar(scip, &(*consdata)->vars[i][j]) );
178 }
179
180 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->cases[i]), ncols); /*lint !e866*/
181 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vars[i]), ncols); /*lint !e866*/
182 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->weights[i]), ncols); /*lint !e866*/
183 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vals[i]), ncols); /*lint !e866*/
184 }
185
186 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->cases), nrows);
187 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vars), nrows);
188 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->weights), nrows);
189 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->vals), nrows);
190
191 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->tmpvals), nrows + ncols);
192 SCIPfreeBlockMemoryArrayNull(scip, &((*consdata)->tmpvars), nrows + ncols);
193
194 SCIPfreeBlockMemory(scip, consdata);
195
196 return SCIP_OKAY;
197}
198
199
200/** creates orbitope constraint data */
201static
202SCIP_RETCODE consdataCreate(
203 SCIP* scip, /**< SCIP data structure */
204 SCIP_CONSDATA** consdata, /**< pointer to store constraint data */
205 SCIP_VAR*** vars, /**< variables array, must have size nspcons x nblocks */
206 int nrows, /**< number of rows in orbitope matrix <=> p */
207 int ncols, /**< number of columns in orbitope matrix <=> q */
208 SCIP_ORBITOPETYPE orbitopetype, /**< type of orbitope constraint */
209 SCIP_Bool resolveprop, /**< should propagation be resolved? */
210 SCIP_Bool ismodelcons /**< whether the orbitope is a model constraint */
211 )
212{
213 int i;
214 int j;
215
216 assert(consdata != NULL);
217
218 SCIP_CALL( SCIPallocBlockMemory(scip, consdata) );
219
220 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->vals, nrows) );
221 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->weights, nrows) );
222 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->vars, nrows) );
223 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->cases, nrows) );
224
225 for (i = 0; i < nrows; ++i)
226 {
227 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->vals[i], ncols) ); /*lint !e866*/
228 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->weights[i], ncols) ); /*lint !e866*/
229 SCIP_CALL( SCIPduplicateBlockMemoryArray(scip, &(*consdata)->vars[i], vars[i], ncols) ); /*lint !e866*/
230 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->cases[i], ncols) ); /*lint !e866*/
231 }
232 (*consdata)->tmpvals = NULL;
233 (*consdata)->tmpvars = NULL;
234 (*consdata)->nrows = nrows;
235 (*consdata)->ncols = ncols;
236 (*consdata)->orbitopetype = orbitopetype;
237 (*consdata)->resolveprop = resolveprop;
238 (*consdata)->istrianglefixed = FALSE;
239 (*consdata)->ismodelcons = ismodelcons;
240
241 /* get transformed variables, if we are in the transformed problem */
242 if ( SCIPisTransformed(scip) )
243 {
244 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->tmpvals, nrows + ncols) );
245 SCIP_CALL( SCIPallocBlockMemoryArray(scip, &(*consdata)->tmpvars, nrows + ncols) );
246
247 for (i = 0; i < nrows; ++i)
248 {
249 /* make sure that no variable gets multiaggregated (cannot be handled by cons_orbitope, since one cannot easily
250 * eliminate single variables from an orbitope constraint).
251 */
252 for (j = 0; j < ncols; ++j)
253 {
254 SCIP_CALL( SCIPgetTransformedVar(scip, (*consdata)->vars[i][j], &(*consdata)->vars[i][j]) );
255 SCIP_CALL( SCIPmarkDoNotMultaggrVar(scip, (*consdata)->vars[i][j]) );
256 }
257 }
258 }
259
260 /* capture vars contained in vars array */
261 for (i = 0; i < nrows; ++i)
262 {
263 for (j = 0; j < ncols; ++j)
264 {
265 assert( (*consdata)->vars[i][j] != NULL );
266 SCIP_CALL( SCIPcaptureVar(scip, (*consdata)->vars[i][j]) );
267 }
268 }
269
270 return SCIP_OKAY;
271}
272
273
274#ifdef PRINT_MATRIX
275/** debug method, prints variable matrix */
276static
277void printMatrix(
278 SCIP* scip, /**< SCIP data structure */
279 SCIP_CONSDATA* consdata /**< the constraint data */
280 )
281{
282 int i;
283 int j;
284
285 assert( consdata != NULL );
286 assert( consdata->nrows > 0 );
287 assert( consdata->ncols > 0 );
288 assert( consdata->vars != NULL );
289
290 for (j = 0; j < consdata->ncols; ++j)
291 SCIPinfoMessage(scip, NULL, "-");
292
293 SCIPinfoMessage(scip, NULL, "\n");
294 for (i = 0; i < consdata->nrows; ++i)
295 {
296 for (j = 0; j < consdata->ncols; ++j)
297 {
298 if ( SCIPvarGetUbLocal(consdata->vars[i][j]) - SCIPvarGetLbLocal(consdata->vars[i][j]) < 0.5 )
299 SCIPinfoMessage(scip, NULL, "%1.0f", REALABS(SCIPvarGetUbLocal(consdata->vars[i][j])));
300 else
301 SCIPinfoMessage(scip, NULL, " ");
302 }
303 SCIPinfoMessage(scip, NULL, "|\n");
304 }
305 for (j = 0; j < consdata->ncols; ++j)
306 SCIPinfoMessage(scip, NULL, "-");
307 SCIPinfoMessage(scip, NULL, "\n");
308}
309#endif
310
311
312#ifdef SHOW_SCI
313/** Print SCI in nice form for debugging */
314static
315SCIP_RETCODE printSCI(
316 SCIP* scip, /**< SCIP pointer */
317 int nrows, /**< number of rows */
318 int ncols, /**< number of columns */
319 int** cases, /**< SCI dynamic programming table */
320 int i, /**< row position of bar */
321 int j /**< column position of bar */
322 )
323{
324 int k;
325 int l;
326 int** M;
327 int p1;
328 int p2;
329
330 SCIP_CALL( SCIPallocBufferArray(scip, &M, nrows) );
331 for (k = 0; k < nrows; ++k)
332 {
333 SCIP_CALL( SCIPallocBufferArray(scip, &M[k], ncols) ); /*lint !e866*/
334 for (l = 0; l < ncols; ++l)
335 M[k][l] = 0;
336 }
337
338 /* first add bar */
339 for (l = j; l < ncols; ++l)
340 {
341 assert( M[i][l] == 0 );
342 M[i][l] = 1;
343 }
344
345 /* then add shifted column */
346 p1 = i-1;
347 p2 = j-1;
348 do
349 {
350 assert( cases[p1][p2] != -1 );
351 assert( p1 >= 0 && p1 < i );
352 assert( p2 >= 0 && p2 < j );
353
354 /* if case 1 */
355 if ( cases[p1][p2] == 1 )
356 --p2; /* decrease column */
357 else
358 {
359 /* case 2 or 3: */
360 assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
361 assert( M[p1][p2] == 0 );
362 M[p1][p2] = -1;
363 if ( cases[p1][p2] == 3 )
364 break;
365 }
366 --p1; /* decrease row */
367 }
368 while ( p1 >= 0 ); /* should always be true, i.e. the break should end the loop */
369 assert( cases[p1][p2] == 3 );
370
371 /* now output matrix M */
372 for (l = 0; l < ncols; ++l)
373 SCIPinfoMessage(scip, NULL, "-");
374 SCIPinfoMessage(scip, NULL, "\n");
375
376 for (k = 0; k < nrows; ++k)
377 {
378 for (l = 0; l < ncols; ++l)
379 {
380 if ( l > k )
381 SCIPinfoMessage(scip, NULL, "*");
382 else
383 {
384 switch (M[k][l])
385 {
386 case 1:
387 SCIPinfoMessage(scip, NULL, "+");
388 break;
389 case -1:
390 SCIPinfoMessage(scip, NULL, "-");
391 break;
392 case 0:
393 SCIPinfoMessage(scip, NULL, "#");
394 break;
395 default:
396 SCIPerrorMessage("unexpected matrix entry <%d>: should be -1, 0 or +1\n", M[k][l]);
397 SCIPABORT();
398 }
399 }
400 }
401 SCIPinfoMessage(scip, NULL, "\n");
402 }
403
404 for (l = 0; l < ncols; ++l)
405 SCIPinfoMessage(scip, NULL, "-");
406 SCIPinfoMessage(scip, NULL, "\n");
407
408 for (k = 0; k < nrows; ++k)
409 SCIPfreeBufferArray(scip, &M[k]);
410 SCIPfreeBufferArray(scip, &M);
411
412 return SCIP_OKAY;
413}
414#endif
415
416
417/** copies the variables values from the solution to the constraint data structure */
418static
419void copyValues(
420 SCIP* scip, /**< the SCIP data structure */
421 SCIP_CONSDATA* consdata, /**< the constraint data */
422 SCIP_SOL* sol /**< a primal solution or NULL for the current LP optimum */
423 )
424{
425 int i;
426 int j;
427
428 assert( scip != NULL );
429 assert( consdata != NULL );
430 assert( consdata->nrows > 0 );
431 assert( consdata->ncols > 0 );
432 assert( consdata->vars != NULL );
433 assert( consdata->vals != NULL );
434
435 for (i = 0; i < consdata->nrows; ++i)
436 {
437 for (j = 0; j < consdata->ncols; ++j)
438 consdata->vals[i][j] = SCIPgetSolVal(scip, sol, consdata->vars[i][j]);
439 }
440}
441
442
443/** compute the dynamic programming table for SC
444 *
445 * Build up dynamic programming table in order to find SCs with minimum weight.
446 *
447 * The values of the minimal SCIs are stored in @a weights.
448 * The array @a cases[i][j] stores which of the cases were applied to get @a weights[i][j].
449 * Here, 3 means that we have reached the upper limit.
450 *
451 * We assume that the upper right triangle is fixed to 0. Hence we can perform the computation a
452 * bit more efficient.
453 */
454static
455void computeSCTable(
456 SCIP* scip, /**< SCIP pointer */
457 int nrows, /**< number of rows in orbitope matrix <=> p */
458 int ncols, /**< number of columns in orbitope matrix <=> q */
459 SCIP_Real** weights, /**< SC weight table */
460 int** cases, /**< indicator of the SC cases */
461 SCIP_Real** vals /**< current solution */
462 )
463{
464 SCIP_Real minvalue;
465 int diagsize;
466 int i;
467 int j;
468
469 assert( weights != NULL );
470 assert( cases != NULL );
471 assert( vals != NULL );
472
473#ifndef NDEBUG
474 /* for debugging */
475 for (i = 0; i < nrows; ++i)
476 {
477 for (j = 0; j < ncols; ++j)
478 {
479 if ( i >= j )
480 {
481 weights[i][j] = -1.0;
482 cases[i][j] = -1;
483 }
484 }
485 }
486#endif
487
488 /* initialize diagonal */
489 minvalue = vals[0][0];
490 weights[0][0] = minvalue;
491 cases[0][0] = 3;
492
493 /* get last row of triangle */
494 diagsize = ncols;
495 if ( nrows < ncols )
496 diagsize = nrows;
497
498 for (j = 1; j < diagsize; ++j)
499 {
500 /* use LT to move entry as far to the left as possible */
501 if ( SCIPisLT(scip, vals[j][j], minvalue) )
502 {
503 minvalue = vals[j][j];
504 cases[j][j] = 3;
505 }
506 else
507 cases[j][j] = 1;
508 weights[j][j] = minvalue;
509 }
510
511 /* initialize first column */
512 for (i = 1; i < nrows; ++i)
513 {
514 weights[i][0] = weights[i-1][0] + vals[i][0];
515 cases[i][0] = 2; /* second case */
516 }
517
518 /* build the table */
519 for (i = 2; i < nrows; ++i)
520 {
521 for (j = 1; j < ncols && j < i; ++j)
522 {
523 SCIP_Real weightleft;
524 SCIP_Real weightright;
525
526 assert( cases[i-1][j] != -1 );
527 assert( cases[i-1][j-1] != -1 );
528
529 weightleft = weights[i-1][j-1];
530 weightright = vals[i][j] + weights[i-1][j];
531
532 /* For first column: cannot take left possibility */
533 if ( SCIPisLT(scip, weightleft, weightright) )
534 {
535 weights[i][j] = weightleft;
536 cases[i][j] = 1;
537 }
538 else
539 {
540 weights[i][j] = weightright;
541 cases[i][j] = 2;
542 }
543 }
544 }
545}
546
547
548/** fix upper right triangle if necessary */
549static
550SCIP_RETCODE fixTriangle(
551 SCIP* scip, /**< SCIP data structure */
552 SCIP_CONS* cons, /**< constraint to be processed */
553 SCIP_Bool* infeasible, /**< pointer to store TRUE, if the node can be cut off */
554 int* nfixedvars /**< pointer to add up the number of found domain reductions */
555 )
556{
557 SCIP_CONSDATA* consdata;
558 SCIP_VAR*** vars;
559 SCIP_Bool fixedglobal;
560 SCIP_Bool fixed;
561 int diagsize;
562 int nrows;
563 int ncols;
564 int i;
565 int j;
566
567 assert( scip != NULL );
568 assert( cons != NULL );
569 assert( infeasible != NULL );
570 assert( nfixedvars != NULL );
571
572 consdata = SCIPconsGetData(cons);
573 assert( consdata != NULL );
574 assert( consdata->nrows > 0 );
575 assert( consdata->ncols > 0 );
576 assert( consdata->vars != NULL );
577
578 *infeasible = FALSE;
579 *nfixedvars = 0;
580
581 if ( consdata->istrianglefixed )
582 return SCIP_OKAY;
583
584 nrows = consdata->nrows;
585 ncols = consdata->ncols;
586 vars = consdata->vars;
587 fixedglobal = TRUE;
588
589 /* get last row of triangle */
590 diagsize = ncols;
591 if ( nrows < ncols )
592 diagsize = nrows;
593
594 /* fix variables to 0 */
595 for (i = 0; i < diagsize; ++i)
596 {
597 for (j = i+1; j < ncols; ++j)
598 {
599 /* fix variable, if not in the root the fixation is local */
600 SCIP_CALL( SCIPfixVar(scip, vars[i][j], 0.0, infeasible, &fixed) );
601
602 if ( *infeasible )
603 {
604 SCIPdebugMsg(scip, "The problem is infeasible: some variable in the upper right triangle is fixed to 1.\n");
605 return SCIP_OKAY;
606 }
607
608 if ( fixed )
609 ++(*nfixedvars);
610
611 if ( SCIPvarGetUbGlobal(vars[i][j]) > 0.5 )
612 fixedglobal = FALSE;
613 }
614 }
615 if ( *nfixedvars > 0 )
616 {
617 SCIPdebugMsg(scip, "<%s>: %s fixed upper right triangle to 0 (fixed vars: %d).\n",
618 SCIPconsGetName(cons), fixedglobal ? "globally" : "locally", *nfixedvars);
619 }
620 else
621 {
622 SCIPdebugMsg(scip, "<%s>: Upper right triangle already fixed to 0.\n", SCIPconsGetName(cons));
623 }
624
625 if ( fixedglobal )
626 consdata->istrianglefixed = TRUE;
627
628 return SCIP_OKAY;
629}
630
631
632/** separates shifted column inequalities according to the solution stored in consdata->vals */
633static
634SCIP_RETCODE separateSCIs(
635 SCIP* scip, /**< the SCIP data structure */
636 SCIP_CONSHDLR* conshdlr, /**< constraint handler */
637 SCIP_CONS* cons, /**< constraint */
638 SCIP_CONSDATA* consdata, /**< the constraint data */
639 SCIP_Bool* infeasible, /**< whether we detected infeasibility */
640 int* nfixedvars, /**< pointer to store the number of variables fixed */
641 int* ncuts /**< pointer to store number of separated SCIs */
642 )
643{
644 SCIP_Real** vals;
645 SCIP_Real** weights;
646 SCIP_Real* tmpvals;
647 SCIP_VAR*** vars;
648 SCIP_VAR** tmpvars;
649 int** cases;
650 int nrows;
651 int ncols;
652 int i;
653 int j;
654 int l;
655
656 assert( scip != NULL );
657 assert( conshdlr != NULL );
658 assert( cons != NULL );
659 assert( infeasible != NULL);
660 assert( nfixedvars != NULL );
661 assert( ncuts != NULL );
662
663 assert( consdata != NULL );
664 assert( consdata->nrows > 0 );
665 assert( consdata->ncols > 0 );
666 assert( consdata->vars != NULL );
667 assert( consdata->vals != NULL );
668 assert( consdata->tmpvars != NULL );
669 assert( consdata->tmpvals != NULL );
670 assert( consdata->weights != NULL );
671 assert( consdata->cases != NULL );
672
673 *infeasible = FALSE;
674 *nfixedvars = 0;
675 *ncuts = 0;
676
677 nrows = consdata->nrows;
678 ncols = consdata->ncols;
679 vars = consdata->vars;
680 vals = consdata->vals;
681 tmpvars = consdata->tmpvars;
682 tmpvals = consdata->tmpvals;
683 weights = consdata->weights;
684 cases = consdata->cases;
685
686 /* check for upper right triangle */
687 if ( ! consdata->istrianglefixed )
688 {
689 SCIP_CALL( fixTriangle(scip, cons, infeasible, nfixedvars) );
690 if ( *infeasible )
691 return SCIP_OKAY;
692 if ( *nfixedvars > 0 )
693 return SCIP_OKAY;
694 }
695
696 /* compute table if necessary (i.e., not computed before) */
697 computeSCTable(scip, nrows, ncols, weights, cases, vals);
698
699 /* loop through rows */
700 for (i = 1; i < nrows && ! (*infeasible); ++i)
701 {
702 SCIP_Real bar; /* value of bar: */
703 int lastcolumn; /* last column considered as part of the bar */
704
705 bar = 0.0;
706 lastcolumn = ncols - 1;
707 if ( lastcolumn > i )
708 lastcolumn = i;
709
710 /* traverse row from right to left: */
711 /* j >= 1, since for j = 0, i.e., the bar is a complete row, there does not exist an SCI */
712 for (j = lastcolumn; j > 0; --j)
713 {
714 bar += vals[i][j];
715
716 /* check whether weights[i-1][j-1] < bar (<=> bar - weights[i-1][j-1] > 0), i.e. cut is violated) */
717 if ( SCIPisEfficacious(scip, bar - weights[i-1][j-1]) )
718 {
719#ifndef NDEBUG
720 SCIP_Real weight = 0.0;
721#endif
722 SCIP_ROW* row;
723#ifdef SCIP_DEBUG
724 char name[SCIP_MAXSTRLEN];
725#endif
726 int nvars;
727 int p1;
728 int p2;
729
730 nvars = 0;
731 p1 = i-1;
732 p2 = j-1;
733
734 /* first add bar */
735 for (l = j; l <= lastcolumn; ++l)
736 {
737 tmpvars[nvars] = vars[i][l];
738 tmpvals[nvars] = 1.0;
739 nvars++;
740 }
741
742 /* then add shifted column */
743 do
744 {
745 assert( cases[p1][p2] != -1 );
746 assert( p1 >= 0 && p1 < i );
747 assert( p2 >= 0 && p2 < j );
748
749 /* if case 1 */
750 if (cases[p1][p2] == 1)
751 p2--; /* decrease column */
752 else
753 {
754 /* case 2 or 3: */
755 assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
756 tmpvars[nvars] = vars[p1][p2];
757 tmpvals[nvars] = -1.0;
758 nvars++;
759#ifndef NDEBUG
760 weight += vals[p1][p2];
761#endif
762 if ( cases[p1][p2] == 3 )
763 break;
764 }
765 p1--; /* decrease row */
766 }
767 while ( p1 >= 0 ); /* should always be true, i.e. the break should end the loop */
768 assert( cases[p1][p2] == 3 );
769
770 /* generate cut */
771#ifdef SCIP_DEBUG
772 (void) SCIPsnprintf(name, SCIP_MAXSTRLEN, "sci_%d_%d", i, j);
773 SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, name, -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
774#else
775 SCIP_CALL( SCIPcreateEmptyRowConshdlr(scip, &row, conshdlr, "", -SCIPinfinity(scip), 0.0, FALSE, FALSE, TRUE) );
776#endif
777 SCIP_CALL( SCIPaddVarsToRow(scip, row, nvars, tmpvars, tmpvals) );
778 /*SCIP_CALL( SCIPprintRow(scip, row, NULL) ); */
779 SCIP_CALL( SCIPaddRow(scip, row, FALSE, infeasible) );
780 SCIP_CALL( SCIPreleaseRow(scip, &row) );
781 ++(*ncuts);
782
783#ifdef SHOW_SCI
784 SCIP_CALL( printSCI(scip, nrows, ncols, cases, i, j) );
785#endif
786
787 assert( SCIPisSumEQ(scip, weights[i-1][j-1], weight) );
788 }
789 }
790 }
791 return SCIP_OKAY;
792}
793
794
795/** propagation method for a single orbitope constraint */
796static
797SCIP_RETCODE propagateCons(
798 SCIP* scip, /**< SCIP data structure */
799 SCIP_CONS* cons, /**< constraint to be processed */
800 SCIP_Bool* infeasible, /**< pointer to store TRUE, if the node can be cut off */
801 int* nfixedvars /**< pointer to add up the number of found domain reductions */
802 )
803{
804 SCIP_CONSDATA* consdata;
805 SCIP_ORBITOPETYPE orbitopetype;
806 SCIP_VAR*** vars;
807 int* firstnonzeros;
808 int* lastones;
809 int* frontiersteps;
810 int lastoneprevrow;
811 int nrows;
812 int ncols;
813 int nsteps;
814 int i;
815 int j;
816
817 assert( scip != NULL );
818 assert( cons != NULL );
819 assert( infeasible != NULL );
820 assert( nfixedvars != NULL );
821
822 consdata = SCIPconsGetData(cons);
823 assert( consdata != NULL );
824
825 *nfixedvars = 0;
826
827 /* if the constraint is not a model constraint, check whether symmetry reductions are permitted */
828 if( !consdata->ismodelcons && !SCIPallowStrongDualReds(scip) )
829 return SCIP_OKAY;
830
831 consdata = SCIPconsGetData(cons);
832 assert( consdata != NULL );
833 assert( consdata->nrows > 0 );
834 assert( consdata->ncols > 0 );
835 assert( consdata->vars != NULL );
836
837 nrows = consdata->nrows;
838 ncols = consdata->ncols;
839 vars = consdata->vars;
840 orbitopetype = consdata->orbitopetype;
841
842 assert( orbitopetype == SCIP_ORBITOPETYPE_PACKING || orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING );
843
844 /* fix upper right triangle if still necessary */
845 if ( ! consdata->istrianglefixed )
846 {
847 int nfixed = 0;
848 SCIP_CALL( fixTriangle(scip, cons, infeasible, &nfixed) );
849 *nfixedvars += nfixed;
850 }
851
852 /* prepare further propagation */
853 SCIP_CALL( SCIPallocBufferArray(scip, &firstnonzeros, nrows) );
854 SCIP_CALL( SCIPallocBufferArray(scip, &lastones, nrows) );
855 SCIP_CALL( SCIPallocBufferArray(scip, &frontiersteps, ncols) );
856
857#ifdef PRINT_MATRIX
858 SCIPdebugMsg(scip, "Matrix:\n");
859 printMatrix(scip, consdata);
860#endif
861
862 /* propagate */
863 lastoneprevrow = 0;
864 lastones[0] = 0;
865
866 if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING )
867 {
868 /* packing case: if entry (0,0) is fixed to 0 */
869 if ( SCIPvarGetUbLocal(vars[0][0]) < 0.5 )
870 {
871 lastoneprevrow = -1;
872 lastones[0] = -1;
873 }
874 }
875 nsteps = 0;
876
877 for (i = 1; i < nrows; ++i)
878 {
879 int lastcolumn;
880 int firstnonzeroinrow;
881 int lastoneinrow;
882 SCIP_Bool infrontier;
883
884 /* last column considered as part of the bar: */
885 lastcolumn = ncols - 1;
886 if ( lastcolumn > i )
887 lastcolumn = i;
888
889 /* find first position not fixed to 0 (partitioning) or fixed to 1 (packing) */
890 firstnonzeroinrow = -1;
891 for (j = 0; j <= lastcolumn; ++j)
892 {
893 if ( orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
894 {
895 /* partitioning case: if variable is not fixed to 0 */
896 if ( SCIPvarGetUbLocal(vars[i][j]) > 0.5 )
897 {
898 firstnonzeroinrow = j;
899 break;
900 }
901 }
902 else
903 {
904 /* packing case: if variable is fixed to 1 */
905 if ( SCIPvarGetLbLocal(vars[i][j]) > 0.5 )
906 {
907 firstnonzeroinrow = j;
908 break;
909 }
910 }
911 }
912 /* if all variables are fixed to 0 in the partitioning case - should not happen */
913 if ( firstnonzeroinrow == -1 && orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
914 {
915 SCIPdebugMsg(scip, " -> Infeasible node: all variables in row %d are fixed to 0.\n", i);
916 *infeasible = TRUE;
917 /* conflict should be analyzed by setppc constraint handler */
918 goto TERMINATE;
919 }
920 firstnonzeros[i] = firstnonzeroinrow;
921 assert( orbitopetype == SCIP_ORBITOPETYPE_PACKING || firstnonzeroinrow >= 0 );
922 assert( -1 <= firstnonzeroinrow && firstnonzeroinrow <= lastcolumn );
923
924 /* compute rightmost possible position for a 1 */
925 assert( orbitopetype == SCIP_ORBITOPETYPE_PACKING || 0 <= lastoneprevrow );
926 assert( lastoneprevrow <= lastcolumn );
927
928 /* if we are at right border or if entry in column lastoneprevrow+1 is fixed to 0 */
929 infrontier = FALSE;
930 assert( lastoneprevrow + 1 >= 0 );
931 if ( lastoneprevrow == ncols-1 || SCIPvarGetUbLocal(vars[i][lastoneprevrow+1]) < 0.5 ) /*lint !e679*/
932 lastoneinrow = lastoneprevrow;
933 else
934 {
935 lastoneinrow = lastoneprevrow + 1;
936 frontiersteps[nsteps++] = i;
937 infrontier = TRUE;
938 }
939
940 /* store lastoneinrow */
941 assert( orbitopetype == SCIP_ORBITOPETYPE_PACKING || 0 <= lastoneinrow );
942 assert( lastoneinrow <= lastcolumn );
943 lastones[i] = lastoneinrow;
944
945 /* check whether we are infeasible */
946 if ( firstnonzeroinrow > lastoneinrow )
947 {
948 int k;
949
950#ifdef SCIP_DEBUG
951 if ( orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
952 {
953 SCIPdebugMsg(scip, " -> Infeasible node: row %d, leftmost nonzero at %d, rightmost 1 at %d\n",
954 i, firstnonzeroinrow, lastoneinrow);
955 }
956 else
957 {
958 SCIPdebugMsg(scip, " -> Infeasible node: row %d, 1 at %d, rightmost position for 1 at %d\n",
959 i, firstnonzeroinrow, lastoneinrow);
960 }
961#endif
962
963 /* check if conflict analysis is applicable */
964 if ( SCIPisConflictAnalysisApplicable(scip) )
965 {
966 /* conflict analysis only applicable in SOLVING stage */
967 assert( SCIPgetStage(scip) == SCIP_STAGE_SOLVING || SCIPinProbing(scip) );
968
969 /* perform conflict analysis */
970 SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) );
971
972 if ( orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
973 {
974 /* add bounds (variables fixed to 0) that result in the first nonzero entry */
975 for (j = 0; j <= lastcolumn; ++j)
976 {
977 /* add varaibles in row up to the first variable fixed to 0 */
978 if ( SCIPvarGetUbLocal(vars[i][j]) > 0.5 )
979 break;
980
981 assert( SCIPvarGetUbLocal(vars[i][j]) < 0.5 );
982 SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i][j]) );
983 }
984 }
985 else
986 {
987 /* add bounds that result in the last one - check top left entry for packing case */
988 if ( lastones[0] == -1 )
989 {
990 assert( SCIPvarGetUbLocal(vars[0][0]) < 0.5 );
991 SCIP_CALL( SCIPaddConflictBinvar(scip, vars[0][0]) );
992 }
993
994 /* mark variable fixed to 1 */
995 assert( SCIPvarGetLbLocal(vars[i][firstnonzeroinrow]) > 0.5 );
996 SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i][firstnonzeroinrow]) );
997 }
998
999 /* add bounds that result in the last one - pass through rows */
1000 for (k = 1; k < i; ++k)
1001 {
1002 int l;
1003 l = lastones[k] + 1;
1004
1005 /* if the frontier has not moved and we are not beyond the matrix boundaries */
1006 if ( l <= ncols-1 && l <= k && lastones[k-1] == lastones[k] )
1007 {
1008 assert( SCIPvarGetUbLocal(vars[k][l]) < 0.5 );
1009 SCIP_CALL( SCIPaddConflictBinvar(scip, vars[k][l]) );
1010 }
1011 }
1012 SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
1013 }
1014
1015 *infeasible = TRUE;
1016 goto TERMINATE;
1017 }
1018
1019 /* fix entries beyond the last possible position for a 1 in the row to 0 (see Lemma 1 in the paper) */
1020 for (j = lastoneinrow+1; j <= lastcolumn; ++j)
1021 {
1022 /* if the entry is not yet fixed to 0 */
1023 if ( SCIPvarGetUbLocal(vars[i][j]) > 0.5 )
1024 {
1025 SCIP_Bool tightened;
1026 int inferInfo;
1027
1028 SCIPdebugMsg(scip, " -> Fixing entry (%d,%d) to 0.\n", i, j);
1029
1030 tightened = FALSE;
1031
1032 /* fix variable to 0 and store position of (i,lastoneinrow+1) for conflict resolution */
1033 inferInfo = i * ncols + lastoneinrow + 1;
1034 /* correction according to Lemma 1 in the paper (second part): store (i,lastoneinrow+2) */
1035 if ( !infrontier )
1036 ++inferInfo;
1037 SCIP_CALL( SCIPinferBinvarCons(scip, vars[i][j], FALSE, cons, inferInfo, infeasible, &tightened) );
1038
1039 /* if entry is fixed to one -> infeasible node */
1040 if ( *infeasible )
1041 {
1042 SCIPdebugMsg(scip, " -> Infeasible node: row %d, 1 in column %d beyond rightmost position %d\n", i, j, lastoneinrow);
1043 /* check if conflict analysis is applicable */
1044 if( SCIPisConflictAnalysisApplicable(scip) )
1045 {
1046 int k;
1047
1048 /* conflict analysis only applicable in SOLVING stage */
1049 assert(SCIPgetStage(scip) == SCIP_STAGE_SOLVING || SCIPinProbing(scip));
1050
1051 /* perform conflict analysis */
1052 SCIP_CALL( SCIPinitConflictAnalysis(scip, SCIP_CONFTYPE_PROPAGATION, FALSE) );
1053
1054 /* add current bound */
1055 SCIP_CALL( SCIPaddConflictBinvar(scip, vars[i][j]) );
1056
1057 /* add bounds that result in the last one - check top left entry for packing case */
1058 if ( orbitopetype == SCIP_ORBITOPETYPE_PACKING && lastones[0] == -1 )
1059 {
1060 assert( SCIPvarGetUbLocal(vars[0][0]) < 0.5 );
1061 SCIP_CALL( SCIPaddConflictBinvar(scip, vars[0][0]) );
1062 }
1063
1064 /* add bounds that result in the last one - pass through rows */
1065 for (k = 1; k < i; ++k)
1066 {
1067 int l;
1068 l = lastones[k] + 1;
1069
1070 /* if the frontier has not moved and we are not beyond the matrix boundaries */
1071 if ( l <= ncols-1 && l <= k && lastones[k-1] == lastones[k] )
1072 {
1073 assert( SCIPvarGetUbLocal(vars[k][l]) < 0.5 );
1074 SCIP_CALL( SCIPaddConflictBinvar(scip, vars[k][l]) );
1075 }
1076 }
1077 SCIP_CALL( SCIPanalyzeConflictCons(scip, cons, NULL) );
1078 }
1079
1080 goto TERMINATE;
1081 }
1082 if ( tightened )
1083 ++(*nfixedvars);
1084 }
1085 }
1086
1087 lastoneprevrow = lastoneinrow;
1088 }
1089
1090 /* check whether fixing any entry to 0 results in a contradiction -> loop through rows in frontiersteps (a.k.a. gamma) */
1091 for (j = 0; j < nsteps; ++j)
1092 {
1093 int s;
1094 int lastoneinrow;
1095
1096 s = frontiersteps[j];
1097 lastoneinrow = lastones[s];
1098 /* note for packing case: if we are in a frontier step then lastoneinrow >= 0 */
1099 assert( 0 <= lastoneinrow && lastoneinrow < ncols );
1100
1101 /* if entry is not fixed */
1102 if ( SCIPvarGetLbLocal(vars[s][lastoneinrow]) < 0.5 && SCIPvarGetUbLocal(vars[s][lastoneinrow]) > 0.5 )
1103 {
1104 int betaprev;
1105 betaprev = lastoneinrow - 1;
1106
1107 /* loop through rows below s */
1108 for (i = s+1; i < nrows; ++i)
1109 {
1110 int beta;
1111
1112 assert( betaprev + 1 >= 0 );
1113 if ( betaprev == ncols-1 || SCIPvarGetUbLocal(vars[i][betaprev+1]) < 0.5 ) /*lint !e679*/
1114 beta = betaprev;
1115 else
1116 beta = betaprev + 1;
1117 assert( -1 <= beta && beta < ncols );
1118
1119 if ( firstnonzeros[i] > beta )
1120 {
1121 SCIP_Bool tightened = FALSE;
1122 int inferInfo;
1123
1124 /* can fix (s,lastoneinrow) (a.k.a (s,alpha)) to 1 (do not need to fix other entries to 0, since they
1125 * will be automatically fixed by SCIPtightenVarLb.)
1126 */
1127 assert( SCIPvarGetLbLocal(vars[s][lastoneinrow]) < 0.5 );
1128 SCIPdebugMsg(scip, " -> Fixing entry (%d,%d) to 1.\n", s, lastoneinrow);
1129
1130 /* store position (i,firstnonzeros[i]) */
1131 inferInfo = ncols * nrows + i * ncols + firstnonzeros[i];
1132 SCIP_CALL( SCIPinferBinvarCons(scip, vars[s][lastoneinrow], TRUE, cons, inferInfo, infeasible, &tightened) );
1133
1134 assert( !(*infeasible) );
1135 if ( tightened )
1136 ++(*nfixedvars);
1137 break;
1138 }
1139 betaprev = beta;
1140 }
1141 }
1142 }
1143
1144 TERMINATE:
1145 SCIPfreeBufferArray(scip, &frontiersteps);
1146 SCIPfreeBufferArray(scip, &lastones);
1147 SCIPfreeBufferArray(scip, &firstnonzeros);
1148
1149 return SCIP_OKAY;
1150}
1151
1152
1153/** Propagation conflict resolving method of propagator
1154 *
1155 * In this function we use that the propagation method above implicitly propagates SCIs, i.e., every
1156 * fixing can also be gotten via an SCI-fixing.
1157 *
1158 * Since the storage of an integer is not enough to store the complete information about the fixing
1159 * nor a complete shifted column, we have to use the linear time algorithm for SCIs.
1160 *
1161 * The inferinfo integer is set as follows:
1162 *
1163 * - If a shifted column is fixed to 0 and the corresponding bar does not necessarily has value 1
1164 * then we fix these entries to 0 and inferinfo is i * ncols + j, where (i,j) is the leader of the
1165 * bar. The SCI depends on whether i is in Gamma or not (see Lemma 1 in the paper and the comments
1166 * above).
1167 *
1168 * - If a bar has value 1 and the shifted column has one entry that is not fixed, it can be fixed to
1169 * 1 and inferinfo is (nrows*ncols) + i * ncols + j, where (i,j) is the leader of the bar; see
1170 * Proposition 1 (2c).
1171 */
1172static
1173SCIP_RETCODE resolvePropagation(
1174 SCIP* scip, /**< SCIP data structure */
1175 SCIP_CONS* cons, /**< constraint that inferred the bound change */
1176 int inferinfo, /**< inference information */
1177 SCIP_BDCHGIDX* bdchgidx, /**< bound change index (time stamp of bound change), or NULL for current time */
1178 SCIP_RESULT* result /**< pointer to store the result of the propagation conflict resolving call */
1179 )
1180{ /*lint --e{715}*/
1181 SCIP_CONSDATA* consdata;
1182 SCIP_Real** vals;
1183 SCIP_Real** weights;
1184 SCIP_VAR*** vars;
1185 SCIP_ORBITOPETYPE orbitopetype;
1186 int** cases;
1187
1188 int i;
1189 int j;
1190 int nrows;
1191 int ncols;
1192
1193 assert( scip != NULL );
1194 assert( cons != NULL );
1195 assert( result != NULL );
1196
1197 consdata = SCIPconsGetData(cons);
1198 assert( consdata != NULL );
1199 assert( consdata->nrows > 0 );
1200 assert( consdata->ncols > 0 );
1201 assert( consdata->vars != NULL );
1202 assert( consdata->vals != NULL );
1203 assert( consdata->weights != NULL );
1204 assert( consdata->cases != NULL );
1205 assert( consdata->istrianglefixed );
1206
1207 *result = SCIP_DIDNOTFIND;
1208 if ( ! consdata->resolveprop )
1209 return SCIP_OKAY;
1210
1211 nrows = consdata->nrows;
1212 ncols = consdata->ncols;
1213 vars = consdata->vars;
1214 vals = consdata->vals;
1215 weights = consdata->weights;
1216 orbitopetype = consdata->orbitopetype;
1217 cases = consdata->cases;
1218
1219 SCIPdebugMsg(scip, "Propagation resolution method of orbitope constraint using orbitopal fixing\n");
1220
1221 /* fill table */
1222 for (i = 0; i < nrows; ++i)
1223 {
1224 int lastcolumn;
1225
1226 /* last column considered as part of the bar: */
1227 lastcolumn = ncols - 1;
1228 if ( lastcolumn > i )
1229 lastcolumn = i;
1230 for (j = 0; j <= lastcolumn; ++j)
1231 {
1232 /* if the variable was fixed to zero at conflict time */
1233 if ( SCIPgetVarUbAtIndex(scip, vars[i][j], bdchgidx, FALSE) < 0.5 )
1234 vals[i][j] = 0.0;
1235 else
1236 {
1237 /* if the variable was fixed to one at conflict time */
1238 if ( SCIPgetVarLbAtIndex(scip, vars[i][j], bdchgidx, FALSE) > 0.5 )
1239 vals[i][j] = 2.0;
1240 else
1241 vals[i][j] = 1.0;
1242 }
1243 }
1244 }
1245
1246#ifdef PRINT_MATRIX
1247 SCIPdebugMsg(scip, "Matrix:\n");
1248 printMatrix(scip, consdata);
1249#endif
1250
1251 /* computation of table: this now minimizes the value of the shifted column */
1252 assert( consdata->istrianglefixed );
1253 computeSCTable(scip, nrows, ncols, weights, cases, vals);
1254
1255 /* if we fixed variables in the bar to zero */
1256 assert( inferinfo >= 0 && inferinfo < 2 * nrows * ncols );
1257 if ( inferinfo < nrows * ncols )
1258 {
1259 int p1;
1260 int p2;
1261#ifdef SCIP_DEBUG
1262 char str[SCIP_MAXSTRLEN];
1263 char tmpstr[SCIP_MAXSTRLEN];
1264#endif
1265
1266 i = (int) (inferinfo / ncols);
1267 j = inferinfo % ncols;
1268 assert( 0 <= i && i < nrows );
1269 assert( 0 <= j && j < ncols );
1270
1271 /* find SCI with value 0 */
1272 assert( weights[i-1][j-1] < 0.5 );
1273
1274 SCIPdebugMsg(scip, " -> reason for x[%d][%d] = ... = x[%d][%d] = 0 was the following SC:\n", i, j, i, MIN(i,ncols));
1275#ifdef SCIP_DEBUG
1276 str[0] = '\0';
1277#endif
1278
1279 p1 = i-1;
1280 p2 = j-1;
1281 do
1282 {
1283 assert( cases[p1][p2] != -1 );
1284 assert( p1 >= 0 && p1 < i );
1285 assert( p2 >= 0 && p2 < j );
1286
1287 /* if case 1 */
1288 if ( cases[p1][p2] == 1 )
1289 --p2; /* decrease column */
1290 else
1291 {
1292 /* case 2 or 3: */
1293 assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
1294 assert( SCIPgetVarUbAtIndex(scip, vars[p1][p2], bdchgidx, FALSE) < 0.5 );
1295 SCIP_CALL( SCIPaddConflictUb(scip, vars[p1][p2], bdchgidx) );
1296 *result = SCIP_SUCCESS;
1297
1298#ifdef SCIP_DEBUG
1299 (void) SCIPsnprintf(tmpstr, SCIP_MAXSTRLEN, " (%d,%d)", p1, p2);
1300 (void) strncat(str, tmpstr, SCIP_MAXSTRLEN-1);
1301#endif
1302
1303 if ( cases[p1][p2] == 3 )
1304 break;
1305 }
1306 --p1; /* decrease row */
1307 }
1308 while ( p1 >= 0 ); /* should always be true, i.e. the break should end the loop */
1309 assert( cases[p1][p2] == 3 );
1310
1311#ifdef SCIP_DEBUG
1312 SCIPdebugMsg(scip, "%s\n", str);
1313#endif
1314 }
1315 else
1316 {
1317 int k;
1318 int p1;
1319 int p2;
1320#ifndef NDEBUG
1321 int pos1;
1322 int pos2;
1323#endif
1324#ifdef SCIP_DEBUG
1325 char str[SCIP_MAXSTRLEN];
1326 char tmpstr[SCIP_MAXSTRLEN];
1327#endif
1328
1329 /* if we fixed a variable in the SC to 1 */
1330 inferinfo -= nrows * ncols;
1331 i = (int) inferinfo / ncols;
1332 j = inferinfo % ncols;
1333 assert( 0 <= i && i < nrows );
1334 assert( 0 <= j && j < ncols );
1335
1336 /* In rare cases it might happen that we fixed a variable to 1, but the node later becomes infeasible by globally
1337 * fixing variables to 0. In this case, it might happen that we find a SC with value 0 instead of 1. We then
1338 * cannot use this SC to repropagate (and do not know how to reconstruct the original reasoning). */
1339 if ( weights[i-1][j-1] > 0.5 && weights[i-1][j-1] < 1.5 )
1340 {
1341 SCIPdebugMsg(scip, " -> reason for x[%d][%d] = 1 was the following SC:\n", i, j);
1342#ifdef SCIP_DEBUG
1343 (void) SCIPsnprintf(str, SCIP_MAXSTRLEN, "SC:");
1344#endif
1345
1346 p1 = i-1;
1347 p2 = j-1;
1348#ifndef NDEBUG
1349 pos1 = -1;
1350 pos2 = -1;
1351#endif
1352 do
1353 {
1354 assert( cases[p1][p2] != -1 );
1355 assert( p1 >= 0 && p1 < i );
1356 assert( p2 >= 0 && p2 < j );
1357
1358 /* if case 1 */
1359 if ( cases[p1][p2] == 1 )
1360 --p2; /* decrease column */
1361 else
1362 {
1363 /* case 2 or 3: reason are formed by variables in SC fixed to 0 */
1364 assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
1365 if ( SCIPgetVarUbAtIndex(scip, vars[p1][p2], bdchgidx, FALSE) < 0.5 )
1366 {
1367 SCIP_CALL( SCIPaddConflictUb(scip, vars[p1][p2], bdchgidx) );
1368 *result = SCIP_SUCCESS;
1369
1370#ifdef SCIP_DEBUG
1371 (void) SCIPsnprintf(tmpstr, SCIP_MAXSTRLEN, " (%d,%d)", p1, p2);
1372 (void) strncat(str, tmpstr, SCIP_MAXSTRLEN-1);
1373#endif
1374 }
1375#ifndef NDEBUG
1376 else
1377 {
1378 assert( SCIPgetVarLbAtIndex(scip, vars[p1][p2], bdchgidx, FALSE) < 0.5 );
1379 assert( pos1 == -1 && pos2 == -1 );
1380 pos1 = p1;
1381 pos2 = p2;
1382 }
1383#endif
1384 if ( cases[p1][p2] == 3 )
1385 break;
1386 }
1387 --p1; /* decrease row */
1388 }
1389 while ( p1 >= 0 ); /* should always be true, i.e., the break should end the loop */
1390 assert( cases[p1][p2] == 3 );
1391 assert( pos1 >= 0 && pos2 >= 0 );
1392
1393 /* distinguish partitioning/packing */
1394 if ( orbitopetype == SCIP_ORBITOPETYPE_PARTITIONING )
1395 {
1396 /* partitioning case */
1397#ifdef SCIP_DEBUG
1398 (void) SCIPsnprintf(tmpstr, SCIP_MAXSTRLEN, " before bar: ");
1399 (void) strncat(str, tmpstr, SCIP_MAXSTRLEN-1);
1400#endif
1401 /* add variables before the bar in the partitioning case */
1402 for (k = 0; k < j; ++k)
1403 {
1404 assert( SCIPgetVarUbAtIndex(scip, vars[i][k], bdchgidx, FALSE) < 0.5 );
1405 SCIP_CALL( SCIPaddConflictUb(scip, vars[i][k], bdchgidx) );
1406 *result = SCIP_SUCCESS;
1407#ifdef SCIP_DEBUG
1408 (void) SCIPsnprintf(tmpstr, SCIP_MAXSTRLEN, " (%d,%d)", i, k);
1409 (void) strncat(str, tmpstr, SCIP_MAXSTRLEN-1);
1410#endif
1411 }
1412
1413#ifdef SCIP_DEBUG
1414 SCIPdebugMsg(scip, "%s\n", str);
1415#endif
1416 }
1417 else
1418 {
1419 /* packing case */
1420 int lastcolumn;
1421
1422 /* last column considered as part of the bar: */
1423 lastcolumn = ncols - 1;
1424 if ( lastcolumn > i )
1425 lastcolumn = i;
1426
1427 /* search for variable in the bar that is fixed to 1 in the packing case */
1428 for (k = j; k <= lastcolumn; ++k)
1429 {
1430 if ( SCIPgetVarLbAtIndex(scip, vars[i][k], bdchgidx, FALSE) > 0.5 )
1431 {
1432 SCIP_CALL( SCIPaddConflictLb(scip, vars[i][k], bdchgidx) );
1433 *result = SCIP_SUCCESS;
1434 SCIPdebugMsg(scip, " and variable x[%d][%d] fixed to 1.\n", i, k);
1435 break;
1436 }
1437 }
1438 }
1439 }
1440 }
1441
1442 return SCIP_OKAY;
1443}
1444
1445
1446/** check packing/partitioning orbitope solution for feasibility */
1447static
1448SCIP_RETCODE enfopsPackingPartitioningOrbitopeSolution(
1449 SCIP* scip, /**< SCIP data structure */
1450 SCIP_CONS* cons, /**< pointer to orbitope constraint */
1451 SCIP_RESULT* result /**< pointer to store the result of the enforcing call */
1452 )
1453{
1454 SCIP_CONSDATA* consdata;
1455 SCIP_Real** weights;
1456 SCIP_Real** vals;
1457 int** cases;
1458 int nrows;
1459 int ncols;
1460 int i;
1461 int j;
1462
1463 assert( scip != NULL );
1464 assert( cons != NULL );
1465 consdata = SCIPconsGetData(cons);
1466 assert( consdata != NULL );
1467
1468 /* do not enforce non-model constraints if strong dual reductions are not permitted */
1469 if ( !consdata->ismodelcons && !SCIPallowStrongDualReds(scip) )
1470 return SCIP_OKAY;
1471
1472 assert( consdata->nrows > 0 );
1473 assert( consdata->ncols > 0 );
1474 assert( consdata->vals != NULL );
1475 assert( consdata->weights != NULL );
1476 assert( consdata->cases != NULL );
1477
1478 /* check for upper right triangle */
1479 if ( ! consdata->istrianglefixed )
1480 {
1481 SCIP_Bool infeasible = FALSE;
1482 int nfixedvars = 0;
1483
1484 SCIP_CALL( fixTriangle(scip, cons, &infeasible, &nfixedvars) );
1485 if ( infeasible )
1486 {
1487 *result = SCIP_CUTOFF;
1488 return SCIP_OKAY;
1489 }
1490 if ( nfixedvars > 0 )
1491 {
1492 *result = SCIP_REDUCEDDOM;
1493 return SCIP_OKAY;
1494 }
1495 }
1496
1497 nrows = consdata->nrows;
1498 ncols = consdata->ncols;
1499 vals = consdata->vals;
1500 weights = consdata->weights;
1501 cases = consdata->cases;
1502
1503 /* get solution */
1504 copyValues(scip, consdata, NULL);
1505 SCIPdebugMsg(scip, "Enforcing (pseudo solutions) for orbitope constraint <%s>\n", SCIPconsGetName(cons));
1506
1507 /* compute table */
1508 assert( consdata->istrianglefixed );
1509 computeSCTable(scip, nrows, ncols, weights, cases, vals);
1510
1511 /* loop through rows */
1512 for (i = 1; i < nrows; ++i)
1513 {
1514 SCIP_Real bar = 0.0;
1515 int lastcolumn;
1516
1517 lastcolumn = ncols - 1;
1518
1519 /* last column considered as part of the bar: */
1520 if ( lastcolumn > i )
1521 lastcolumn = i;
1522
1523 /* traverse row from right to left */
1524 for (j = lastcolumn; j > 0; --j)
1525 {
1526 bar += vals[i][j];
1527 assert( SCIPisIntegral(scip, vals[i][j]) );
1528
1529 /* check whether weights[i-1][j-1] < bar (<=> bar - weights[i-1][j-1] > 0), i.e. cut is violated) */
1530 if ( SCIPisGT(scip, bar - weights[i-1][j-1], 0.0) )
1531 {
1532 SCIPdebugMsg(scip, "Solution is infeasible.\n");
1533 *result = SCIP_INFEASIBLE;
1534 return SCIP_OKAY;
1535 }
1536 }
1537 }
1538
1539 return SCIP_OKAY;
1540}
1541
1542
1543/** check packing/partitioning orbitope solution for feasibility */
1544static
1545SCIP_RETCODE checkPackingPartitioningOrbitopeSolution(
1546 SCIP* scip, /**< SCIP data structure */
1547 SCIP_CONS* cons, /**< pointer to orbitope constraint */
1548 SCIP_SOL* sol, /**< solution to be checked */
1549 SCIP_RESULT* result, /**< pointer to store the result of the enforcing call */
1550 SCIP_Bool printreason /**< whether reason for infeasibility should be printed */
1551 )
1552{
1553 SCIP_CONSDATA* consdata;
1554 SCIP_VAR*** vars;
1555 SCIP_Real** vals;
1556 SCIP_Real** weights;
1557 int** cases;
1558 int nrows;
1559 int ncols;
1560 int i;
1561 int j;
1562
1563 /* get data of constraint */
1564 assert( cons != 0 );
1565 consdata = SCIPconsGetData(cons);
1566 assert( consdata != NULL );
1567 assert( consdata->nrows > 0 );
1568 assert( consdata->ncols > 0 );
1569 assert( consdata->vars != NULL );
1570 assert( consdata->vals != NULL );
1571 assert( consdata->weights != NULL );
1572 assert( consdata->cases != NULL );
1573
1574 nrows = consdata->nrows;
1575 ncols = consdata->ncols;
1576 vars = consdata->vars;
1577 vals = consdata->vals;
1578 weights = consdata->weights;
1579 cases = consdata->cases;
1580
1581 /* get solution */
1582 copyValues(scip, consdata, sol);
1583 SCIPdebugMsg(scip, "Checking orbitope constraint <%s> ...\n", SCIPconsGetName(cons));
1584
1585 /* check upper right triangle (if not yet fixed to zero or in debug mode */
1586#ifdef NDEBUG
1587 if ( ! consdata->istrianglefixed )
1588#endif
1589 {
1590 int diagsize;
1591
1592 /* get last row of triangle */
1593 diagsize = ncols;
1594 if ( nrows < ncols )
1595 diagsize = nrows;
1596
1597 /* check variables */
1598 for (i = 0; i < diagsize; ++i)
1599 {
1600 for (j = i+1; j < ncols; ++j)
1601 {
1602 if ( ! SCIPisFeasZero(scip, vals[i][j]) )
1603 {
1604 if ( printreason )
1605 SCIPinfoMessage(scip, NULL, "variable x[%d][%d] = %f on upper right nonzero.\n", i, j, vals[i][j]);
1606 *result = SCIP_INFEASIBLE;
1607
1608 return SCIP_OKAY;
1609 }
1610 }
1611 }
1612 }
1613
1614 /* compute table */
1615 computeSCTable(scip, nrows, ncols, weights, cases, vals);
1616
1617 /* loop through rows */
1618 for (i = 1; i < nrows; ++i)
1619 {
1620 SCIP_Real bar;
1621 int lastcolumn;
1622
1623 lastcolumn = ncols - 1;
1624 bar = 0.0;
1625 /* last column considered as part of the bar: */
1626 if ( lastcolumn > i )
1627 lastcolumn = i;
1628
1629 /* traverse row from right to left */
1630 for (j = lastcolumn; j > 0; --j)
1631 {
1632 bar += vals[i][j];
1633 assert( SCIPisFeasIntegral(scip, vals[i][j]) );
1634
1635 /* check whether weights[i-1][j-1] < bar (<=> bar - weights[i-1][j-1] > 0), i.e. cut is violated) */
1636 if ( SCIPisGT(scip, bar - weights[i-1][j-1], 0.0) )
1637 {
1638 SCIPdebugMsg(scip, "Solution is infeasible.\n");
1639 *result = SCIP_INFEASIBLE;
1640
1641 if ( printreason )
1642 {
1643 int l;
1644 int p1;
1645 int p2;
1646
1647 SCIPinfoMessage(scip, NULL, "violated SCI: bar(");
1648
1649 /* first output bar */
1650 for (l = j; l < ncols; ++l)
1651 SCIPinfoMessage(scip, NULL, "<%s> (%f)", SCIPvarGetName(vars[i][l]), consdata->vals[i][l]);
1652
1653 SCIPinfoMessage(scip, NULL, ") SC(");
1654
1655 /* output shifted column */
1656 p1 = i-1;
1657 p2 = j-1;
1658 do
1659 {
1660 assert( cases[p1][p2] != -1 );
1661 assert( p1 >= 0 && p1 < i );
1662 assert( p2 >= 0 && p2 < j );
1663
1664 /* if case 1 */
1665 if (cases[p1][p2] == 1)
1666 --p2; /* decrease column */
1667 else
1668 {
1669 /* case 2 or 3: */
1670 assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
1671 SCIPinfoMessage(scip, NULL, "<%s> (%f)", SCIPvarGetName(vars[p1][p2]), consdata->vals[p1][p2]);
1672 if ( cases[p1][p2] == 3 )
1673 break;
1674 }
1675 --p1; /* decrease row */
1676 }
1677 while ( p1 >= 0 ); /* should always be true, i.e. the break should end the loop */
1678 assert( cases[p1][p2] == 3 );
1679
1680 SCIPinfoMessage(scip, NULL, ")");
1681 }
1682
1683 return SCIP_OKAY;
1684 }
1685 }
1686 }
1687
1688 return SCIP_OKAY;
1689}
1690
1691
1692/** separate or enforce constraints */
1693static
1694SCIP_RETCODE separateConstraints(
1695 SCIP* scip, /**< SCIP data structure */
1696 SCIP_CONSHDLR* conshdlr, /**< constraint handler */
1697 SCIP_CONS** conss, /**< constraints to process */
1698 int nconss, /**< number of constraints */
1699 int nusefulconss, /**< number of useful (non-obsolete) constraints to process */
1700 SCIP_SOL* sol, /**< solution to separate (NULL for the LP solution) */
1701 SCIP_RESULT* result, /**< pointer to store the result (should be initialized) */
1702 SCIP_Bool enforce /**< whether we enforce orbitope constraints */
1703 )
1704{
1705 SCIP_Bool infeasible = FALSE;
1706 int nfixedvars = 0;
1707 int ncuts = 0;
1708 int c;
1709
1710 assert( scip != NULL );
1711 assert( conshdlr != NULL );
1712 assert( result != NULL );
1713
1714 SCIP_STRINGEQ( SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
1715
1716 /* loop through constraints */
1717 for (c = 0; c < nconss && ! infeasible; c++)
1718 {
1719 SCIP_CONSDATA* consdata;
1720 int nconsfixedvars = 0;
1721 int nconscuts = 0;
1722
1723 assert( conss[c] != NULL );
1724
1725 /* get data of constraint */
1726 consdata = SCIPconsGetData(conss[c]);
1727 assert( consdata != NULL );
1728
1729 /* skip non-model constraints if strong dual reductions are not permitted */
1730 if ( !consdata->ismodelcons && !SCIPallowStrongDualReds(scip) )
1731 continue;
1732
1733 /* do not enforce non-model constraints */
1734 if ( enforce && !consdata->ismodelcons )
1735 continue;
1736
1737 /* get solution */
1738 copyValues(scip, consdata, sol);
1739
1740 /* separate */
1741 SCIP_CALL( separateSCIs(scip, conshdlr, conss[c], consdata, &infeasible, &nconsfixedvars, &nconscuts) );
1742 nfixedvars += nconsfixedvars;
1743 ncuts += nconscuts;
1744
1745 /* stop after the useful constraints if we found cuts of fixed variables */
1746 if ( c >= nusefulconss && (ncuts > 0 || nfixedvars > 0) )
1747 break;
1748 }
1749
1750 if ( infeasible )
1751 {
1752 SCIPdebugMsg(scip, "Infeasible node.\n");
1753 *result = SCIP_CUTOFF;
1754 }
1755 else if ( nfixedvars > 0 )
1756 {
1757 SCIPdebugMsg(scip, "Fixed %d variables.\n", nfixedvars);
1758 *result = SCIP_REDUCEDDOM;
1759 }
1760 else if ( ncuts > 0 )
1761 {
1762 SCIPdebugMsg(scip, "Separated %dinequalities.\n", ncuts);
1763 *result = SCIP_SEPARATED;
1764 }
1765 else
1766 {
1767 SCIPdebugMsg(scip, "No violated inequality found during separation.\n");
1768 }
1769
1770 return SCIP_OKAY;
1771}
1772
1773
1774/** check whether all variables in an orbitope constraint are fixed */
1775static
1776SCIP_RETCODE checkRedundantCons(
1777 SCIP* scip, /**< SCIP data structure */
1778 SCIP_CONS* cons, /**< constraint to be processed */
1779 SCIP_Bool* redundant /**< pointer to store whether constraint is redundant (contains no active vars) */
1780 )
1781{
1782 SCIP_CONSDATA* consdata;
1783 SCIP_VAR*** vars;
1784 int i;
1785 int j;
1786 int nrows;
1787 int ncols;
1788
1789 assert( scip != NULL );
1790 assert( cons != NULL );
1791 assert( redundant != NULL );
1792
1793 *redundant = FALSE;
1794
1795 consdata = SCIPconsGetData(cons);
1796 assert( consdata != NULL );
1797 assert( consdata->vars != NULL );
1798 assert( consdata->nrows > 0 );
1799 assert( consdata->ncols > 0 );
1800
1801 vars = consdata->vars;
1802 nrows = consdata->nrows;
1803 ncols = consdata->ncols;
1804
1805 /* check whether there exists an active variable in the orbitope */
1806 for (i = 0; i < nrows; ++i)
1807 {
1808 for (j = 0; j < ncols; ++j)
1809 {
1810 if ( SCIPvarIsActive(vars[i][j]) )
1811 return SCIP_OKAY;
1812 }
1813 }
1814 *redundant = TRUE;
1815
1816 return SCIP_OKAY;
1817}
1818
1819/** replace aggregated variables by active variables */
1820static
1821SCIP_RETCODE replaceAggregatedVarsOrbitopePP(
1822 SCIP* scip, /**< SCIP data structure */
1823 SCIP_CONS* cons /**< constraint to be processed */
1824 )
1825{
1826 SCIP_CONSDATA* consdata;
1827 SCIP_VAR*** vars;
1828 int i;
1829 int j;
1830 int nrows;
1831 int ncols;
1832
1833 assert( scip != NULL );
1834 assert( cons != NULL );
1835
1836 consdata = SCIPconsGetData(cons);
1837 assert( consdata != NULL );
1838 assert( consdata->vars != NULL );
1839 assert( consdata->nrows > 0 );
1840 assert( consdata->ncols > 0 );
1841
1842 vars = consdata->vars;
1843 nrows = consdata->nrows;
1844 ncols = consdata->ncols;
1845
1846 /* check whether there exists an aggregated variable in the orbitope */
1847 for (i = 0; i < nrows; ++i)
1848 {
1849 for (j = 0; j < ncols; ++j)
1850 {
1851 SCIP_VAR* var;
1852 SCIP_Bool negated;
1853
1854 assert( SCIPvarGetStatus(vars[i][j]) != SCIP_VARSTATUS_MULTAGGR ); /* variables are marked as not to be multi-aggregated */
1855
1856 SCIP_CALL( SCIPgetBinvarRepresentative(scip, vars[i][j], &var, &negated) );
1857 SCIP_UNUSED( negated );
1858 assert( SCIPvarIsActive(var) || SCIPvarGetStatus(var) == SCIP_VARSTATUS_NEGATED || SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED );
1859 if ( var != vars[i][j] )
1860 {
1861 SCIP_CALL( SCIPunlockVarCons(scip, vars[i][j], cons, TRUE, TRUE) );
1862 SCIP_CALL( SCIPreleaseVar(scip, &vars[i][j]) );
1863 vars[i][j] = var;
1864 SCIP_CALL( SCIPlockVarCons(scip, vars[i][j], cons, TRUE, TRUE) );
1865 SCIP_CALL( SCIPcaptureVar(scip, var) );
1866 }
1867 }
1868 }
1869
1870 return SCIP_OKAY;
1871}
1872
1873
1874/*
1875 * Callback methods of constraint handler
1876 */
1877
1878/** copy method for constraint handler plugins (called when SCIP copies plugins) */
1879static
1880SCIP_DECL_CONSHDLRCOPY(conshdlrCopyOrbitopePP)
1881{ /*lint --e{715}*/
1882 assert(scip != NULL);
1883 assert(conshdlr != NULL);
1884 assert(valid != NULL);
1885
1886 SCIP_STRINGEQ( SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
1887
1888 /* call inclusion method of constraint handler */
1889 SCIP_CALL( SCIPincludeConshdlrOrbitopePP(scip) );
1890
1891 *valid = TRUE;
1892
1893 return SCIP_OKAY;
1894}
1895
1896/** frees constraint handler */
1897static
1898SCIP_DECL_CONSFREE(consFreeOrbitopePP)
1899{ /*lint --e{715}*/
1900 SCIP_CONSHDLRDATA* conshdlrdata;
1901
1902 assert( scip != 0 );
1903 assert( conshdlr != 0 );
1904
1905 SCIP_STRINGEQ( SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
1906
1907 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1908 assert( conshdlrdata != NULL );
1909
1910 SCIPfreeBlockMemory(scip, &conshdlrdata);
1911
1912 return SCIP_OKAY;
1913}
1914
1915/** frees specific constraint data */
1916static
1917SCIP_DECL_CONSDELETE(consDeleteOrbitopePP)
1918{ /*lint --e{715}*/
1919 assert(conshdlr != NULL);
1920
1921 SCIP_STRINGEQ( SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
1922
1923 SCIP_CALL( consdataFree(scip, consdata) );
1924
1925 return SCIP_OKAY;
1926}
1927
1928/** transforms constraint data into data belonging to the transformed problem */
1929static
1930SCIP_DECL_CONSTRANS(consTransOrbitopePP)
1931{ /*lint --e{715}*/
1932 SCIP_CONSDATA* sourcedata;
1933 SCIP_CONSDATA* targetdata;
1934
1935 assert(conshdlr != NULL);
1936 assert(SCIPgetStage(scip) == SCIP_STAGE_TRANSFORMING);
1937 assert(sourcecons != NULL);
1938 assert(targetcons != NULL);
1939
1940 SCIP_STRINGEQ( SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
1941
1942 sourcedata = SCIPconsGetData(sourcecons);
1943 assert(sourcedata != NULL);
1944
1945 /* create linear constraint data for target constraint */
1946 SCIP_CALL( consdataCreate(scip, &targetdata, sourcedata->vars, sourcedata->nrows, sourcedata->ncols,
1947 sourcedata->orbitopetype, sourcedata->resolveprop, sourcedata->ismodelcons) );
1948
1949 /* create target constraint */
1950 SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
1951 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
1952 SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),
1953 SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons),
1954 SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
1955
1956 return SCIP_OKAY;
1957}
1958
1959/** separation method of constraint handler for LP solutions */
1960static
1961SCIP_DECL_CONSSEPALP(consSepalpOrbitopePP)
1962{ /*lint --e{715}*/
1963 assert( scip != NULL );
1964 assert( result != NULL );
1965
1966 SCIPdebugMsg(scip, "Separation of packing/partitioning orbitope constraint handler <%s> for LP solution.\n",
1967 SCIPconshdlrGetName(conshdlr));
1968
1969 *result = SCIP_DIDNOTRUN;
1970
1971 /* if solution is integer, skip separation */
1972 if ( SCIPgetNLPBranchCands(scip) <= 0 )
1973 return SCIP_OKAY;
1974
1975 *result = SCIP_DIDNOTFIND;
1976
1977 /* separate constraints */
1978 SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, NULL, result, FALSE) );
1979
1980 return SCIP_OKAY;
1981}
1982
1983/** separation method of constraint handler for arbitrary primal solutions */
1984static
1985SCIP_DECL_CONSSEPASOL(consSepasolOrbitopePP)
1986{ /*lint --e{715}*/
1987 assert( scip != NULL );
1988 assert( result != NULL );
1989
1990 SCIPdebugMsg(scip, "Separation of packing/partitioning orbitope constraint handler <%s> for primal solution.\n",
1991 SCIPconshdlrGetName(conshdlr));
1992
1993 *result = SCIP_DIDNOTFIND;
1994
1995 /* separate constraints */
1996 SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, sol, result, FALSE) );
1997
1998 return SCIP_OKAY;
1999}
2000
2001
2002/** constraint enforcing method of constraint handler for LP solutions */
2003static
2004SCIP_DECL_CONSENFOLP(consEnfolpOrbitopePP)
2005{ /*lint --e{715}*/
2006 assert( scip != NULL );
2007 assert( result != NULL );
2008
2009 /* we have a negative priority, so we should come after the integrality conshdlr */
2010 assert( SCIPgetNLPBranchCands(scip) == 0 );
2011
2012 SCIPdebugMsg(scip, "Enforcement for packing/partitioning orbitope constraint handler <%s> for LP solution.\n",
2013 SCIPconshdlrGetName(conshdlr));
2014
2015 *result = SCIP_FEASIBLE;
2016
2017 /* separate constraints */
2018 SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, NULL, result, TRUE) );
2019
2020 return SCIP_OKAY;
2021}
2022
2023
2024/** constraint enforcing method of constraint handler for relaxation solutions */
2025static
2026SCIP_DECL_CONSENFORELAX(consEnforelaxOrbitopePP)
2027{ /*lint --e{715}*/
2028 assert( result != NULL );
2029 assert( scip != NULL );
2030
2031 SCIPdebugMsg(scip,
2032 "Enforcement for packing/partitioning orbitope constraint handler <%s> for relaxation solution.\n",
2033 SCIPconshdlrGetName(conshdlr));
2034
2035 *result = SCIP_FEASIBLE;
2036
2037 /* separate constraints */
2038 SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, sol, result, TRUE) );
2039
2040 return SCIP_OKAY;
2041}
2042
2043
2044/** constraint enforcing method of constraint handler for pseudo solutions */
2045static
2046SCIP_DECL_CONSENFOPS(consEnfopsOrbitopePP)
2047{ /*lint --e{715}*/
2048 int c;
2049
2050 assert( scip != NULL );
2051 assert( conshdlr != NULL );
2052 assert( result != NULL );
2053
2054 SCIP_STRINGEQ( SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
2055
2056 *result = SCIP_FEASIBLE;
2057 if ( objinfeasible || solinfeasible )
2058 return SCIP_OKAY;
2059
2060 /* loop through constraints */
2061 for (c = 0; c < nconss; ++c)
2062 {
2063 SCIP_CONS* cons;
2064 SCIP_CONSDATA* consdata;
2065
2066 /* get data of constraint */
2067 cons = conss[c];
2068 assert( cons != 0 );
2069 consdata = SCIPconsGetData(cons);
2070
2071 assert( consdata != NULL );
2072
2073 /* do not enforce non-model constraints */
2074 if ( ! consdata->ismodelcons )
2075 continue;
2076
2077 SCIP_CALL( enfopsPackingPartitioningOrbitopeSolution(scip, cons, result) );
2078
2079 if ( *result == SCIP_INFEASIBLE )
2080 break;
2081 }
2082
2083 return SCIP_OKAY;
2084}
2085
2086
2087/** feasibility check method of constraint handler for integral solutions */
2088static
2089SCIP_DECL_CONSCHECK(consCheckOrbitopePP)
2090{ /*lint --e{715}*/
2091 int c;
2092 SCIP_CONSDATA* consdata;
2093
2094 assert( scip != NULL );
2095 assert( conshdlr != NULL );
2096 assert( result != NULL );
2097
2098 SCIP_STRINGEQ( SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
2099
2100 *result = SCIP_FEASIBLE;
2101
2102 /* loop through constraints */
2103 for( c = 0; c < nconss && (*result == SCIP_FEASIBLE || completely); ++c )
2104 {
2105 assert( conss[c] != 0 );
2106 consdata = SCIPconsGetData(conss[c]);
2107
2108 assert( consdata != NULL );
2109
2110 /* do not check non-model constraints */
2111 if ( !consdata->ismodelcons )
2112 continue;
2113
2114 SCIP_CALL( checkPackingPartitioningOrbitopeSolution(scip, conss[c], sol, result, printreason) );
2115 }
2116
2117 if( *result == SCIP_FEASIBLE )
2118 {
2119 SCIPdebugMsg(scip, "Solution is feasible.\n");
2120 }
2121 else
2122 {
2123 SCIPdebugMsg(scip, "Solution is infeasible.\n");
2124 }
2125
2126 return SCIP_OKAY;
2127}
2128
2129
2130/** domain propagation method of constraint handler */
2131static
2132SCIP_DECL_CONSPROP(consPropOrbitopePP)
2133{ /*lint --e{715}*/
2134 SCIP_Bool infeasible = FALSE;
2135 int nfixedvars = 0;
2136 int c;
2137
2138 assert( scip != NULL );
2139 assert( conshdlr != NULL );
2140 assert( result != NULL );
2141
2142 SCIP_STRINGEQ( SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
2143
2144 *result = SCIP_DIDNOTRUN;
2145
2146 /* propagate all useful constraints */
2147 for (c = 0; c < nusefulconss && !infeasible; ++c)
2148 {
2149 int nfixed;
2150
2151 assert( conss[c] != 0 );
2152
2153 SCIPdebugMsg(scip, "Propagation of packing/partitioning orbitope constraint <%s> ...\n",
2154 SCIPconsGetName(conss[c]));
2155
2156 SCIP_CALL( propagateCons(scip, conss[c], &infeasible, &nfixed) );
2157 nfixedvars += nfixed;
2158 }
2159
2160 /* return the correct result */
2161 if ( infeasible )
2162 {
2163 *result = SCIP_CUTOFF;
2164 SCIPdebugMsg(scip, "Propagation via orbitopal fixing proved node to be infeasible.\n");
2165 }
2166 else if ( nfixedvars > 0 )
2167 {
2168 *result = SCIP_REDUCEDDOM;
2169 SCIPdebugMsg(scip, "Propagated %d variables via orbitopal fixing.\n", nfixedvars);
2170 }
2171 else if ( nusefulconss > 0 )
2172 {
2173 *result = SCIP_DIDNOTFIND;
2174 SCIPdebugMsg(scip, "Propagation via orbitopal fixing did not find anything.\n");
2175 }
2176
2177 return SCIP_OKAY;
2178}
2179
2180
2181/** presolving method of constraint handler */
2182static
2183SCIP_DECL_CONSPRESOL(consPresolOrbitopePP)
2184{ /*lint --e{715}*/
2185 SCIP_Bool infeasible = FALSE;
2186 int noldfixedvars;
2187 int c;
2188 SCIP_Bool redundant;
2189
2190 assert( scip != NULL );
2191 assert( conshdlr != NULL );
2192 assert( result != NULL );
2193
2194 SCIP_STRINGEQ( SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
2195
2196 *result = SCIP_DIDNOTRUN;
2197 noldfixedvars = *nfixedvars;
2198
2199 /* propagate all useful constraints
2200 *
2201 * @todo use an event handler to only propagate if a variable in the orbitope has been fixed
2202 */
2203 for (c = 0; c < nconss && !infeasible; ++c)
2204 {
2205 int nfixed = 0;
2206
2207 assert( conss[c] != 0 );
2208
2209 SCIPdebugMsg(scip, "Presolving of packing/partitioning orbitope constraint <%s> ...\n",
2210 SCIPconsGetName(conss[c]));
2211
2212 /* first propagate */
2213 SCIP_CALL( propagateCons(scip, conss[c], &infeasible, &nfixed) );
2214 *nfixedvars += nfixed;
2215
2216 if ( ! infeasible )
2217 {
2218 SCIP_CALL( checkRedundantCons(scip, conss[c], &redundant) );
2219
2220 if ( redundant )
2221 {
2222 SCIPdebugMsg(scip,
2223 "Packing/Partitioning orbitope constraint <%s> is redundant: it does not contain active variables\n",
2224 SCIPconsGetName(conss[c]));
2225 SCIP_CALL( SCIPdelCons(scip, conss[c]) );
2226 assert( ! SCIPconsIsActive(conss[c]) );
2227 (*ndelconss)++;
2228 continue;
2229 }
2230 }
2231 }
2232
2233 if ( infeasible )
2234 {
2235 *result = SCIP_CUTOFF;
2236 SCIPdebugMsg(scip, "Presolving detected infeasibility.\n");
2237 }
2238 else if ( *nfixedvars > noldfixedvars )
2239 {
2240 *result = SCIP_SUCCESS;
2241 }
2242 else if ( nconss > 0 )
2243 {
2244 *result = SCIP_DIDNOTFIND;
2245 SCIPdebugMsg(scip, "Presolving via orbitopal fixing did not find anything.\n");
2246 }
2247
2248 return SCIP_OKAY;
2249}
2250
2251
2252/** propagation conflict resolving method of constraint handler */
2253static
2254SCIP_DECL_CONSRESPROP(consRespropOrbitopePP)
2255{ /*lint --e{715}*/
2256 assert( scip != NULL );
2257 assert( cons != NULL );
2258 assert( infervar != NULL );
2259 assert( bdchgidx != NULL );
2260 assert( result != NULL );
2261
2262 SCIP_CALL( resolvePropagation(scip, cons, inferinfo, bdchgidx, result) );
2263
2264 return SCIP_OKAY;
2265}
2266
2267
2268/** presolving deinitialization method of constraint handler (called after presolving has been finished) */
2269static
2270SCIP_DECL_CONSEXITPRE(consExitpreOrbitopePP)
2271{
2272 int c;
2273
2274 assert( scip != NULL );
2275 assert( conshdlr != NULL );
2276
2277 SCIP_STRINGEQ( SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
2278
2279 for (c = 0; c < nconss; ++c)
2280 {
2281 /* replace aggregated variables by active variables */
2282 SCIP_CALL( replaceAggregatedVarsOrbitopePP(scip, conss[c]) );
2283 }
2284 return SCIP_OKAY;
2285}
2286
2287
2288/** variable rounding lock method of constraint handler */
2289static
2290SCIP_DECL_CONSLOCK(consLockOrbitopePP)
2291{ /*lint --e{715}*/
2292 SCIP_CONSDATA* consdata;
2293 SCIP_VAR*** vars;
2294 int i;
2295 int j;
2296 int nrows;
2297 int ncols;
2298
2299 assert( scip != NULL );
2300 assert( conshdlr != NULL );
2301 assert( cons != NULL );
2302 assert( locktype == SCIP_LOCKTYPE_MODEL );
2303
2304 SCIP_STRINGEQ( SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
2305
2306 consdata = SCIPconsGetData(cons);
2307 assert( consdata != NULL );
2308 assert( consdata->nrows > 0 );
2309 assert( consdata->ncols > 0 );
2310 assert( consdata->vars != NULL );
2311
2312 SCIPdebugMsg(scip, "Locking method for packing/partitioning orbitope constraint handler\n");
2313
2314 nrows = consdata->nrows;
2315 ncols = consdata->ncols;
2316 vars = consdata->vars;
2317
2318 /* add up locks and down locks on each variable */
2319 for (i = 0; i < nrows; ++i)
2320 {
2321 for (j = 0; j < ncols; ++j)
2322 SCIP_CALL( SCIPaddVarLocksType(scip, vars[i][j], locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) );
2323 }
2324
2325 return SCIP_OKAY;
2326}
2327
2328
2329/** constraint display method of constraint handler */
2330static
2331SCIP_DECL_CONSPRINT(consPrintOrbitopePP)
2332{
2333 SCIP_CONSDATA* consdata;
2334 SCIP_VAR*** vars;
2335 int i;
2336 int j;
2337 int nrows;
2338 int ncols;
2339 SCIP_ORBITOPETYPE orbitopetype;
2340
2341 assert( scip != NULL );
2342 assert( conshdlr != NULL );
2343 assert( cons != NULL );
2344
2345 SCIP_STRINGEQ( SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
2346
2347 consdata = SCIPconsGetData(cons);
2348 assert( consdata != NULL );
2349 assert( consdata->nrows > 0 );
2350 assert( consdata->ncols > 0 );
2351 assert( consdata->vars != NULL );
2352
2353 nrows = consdata->nrows;
2354 ncols = consdata->ncols;
2355 vars = consdata->vars;
2356 orbitopetype = consdata->orbitopetype;
2357
2358 SCIPdebugMsg(scip, "Printing method for packing/partitioning orbitope constraint handler\n");
2359
2360 switch ( orbitopetype )
2361 {
2362 case SCIP_ORBITOPETYPE_PARTITIONING:
2363 SCIPinfoMessage(scip, file, "partOrbitope(");
2364 break;
2365 case SCIP_ORBITOPETYPE_PACKING:
2366 SCIPinfoMessage(scip, file, "packOrbitope(");
2367 break;
2368 default:
2369 SCIPABORT();
2370 } /*lint !e788*/
2371
2372 for (i = 0; i < nrows; ++i)
2373 {
2374 for (j = 0; j < ncols; ++j)
2375 {
2376 if ( j > 0 )
2377 SCIPinfoMessage(scip, file, ",");
2378 SCIP_CALL( SCIPwriteVarName(scip, file, vars[i][j], TRUE) );
2379 }
2380 if ( i < nrows-1 )
2381 SCIPinfoMessage(scip, file, ".");
2382 }
2383 SCIPinfoMessage(scip, file, ")");
2384
2385 return SCIP_OKAY;
2386}
2387
2388
2389/** constraint copying method of constraint handler */
2390static
2391SCIP_DECL_CONSCOPY(consCopyOrbitopePP)
2392{
2393 SCIP_CONSHDLRDATA* conshdlrdata;
2394 SCIP_CONSDATA* sourcedata;
2395 SCIP_VAR*** sourcevars;
2396 SCIP_VAR*** vars;
2397 int nrows;
2398 int ncols;
2399 int i;
2400 int k;
2401 int j;
2402
2403 assert( scip != NULL );
2404 assert( cons != NULL );
2405 assert( sourcescip != NULL );
2406 assert( sourceconshdlr != NULL );
2407 assert( sourcecons != NULL );
2408 assert( varmap != NULL );
2409 assert( valid != NULL );
2410
2411 SCIP_STRINGEQ( SCIPconshdlrGetName(sourceconshdlr), CONSHDLR_NAME, SCIP_INVALIDCALL );
2412
2413 *valid = TRUE;
2414
2415 SCIPdebugMsg(scip, "Copying method for packing/partOrbitope orbitope constraint handler.\n");
2416
2417 sourcedata = SCIPconsGetData(sourcecons);
2418 assert( sourcedata != NULL );
2419 assert( sourcedata->nrows > 0 );
2420 assert( sourcedata->ncols > 0 );
2421 assert( sourcedata->vars != NULL );
2422
2423 conshdlrdata = SCIPconshdlrGetData(sourceconshdlr);
2424 assert( conshdlrdata != NULL );
2425
2426 /* do not copy non-model constraints */
2427 if ( !sourcedata->ismodelcons && !conshdlrdata->forceconscopy )
2428 {
2429 *valid = FALSE;
2430
2431 return SCIP_OKAY;
2432 }
2433
2434 nrows = sourcedata->nrows;
2435 ncols = sourcedata->ncols;
2436 sourcevars = sourcedata->vars;
2437
2438 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nrows) );
2439 for (i = 0; i < nrows && *valid; ++i)
2440 {
2441 SCIP_CALL( SCIPallocBufferArray(scip, &(vars[i]), ncols) ); /*lint !e866*/
2442
2443 for (j = 0; j < ncols && *valid; ++j)
2444 {
2445 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[i][j], &(vars[i][j]), varmap, consmap, global, valid) );
2446 assert( !(*valid) || vars[i][j] != NULL );
2447 }
2448 }
2449
2450 /* only create the target constraint, if all variables could be copied */
2451 if ( *valid )
2452 {
2453 /* create copied constraint */
2454 if ( name == NULL )
2455 name = SCIPconsGetName(sourcecons);
2456
2457 SCIP_CALL( SCIPcreateConsOrbitopePP(scip, cons, name, vars,
2458 sourcedata->orbitopetype, nrows, ncols, sourcedata->resolveprop, sourcedata->ismodelcons,
2459 initial, separate, enforce, check, propagate,
2460 local, modifiable, dynamic, removable, stickingatnode) );
2461 }
2462
2463 /* free space; only up to row i if copying failed */
2464 assert( 0 <= i && i <= nrows );
2465 for (k = i - 1; k >= 0; --k)
2466 SCIPfreeBufferArray(scip, &vars[k]);
2467 SCIPfreeBufferArray(scip, &vars);
2468
2469 return SCIP_OKAY;
2470}
2471
2472
2473/** constraint parsing method of constraint handler */
2474static
2475SCIP_DECL_CONSPARSE(consParseOrbitopePP)
2476{ /*lint --e{715}*/
2477 const char* s;
2478 char* endptr;
2479 SCIP_ORBITOPETYPE orbitopetype;
2480 SCIP_VAR*** vars;
2481 SCIP_VAR* var;
2482 int nrows;
2483 int maxnrows;
2484 int ncols;
2485 int maxncols;
2486 int k;
2487 int j;
2488
2489 assert( success != NULL );
2490
2491 *success = TRUE;
2492 s = str;
2493
2494 /* skip white space */
2495 SCIP_CALL( SCIPskipSpace((char**)&s) );
2496
2497 if( strncmp(s, "partOrbitope(", 13) == 0 )
2498 orbitopetype = SCIP_ORBITOPETYPE_PARTITIONING;
2499 else
2500 {
2501 if( strncmp(s, "packOrbitope(", 13) != 0 )
2502 {
2503 SCIPerrorMessage("Syntax error - expected \"partOrbitope\" or \"packOrbitope\": %s\n", s);
2504 *success = FALSE;
2505 return SCIP_OKAY;
2506 }
2507 orbitopetype = SCIP_ORBITOPETYPE_PACKING;
2508 }
2509 s += 13;
2510
2511 /* loop through string */
2512 nrows = 0;
2513 ncols = 0;
2514 maxnrows = 10;
2515 maxncols = 10;
2516
2517 SCIP_CALL( SCIPallocBufferArray(scip, &vars, maxnrows) );
2518
2519 j = 0;
2520 do
2521 {
2522 /* parse variable name */
2523 SCIP_CALL( SCIPparseVarName(scip, s, &var, &endptr) );
2524
2525 if( var == NULL )
2526 {
2527 endptr = strchr(endptr, ')');
2528
2529 if( endptr == NULL || j > 0 )
2530 {
2531 SCIPerrorMessage("not enough variables.\n");
2532 *success = FALSE;
2533 }
2534
2535 break;
2536 }
2537
2538 s = endptr;
2539 assert( s != NULL );
2540
2541 /* skip white space */
2542 SCIP_CALL( SCIPskipSpace((char**)&s) );
2543
2544 /* begin new row if required */
2545 if( j == 0 )
2546 {
2547 ++nrows;
2548
2549 if( nrows > maxnrows )
2550 {
2551 maxnrows = SCIPcalcMemGrowSize(scip, nrows);
2552 SCIP_CALL( SCIPreallocBufferArray(scip, &vars, maxnrows) );
2553 assert( nrows <= maxnrows );
2554 }
2555
2556 SCIP_CALL( SCIPallocBufferArray(scip, &(vars[nrows-1]), nrows == 1 ? maxncols : ncols) ); /*lint !e866*/
2557 }
2558
2559 /* determine number of columns */
2560 if( nrows == 1 )
2561 {
2562 ncols = j + 1;
2563
2564 if( *s == '.' || *s == ')' )
2565 SCIP_CALL( SCIPreallocBufferArray(scip, &(vars[nrows-1]), ncols) ); /*lint !e866*/
2566 else if( ncols > maxncols )
2567 {
2568 maxncols = SCIPcalcMemGrowSize(scip, ncols);
2569 SCIP_CALL( SCIPreallocBufferArray(scip, &(vars[nrows-1]), maxncols) ); /*lint !e866*/
2570 assert( ncols <= maxncols );
2571 }
2572 }
2573 else if( ( j < ncols-1 ) == ( *s == '.' || *s == ')' ) )
2574 {
2575 SCIPerrorMessage("variables per row do not match.\n");
2576 *success = FALSE;
2577 break;
2578 }
2579
2580 vars[nrows-1][j] = var;
2581
2582 if( *s == '.' )
2583 j = 0;
2584 else
2585 ++j;
2586
2587 /* skip ',' or '.' */
2588 if( *s == ',' || *s == '.' )
2589 ++s;
2590 }
2591 while( *s != ')' );
2592
2593 if( *success )
2594 {
2595 SCIP_CALL( SCIPcreateConsOrbitopePP(scip, cons, name, vars, orbitopetype, nrows, ncols, TRUE, TRUE,
2596 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
2597 }
2598
2599 for( k = nrows - 1; k >= 0; --k )
2600 SCIPfreeBufferArray(scip, &vars[k]);
2601 SCIPfreeBufferArray(scip, &vars);
2602
2603 return SCIP_OKAY;
2604}
2605
2606
2607/** constraint method of constraint handler which returns the variables (if possible) */
2608static
2609SCIP_DECL_CONSGETVARS(consGetVarsOrbitopePP)
2610{ /*lint --e{715}*/
2611 SCIP_CONSDATA* consdata;
2612
2613 assert( cons != NULL );
2614 assert( success != NULL );
2615 assert( vars != NULL );
2616
2617 consdata = SCIPconsGetData(cons);
2618 assert( consdata != NULL );
2619
2620 if ( varssize < consdata->ncols * consdata->nrows )
2621 *success = FALSE;
2622 else
2623 {
2624 int cnt = 0;
2625 int i;
2626 int j;
2627
2628 for (i = 0; i < consdata->nrows; ++i)
2629 {
2630 for (j = 0; j < consdata->ncols; ++j)
2631 vars[cnt++] = consdata->vars[i][j];
2632 }
2633 *success = TRUE;
2634 }
2635
2636 return SCIP_OKAY;
2637}
2638
2639
2640/** constraint method of constraint handler which returns the number of variables (if possible) */
2641static
2642SCIP_DECL_CONSGETNVARS(consGetNVarsOrbitopePP)
2643{ /*lint --e{715}*/
2644 SCIP_CONSDATA* consdata;
2645
2646 assert( cons != NULL );
2647
2648 consdata = SCIPconsGetData(cons);
2649 assert( consdata != NULL );
2650
2651 *nvars = consdata->ncols * consdata->nrows;
2652 *success = TRUE;
2653
2654 return SCIP_OKAY;
2655}
2656
2657
2658/*
2659 * constraint specific interface methods
2660 */
2661
2662/** creates the handler for packing/partitioning orbitope constraints and includes it in SCIP */
2663SCIP_RETCODE SCIPincludeConshdlrOrbitopePP(
2664 SCIP* scip /**< SCIP data structure */
2665 )
2666{
2667 SCIP_CONSHDLRDATA* conshdlrdata;
2668 SCIP_CONSHDLR* conshdlr;
2669
2670 /* create orbitope constraint handler data */
2671 SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) );
2672
2673 /* include constraint handler */
2674 SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC,
2675 CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY,
2676 CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS,
2677 consEnfolpOrbitopePP, consEnfopsOrbitopePP, consCheckOrbitopePP, consLockOrbitopePP,
2678 conshdlrdata) );
2679 assert(conshdlr != NULL);
2680
2681 /* set non-fundamental callbacks via specific setter functions */
2682 SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyOrbitopePP, consCopyOrbitopePP) );
2683 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeOrbitopePP) );
2684 SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteOrbitopePP) );
2685 SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsOrbitopePP) );
2686 SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsOrbitopePP) );
2687 SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseOrbitopePP) );
2688 SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolOrbitopePP, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
2689 SCIP_CALL( SCIPsetConshdlrExitpre(scip, conshdlr, consExitpreOrbitopePP) );
2690 SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintOrbitopePP) );
2691 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropOrbitopePP, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
2692 CONSHDLR_PROP_TIMING) );
2693 SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropOrbitopePP) );
2694 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpOrbitopePP, consSepasolOrbitopePP, CONSHDLR_SEPAFREQ,
2695 CONSHDLR_SEPAPRIORITY, CONSHDLR_DELAYSEPA) );
2696 SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransOrbitopePP) );
2697 SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxOrbitopePP) );
2698
2699 SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/forceconscopy",
2700 "Whether orbitope constraints should be forced to be copied to sub SCIPs.",
2701 &conshdlrdata->forceconscopy, TRUE, DEFAULT_FORCECONSCOPY, NULL, NULL) );
2702
2703 return SCIP_OKAY;
2704}
2705
2706
2707/** creates and captures a packing/partitioning orbitope constraint
2708 *
2709 * @pre This constraint handler assumes that constraints which enforce the packing/partitioning constraints are
2710 * contained in the problem. It does not implement, e.g., separation and propagation of set packing/partitioning
2711 * constraints, since this would just copy large parts of the code of the setppc constraint handler.
2712 *
2713 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
2714 */
2715SCIP_RETCODE SCIPcreateConsOrbitopePP(
2716 SCIP* scip, /**< SCIP data structure */
2717 SCIP_CONS** cons, /**< pointer to hold the created constraint */
2718 const char* name, /**< name of constraint */
2719 SCIP_VAR*** vars, /**< matrix of variables on which the symmetry acts */
2720 SCIP_ORBITOPETYPE orbitopetype, /**< type of orbitope constraint */
2721 int nrows, /**< number of rows in orbitope matrix <=> p */
2722 int ncols, /**< number of columns in orbitope matrix <=> q */
2723 SCIP_Bool resolveprop, /**< should propagation be resolved? */
2724 SCIP_Bool ismodelcons, /**< whether the orbitope is a model constraint */
2725 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
2726 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
2727 SCIP_Bool separate, /**< should the constraint be separated during LP processing?
2728 * Usually set to TRUE. */
2729 SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
2730 * TRUE for model constraints, FALSE for additional, redundant constraints. */
2731 SCIP_Bool check, /**< should the constraint be checked for feasibility?
2732 * TRUE for model constraints, FALSE for additional, redundant constraints. */
2733 SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
2734 * Usually set to TRUE. */
2735 SCIP_Bool local, /**< is constraint only valid locally?
2736 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
2737 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
2738 * Usually set to FALSE. In column generation applications, set to TRUE if pricing
2739 * adds coefficients to this constraint. */
2740 SCIP_Bool dynamic, /**< is constraint subject to aging?
2741 * Usually set to FALSE. Set to TRUE for own cuts which
2742 * are separated as constraints. */
2743 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
2744 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
2745 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
2746 * if it may be moved to a more global node?
2747 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
2748 )
2749{
2750 SCIP_CONSHDLR* conshdlr;
2751 SCIP_CONSDATA* consdata;
2752
2753 /* find the orbitope constraint handler */
2754 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2755 if ( conshdlr == NULL )
2756 {
2757 SCIPerrorMessage("packing/partitioning orbitope constraint handler not found\n");
2758 return SCIP_PLUGINNOTFOUND;
2759 }
2760 assert( nrows > 0 );
2761 assert( ncols > 0 );
2762
2763 /* run some checks */
2764#ifndef NDEBUG
2765 {
2766 SCIP_Real obj;
2767 int i;
2768 int j;
2769 for (i = 0; i < nrows; ++i)
2770 {
2771 /* initialize obj to infinity */
2772 obj = SCIPinfinity(scip);
2773 for (j = 0; j < ncols; ++j)
2774 {
2775 SCIP_Bool fixedZero;
2776 SCIP_VAR* var;
2777
2778 var = vars[i][j];
2779 assert(var != NULL);
2780
2781 if ( SCIPvarIsNegated(var) )
2782 var = SCIPvarGetNegatedVar(var);
2783
2784 /* all variables need to be binary */
2785 assert( SCIPvarIsBinary(var) );
2786
2787 /* fixed variables have obj = 0; for variables fixed to 0, we assume that there is no
2788 problem (but we cannot always check it, e.g., when in the original problem
2789 variables were fixed and this problem was copied.) */
2790 fixedZero = ( SCIPisZero(scip, SCIPvarGetLbGlobal(var)) && SCIPisZero(scip, SCIPvarGetUbGlobal(var)) );
2791
2792 /* @todo adapt correctness of the following check for sub-scips */
2793 if ( SCIPgetSubscipDepth(scip) == 0 )
2794 {
2795 /* check whether all variables in a row have the same objective */
2796 if ( ! fixedZero && SCIPisInfinity(scip, obj) )
2797 obj = SCIPvarGetObj(var);
2798 else
2799 {
2800 assert( fixedZero || ! SCIPvarIsActive(var) || SCIPisEQ(scip, obj, SCIPvarGetObj(var)) );
2801 }
2802 }
2803 }
2804 }
2805 }
2806#endif
2807
2808 /* create constraint data */
2809 SCIP_CALL( consdataCreate(scip, &consdata, vars, nrows, ncols, orbitopetype, resolveprop, ismodelcons) );
2810
2811 /* create constraint */
2812 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
2813 local, modifiable, dynamic, removable, stickingatnode) );
2814
2815 return SCIP_OKAY;
2816}
2817
2818/** creates and captures a packing/partitioning orbitope constraint in its most basic variant, i. e., with all
2819 * constraint flags set to their default values, which can be set afterwards using SCIPsetConsFLAGNAME()
2820 *
2821 * @see SCIPcreateConsOrbitopePP() for the default constraint flag configuration
2822 *
2823 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
2824 */
2825SCIP_RETCODE SCIPcreateConsBasicOrbitopePP(
2826 SCIP* scip, /**< SCIP data structure */
2827 SCIP_CONS** cons, /**< pointer to hold the created constraint */
2828 const char* name, /**< name of constraint */
2829 SCIP_VAR*** vars, /**< matrix of variables on which the symmetry acts */
2830 SCIP_ORBITOPETYPE orbitopetype, /**< type of orbitope constraint */
2831 int nrows, /**< number of rows in orbitope matrix <=> p */
2832 int ncols, /**< number of columns in orbitope matrix <=> q */
2833 SCIP_Bool resolveprop, /**< should propagation be resolved? */
2834 SCIP_Bool ismodelcons /**< whether the orbitope is a model constraint */
2835 )
2836{
2837 SCIP_CALL( SCIPcreateConsOrbitopePP(scip, cons, name, vars, orbitopetype, nrows, ncols,
2838 resolveprop, ismodelcons, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
2839
2840 return SCIP_OKAY;
2841}
CONSHDLR_NEEDSCONS
#define CONSHDLR_NEEDSCONS
Definition cons_and.c:96
CONSHDLR_SEPAFREQ
#define CONSHDLR_SEPAFREQ
Definition cons_and.c:89
CONSHDLR_CHECKPRIORITY
#define CONSHDLR_CHECKPRIORITY
Definition cons_and.c:88
CONSHDLR_DESC
#define CONSHDLR_DESC
Definition cons_and.c:85
CONSHDLR_PROP_TIMING
#define CONSHDLR_PROP_TIMING
Definition cons_and.c:99
CONSHDLR_MAXPREROUNDS
#define CONSHDLR_MAXPREROUNDS
Definition cons_and.c:93
CONSHDLR_SEPAPRIORITY
#define CONSHDLR_SEPAPRIORITY
Definition cons_and.c:86
CONSHDLR_PROPFREQ
#define CONSHDLR_PROPFREQ
Definition cons_and.c:90
CONSHDLR_PRESOLTIMING
#define CONSHDLR_PRESOLTIMING
Definition cons_and.c:98
CONSHDLR_EAGERFREQ
#define CONSHDLR_EAGERFREQ
Definition cons_and.c:91
CONSHDLR_ENFOPRIORITY
#define CONSHDLR_ENFOPRIORITY
Definition cons_and.c:87
CONSHDLR_DELAYSEPA
#define CONSHDLR_DELAYSEPA
Definition cons_and.c:94
CONSHDLR_NAME
#define CONSHDLR_NAME
Definition cons_and.c:84
CONSHDLR_DELAYPROP
#define CONSHDLR_DELAYPROP
Definition cons_and.c:95
DEFAULT_FORCECONSCOPY
#define DEFAULT_FORCECONSCOPY
Definition cons_orbisack.c:101
checkRedundantCons
static SCIP_RETCODE checkRedundantCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *redundant)
Definition cons_orbitope_pp.c:1776
replaceAggregatedVarsOrbitopePP
static SCIP_RETCODE replaceAggregatedVarsOrbitopePP(SCIP *scip, SCIP_CONS *cons)
Definition cons_orbitope_pp.c:1821
enfopsPackingPartitioningOrbitopeSolution
static SCIP_RETCODE enfopsPackingPartitioningOrbitopeSolution(SCIP *scip, SCIP_CONS *cons, SCIP_RESULT *result)
Definition cons_orbitope_pp.c:1448
resolvePropagation
static SCIP_RETCODE resolvePropagation(SCIP *scip, SCIP_CONS *cons, int inferinfo, SCIP_BDCHGIDX *bdchgidx, SCIP_RESULT *result)
Definition cons_orbitope_pp.c:1173
separateConstraints
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)
Definition cons_orbitope_pp.c:1694
checkPackingPartitioningOrbitopeSolution
static SCIP_RETCODE checkPackingPartitioningOrbitopeSolution(SCIP *scip, SCIP_CONS *cons, SCIP_SOL *sol, SCIP_RESULT *result, SCIP_Bool printreason)
Definition cons_orbitope_pp.c:1545
separateSCIs
static SCIP_RETCODE separateSCIs(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_Bool *infeasible, int *nfixedvars, int *ncuts)
Definition cons_orbitope_pp.c:634
propagateCons
static SCIP_RETCODE propagateCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible, int *nfixedvars)
Definition cons_orbitope_pp.c:797
computeSCTable
static void computeSCTable(SCIP *scip, int nrows, int ncols, SCIP_Real **weights, int **cases, SCIP_Real **vals)
Definition cons_orbitope_pp.c:455
consdataFree
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata)
Definition cons_orbitope_pp.c:156
fixTriangle
static SCIP_RETCODE fixTriangle(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible, int *nfixedvars)
Definition cons_orbitope_pp.c:550
consdataCreate
static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSDATA **consdata, SCIP_VAR ***vars, int nrows, int ncols, SCIP_ORBITOPETYPE orbitopetype, SCIP_Bool resolveprop, SCIP_Bool ismodelcons)
Definition cons_orbitope_pp.c:202
copyValues
static void copyValues(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_SOL *sol)
Definition cons_orbitope_pp.c:419
cons_orbitope_pp.h
constraint handler for partitioning/packing orbitope constraints w.r.t. the full symmetric group
cons_setppc.h
Constraint handler for the set partitioning / packing / covering constraints .
NULL
#define NULL
Definition def.h:257
SCIP_MAXSTRLEN
#define SCIP_MAXSTRLEN
Definition def.h:278
SCIP_UNUSED
#define SCIP_UNUSED(x)
Definition def.h:418
SCIP_Bool
#define SCIP_Bool
Definition def.h:100
MIN
#define MIN(x, y)
Definition def.h:233
SCIP_STRINGEQ
#define SCIP_STRINGEQ(name, reference, retcode)
Definition def.h:454
SCIP_Real
#define SCIP_Real
Definition def.h:165
TRUE
#define TRUE
Definition def.h:102
FALSE
#define FALSE
Definition def.h:103
SCIPABORT
#define SCIPABORT()
Definition def.h:336
REALABS
#define REALABS(x)
Definition def.h:191
SCIP_CALL
#define SCIP_CALL(x)
Definition def.h:364
SCIPcreateConsOrbitopePP
SCIP_RETCODE SCIPcreateConsOrbitopePP(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR ***vars, SCIP_ORBITOPETYPE orbitopetype, int nrows, int ncols, SCIP_Bool resolveprop, SCIP_Bool ismodelcons, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition cons_orbitope_pp.c:2715
SCIPcreateConsBasicOrbitopePP
SCIP_RETCODE SCIPcreateConsBasicOrbitopePP(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR ***vars, SCIP_ORBITOPETYPE orbitopetype, int nrows, int ncols, SCIP_Bool resolveprop, SCIP_Bool ismodelcons)
Definition cons_orbitope_pp.c:2825
SCIPincludeConshdlrOrbitopePP
SCIP_RETCODE SCIPincludeConshdlrOrbitopePP(SCIP *scip)
Definition cons_orbitope_pp.c:2663
SCIPgetSubscipDepth
int SCIPgetSubscipDepth(SCIP *scip)
Definition scip_copy.c:2589
SCIPgetVarCopy
SCIP_RETCODE SCIPgetVarCopy(SCIP *sourcescip, SCIP *targetscip, SCIP_VAR *sourcevar, SCIP_VAR **targetvar, SCIP_HASHMAP *varmap, SCIP_HASHMAP *consmap, SCIP_Bool global, SCIP_Bool *success)
Definition scip_copy.c:713
SCIPisTransformed
SCIP_Bool SCIPisTransformed(SCIP *scip)
Definition scip_general.c:655
SCIPgetStage
SCIP_STAGE SCIPgetStage(SCIP *scip)
Definition scip_general.c:444
SCIPdelCons
SCIP_RETCODE SCIPdelCons(SCIP *scip, SCIP_CONS *cons)
Definition scip_prob.c:3420
SCIPinfoMessage
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
Definition scip_message.c:208
SCIPdebugMsg
#define SCIPdebugMsg
Definition scip_message.h:78
SCIPaddBoolParam
SCIP_RETCODE SCIPaddBoolParam(SCIP *scip, const char *name, const char *desc, SCIP_Bool *valueptr, SCIP_Bool isadvanced, SCIP_Bool defaultvalue, SCIP_DECL_PARAMCHGD((*paramchgd)), SCIP_PARAMDATA *paramdata)
Definition scip_param.c:57
SCIPgetNLPBranchCands
int SCIPgetNLPBranchCands(SCIP *scip)
Definition scip_branch.c:436
SCIPaddConflictLb
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
Definition scip_conflict.c:365
SCIPinitConflictAnalysis
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
Definition scip_conflict.c:336
SCIPaddConflictUb
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
Definition scip_conflict.c:432
SCIPisConflictAnalysisApplicable
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
Definition scip_conflict.c:314
SCIPaddConflictBinvar
SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var)
Definition scip_conflict.c:569
SCIPanalyzeConflictCons
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
Definition scip_conflict.c:728
SCIPsetConshdlrFree
SCIP_RETCODE SCIPsetConshdlrFree(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:372
SCIPsetConshdlrPresol
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
Definition scip_cons.c:540
SCIPsetConshdlrSepa
SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa)
Definition scip_cons.c:235
SCIPsetConshdlrProp
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)
Definition scip_cons.c:281
SCIPsetConshdlrEnforelax
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:323
SCIPincludeConshdlrBasic
SCIP_RETCODE SCIPincludeConshdlrBasic(SCIP *scip, SCIP_CONSHDLR **conshdlrptr, const char *name, const char *desc, int enfopriority, int chckpriority, int eagerfreq, SCIP_Bool needscons, SCIP_DECL_CONSENFOLP((*consenfolp)), SCIP_DECL_CONSENFOPS((*consenfops)), SCIP_DECL_CONSCHECK((*conscheck)), SCIP_DECL_CONSLOCK((*conslock)), SCIP_CONSHDLRDATA *conshdlrdata)
Definition scip_cons.c:181
SCIPsetConshdlrParse
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:808
SCIPsetConshdlrGetVars
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:831
SCIPsetConshdlrPrint
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:785
SCIPconshdlrGetName
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4320
SCIPsetConshdlrCopy
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)),)
Definition scip_cons.c:347
SCIPfindConshdlr
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
Definition scip_cons.c:940
SCIPsetConshdlrDelete
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:578
SCIPconshdlrGetData
SCIP_CONSHDLRDATA * SCIPconshdlrGetData(SCIP_CONSHDLR *conshdlr)
Definition cons.c:4340
SCIPsetConshdlrTrans
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:601
SCIPsetConshdlrResprop
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:647
SCIPsetConshdlrExitpre
SCIP_RETCODE SCIPsetConshdlrExitpre(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:516
SCIPsetConshdlrGetNVars
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr,)
Definition scip_cons.c:854
SCIPconsGetData
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
Definition cons.c:8423
SCIPconsIsDynamic
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition cons.c:8652
SCIPconsIsInitial
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition cons.c:8562
SCIPconsIsChecked
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition cons.c:8592
SCIPconsIsEnforced
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition cons.c:8582
SCIPconsIsActive
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
Definition cons.c:8454
SCIPcreateCons
SCIP_RETCODE SCIPcreateCons(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_CONSHDLR *conshdlr, SCIP_CONSDATA *consdata, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
Definition scip_cons.c:997
SCIPconsIsPropagated
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
Definition cons.c:8612
SCIPconsIsLocal
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition cons.c:8632
SCIPconsGetName
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition cons.c:8393
SCIPconsIsModifiable
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition cons.c:8642
SCIPconsIsStickingAtNode
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition cons.c:8672
SCIPconsIsSeparated
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition cons.c:8572
SCIPconsIsRemovable
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition cons.c:8662
SCIPisEfficacious
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
Definition scip_cut.c:135
SCIPaddRow
SCIP_RETCODE SCIPaddRow(SCIP *scip, SCIP_ROW *row, SCIP_Bool forcecut, SCIP_Bool *infeasible)
Definition scip_cut.c:225
SCIPcalcMemGrowSize
int SCIPcalcMemGrowSize(SCIP *scip, int num)
Definition scip_mem.c:139
SCIPallocBufferArray
#define SCIPallocBufferArray(scip, ptr, num)
Definition scip_mem.h:124
SCIPreallocBufferArray
#define SCIPreallocBufferArray(scip, ptr, num)
Definition scip_mem.h:128
SCIPfreeBufferArray
#define SCIPfreeBufferArray(scip, ptr)
Definition scip_mem.h:136
SCIPallocBlockMemoryArray
#define SCIPallocBlockMemoryArray(scip, ptr, num)
Definition scip_mem.h:93
SCIPfreeBlockMemory
#define SCIPfreeBlockMemory(scip, ptr)
Definition scip_mem.h:108
SCIPfreeBlockMemoryArrayNull
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
Definition scip_mem.h:111
SCIPallocBlockMemory
#define SCIPallocBlockMemory(scip, ptr)
Definition scip_mem.h:89
SCIPduplicateBlockMemoryArray
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
Definition scip_mem.h:105
SCIPinProbing
SCIP_Bool SCIPinProbing(SCIP *scip)
Definition scip_probing.c:98
SCIPcreateEmptyRowConshdlr
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:1367
SCIPreleaseRow
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
Definition scip_lp.c:1508
SCIPaddVarsToRow
SCIP_RETCODE SCIPaddVarsToRow(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
Definition scip_lp.c:1672
SCIPgetSolVal
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
Definition scip_sol.c:1763
SCIPinfinity
SCIP_Real SCIPinfinity(SCIP *scip)
Definition scip_numerics.c:501
SCIPisIntegral
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
Definition scip_numerics.c:585
SCIPisFeasZero
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
Definition scip_numerics.c:836
SCIPisInfinity
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
Definition scip_numerics.c:512
SCIPisSumEQ
SCIP_Bool SCIPisSumEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition scip_numerics.c:670
SCIPisFeasIntegral
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
Definition scip_numerics.c:872
SCIPisGT
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition scip_numerics.c:475
SCIPisEQ
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition scip_numerics.c:436
SCIPisZero
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
Definition scip_numerics.c:549
SCIPisLT
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
Definition scip_numerics.c:449
SCIPlockVarCons
SCIP_RETCODE SCIPlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition scip_var.c:5210
SCIPvarGetNegatedVar
SCIP_VAR * SCIPvarGetNegatedVar(SCIP_VAR *var)
Definition var.c:23900
SCIPvarIsActive
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition var.c:23674
SCIPvarIsBinary
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition var.c:23510
SCIPvarGetStatus
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition var.c:23418
SCIPvarGetUbLocal
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:24300
SCIPvarGetObj
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition var.c:23932
SCIPparseVarName
SCIP_RETCODE SCIPparseVarName(SCIP *scip, const char *str, SCIP_VAR **var, char **endptr)
Definition scip_var.c:728
SCIPvarGetUbGlobal
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
Definition var.c:24174
SCIPaddVarLocksType
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition scip_var.c:5118
SCIPunlockVarCons
SCIP_RETCODE SCIPunlockVarCons(SCIP *scip, SCIP_VAR *var, SCIP_CONS *cons, SCIP_Bool lockdown, SCIP_Bool lockup)
Definition scip_var.c:5296
SCIPgetVarUbAtIndex
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition scip_var.c:2872
SCIPvarGetName
const char * SCIPvarGetName(SCIP_VAR *var)
Definition var.c:23299
SCIPreleaseVar
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition scip_var.c:1887
SCIPvarGetLbLocal
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:24266
SCIPvarIsNegated
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition var.c:23475
SCIPvarGetLbGlobal
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition var.c:24152
SCIPmarkDoNotMultaggrVar
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
Definition scip_var.c:11057
SCIPfixVar
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
Definition scip_var.c:10318
SCIPgetVarLbAtIndex
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
Definition scip_var.c:2736
SCIPinferBinvarCons
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:7412
SCIPwriteVarName
SCIP_RETCODE SCIPwriteVarName(SCIP *scip, FILE *file, SCIP_VAR *var, SCIP_Bool type)
Definition scip_var.c:361
SCIPgetBinvarRepresentative
SCIP_RETCODE SCIPgetBinvarRepresentative(SCIP *scip, SCIP_VAR *var, SCIP_VAR **repvar, SCIP_Bool *negated)
Definition scip_var.c:2236
SCIPgetTransformedVar
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
Definition scip_var.c:2078
SCIPcaptureVar
SCIP_RETCODE SCIPcaptureVar(SCIP *scip, SCIP_VAR *var)
Definition scip_var.c:1853
SCIPallowStrongDualReds
SCIP_Bool SCIPallowStrongDualReds(SCIP *scip)
Definition scip_var.c:10984
SCIPsnprintf
int SCIPsnprintf(char *t, int len, const char *s,...)
Definition misc.c:10827
SCIPskipSpace
SCIP_RETCODE SCIPskipSpace(char **s)
Definition misc.c:10816
result
* result
Definition heur_actconsdiving.c:297
SCIP_OKAY
return SCIP_OKAY
Definition heur_actconsdiving.c:237
c
int c
Definition heur_intdiving.c:223
sol
static SCIP_SOL * sol
Definition heur_intshifting.c:696
obj
SCIP_Real obj
Definition heur_intshifting.c:708
assert
assert(minobj< SCIPgetCutoffbound(scip))
nvars
int nvars
Definition heur_intshifting.c:711
var
SCIP_VAR * var
Definition heur_objpscostdiving.c:269
propagate
static SCIP_Bool propagate
Definition heur_randrounding.c:468
vars
static SCIP_VAR ** vars
Definition heur_rootsoldiving.c:190
i
int i
Definition heur_rootsoldiving.c:216
memory.h
memory allocation routines
pub_cons.h
public methods for managing constraints
pub_message.h
public methods for message output
SCIPerrorMessage
#define SCIPerrorMessage
Definition pub_message.h:64
pub_var.h
public methods for problem variables
scip.h
SCIP callable library.
scip_branch.h
public methods for branching rule plugins and branching
scip_conflict.h
public methods for conflict handler plugins and conflict analysis
scip_cons.h
public methods for constraint handler plugins and constraints
scip_copy.h
public methods for problem copies
scip_cut.h
public methods for cuts and aggregation rows
scip_general.h
general public methods
scip_lp.h
public methods for the LP relaxation, rows and columns
scip_mem.h
public methods for memory management
scip_message.h
public methods for message handling
scip_numerics.h
public methods for numerical tolerances
scip_param.h
public methods for SCIP parameter handling
scip_prob.h
public methods for global and local (sub)problems
scip_probing.h
public methods for the probing mode
scip_sol.h
public methods for solutions
scip_var.h
public methods for SCIP variables
separate
static SCIP_RETCODE separate(SCIP *scip, SCIP_SEPA *sepa, SCIP_SOL *sol, SCIP_RESULT *result)
Main separation function.
Definition sepa_flower.c:1219
symmetry.h
methods for handling symmetries
SCIP_CONFTYPE_PROPAGATION
@ SCIP_CONFTYPE_PROPAGATION
Definition type_conflict.h:62
SCIP_DECL_CONSENFOLP
#define SCIP_DECL_CONSENFOLP(x)
Definition type_cons.h:363
SCIP_DECL_CONSDELETE
#define SCIP_DECL_CONSDELETE(x)
Definition type_cons.h:229
SCIP_CONS
struct SCIP_Cons SCIP_CONS
Definition type_cons.h:63
SCIP_DECL_CONSGETVARS
#define SCIP_DECL_CONSGETVARS(x)
Definition type_cons.h:867
SCIP_DECL_CONSPRINT
#define SCIP_DECL_CONSPRINT(x)
Definition type_cons.h:769
SCIP_CONSHDLRDATA
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
Definition type_cons.h:64
SCIP_DECL_CONSSEPALP
#define SCIP_DECL_CONSSEPALP(x)
Definition type_cons.h:288
SCIP_DECL_CONSENFORELAX
#define SCIP_DECL_CONSENFORELAX(x)
Definition type_cons.h:388
SCIP_DECL_CONSPROP
#define SCIP_DECL_CONSPROP(x)
Definition type_cons.h:506
SCIP_DECL_CONSGETNVARS
#define SCIP_DECL_CONSGETNVARS(x)
Definition type_cons.h:885
SCIP_DECL_CONSRESPROP
#define SCIP_DECL_CONSRESPROP(x)
Definition type_cons.h:612
SCIP_DECL_CONSENFOPS
#define SCIP_DECL_CONSENFOPS(x)
Definition type_cons.h:431
SCIP_DECL_CONSPARSE
#define SCIP_DECL_CONSPARSE(x)
Definition type_cons.h:845
SCIP_DECL_CONSTRANS
#define SCIP_DECL_CONSTRANS(x)
Definition type_cons.h:239
SCIP_DECL_CONSPRESOL
#define SCIP_DECL_CONSPRESOL(x)
Definition type_cons.h:561
SCIP_DECL_CONSEXITPRE
#define SCIP_DECL_CONSEXITPRE(x)
Definition type_cons.h:180
SCIP_DECL_CONSLOCK
#define SCIP_DECL_CONSLOCK(x)
Definition type_cons.h:676
SCIP_CONSHDLR
struct SCIP_Conshdlr SCIP_CONSHDLR
Definition type_cons.h:62
SCIP_DECL_CONSCOPY
#define SCIP_DECL_CONSCOPY(x)
Definition type_cons.h:810
SCIP_CONSDATA
struct SCIP_ConsData SCIP_CONSDATA
Definition type_cons.h:65
SCIP_DECL_CONSCHECK
#define SCIP_DECL_CONSCHECK(x)
Definition type_cons.h:474
SCIP_DECL_CONSHDLRCOPY
#define SCIP_DECL_CONSHDLRCOPY(x)
Definition type_cons.h:108
SCIP_DECL_CONSFREE
#define SCIP_DECL_CONSFREE(x)
Definition type_cons.h:116
SCIP_DECL_CONSSEPASOL
#define SCIP_DECL_CONSSEPASOL(x)
Definition type_cons.h:320
SCIP_ROW
struct SCIP_Row SCIP_ROW
Definition type_lp.h:105
SCIP_DIDNOTRUN
@ SCIP_DIDNOTRUN
Definition type_result.h:42
SCIP_CUTOFF
@ SCIP_CUTOFF
Definition type_result.h:48
SCIP_FEASIBLE
@ SCIP_FEASIBLE
Definition type_result.h:45
SCIP_REDUCEDDOM
@ SCIP_REDUCEDDOM
Definition type_result.h:51
SCIP_DIDNOTFIND
@ SCIP_DIDNOTFIND
Definition type_result.h:44
SCIP_SEPARATED
@ SCIP_SEPARATED
Definition type_result.h:49
SCIP_SUCCESS
@ SCIP_SUCCESS
Definition type_result.h:58
SCIP_INFEASIBLE
@ SCIP_INFEASIBLE
Definition type_result.h:46
SCIP_RESULT
enum SCIP_Result SCIP_RESULT
Definition type_result.h:61
SCIP_PLUGINNOTFOUND
@ SCIP_PLUGINNOTFOUND
Definition type_retcode.h:54
SCIP_INVALIDCALL
@ SCIP_INVALIDCALL
Definition type_retcode.h:51
SCIP_RETCODE
enum SCIP_Retcode SCIP_RETCODE
Definition type_retcode.h:63
SCIP
struct Scip SCIP
Definition type_scip.h:39
SCIP_STAGE_SOLVING
@ SCIP_STAGE_SOLVING
Definition type_set.h:53
SCIP_STAGE_TRANSFORMING
@ SCIP_STAGE_TRANSFORMING
Definition type_set.h:46
SCIP_SOL
struct SCIP_Sol SCIP_SOL
Definition type_sol.h:57
type_symmetry.h
type definitions for symmetry computations
SCIP_ORBITOPETYPE_PACKING
@ SCIP_ORBITOPETYPE_PACKING
Definition type_symmetry.h:142
SCIP_ORBITOPETYPE_PARTITIONING
@ SCIP_ORBITOPETYPE_PARTITIONING
Definition type_symmetry.h:141
SCIP_ORBITOPETYPE
enum SCIP_OrbitopeType SCIP_ORBITOPETYPE
Definition type_symmetry.h:144
SCIP_VAR
struct SCIP_Var SCIP_VAR
Definition type_var.h:166
SCIP_BDCHGIDX
struct SCIP_BdChgIdx SCIP_BDCHGIDX
Definition type_var.h:151
SCIP_VARSTATUS_FIXED
@ SCIP_VARSTATUS_FIXED
Definition type_var.h:54
SCIP_VARSTATUS_MULTAGGR
@ SCIP_VARSTATUS_MULTAGGR
Definition type_var.h:56
SCIP_VARSTATUS_NEGATED
@ SCIP_VARSTATUS_NEGATED
Definition type_var.h:57
SCIP_LOCKTYPE_MODEL
@ SCIP_LOCKTYPE_MODEL
Definition type_var.h:141