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( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1713 assert( result != NULL );
1714
1715 /* loop through constraints */
1716 for (c = 0; c < nconss && ! infeasible; c++)
1717 {
1718 SCIP_CONSDATA* consdata;
1719 int nconsfixedvars = 0;
1720 int nconscuts = 0;
1721
1722 assert( conss[c] != NULL );
1723
1724 /* get data of constraint */
1725 consdata = SCIPconsGetData(conss[c]);
1726 assert( consdata != NULL );
1727
1728 /* skip non-model constraints if strong dual reductions are not permitted */
1729 if ( !consdata->ismodelcons && !SCIPallowStrongDualReds(scip) )
1730 continue;
1731
1732 /* do not enforce non-model constraints */
1733 if ( enforce && !consdata->ismodelcons )
1734 continue;
1735
1736 /* get solution */
1737 copyValues(scip, consdata, sol);
1738
1739 /* separate */
1740 SCIP_CALL( separateSCIs(scip, conshdlr, conss[c], consdata, &infeasible, &nconsfixedvars, &nconscuts) );
1741 nfixedvars += nconsfixedvars;
1742 ncuts += nconscuts;
1743
1744 /* stop after the useful constraints if we found cuts of fixed variables */
1745 if ( c >= nusefulconss && (ncuts > 0 || nfixedvars > 0) )
1746 break;
1747 }
1748
1749 if ( infeasible )
1750 {
1751 SCIPdebugMsg(scip, "Infeasible node.\n");
1752 *result = SCIP_CUTOFF;
1753 }
1754 else if ( nfixedvars > 0 )
1755 {
1756 SCIPdebugMsg(scip, "Fixed %d variables.\n", nfixedvars);
1757 *result = SCIP_REDUCEDDOM;
1758 }
1759 else if ( ncuts > 0 )
1760 {
1761 SCIPdebugMsg(scip, "Separated %dinequalities.\n", ncuts);
1762 *result = SCIP_SEPARATED;
1763 }
1764 else
1765 {
1766 SCIPdebugMsg(scip, "No violated inequality found during separation.\n");
1767 }
1768
1769 return SCIP_OKAY;
1770}
1771
1772
1773/** check whether all variables in an orbitope constraint are fixed */
1774static
1775SCIP_RETCODE checkRedundantCons(
1776 SCIP* scip, /**< SCIP data structure */
1777 SCIP_CONS* cons, /**< constraint to be processed */
1778 SCIP_Bool* redundant /**< pointer to store whether constraint is redundant (contains no active vars) */
1779 )
1780{
1781 SCIP_CONSDATA* consdata;
1782 SCIP_VAR*** vars;
1783 int i;
1784 int j;
1785 int nrows;
1786 int ncols;
1787
1788 assert( scip != NULL );
1789 assert( cons != NULL );
1790 assert( redundant != NULL );
1791
1792 *redundant = FALSE;
1793
1794 consdata = SCIPconsGetData(cons);
1795 assert( consdata != NULL );
1796 assert( consdata->vars != NULL );
1797 assert( consdata->nrows > 0 );
1798 assert( consdata->ncols > 0 );
1799
1800 vars = consdata->vars;
1801 nrows = consdata->nrows;
1802 ncols = consdata->ncols;
1803
1804 /* check whether there exists an active variable in the orbitope */
1805 for (i = 0; i < nrows; ++i)
1806 {
1807 for (j = 0; j < ncols; ++j)
1808 {
1809 if ( SCIPvarIsActive(vars[i][j]) )
1810 return SCIP_OKAY;
1811 }
1812 }
1813 *redundant = TRUE;
1814
1815 return SCIP_OKAY;
1816}
1817
1818/** replace aggregated variables by active variables */
1819static
1820SCIP_RETCODE replaceAggregatedVarsOrbitopePP(
1821 SCIP* scip, /**< SCIP data structure */
1822 SCIP_CONS* cons /**< constraint to be processed */
1823 )
1824{
1825 SCIP_CONSDATA* consdata;
1826 SCIP_VAR*** vars;
1827 int i;
1828 int j;
1829 int nrows;
1830 int ncols;
1831
1832 assert( scip != NULL );
1833 assert( cons != NULL );
1834
1835 consdata = SCIPconsGetData(cons);
1836 assert( consdata != NULL );
1837 assert( consdata->vars != NULL );
1838 assert( consdata->nrows > 0 );
1839 assert( consdata->ncols > 0 );
1840
1841 vars = consdata->vars;
1842 nrows = consdata->nrows;
1843 ncols = consdata->ncols;
1844
1845 /* check whether there exists an aggregated variable in the orbitope */
1846 for (i = 0; i < nrows; ++i)
1847 {
1848 for (j = 0; j < ncols; ++j)
1849 {
1850 SCIP_VAR* var;
1851 SCIP_Bool negated;
1852
1853 assert( SCIPvarGetStatus(vars[i][j]) != SCIP_VARSTATUS_MULTAGGR ); /* variables are marked as not to be multi-aggregated */
1854
1855 SCIP_CALL( SCIPgetBinvarRepresentative(scip, vars[i][j], &var, &negated) );
1856 SCIP_UNUSED( negated );
1857 assert( SCIPvarIsActive(var) || SCIPvarGetStatus(var) == SCIP_VARSTATUS_NEGATED || SCIPvarGetStatus(var) == SCIP_VARSTATUS_FIXED );
1858 if ( var != vars[i][j] )
1859 {
1860 SCIP_CALL( SCIPreleaseVar(scip, &vars[i][j]) );
1861 vars[i][j] = var;
1862 SCIP_CALL( SCIPcaptureVar(scip, var) );
1863 }
1864 }
1865 }
1866
1867 return SCIP_OKAY;
1868}
1869
1870
1871/*
1872 * Callback methods of constraint handler
1873 */
1874
1875/** copy method for constraint handler plugins (called when SCIP copies plugins) */
1876static
1877SCIP_DECL_CONSHDLRCOPY(conshdlrCopyOrbitopePP)
1878{ /*lint --e{715}*/
1879 assert(scip != NULL);
1880 assert(conshdlr != NULL);
1881 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1882 assert(valid != NULL);
1883
1884 /* call inclusion method of constraint handler */
1885 SCIP_CALL( SCIPincludeConshdlrOrbitopePP(scip) );
1886
1887 *valid = TRUE;
1888
1889 return SCIP_OKAY;
1890}
1891
1892/** frees constraint handler */
1893static
1894SCIP_DECL_CONSFREE(consFreeOrbitopePP)
1895{ /*lint --e{715}*/
1896 SCIP_CONSHDLRDATA* conshdlrdata;
1897
1898 assert( scip != 0 );
1899 assert( conshdlr != 0 );
1900 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
1901
1902 conshdlrdata = SCIPconshdlrGetData(conshdlr);
1903 assert( conshdlrdata != NULL );
1904
1905 SCIPfreeBlockMemory(scip, &conshdlrdata);
1906
1907 return SCIP_OKAY;
1908}
1909
1910/** frees specific constraint data */
1911static
1912SCIP_DECL_CONSDELETE(consDeleteOrbitopePP)
1913{ /*lint --e{715}*/
1914 assert(conshdlr != NULL);
1915 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1916
1917 SCIP_CALL( consdataFree(scip, consdata) );
1918
1919 return SCIP_OKAY;
1920}
1921
1922/** transforms constraint data into data belonging to the transformed problem */
1923static
1924SCIP_DECL_CONSTRANS(consTransOrbitopePP)
1925{ /*lint --e{715}*/
1926 SCIP_CONSDATA* sourcedata;
1927 SCIP_CONSDATA* targetdata;
1928
1929 assert(conshdlr != NULL);
1930 assert(strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0);
1931 assert(SCIPgetStage(scip) == SCIP_STAGE_TRANSFORMING);
1932 assert(sourcecons != NULL);
1933 assert(targetcons != NULL);
1934
1935 sourcedata = SCIPconsGetData(sourcecons);
1936 assert(sourcedata != NULL);
1937
1938 /* create linear constraint data for target constraint */
1939 SCIP_CALL( consdataCreate(scip, &targetdata, sourcedata->vars, sourcedata->nrows, sourcedata->ncols,
1940 sourcedata->orbitopetype, sourcedata->resolveprop, sourcedata->ismodelcons) );
1941
1942 /* create target constraint */
1943 SCIP_CALL( SCIPcreateCons(scip, targetcons, SCIPconsGetName(sourcecons), conshdlr, targetdata,
1944 SCIPconsIsInitial(sourcecons), SCIPconsIsSeparated(sourcecons), SCIPconsIsEnforced(sourcecons),
1945 SCIPconsIsChecked(sourcecons), SCIPconsIsPropagated(sourcecons),
1946 SCIPconsIsLocal(sourcecons), SCIPconsIsModifiable(sourcecons),
1947 SCIPconsIsDynamic(sourcecons), SCIPconsIsRemovable(sourcecons), SCIPconsIsStickingAtNode(sourcecons)) );
1948
1949 return SCIP_OKAY;
1950}
1951
1952/** separation method of constraint handler for LP solutions */
1953static
1954SCIP_DECL_CONSSEPALP(consSepalpOrbitopePP)
1955{ /*lint --e{715}*/
1956 assert( scip != NULL );
1957 assert( result != NULL );
1958
1959 SCIPdebugMsg(scip, "Separation of packing/partitioning orbitope constraint handler <%s> for LP solution.\n",
1960 SCIPconshdlrGetName(conshdlr));
1961
1962 *result = SCIP_DIDNOTRUN;
1963
1964 /* if solution is integer, skip separation */
1965 if ( SCIPgetNLPBranchCands(scip) <= 0 )
1966 return SCIP_OKAY;
1967
1968 *result = SCIP_DIDNOTFIND;
1969
1970 /* separate constraints */
1971 SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, NULL, result, FALSE) );
1972
1973 return SCIP_OKAY;
1974}
1975
1976/** separation method of constraint handler for arbitrary primal solutions */
1977static
1978SCIP_DECL_CONSSEPASOL(consSepasolOrbitopePP)
1979{ /*lint --e{715}*/
1980 assert( scip != NULL );
1981 assert( result != NULL );
1982
1983 SCIPdebugMsg(scip, "Separation of packing/partitioning orbitope constraint handler <%s> for primal solution.\n",
1984 SCIPconshdlrGetName(conshdlr));
1985
1986 *result = SCIP_DIDNOTFIND;
1987
1988 /* separate constraints */
1989 SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, sol, result, FALSE) );
1990
1991 return SCIP_OKAY;
1992}
1993
1994
1995/** constraint enforcing method of constraint handler for LP solutions */
1996static
1997SCIP_DECL_CONSENFOLP(consEnfolpOrbitopePP)
1998{ /*lint --e{715}*/
1999 assert( scip != NULL );
2000 assert( result != NULL );
2001
2002 /* we have a negative priority, so we should come after the integrality conshdlr */
2003 assert( SCIPgetNLPBranchCands(scip) == 0 );
2004
2005 SCIPdebugMsg(scip, "Enforcement for packing/partitioning orbitope constraint handler <%s> for LP solution.\n",
2006 SCIPconshdlrGetName(conshdlr));
2007
2008 *result = SCIP_FEASIBLE;
2009
2010 /* separate constraints */
2011 SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, NULL, result, TRUE) );
2012
2013 return SCIP_OKAY;
2014}
2015
2016
2017/** constraint enforcing method of constraint handler for relaxation solutions */
2018static
2019SCIP_DECL_CONSENFORELAX(consEnforelaxOrbitopePP)
2020{ /*lint --e{715}*/
2021 assert( result != NULL );
2022 assert( scip != NULL );
2023
2024 SCIPdebugMsg(scip,
2025 "Enforcement for packing/partitioning orbitope constraint handler <%s> for relaxation solution.\n",
2026 SCIPconshdlrGetName(conshdlr));
2027
2028 *result = SCIP_FEASIBLE;
2029
2030 /* separate constraints */
2031 SCIP_CALL( separateConstraints(scip, conshdlr, conss, nconss, nusefulconss, sol, result, TRUE) );
2032
2033 return SCIP_OKAY;
2034}
2035
2036
2037/** constraint enforcing method of constraint handler for pseudo solutions */
2038static
2039SCIP_DECL_CONSENFOPS(consEnfopsOrbitopePP)
2040{ /*lint --e{715}*/
2041 int c;
2042
2043 assert( scip != NULL );
2044 assert( conshdlr != NULL );
2045 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2046 assert( result != NULL );
2047
2048 *result = SCIP_FEASIBLE;
2049 if ( objinfeasible || solinfeasible )
2050 return SCIP_OKAY;
2051
2052 /* loop through constraints */
2053 for (c = 0; c < nconss; ++c)
2054 {
2055 SCIP_CONS* cons;
2056 SCIP_CONSDATA* consdata;
2057
2058 /* get data of constraint */
2059 cons = conss[c];
2060 assert( cons != 0 );
2061 consdata = SCIPconsGetData(cons);
2062
2063 assert( consdata != NULL );
2064
2065 /* do not enforce non-model constraints */
2066 if ( ! consdata->ismodelcons )
2067 continue;
2068
2069 SCIP_CALL( enfopsPackingPartitioningOrbitopeSolution(scip, cons, result) );
2070
2071 if ( *result == SCIP_INFEASIBLE )
2072 break;
2073 }
2074
2075 return SCIP_OKAY;
2076}
2077
2078
2079/** feasibility check method of constraint handler for integral solutions */
2080static
2081SCIP_DECL_CONSCHECK(consCheckOrbitopePP)
2082{ /*lint --e{715}*/
2083 int c;
2084 SCIP_CONSDATA* consdata;
2085
2086 assert( scip != NULL );
2087 assert( conshdlr != NULL );
2088 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2089 assert( result != NULL );
2090
2091 *result = SCIP_FEASIBLE;
2092
2093 /* loop through constraints */
2094 for( c = 0; c < nconss && (*result == SCIP_FEASIBLE || completely); ++c )
2095 {
2096 assert( conss[c] != 0 );
2097 consdata = SCIPconsGetData(conss[c]);
2098
2099 assert( consdata != NULL );
2100
2101 /* do not check non-model constraints */
2102 if ( !consdata->ismodelcons )
2103 continue;
2104
2105 SCIP_CALL( checkPackingPartitioningOrbitopeSolution(scip, conss[c], sol, result, printreason) );
2106 }
2107
2108 if( *result == SCIP_FEASIBLE )
2109 {
2110 SCIPdebugMsg(scip, "Solution is feasible.\n");
2111 }
2112 else
2113 {
2114 SCIPdebugMsg(scip, "Solution is infeasible.\n");
2115 }
2116
2117 return SCIP_OKAY;
2118}
2119
2120
2121/** domain propagation method of constraint handler */
2122static
2123SCIP_DECL_CONSPROP(consPropOrbitopePP)
2124{ /*lint --e{715}*/
2125 SCIP_Bool infeasible = FALSE;
2126 int nfixedvars = 0;
2127 int c;
2128
2129 assert( scip != NULL );
2130 assert( conshdlr != NULL );
2131 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2132 assert( result != NULL );
2133
2134 *result = SCIP_DIDNOTRUN;
2135
2136 /* propagate all useful constraints */
2137 for (c = 0; c < nusefulconss && !infeasible; ++c)
2138 {
2139 int nfixed;
2140
2141 assert( conss[c] != 0 );
2142
2143 SCIPdebugMsg(scip, "Propagation of packing/partitioning orbitope constraint <%s> ...\n",
2144 SCIPconsGetName(conss[c]));
2145
2146 SCIP_CALL( propagateCons(scip, conss[c], &infeasible, &nfixed) );
2147 nfixedvars += nfixed;
2148 }
2149
2150 /* return the correct result */
2151 if ( infeasible )
2152 {
2153 *result = SCIP_CUTOFF;
2154 SCIPdebugMsg(scip, "Propagation via orbitopal fixing proved node to be infeasible.\n");
2155 }
2156 else if ( nfixedvars > 0 )
2157 {
2158 *result = SCIP_REDUCEDDOM;
2159 SCIPdebugMsg(scip, "Propagated %d variables via orbitopal fixing.\n", nfixedvars);
2160 }
2161 else if ( nusefulconss > 0 )
2162 {
2163 *result = SCIP_DIDNOTFIND;
2164 SCIPdebugMsg(scip, "Propagation via orbitopal fixing did not find anything.\n");
2165 }
2166
2167 return SCIP_OKAY;
2168}
2169
2170
2171/** presolving method of constraint handler */
2172static
2173SCIP_DECL_CONSPRESOL(consPresolOrbitopePP)
2174{ /*lint --e{715}*/
2175 SCIP_Bool infeasible = FALSE;
2176 int noldfixedvars;
2177 int c;
2178 SCIP_Bool redundant;
2179
2180 assert( scip != NULL );
2181 assert( conshdlr != NULL );
2182 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2183 assert( result != NULL );
2184
2185 *result = SCIP_DIDNOTRUN;
2186 noldfixedvars = *nfixedvars;
2187
2188 /* propagate all useful constraints
2189 *
2190 * @todo use an event handler to only propagate if a variable in the orbitope has been fixed
2191 */
2192 for (c = 0; c < nconss && !infeasible; ++c)
2193 {
2194 int nfixed = 0;
2195
2196 assert( conss[c] != 0 );
2197
2198 SCIPdebugMsg(scip, "Presolving of packing/partitioning orbitope constraint <%s> ...\n",
2199 SCIPconsGetName(conss[c]));
2200
2201 /* first propagate */
2202 SCIP_CALL( propagateCons(scip, conss[c], &infeasible, &nfixed) );
2203 *nfixedvars += nfixed;
2204
2205 if ( ! infeasible )
2206 {
2207 SCIP_CALL( checkRedundantCons(scip, conss[c], &redundant) );
2208
2209 if ( redundant )
2210 {
2211 SCIPdebugMsg(scip,
2212 "Packing/Partitioning orbitope constraint <%s> is redundant: it does not contain active variables\n",
2213 SCIPconsGetName(conss[c]));
2214 SCIP_CALL( SCIPdelCons(scip, conss[c]) );
2215 assert( ! SCIPconsIsActive(conss[c]) );
2216 (*ndelconss)++;
2217 continue;
2218 }
2219 }
2220 }
2221
2222 if ( infeasible )
2223 {
2224 *result = SCIP_CUTOFF;
2225 SCIPdebugMsg(scip, "Presolving detected infeasibility.\n");
2226 }
2227 else if ( *nfixedvars > noldfixedvars )
2228 {
2229 *result = SCIP_SUCCESS;
2230 }
2231 else if ( nconss > 0 )
2232 {
2233 *result = SCIP_DIDNOTFIND;
2234 SCIPdebugMsg(scip, "Presolving via orbitopal fixing did not find anything.\n");
2235 }
2236
2237 return SCIP_OKAY;
2238}
2239
2240
2241/** propagation conflict resolving method of constraint handler */
2242static
2243SCIP_DECL_CONSRESPROP(consRespropOrbitopePP)
2244{ /*lint --e{715}*/
2245 assert( scip != NULL );
2246 assert( cons != NULL );
2247 assert( infervar != NULL );
2248 assert( bdchgidx != NULL );
2249 assert( result != NULL );
2250
2251 SCIP_CALL( resolvePropagation(scip, cons, inferinfo, bdchgidx, result) );
2252
2253 return SCIP_OKAY;
2254}
2255
2256
2257/** presolving deinitialization method of constraint handler (called after presolving has been finished) */
2258static
2259SCIP_DECL_CONSEXITPRE(consExitpreOrbitopePP)
2260{
2261 int c;
2262
2263 assert( scip != NULL );
2264 assert( conshdlr != NULL );
2265 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2266
2267 for (c = 0; c < nconss; ++c)
2268 {
2269 /* replace aggregated variables by active variables */
2270 SCIP_CALL( replaceAggregatedVarsOrbitopePP(scip, conss[c]) );
2271 }
2272 return SCIP_OKAY;
2273}
2274
2275
2276/** variable rounding lock method of constraint handler */
2277static
2278SCIP_DECL_CONSLOCK(consLockOrbitopePP)
2279{ /*lint --e{715}*/
2280 SCIP_CONSDATA* consdata;
2281 SCIP_VAR*** vars;
2282 int i;
2283 int j;
2284 int nrows;
2285 int ncols;
2286
2287 assert( scip != NULL );
2288 assert( conshdlr != NULL );
2289 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2290 assert( cons != NULL );
2291 assert( locktype == SCIP_LOCKTYPE_MODEL );
2292
2293 consdata = SCIPconsGetData(cons);
2294 assert( consdata != NULL );
2295 assert( consdata->nrows > 0 );
2296 assert( consdata->ncols > 0 );
2297 assert( consdata->vars != NULL );
2298
2299 SCIPdebugMsg(scip, "Locking method for packing/partitioning orbitope constraint handler\n");
2300
2301 nrows = consdata->nrows;
2302 ncols = consdata->ncols;
2303 vars = consdata->vars;
2304
2305 /* add up locks and down locks on each variable */
2306 for (i = 0; i < nrows; ++i)
2307 {
2308 for (j = 0; j < ncols; ++j)
2309 SCIP_CALL( SCIPaddVarLocksType(scip, vars[i][j], locktype, nlockspos + nlocksneg, nlockspos + nlocksneg) );
2310 }
2311
2312 return SCIP_OKAY;
2313}
2314
2315
2316/** constraint display method of constraint handler */
2317static
2318SCIP_DECL_CONSPRINT(consPrintOrbitopePP)
2319{
2320 SCIP_CONSDATA* consdata;
2321 SCIP_VAR*** vars;
2322 int i;
2323 int j;
2324 int nrows;
2325 int ncols;
2326 SCIP_ORBITOPETYPE orbitopetype;
2327
2328 assert( scip != NULL );
2329 assert( conshdlr != NULL );
2330 assert( strcmp(SCIPconshdlrGetName(conshdlr), CONSHDLR_NAME) == 0 );
2331 assert( cons != NULL );
2332
2333 consdata = SCIPconsGetData(cons);
2334 assert( consdata != NULL );
2335 assert( consdata->nrows > 0 );
2336 assert( consdata->ncols > 0 );
2337 assert( consdata->vars != NULL );
2338
2339 nrows = consdata->nrows;
2340 ncols = consdata->ncols;
2341 vars = consdata->vars;
2342 orbitopetype = consdata->orbitopetype;
2343
2344 SCIPdebugMsg(scip, "Printing method for packing/partitioning orbitope constraint handler\n");
2345
2346 switch ( orbitopetype )
2347 {
2348 case SCIP_ORBITOPETYPE_PARTITIONING:
2349 SCIPinfoMessage(scip, file, "partOrbitope(");
2350 break;
2351 case SCIP_ORBITOPETYPE_PACKING:
2352 SCIPinfoMessage(scip, file, "packOrbitope(");
2353 break;
2354 default:
2355 SCIPABORT();
2356 } /*lint !e788*/
2357
2358 for (i = 0; i < nrows; ++i)
2359 {
2360 for (j = 0; j < ncols; ++j)
2361 {
2362 if ( j > 0 )
2363 SCIPinfoMessage(scip, file, ",");
2364 SCIP_CALL( SCIPwriteVarName(scip, file, vars[i][j], TRUE) );
2365 }
2366 if ( i < nrows-1 )
2367 SCIPinfoMessage(scip, file, ".");
2368 }
2369 SCIPinfoMessage(scip, file, ")");
2370
2371 return SCIP_OKAY;
2372}
2373
2374
2375/** constraint copying method of constraint handler */
2376static
2377SCIP_DECL_CONSCOPY(consCopyOrbitopePP)
2378{
2379 SCIP_CONSHDLRDATA* conshdlrdata;
2380 SCIP_CONSDATA* sourcedata;
2381 SCIP_VAR*** sourcevars;
2382 SCIP_VAR*** vars;
2383 int nrows;
2384 int ncols;
2385 int i;
2386 int k;
2387 int j;
2388
2389 assert( scip != NULL );
2390 assert( cons != NULL );
2391 assert( sourcescip != NULL );
2392 assert( sourceconshdlr != NULL );
2393 assert( strcmp(SCIPconshdlrGetName(sourceconshdlr), CONSHDLR_NAME) == 0 );
2394 assert( sourcecons != NULL );
2395 assert( varmap != NULL );
2396 assert( valid != NULL );
2397
2398 *valid = TRUE;
2399
2400 SCIPdebugMsg(scip, "Copying method for packing/partOrbitope orbitope constraint handler.\n");
2401
2402 sourcedata = SCIPconsGetData(sourcecons);
2403 assert( sourcedata != NULL );
2404 assert( sourcedata->nrows > 0 );
2405 assert( sourcedata->ncols > 0 );
2406 assert( sourcedata->vars != NULL );
2407
2408 conshdlrdata = SCIPconshdlrGetData(sourceconshdlr);
2409 assert( conshdlrdata != NULL );
2410
2411 /* do not copy non-model constraints */
2412 if ( !sourcedata->ismodelcons && !conshdlrdata->forceconscopy )
2413 {
2414 *valid = FALSE;
2415
2416 return SCIP_OKAY;
2417 }
2418
2419 nrows = sourcedata->nrows;
2420 ncols = sourcedata->ncols;
2421 sourcevars = sourcedata->vars;
2422
2423 SCIP_CALL( SCIPallocBufferArray(scip, &vars, nrows) );
2424 for (i = 0; i < nrows && *valid; ++i)
2425 {
2426 SCIP_CALL( SCIPallocBufferArray(scip, &(vars[i]), ncols) ); /*lint !e866*/
2427
2428 for (j = 0; j < ncols && *valid; ++j)
2429 {
2430 SCIP_CALL( SCIPgetVarCopy(sourcescip, scip, sourcevars[i][j], &(vars[i][j]), varmap, consmap, global, valid) );
2431 assert( !(*valid) || vars[i][j] != NULL );
2432 }
2433 }
2434
2435 /* only create the target constraint, if all variables could be copied */
2436 if ( *valid )
2437 {
2438 /* create copied constraint */
2439 if ( name == NULL )
2440 name = SCIPconsGetName(sourcecons);
2441
2442 SCIP_CALL( SCIPcreateConsOrbitopePP(scip, cons, name, vars,
2443 sourcedata->orbitopetype, nrows, ncols, sourcedata->resolveprop, sourcedata->ismodelcons,
2444 initial, separate, enforce, check, propagate,
2445 local, modifiable, dynamic, removable, stickingatnode) );
2446 }
2447
2448 /* free space; only up to row i if copying failed */
2449 assert( 0 <= i && i <= nrows );
2450 for (k = i - 1; k >= 0; --k)
2451 SCIPfreeBufferArray(scip, &vars[k]);
2452 SCIPfreeBufferArray(scip, &vars);
2453
2454 return SCIP_OKAY;
2455}
2456
2457
2458/** constraint parsing method of constraint handler */
2459static
2460SCIP_DECL_CONSPARSE(consParseOrbitopePP)
2461{ /*lint --e{715}*/
2462 const char* s;
2463 char* endptr;
2464 SCIP_ORBITOPETYPE orbitopetype;
2465 SCIP_VAR*** vars;
2466 SCIP_VAR* var;
2467 int nrows;
2468 int maxnrows;
2469 int ncols;
2470 int maxncols;
2471 int k;
2472 int j;
2473
2474 assert( success != NULL );
2475
2476 *success = TRUE;
2477 s = str;
2478
2479 /* skip white space */
2480 SCIP_CALL( SCIPskipSpace((char**)&s) );
2481
2482 if( strncmp(s, "partOrbitope(", 13) == 0 )
2483 orbitopetype = SCIP_ORBITOPETYPE_PARTITIONING;
2484 else
2485 {
2486 if( strncmp(s, "packOrbitope(", 13) != 0 )
2487 {
2488 SCIPerrorMessage("Syntax error - expected \"partOrbitope\" or \"packOrbitope\": %s\n", s);
2489 *success = FALSE;
2490 return SCIP_OKAY;
2491 }
2492 orbitopetype = SCIP_ORBITOPETYPE_PACKING;
2493 }
2494 s += 13;
2495
2496 /* loop through string */
2497 nrows = 0;
2498 ncols = 0;
2499 maxnrows = 10;
2500 maxncols = 10;
2501
2502 SCIP_CALL( SCIPallocBufferArray(scip, &vars, maxnrows) );
2503
2504 j = 0;
2505 do
2506 {
2507 /* parse variable name */
2508 SCIP_CALL( SCIPparseVarName(scip, s, &var, &endptr) );
2509
2510 if( var == NULL )
2511 {
2512 endptr = strchr(endptr, ')');
2513
2514 if( endptr == NULL || j > 0 )
2515 {
2516 SCIPerrorMessage("not enough variables.\n");
2517 *success = FALSE;
2518 }
2519
2520 break;
2521 }
2522
2523 s = endptr;
2524 assert( s != NULL );
2525
2526 /* skip white space */
2527 SCIP_CALL( SCIPskipSpace((char**)&s) );
2528
2529 /* begin new row if required */
2530 if( j == 0 )
2531 {
2532 ++nrows;
2533
2534 if( nrows > maxnrows )
2535 {
2536 maxnrows = SCIPcalcMemGrowSize(scip, nrows);
2537 SCIP_CALL( SCIPreallocBufferArray(scip, &vars, maxnrows) );
2538 assert( nrows <= maxnrows );
2539 }
2540
2541 SCIP_CALL( SCIPallocBufferArray(scip, &(vars[nrows-1]), nrows == 1 ? maxncols : ncols) ); /*lint !e866*/
2542 }
2543
2544 /* determine number of columns */
2545 if( nrows == 1 )
2546 {
2547 ncols = j + 1;
2548
2549 if( *s == '.' || *s == ')' )
2550 SCIP_CALL( SCIPreallocBufferArray(scip, &(vars[nrows-1]), ncols) ); /*lint !e866*/
2551 else if( ncols > maxncols )
2552 {
2553 maxncols = SCIPcalcMemGrowSize(scip, ncols);
2554 SCIP_CALL( SCIPreallocBufferArray(scip, &(vars[nrows-1]), maxncols) ); /*lint !e866*/
2555 assert( ncols <= maxncols );
2556 }
2557 }
2558 else if( ( j < ncols-1 ) == ( *s == '.' || *s == ')' ) )
2559 {
2560 SCIPerrorMessage("variables per row do not match.\n");
2561 *success = FALSE;
2562 break;
2563 }
2564
2565 vars[nrows-1][j] = var;
2566
2567 if( *s == '.' )
2568 j = 0;
2569 else
2570 ++j;
2571
2572 /* skip ',' or '.' */
2573 if( *s == ',' || *s == '.' )
2574 ++s;
2575 }
2576 while( *s != ')' );
2577
2578 if( *success )
2579 {
2580 SCIP_CALL( SCIPcreateConsOrbitopePP(scip, cons, name, vars, orbitopetype, nrows, ncols, TRUE, TRUE,
2581 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
2582 }
2583
2584 for( k = nrows - 1; k >= 0; --k )
2585 SCIPfreeBufferArray(scip, &vars[k]);
2586 SCIPfreeBufferArray(scip, &vars);
2587
2588 return SCIP_OKAY;
2589}
2590
2591
2592/** constraint method of constraint handler which returns the variables (if possible) */
2593static
2594SCIP_DECL_CONSGETVARS(consGetVarsOrbitopePP)
2595{ /*lint --e{715}*/
2596 SCIP_CONSDATA* consdata;
2597
2598 assert( cons != NULL );
2599 assert( success != NULL );
2600 assert( vars != NULL );
2601
2602 consdata = SCIPconsGetData(cons);
2603 assert( consdata != NULL );
2604
2605 if ( varssize < consdata->ncols * consdata->nrows )
2606 *success = FALSE;
2607 else
2608 {
2609 int cnt = 0;
2610 int i;
2611 int j;
2612
2613 for (i = 0; i < consdata->nrows; ++i)
2614 {
2615 for (j = 0; j < consdata->ncols; ++j)
2616 vars[cnt++] = consdata->vars[i][j];
2617 }
2618 *success = TRUE;
2619 }
2620
2621 return SCIP_OKAY;
2622}
2623
2624
2625/** constraint method of constraint handler which returns the number of variables (if possible) */
2626static
2627SCIP_DECL_CONSGETNVARS(consGetNVarsOrbitopePP)
2628{ /*lint --e{715}*/
2629 SCIP_CONSDATA* consdata;
2630
2631 assert( cons != NULL );
2632
2633 consdata = SCIPconsGetData(cons);
2634 assert( consdata != NULL );
2635
2636 *nvars = consdata->ncols * consdata->nrows;
2637 *success = TRUE;
2638
2639 return SCIP_OKAY;
2640}
2641
2642
2643/*
2644 * constraint specific interface methods
2645 */
2646
2647/** creates the handler for packing/partitioning orbitope constraints and includes it in SCIP */
2648SCIP_RETCODE SCIPincludeConshdlrOrbitopePP(
2649 SCIP* scip /**< SCIP data structure */
2650 )
2651{
2652 SCIP_CONSHDLRDATA* conshdlrdata;
2653 SCIP_CONSHDLR* conshdlr;
2654
2655 /* create orbitope constraint handler data */
2656 SCIP_CALL( SCIPallocBlockMemory(scip, &conshdlrdata) );
2657
2658 /* include constraint handler */
2659 SCIP_CALL( SCIPincludeConshdlrBasic(scip, &conshdlr, CONSHDLR_NAME, CONSHDLR_DESC,
2660 CONSHDLR_ENFOPRIORITY, CONSHDLR_CHECKPRIORITY,
2661 CONSHDLR_EAGERFREQ, CONSHDLR_NEEDSCONS,
2662 consEnfolpOrbitopePP, consEnfopsOrbitopePP, consCheckOrbitopePP, consLockOrbitopePP,
2663 conshdlrdata) );
2664 assert(conshdlr != NULL);
2665
2666 /* set non-fundamental callbacks via specific setter functions */
2667 SCIP_CALL( SCIPsetConshdlrCopy(scip, conshdlr, conshdlrCopyOrbitopePP, consCopyOrbitopePP) );
2668 SCIP_CALL( SCIPsetConshdlrFree(scip, conshdlr, consFreeOrbitopePP) );
2669 SCIP_CALL( SCIPsetConshdlrDelete(scip, conshdlr, consDeleteOrbitopePP) );
2670 SCIP_CALL( SCIPsetConshdlrGetVars(scip, conshdlr, consGetVarsOrbitopePP) );
2671 SCIP_CALL( SCIPsetConshdlrGetNVars(scip, conshdlr, consGetNVarsOrbitopePP) );
2672 SCIP_CALL( SCIPsetConshdlrParse(scip, conshdlr, consParseOrbitopePP) );
2673 SCIP_CALL( SCIPsetConshdlrPresol(scip, conshdlr, consPresolOrbitopePP, CONSHDLR_MAXPREROUNDS, CONSHDLR_PRESOLTIMING) );
2674 SCIP_CALL( SCIPsetConshdlrExitpre(scip, conshdlr, consExitpreOrbitopePP) );
2675 SCIP_CALL( SCIPsetConshdlrPrint(scip, conshdlr, consPrintOrbitopePP) );
2676 SCIP_CALL( SCIPsetConshdlrProp(scip, conshdlr, consPropOrbitopePP, CONSHDLR_PROPFREQ, CONSHDLR_DELAYPROP,
2677 CONSHDLR_PROP_TIMING) );
2678 SCIP_CALL( SCIPsetConshdlrResprop(scip, conshdlr, consRespropOrbitopePP) );
2679 SCIP_CALL( SCIPsetConshdlrSepa(scip, conshdlr, consSepalpOrbitopePP, consSepasolOrbitopePP, CONSHDLR_SEPAFREQ,
2680 CONSHDLR_SEPAPRIORITY, CONSHDLR_DELAYSEPA) );
2681 SCIP_CALL( SCIPsetConshdlrTrans(scip, conshdlr, consTransOrbitopePP) );
2682 SCIP_CALL( SCIPsetConshdlrEnforelax(scip, conshdlr, consEnforelaxOrbitopePP) );
2683
2684 SCIP_CALL( SCIPaddBoolParam(scip, "constraints/" CONSHDLR_NAME "/forceconscopy",
2685 "Whether orbitope constraints should be forced to be copied to sub SCIPs.",
2686 &conshdlrdata->forceconscopy, TRUE, DEFAULT_FORCECONSCOPY, NULL, NULL) );
2687
2688 return SCIP_OKAY;
2689}
2690
2691
2692/** creates and captures a packing/partitioning orbitope constraint
2693 *
2694 * @pre This constraint handler assumes that constraints which enforce the packing/partitioning constraints are
2695 * contained in the problem. It does not implement, e.g., separation and propagation of set packing/partitioning
2696 * constraints, since this would just copy large parts of the code of the setppc constraint handler.
2697 *
2698 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
2699 */
2700SCIP_RETCODE SCIPcreateConsOrbitopePP(
2701 SCIP* scip, /**< SCIP data structure */
2702 SCIP_CONS** cons, /**< pointer to hold the created constraint */
2703 const char* name, /**< name of constraint */
2704 SCIP_VAR*** vars, /**< matrix of variables on which the symmetry acts */
2705 SCIP_ORBITOPETYPE orbitopetype, /**< type of orbitope constraint */
2706 int nrows, /**< number of rows in orbitope matrix <=> p */
2707 int ncols, /**< number of columns in orbitope matrix <=> q */
2708 SCIP_Bool resolveprop, /**< should propagation be resolved? */
2709 SCIP_Bool ismodelcons, /**< whether the orbitope is a model constraint */
2710 SCIP_Bool initial, /**< should the LP relaxation of constraint be in the initial LP?
2711 * Usually set to TRUE. Set to FALSE for 'lazy constraints'. */
2712 SCIP_Bool separate, /**< should the constraint be separated during LP processing?
2713 * Usually set to TRUE. */
2714 SCIP_Bool enforce, /**< should the constraint be enforced during node processing?
2715 * TRUE for model constraints, FALSE for additional, redundant constraints. */
2716 SCIP_Bool check, /**< should the constraint be checked for feasibility?
2717 * TRUE for model constraints, FALSE for additional, redundant constraints. */
2718 SCIP_Bool propagate, /**< should the constraint be propagated during node processing?
2719 * Usually set to TRUE. */
2720 SCIP_Bool local, /**< is constraint only valid locally?
2721 * Usually set to FALSE. Has to be set to TRUE, e.g., for branching constraints. */
2722 SCIP_Bool modifiable, /**< is constraint modifiable (subject to column generation)?
2723 * Usually set to FALSE. In column generation applications, set to TRUE if pricing
2724 * adds coefficients to this constraint. */
2725 SCIP_Bool dynamic, /**< is constraint subject to aging?
2726 * Usually set to FALSE. Set to TRUE for own cuts which
2727 * are separated as constraints. */
2728 SCIP_Bool removable, /**< should the relaxation be removed from the LP due to aging or cleanup?
2729 * Usually set to FALSE. Set to TRUE for 'lazy constraints' and 'user cuts'. */
2730 SCIP_Bool stickingatnode /**< should the constraint always be kept at the node where it was added, even
2731 * if it may be moved to a more global node?
2732 * Usually set to FALSE. Set to TRUE to for constraints that represent node data. */
2733 )
2734{
2735 SCIP_CONSHDLR* conshdlr;
2736 SCIP_CONSDATA* consdata;
2737
2738 /* find the orbitope constraint handler */
2739 conshdlr = SCIPfindConshdlr(scip, CONSHDLR_NAME);
2740 if ( conshdlr == NULL )
2741 {
2742 SCIPerrorMessage("packing/partitioning orbitope constraint handler not found\n");
2743 return SCIP_PLUGINNOTFOUND;
2744 }
2745 assert( nrows > 0 );
2746 assert( ncols > 0 );
2747
2748 /* run some checks */
2749#ifndef NDEBUG
2750 {
2751 SCIP_Real obj;
2752 int i;
2753 int j;
2754 for (i = 0; i < nrows; ++i)
2755 {
2756 /* initialize obj to infinity */
2757 obj = SCIPinfinity(scip);
2758 for (j = 0; j < ncols; ++j)
2759 {
2760 SCIP_Bool fixedZero;
2761 SCIP_VAR* var;
2762
2763 var = vars[i][j];
2764 assert(var != NULL);
2765
2766 if ( SCIPvarIsNegated(var) )
2767 var = SCIPvarGetNegatedVar(var);
2768
2769 /* all variables need to be binary */
2770 assert( SCIPvarIsBinary(var) );
2771
2772 /* fixed variables have obj = 0; for variables fixed to 0, we assume that there is no
2773 problem (but we cannot always check it, e.g., when in the original problem
2774 variables were fixed and this problem was copied.) */
2775 fixedZero = ( SCIPisZero(scip, SCIPvarGetLbGlobal(var)) && SCIPisZero(scip, SCIPvarGetUbGlobal(var)) );
2776
2777 /* @todo adapt correctness of the following check for sub-scips */
2778 if ( SCIPgetSubscipDepth(scip) == 0 )
2779 {
2780 /* check whether all variables in a row have the same objective */
2781 if ( ! fixedZero && SCIPisInfinity(scip, obj) )
2782 obj = SCIPvarGetObj(var);
2783 else
2784 {
2785 assert( fixedZero || ! SCIPvarIsActive(var) || SCIPisEQ(scip, obj, SCIPvarGetObj(var)) );
2786 }
2787 }
2788 }
2789 }
2790 }
2791#endif
2792
2793 /* create constraint data */
2794 SCIP_CALL( consdataCreate(scip, &consdata, vars, nrows, ncols, orbitopetype, resolveprop, ismodelcons) );
2795
2796 /* create constraint */
2797 SCIP_CALL( SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
2798 local, modifiable, dynamic, removable, stickingatnode) );
2799
2800 return SCIP_OKAY;
2801}
2802
2803/** creates and captures a packing/partitioning orbitope constraint in its most basic variant, i. e., with all
2804 * constraint flags set to their default values, which can be set afterwards using SCIPsetConsFLAGNAME()
2805 *
2806 * @see SCIPcreateConsOrbitopePP() for the default constraint flag configuration
2807 *
2808 * @note the constraint gets captured, hence at one point you have to release it using the method SCIPreleaseCons()
2809 */
2810SCIP_RETCODE SCIPcreateConsBasicOrbitopePP(
2811 SCIP* scip, /**< SCIP data structure */
2812 SCIP_CONS** cons, /**< pointer to hold the created constraint */
2813 const char* name, /**< name of constraint */
2814 SCIP_VAR*** vars, /**< matrix of variables on which the symmetry acts */
2815 SCIP_ORBITOPETYPE orbitopetype, /**< type of orbitope constraint */
2816 int nrows, /**< number of rows in orbitope matrix <=> p */
2817 int ncols, /**< number of columns in orbitope matrix <=> q */
2818 SCIP_Bool resolveprop, /**< should propagation be resolved? */
2819 SCIP_Bool ismodelcons /**< whether the orbitope is a model constraint */
2820 )
2821{
2822 SCIP_CALL( SCIPcreateConsOrbitopePP(scip, cons, name, vars, orbitopetype, nrows, ncols,
2823 resolveprop, ismodelcons, TRUE, TRUE, TRUE, TRUE, TRUE, FALSE, FALSE, FALSE, FALSE, FALSE) );
2824
2825 return SCIP_OKAY;
2826}
CONSHDLR_NEEDSCONS
#define CONSHDLR_NEEDSCONS
Definition cons_and.c:97
CONSHDLR_SEPAFREQ
#define CONSHDLR_SEPAFREQ
Definition cons_and.c:90
CONSHDLR_CHECKPRIORITY
#define CONSHDLR_CHECKPRIORITY
Definition cons_and.c:89
CONSHDLR_DESC
#define CONSHDLR_DESC
Definition cons_and.c:86
CONSHDLR_PROP_TIMING
#define CONSHDLR_PROP_TIMING
Definition cons_and.c:100
CONSHDLR_MAXPREROUNDS
#define CONSHDLR_MAXPREROUNDS
Definition cons_and.c:94
CONSHDLR_SEPAPRIORITY
#define CONSHDLR_SEPAPRIORITY
Definition cons_and.c:87
CONSHDLR_PROPFREQ
#define CONSHDLR_PROPFREQ
Definition cons_and.c:91
CONSHDLR_PRESOLTIMING
#define CONSHDLR_PRESOLTIMING
Definition cons_and.c:99
CONSHDLR_EAGERFREQ
#define CONSHDLR_EAGERFREQ
Definition cons_and.c:92
CONSHDLR_ENFOPRIORITY
#define CONSHDLR_ENFOPRIORITY
Definition cons_and.c:88
CONSHDLR_DELAYSEPA
#define CONSHDLR_DELAYSEPA
Definition cons_and.c:95
CONSHDLR_NAME
#define CONSHDLR_NAME
Definition cons_and.c:85
CONSHDLR_DELAYPROP
#define CONSHDLR_DELAYPROP
Definition cons_and.c:96
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:1775
replaceAggregatedVarsOrbitopePP
static SCIP_RETCODE replaceAggregatedVarsOrbitopePP(SCIP *scip, SCIP_CONS *cons)
Definition cons_orbitope_pp.c:1820
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:255
SCIP_MAXSTRLEN
#define SCIP_MAXSTRLEN
Definition def.h:276
SCIP_UNUSED
#define SCIP_UNUSED(x)
Definition def.h:416
SCIP_Bool
#define SCIP_Bool
Definition def.h:98
MIN
#define MIN(x, y)
Definition def.h:231
SCIP_Real
#define SCIP_Real
Definition def.h:163
TRUE
#define TRUE
Definition def.h:100
FALSE
#define FALSE
Definition def.h:101
SCIPABORT
#define SCIPABORT()
Definition def.h:334
REALABS
#define REALABS(x)
Definition def.h:189
SCIP_CALL
#define SCIP_CALL(x)
Definition def.h:362
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:2700
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:2810
SCIPincludeConshdlrOrbitopePP
SCIP_RETCODE SCIPincludeConshdlrOrbitopePP(SCIP *scip)
Definition cons_orbitope_pp.c:2648
SCIPgetSubscipDepth
int SCIPgetSubscipDepth(SCIP *scip)
Definition scip_copy.c:2588
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:647
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:4316
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:4336
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:8419
SCIPconsIsDynamic
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
Definition cons.c:8648
SCIPconsIsInitial
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
Definition cons.c:8558
SCIPconsIsChecked
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
Definition cons.c:8588
SCIPconsIsEnforced
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
Definition cons.c:8578
SCIPconsIsActive
SCIP_Bool SCIPconsIsActive(SCIP_CONS *cons)
Definition cons.c:8450
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:8608
SCIPconsIsLocal
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
Definition cons.c:8628
SCIPconsGetName
const char * SCIPconsGetName(SCIP_CONS *cons)
Definition cons.c:8389
SCIPconsIsModifiable
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
Definition cons.c:8638
SCIPconsIsStickingAtNode
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
Definition cons.c:8668
SCIPconsIsSeparated
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
Definition cons.c:8568
SCIPconsIsRemovable
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
Definition cons.c:8658
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:1765
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
SCIPvarGetNegatedVar
SCIP_VAR * SCIPvarGetNegatedVar(SCIP_VAR *var)
Definition var.c:23868
SCIPvarIsActive
SCIP_Bool SCIPvarIsActive(SCIP_VAR *var)
Definition var.c:23642
SCIPvarIsBinary
SCIP_Bool SCIPvarIsBinary(SCIP_VAR *var)
Definition var.c:23478
SCIPvarGetStatus
SCIP_VARSTATUS SCIPvarGetStatus(SCIP_VAR *var)
Definition var.c:23386
SCIPvarGetUbLocal
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
Definition var.c:24268
SCIPvarGetObj
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
Definition var.c:23900
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:24142
SCIPaddVarLocksType
SCIP_RETCODE SCIPaddVarLocksType(SCIP *scip, SCIP_VAR *var, SCIP_LOCKTYPE locktype, int nlocksdown, int nlocksup)
Definition scip_var.c:5118
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:23267
SCIPreleaseVar
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
Definition scip_var.c:1887
SCIPvarGetLbLocal
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
Definition var.c:24234
SCIPvarIsNegated
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
Definition var.c:23443
SCIPvarGetLbGlobal
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
Definition var.c:24120
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:293
SCIP_OKAY
return SCIP_OKAY
Definition heur_actconsdiving.c:235
c
int c
Definition heur_intdiving.c:219
sol
static SCIP_SOL * sol
Definition heur_intshifting.c:694
obj
SCIP_Real obj
Definition heur_intshifting.c:706
assert
assert(minobj< SCIPgetCutoffbound(scip))
nvars
int nvars
Definition heur_intshifting.c:709
var
SCIP_VAR * var
Definition heur_objpscostdiving.c:265
propagate
static SCIP_Bool propagate
Definition heur_randrounding.c:465
vars
static SCIP_VAR ** vars
Definition heur_rootsoldiving.c:186
i
int i
Definition heur_rootsoldiving.c:212
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:1221
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:866
SCIP_DECL_CONSPRINT
#define SCIP_DECL_CONSPRINT(x)
Definition type_cons.h:768
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:505
SCIP_DECL_CONSGETNVARS
#define SCIP_DECL_CONSGETNVARS(x)
Definition type_cons.h:884
SCIP_DECL_CONSRESPROP
#define SCIP_DECL_CONSRESPROP(x)
Definition type_cons.h:611
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:844
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:560
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:675
SCIP_CONSHDLR
struct SCIP_Conshdlr SCIP_CONSHDLR
Definition type_cons.h:62
SCIP_DECL_CONSCOPY
#define SCIP_DECL_CONSCOPY(x)
Definition type_cons.h:809
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_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