69 #define CONSHDLR_NAME "orbitope" 70 #define CONSHDLR_DESC "symmetry breaking constraint handler relying on (partitioning/packing) orbitopes" 71 #define CONSHDLR_SEPAPRIORITY +40100 72 #define CONSHDLR_ENFOPRIORITY -1005200 73 #define CONSHDLR_CHECKPRIORITY -1005200 74 #define CONSHDLR_SEPAFREQ 5 75 #define CONSHDLR_PROPFREQ -1 76 #define CONSHDLR_EAGERFREQ -1 78 #define CONSHDLR_MAXPREROUNDS -1 79 #define CONSHDLR_DELAYSEPA FALSE 80 #define CONSHDLR_DELAYPROP FALSE 81 #define CONSHDLR_NEEDSCONS TRUE 83 #define CONSHDLR_PROP_TIMING SCIP_PROPTIMING_BEFORELP 84 #define CONSHDLR_PRESOLTIMING SCIP_PRESOLTIMING_MEDIUM 123 assert( consdata !=
NULL );
124 assert( *consdata !=
NULL );
126 p = (*consdata)->nspcons;
127 q = (*consdata)->nblocks;
128 for (i = 0; i < p; ++i)
165 assert(consdata !=
NULL);
174 for (i = 0; i < nspcons; ++i)
182 (*consdata)->tmpvals =
NULL;
183 (*consdata)->tmpvars =
NULL;
184 (*consdata)->nspcons = nspcons;
185 (*consdata)->nblocks = nblocks;
186 (*consdata)->ispart = ispart;
187 (*consdata)->resolveprop = resolveprop;
188 (*consdata)->istrianglefixed =
FALSE;
196 for (i = 0; i < nspcons; ++i)
200 for (j = 0; j < nblocks; ++j)
223 assert( consdata !=
NULL );
224 assert( consdata->nspcons > 0 );
225 assert( consdata->nblocks > 0 );
226 assert( consdata->vars !=
NULL );
228 for (j = 0; j < consdata->nblocks; ++j)
232 for (i = 0; i < consdata->nspcons; ++i)
234 for (j = 0; j < consdata->nblocks; ++j)
243 for (j = 0; j < consdata->nblocks; ++j)
269 for (k = 0; k < p; ++k)
272 for (l = 0; l < q; ++l)
277 for (l = j; l < q; ++l)
279 assert( M[i][l] == 0 );
288 assert( cases[p1][p2] != -1 );
289 assert( p1 >= 0 && p1 < i );
290 assert( p2 >= 0 && p2 < j );
293 if ( cases[p1][p2] == 1 )
298 assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
299 assert( M[p1][p2] == 0 );
301 if ( cases[p1][p2] == 3 )
307 assert( cases[p1][p2] == 3 );
310 for (l = 0; l < q; ++l)
314 for (k = 0; k < p; ++k)
316 for (l = 0; l < q; ++l)
334 SCIPerrorMessage(
"unexpected matrix entry <%d>: should be -1, 0 or +1\n", M[k][l]);
342 for (l = 0; l < q; ++l)
346 for (k = 0; k < p; ++k)
366 assert( scip !=
NULL );
367 assert( consdata !=
NULL );
368 assert( consdata->nspcons > 0 );
369 assert( consdata->nblocks > 0 );
370 assert( consdata->vars !=
NULL );
371 assert( consdata->vals !=
NULL );
373 for (i = 0; i < consdata->nspcons; ++i)
375 for (j = 0; j < consdata->nblocks; ++j)
376 consdata->vals[i][j] =
SCIPgetSolVal(scip, sol, consdata->vars[i][j]);
407 assert( weights !=
NULL );
408 assert( cases !=
NULL );
409 assert( vals !=
NULL );
413 for (i = 0; i < nspcons; ++i)
415 for (j = 0; j < nblocks; ++j)
419 weights[i][j] = -1.0;
427 minvalue = vals[0][0];
428 weights[0][0] = minvalue;
433 if ( nspcons < nblocks )
436 for (j = 1; j < diagsize; ++j)
439 if (
SCIPisLT(scip, vals[j][j], minvalue) )
441 minvalue = vals[j][j];
446 weights[j][j] = minvalue;
450 for (i = 1; i < nspcons; ++i)
452 weights[i][0] = weights[i-1][0] + vals[i][0];
457 for (i = 2; i < nspcons; ++i)
459 for (j = 1; j < nblocks && j < i; ++j)
464 assert( cases[i-1][j] != -1 );
465 assert( cases[i-1][j-1] != -1 );
467 weightleft = weights[i-1][j-1];
468 weightright = vals[i][j] + weights[i-1][j];
471 if (
SCIPisLT(scip, weightleft, weightright) )
473 weights[i][j] = weightleft;
478 weights[i][j] = weightright;
505 assert( scip !=
NULL );
506 assert( cons !=
NULL );
507 assert( infeasible !=
NULL );
508 assert( nfixedvars !=
NULL );
511 assert( consdata !=
NULL );
512 assert( consdata->nspcons > 0 );
513 assert( consdata->nblocks > 0 );
514 assert( consdata->vars !=
NULL );
519 if ( consdata->istrianglefixed )
522 nspcons = consdata->nspcons;
523 nblocks = consdata->nblocks;
524 vars = consdata->vars;
529 if ( nspcons < nblocks )
533 for (i = 0; i < diagsize; ++i)
535 for (j = i+1; j < nblocks; ++j)
542 SCIPdebugMsg(scip,
"The problem is infeasible: some variable in the upper right triangle is fixed to 1.\n");
553 if ( *nfixedvars > 0 )
555 SCIPdebugMsg(scip,
"<%s>: %s fixed upper right triangle to 0 (fixed vars: %d).\n",
SCIPconsGetName(cons), fixedglobal ?
"globally" :
"locally", *nfixedvars);
563 consdata->istrianglefixed =
TRUE;
593 assert( scip !=
NULL );
594 assert( conshdlr !=
NULL );
595 assert( cons !=
NULL );
596 assert( infeasible !=
NULL);
597 assert( nfixedvars !=
NULL );
598 assert( ncuts !=
NULL );
600 assert( consdata !=
NULL );
601 assert( consdata->nspcons > 0 );
602 assert( consdata->nblocks > 0 );
603 assert( consdata->vars !=
NULL );
604 assert( consdata->vals !=
NULL );
605 assert( consdata->tmpvars !=
NULL );
606 assert( consdata->tmpvals !=
NULL );
607 assert( consdata->weights !=
NULL );
608 assert( consdata->cases !=
NULL );
614 nspcons = consdata->nspcons;
615 nblocks = consdata->nblocks;
616 vars = consdata->vars;
617 vals = consdata->vals;
618 tmpvars = consdata->tmpvars;
619 tmpvals = consdata->tmpvals;
620 weights = consdata->weights;
621 cases = consdata->cases;
624 if ( ! consdata->istrianglefixed )
629 if ( *nfixedvars > 0 )
637 for (i = 1; i < nspcons && ! (*infeasible); ++i)
643 lastcolumn = nblocks - 1;
644 if ( lastcolumn > i )
649 for (j = lastcolumn; j > 1; --j)
671 for (l = j; l <= lastcolumn; ++l)
673 tmpvars[nvars] = vars[i][l];
674 tmpvals[nvars] = 1.0;
681 assert( cases[p1][p2] != -1 );
682 assert( p1 >= 0 && p1 < i );
683 assert( p2 >= 0 && p2 < j );
686 if (cases[p1][p2] == 1)
691 assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
692 tmpvars[nvars] = vars[p1][p2];
693 tmpvals[nvars] = -1.0;
695 weight += vals[p1][p2];
696 if ( cases[p1][p2] == 3 )
702 assert( cases[p1][p2] == 3 );
718 SCIP_CALL( printSCI(scip, nspcons, nblocks, cases, i, j) );
721 assert(
SCIPisSumEQ(scip, weights[i-1][j-1], weight) );
751 assert( scip !=
NULL );
752 assert( cons !=
NULL );
753 assert( infeasible !=
NULL );
754 assert( nfixedvars !=
NULL );
762 assert( consdata !=
NULL );
763 assert( consdata->nspcons > 0 );
764 assert( consdata->nblocks > 0 );
765 assert( consdata->vars !=
NULL );
767 nspcons = consdata->nspcons;
768 nblocks = consdata->nblocks;
769 vars = consdata->vars;
770 ispart = consdata->ispart;
773 if ( ! consdata->istrianglefixed )
777 *nfixedvars += nfixed;
787 printMatrix(scip, consdata);
805 for (i = 1; i < nspcons; ++i)
808 int firstnonzeroinrow;
813 lastcolumn = nblocks - 1;
814 if ( lastcolumn > i )
818 firstnonzeroinrow = -1;
819 for (j = 0; j <= lastcolumn; ++j)
826 firstnonzeroinrow = j;
835 firstnonzeroinrow = j;
841 if ( firstnonzeroinrow == -1 && ispart )
843 SCIPdebugMsg(scip,
" -> Infeasible node: all variables in row %d are fixed to 0.\n", i);
848 firstnonzeros[i] = firstnonzeroinrow;
849 assert( !ispart || firstnonzeroinrow >= 0 );
850 assert( -1 <= firstnonzeroinrow && firstnonzeroinrow <= lastcolumn );
853 assert( !ispart || 0 <= lastoneprevrow );
854 assert( lastoneprevrow <= lastcolumn );
858 assert( lastoneprevrow + 1 >= 0 );
859 if ( lastoneprevrow == nblocks-1 ||
SCIPvarGetUbLocal(vars[i][lastoneprevrow+1]) < 0.5 )
860 lastoneinrow = lastoneprevrow;
863 lastoneinrow = lastoneprevrow + 1;
864 frontiersteps[nsteps++] = i;
869 assert( !ispart || 0 <= lastoneinrow );
870 assert( lastoneinrow <= lastcolumn );
871 lastones[i] = lastoneinrow;
874 if ( firstnonzeroinrow > lastoneinrow )
881 SCIPdebugMsg(scip,
" -> Infeasible node: row %d, leftmost nonzero at %d, rightmost 1 at %d\n",
882 i, firstnonzeroinrow, lastoneinrow);
886 SCIPdebugMsg(scip,
" -> Infeasible node: row %d, 1 at %d, rightmost position for 1 at %d\n",
887 i, firstnonzeroinrow, lastoneinrow);
902 for (j = 0; j <= lastcolumn; ++j)
915 if ( lastones[0] == -1 )
927 for (k = 1; k < i; ++k)
933 if ( l <= nblocks-1 && l <= k && lastones[k-1] == lastones[k] )
947 for (j = lastoneinrow+1; j <= lastcolumn; ++j)
955 SCIPdebugMsg(scip,
" -> Fixing entry (%d,%d) to 0.\n", i, j);
960 inferInfo = i * nblocks + lastoneinrow + 1;
969 SCIPdebugMsg(scip,
" -> Infeasible node: row %d, 1 in column %d beyond rightmost position %d\n", i, j, lastoneinrow);
985 if ( ! ispart && lastones[0] == -1 )
992 for (k = 1; k < i; ++k)
998 if ( l <= nblocks-1 && l <= k && lastones[k-1] == lastones[k] )
1014 lastoneprevrow = lastoneinrow;
1018 for (j = 0; j < nsteps; ++j)
1023 s = frontiersteps[j];
1024 lastoneinrow = lastones[s];
1026 assert( 0 <= lastoneinrow && lastoneinrow < nblocks );
1032 betaprev = lastoneinrow - 1;
1035 for (i = s+1; i < nspcons; ++i)
1039 assert( betaprev + 1 >= 0 );
1043 beta = betaprev + 1;
1044 assert( -1 <= beta && beta < nblocks );
1046 if ( firstnonzeros[i] > beta )
1056 SCIPdebugMsg(scip,
" -> Fixing entry (%d,%d) to 1.\n", s, lastoneinrow);
1061 inferInfo = nblocks * nspcons + i * nblocks + firstnonzeros[i];
1064 assert( !(*infeasible) );
1125 assert( scip !=
NULL );
1126 assert( cons !=
NULL );
1127 assert( result !=
NULL );
1130 assert( consdata !=
NULL );
1131 assert( consdata->nspcons > 0 );
1132 assert( consdata->nblocks > 0 );
1133 assert( consdata->vars !=
NULL );
1134 assert( consdata->vals !=
NULL );
1135 assert( consdata->weights !=
NULL );
1136 assert( consdata->cases !=
NULL );
1137 assert( consdata->istrianglefixed );
1140 if ( ! consdata->resolveprop )
1143 nspcons = consdata->nspcons;
1144 nblocks = consdata->nblocks;
1145 vars = consdata->vars;
1146 vals = consdata->vals;
1147 weights = consdata->weights;
1148 ispart = consdata->ispart;
1149 cases = consdata->cases;
1151 SCIPdebugMsg(scip,
"Propagation resolution method of orbitope constraint using orbitopal fixing\n");
1154 for (i = 0; i < nspcons; ++i)
1159 lastcolumn = nblocks - 1;
1160 if ( lastcolumn > i )
1162 for (j = 0; j <= lastcolumn; ++j)
1180 printMatrix(scip, consdata);
1184 assert( consdata->istrianglefixed );
1188 assert( inferinfo >= 0 && inferinfo < 2 * nspcons * nblocks );
1189 if ( inferinfo < nspcons * nblocks )
1198 i = (int) (inferinfo / nblocks);
1199 j = inferinfo % nblocks;
1200 assert( 0 <= i && i < nspcons );
1201 assert( 0 <= j && j < nblocks );
1204 assert( weights[i-1][j-1] < 0.5 );
1206 SCIPdebugMsg(scip,
" -> reason for x[%d][%d] = ... = x[%d][%d] = 0 was the following SC:\n", i, j, i,
MIN(i,nblocks));
1215 assert( cases[p1][p2] != -1 );
1216 assert( p1 >= 0 && p1 < i );
1217 assert( p2 >= 0 && p2 < j );
1220 if ( cases[p1][p2] == 1 )
1225 assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
1235 if ( cases[p1][p2] == 3 )
1241 assert( cases[p1][p2] == 3 );
1262 inferinfo -= nspcons * nblocks;
1263 i = (int) inferinfo / nblocks;
1264 j = inferinfo % nblocks;
1265 assert( 0 <= i && i < nspcons );
1266 assert( 0 <= j && j < nblocks );
1271 if ( weights[i-1][j-1] > 0.5 && weights[i-1][j-1] < 1.5 )
1273 SCIPdebugMsg(scip,
" -> reason for x[%d][%d] = 1 was the following SC:\n", i, j);
1286 assert( cases[p1][p2] != -1 );
1287 assert( p1 >= 0 && p1 < i );
1288 assert( p2 >= 0 && p2 < j );
1291 if ( cases[p1][p2] == 1 )
1296 assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
1311 assert( pos1 == -1 && pos2 == -1 );
1316 if ( cases[p1][p2] == 3 )
1322 assert( cases[p1][p2] == 3 );
1323 assert( pos1 >= 0 && pos2 >= 0 );
1334 for (k = 0; k < j; ++k)
1355 lastcolumn = nblocks - 1;
1356 if ( lastcolumn > i )
1360 for (k = j; k <= lastcolumn; ++k)
1366 SCIPdebugMsg(scip,
" and variable x[%d][%d] fixed to 1.\n", i, k);
1394 assert( scip !=
NULL );
1395 assert( conshdlr !=
NULL );
1397 assert( result !=
NULL );
1400 for (c = 0; c < nconss && ! infeasible; c++)
1406 assert( conss[c] !=
NULL );
1410 assert( consdata !=
NULL );
1416 SCIP_CALL(
separateSCIs(scip, conshdlr, conss[c], consdata, &infeasible, &nconsfixedvars, &nconscuts) );
1417 nfixedvars += nconsfixedvars;
1421 if ( c >= nusefulconss && (ncuts > 0 || nfixedvars > 0) )
1430 else if ( nfixedvars > 0 )
1432 SCIPdebugMsg(scip,
"Fixed %d variables.\n", nfixedvars);
1435 else if ( ncuts > 0 )
1442 SCIPdebugMsg(scip,
"No violated SCI found during separation.\n");
1456 assert(scip !=
NULL);
1457 assert(conshdlr !=
NULL);
1472 assert(conshdlr !=
NULL);
1487 assert(conshdlr !=
NULL);
1490 assert(sourcecons !=
NULL);
1491 assert(targetcons !=
NULL);
1494 assert(sourcedata !=
NULL);
1498 sourcedata->ispart, sourcedata->resolveprop) );
1514 assert( scip !=
NULL );
1515 assert( result !=
NULL );
1537 assert( scip !=
NULL );
1538 assert( result !=
NULL );
1555 assert( scip !=
NULL );
1556 assert( result !=
NULL );
1576 assert( result !=
NULL );
1577 assert( scip !=
NULL );
1596 assert( scip !=
NULL );
1597 assert( conshdlr !=
NULL );
1599 assert( result !=
NULL );
1602 if ( objinfeasible || solinfeasible )
1606 for (c = 0; c < nconss; ++c)
1620 assert( cons != 0 );
1623 assert( consdata !=
NULL );
1624 assert( consdata->nspcons > 0 );
1625 assert( consdata->nblocks > 0 );
1626 assert( consdata->vals !=
NULL );
1627 assert( consdata->weights !=
NULL );
1628 assert( consdata->cases !=
NULL );
1631 if ( ! consdata->istrianglefixed )
1642 if ( nfixedvars > 0 )
1649 nspcons = consdata->nspcons;
1650 nblocks = consdata->nblocks;
1651 vals = consdata->vals;
1652 weights = consdata->weights;
1653 cases = consdata->cases;
1660 assert( consdata->istrianglefixed );
1664 for (i = 1; i < nspcons; ++i)
1669 lastcolumn = nblocks - 1;
1672 if ( lastcolumn > i )
1676 for (j = lastcolumn; j > 1; --j)
1682 if (
SCIPisGT(scip, bar - weights[i-1][j-1], 0.0) )
1702 assert( scip !=
NULL );
1703 assert( conshdlr !=
NULL );
1705 assert( result !=
NULL );
1710 for( c = 0; c < nconss && (*result ==
SCIP_FEASIBLE || completely); ++c )
1723 assert( conss[c] != 0 );
1726 assert( consdata !=
NULL );
1727 assert( consdata->nspcons > 0 );
1728 assert( consdata->nblocks > 0 );
1729 assert( consdata->vars !=
NULL );
1730 assert( consdata->vals !=
NULL );
1731 assert( consdata->weights !=
NULL );
1732 assert( consdata->cases !=
NULL );
1734 nspcons = consdata->nspcons;
1735 nblocks = consdata->nblocks;
1736 vars = consdata->vars;
1737 vals = consdata->vals;
1738 weights = consdata->weights;
1739 cases = consdata->cases;
1747 if ( ! consdata->istrianglefixed )
1754 if ( nspcons < nblocks )
1758 for (i = 0; i < diagsize; ++i)
1760 for (j = i+1; j < nblocks; ++j)
1765 SCIPinfoMessage(scip,
NULL,
"variable x[%d][%d] = %f on upper right nonzero.\n", i, j, vals[i][j]);
1776 for (i = 1; i < nspcons; ++i)
1781 lastcolumn = nblocks - 1;
1784 if ( lastcolumn > i )
1788 for (j = lastcolumn; j > 1; --j)
1794 if (
SCIPisGT(scip, bar - weights[i-1][j-1], 0.0) )
1808 for (l = j; l < nblocks; ++l)
1818 assert( cases[p1][p2] != -1 );
1819 assert( p1 >= 0 && p1 < i );
1820 assert( p2 >= 0 && p2 < j );
1823 if (cases[p1][p2] == 1)
1828 assert( cases[p1][p2] == 2 || cases[p1][p2] == 3 );
1830 if ( cases[p1][p2] == 3 )
1836 assert( cases[p1][p2] == 3 );
1858 assert( scip !=
NULL );
1859 assert( conshdlr !=
NULL );
1861 assert( result !=
NULL );
1866 for (c = 0; c < nusefulconss && !infeasible; ++c)
1868 assert( conss[c] != 0 );
1879 SCIPdebugMsg(scip,
"Propagation via orbitopal fixing proved node to be infeasible.\n");
1881 else if ( nfixedvars > 0 )
1884 SCIPdebugMsg(scip,
"Propagated %d variables via orbitopal fixing.\n", nfixedvars);
1886 else if ( nusefulconss > 0 )
1889 SCIPdebugMsg(scip,
"Propagation via orbitopal fixing did not find anything.\n");
1904 assert( scip !=
NULL );
1905 assert( conshdlr !=
NULL );
1907 assert( result !=
NULL );
1910 noldfixedvars = *nfixedvars;
1913 for (c = 0; c < nconss && !infeasible; ++c)
1917 assert( conss[c] != 0 );
1922 *nfixedvars += nfixed;
1928 SCIPdebugMsg(scip,
"Presolving detected infeasibility.\n");
1930 else if ( *nfixedvars > noldfixedvars )
1934 else if ( nconss > 0 )
1937 SCIPdebugMsg(scip,
"Presolving via orbitopal fixing did not find anything.\n");
1948 assert( scip !=
NULL );
1949 assert( cons !=
NULL );
1950 assert( infervar !=
NULL );
1951 assert( bdchgidx !=
NULL );
1952 assert( result !=
NULL );
1971 assert( scip !=
NULL );
1972 assert( conshdlr !=
NULL );
1974 assert( cons !=
NULL );
1977 assert( consdata !=
NULL );
1978 assert( consdata->nspcons > 0 );
1979 assert( consdata->nblocks > 0 );
1980 assert( consdata->vars !=
NULL );
1982 SCIPdebugMsg(scip,
"Locking method for orbitope constraint handler\n");
1984 nspcons = consdata->nspcons;
1985 nblocks = consdata->nblocks;
1986 vars = consdata->vars;
1989 for (i = 0; i < nspcons; ++i)
1991 for (j = 0; j < nblocks; ++j)
2010 assert( scip !=
NULL );
2011 assert( conshdlr !=
NULL );
2013 assert( cons !=
NULL );
2016 assert( consdata !=
NULL );
2017 assert( consdata->nspcons > 0 );
2018 assert( consdata->nblocks > 0 );
2019 assert( consdata->vars !=
NULL );
2021 nspcons = consdata->nspcons;
2022 nblocks = consdata->nblocks;
2023 vars = consdata->vars;
2025 SCIPdebugMsg(scip,
"Printing method for orbitope constraint handler\n");
2027 if ( consdata->ispart )
2032 for (i = 0; i < nspcons; ++i)
2034 for (j = 0; j < nblocks; ++j)
2040 if ( i < nspcons-1 )
2062 assert( scip !=
NULL );
2063 assert( cons !=
NULL );
2064 assert( sourcescip !=
NULL );
2065 assert( sourceconshdlr !=
NULL );
2067 assert( sourcecons !=
NULL );
2068 assert( varmap !=
NULL );
2069 assert( valid !=
NULL );
2073 SCIPdebugMsg(scip,
"Copying method for orbitope constraint handler.\n");
2076 assert( sourcedata !=
NULL );
2077 assert( sourcedata->nspcons > 0 );
2078 assert( sourcedata->nblocks > 0 );
2079 assert( sourcedata->vars !=
NULL );
2081 nspcons = sourcedata->nspcons;
2082 nblocks = sourcedata->nblocks;
2083 sourcevars = sourcedata->vars;
2086 for (i = 0; i < nspcons && *valid; ++i)
2090 for (j = 0; j < nblocks && *valid; ++j)
2092 SCIP_CALL(
SCIPgetVarCopy(sourcescip, scip, sourcevars[i][j], &(vars[i][j]), varmap, consmap, global, valid) );
2093 assert( !(*valid) || vars[i][j] !=
NULL );
2105 vars, sourcedata->ispart, nspcons, nblocks, sourcedata->resolveprop,
2106 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
2110 assert( 0 <= i && i <= nspcons );
2111 for (k = 0; k < i; ++k)
2135 assert( success !=
NULL );
2141 while ( *s !=
'\0' && isspace((
unsigned char)*s) )
2145 if ( strncmp(s,
"partOrbitope(", 13) == 0 )
2149 if ( strncmp(s,
"packOrbitope(", 13) != 0 )
2172 while ( *s !=
'\0' && ! isspace((
unsigned char)*s) && *s !=
',' && *s !=
'.' && *s !=
')' )
2173 varname[k++] = *s++;
2184 vars[nspcons][j++] = var;
2196 if ( nblocks > maxnblocks )
2202 maxnblocks = newsize;
2205 assert( nblocks <= maxnblocks );
2208 while ( *s !=
'\0' && ( isspace((
unsigned char)*s) || *s ==
',' ) )
2217 if ( nspcons >= maxnspcons )
2223 maxnspcons = newsize;
2225 assert(nspcons < maxnspcons);
2231 while ( *s !=
')' );
2235 initial, separate, enforce, check, propagate, local, modifiable, dynamic, removable, stickingatnode) );
2237 for (k = 0; k < nspcons; ++k)
2251 assert( cons !=
NULL );
2252 assert( success !=
NULL );
2253 assert( vars !=
NULL );
2256 assert( consdata !=
NULL );
2258 if ( varssize < consdata->nblocks * consdata->nspcons )
2266 for (i = 0; i < consdata->nspcons; ++i)
2268 for (j = 0; j < consdata->nblocks; ++j)
2269 vars[cnt++] = consdata->vars[i][j];
2284 assert( cons !=
NULL );
2287 assert( consdata !=
NULL );
2289 (*nvars) = consdata->nblocks * consdata->nspcons;
2309 conshdlrdata =
NULL;
2315 consEnfolpOrbitope, consEnfopsOrbitope, consCheckOrbitope, consLockOrbitope,
2317 assert(conshdlr !=
NULL);
2382 if ( conshdlr ==
NULL )
2388 assert( nspcons > 0 );
2389 assert( nblocks > 0 );
2397 for (i = 0; i < nspcons; ++i)
2401 for (j = 0; j < nblocks; ++j)
2407 assert(var !=
NULL);
2436 SCIP_CALL(
SCIPcreateCons(scip, cons, name, conshdlr, consdata, initial, separate, enforce, check, propagate,
2437 local, modifiable, dynamic, removable, stickingatnode) );
enum SCIP_Result SCIP_RESULT
enum SCIP_BoundType SCIP_BOUNDTYPE
SCIP_Bool SCIPisFeasZero(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPsetConshdlrDelete(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSDELETE((*consdelete)))
static SCIP_DECL_CONSPARSE(consParseOrbitope)
#define SCIPallocBlockMemoryArray(scip, ptr, num)
SCIP_Real SCIPgetVarUbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
SCIP_STAGE SCIPgetStage(SCIP *scip)
static SCIP_RETCODE fixTriangle(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible, int *nfixedvars)
#define CONSHDLR_SEPAFREQ
SCIP_Bool SCIPconsIsDynamic(SCIP_CONS *cons)
SCIP_RETCODE SCIPsetConshdlrTrans(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSTRANS((*constrans)))
#define CONSHDLR_DELAYPROP
SCIP_Real SCIPgetVarLbAtIndex(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx, SCIP_Bool after)
static SCIP_DECL_CONSENFORELAX(consEnforelaxOrbitope)
SCIP_CONSHDLR * SCIPfindConshdlr(SCIP *scip, const char *name)
SCIP_Real SCIPvarGetLbGlobal(SCIP_VAR *var)
SCIP_RETCODE SCIPsetConshdlrGetVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETVARS((*consgetvars)))
static void copyValues(SCIP *scip, SCIP_CONSDATA *consdata, SCIP_SOL *sol)
SCIP_RETCODE SCIPsetConshdlrEnforelax(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSENFORELAX((*consenforelax)))
int SCIPcalcMemGrowSize(SCIP *scip, int num)
SCIP_Real SCIPvarGetLbLocal(SCIP_VAR *var)
SCIP_RETCODE SCIPaddConflictBinvar(SCIP *scip, SCIP_VAR *var)
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
#define CONSHDLR_SEPAPRIORITY
static SCIP_DECL_CONSPRESOL(consPresolOrbitope)
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)
SCIP_Real SCIPinfinity(SCIP *scip)
int SCIPsnprintf(char *t, int len, const char *s,...)
static SCIP_DECL_CONSENFOPS(consEnfopsOrbitope)
enum SCIP_Retcode SCIP_RETCODE
static SCIP_DECL_CONSGETVARS(consGetVarsOrbitope)
SCIP_RETCODE SCIPaddConflictUb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
SCIP_RETCODE SCIPaddVarLocks(SCIP *scip, SCIP_VAR *var, int nlocksdown, int nlocksup)
SCIP_Bool SCIPconsIsStickingAtNode(SCIP_CONS *cons)
SCIP_RETCODE SCIPinitConflictAnalysis(SCIP *scip, SCIP_CONFTYPE conftype, SCIP_Bool iscutoffinvolved)
#define SCIPfreeBlockMemory(scip, ptr)
SCIP_RETCODE SCIPsetConshdlrSepa(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSSEPALP((*conssepalp)), SCIP_DECL_CONSSEPASOL((*conssepasol)), int sepafreq, int sepapriority, SCIP_Bool delaysepa)
SCIP_Bool SCIPisEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
#define CONSHDLR_PROPFREQ
#define CONSHDLR_PROP_TIMING
SCIP_RETCODE SCIPcreateConsBasicOrbitope(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR ***vars, SCIP_Bool ispart, int nspcons, int nblocks, SCIP_Bool resolveprop)
#define SCIPfreeBufferArray(scip, ptr)
#define SCIPallocBlockMemory(scip, ptr)
SCIP_Bool SCIPisTransformed(SCIP *scip)
int SCIPgetNLPBranchCands(SCIP *scip)
SCIP_Bool SCIPconsIsRemovable(SCIP_CONS *cons)
static SCIP_DECL_CONSPRINT(consPrintOrbitope)
SCIP_RETCODE SCIPsetConshdlrParse(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPARSE((*consparse)))
SCIP_RETCODE SCIPincludeConshdlrOrbitope(SCIP *scip)
#define CONSHDLR_ENFOPRIORITY
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
static SCIP_DECL_CONSENFOLP(consEnfolpOrbitope)
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)
SCIP_RETCODE SCIPaddConflictLb(SCIP *scip, SCIP_VAR *var, SCIP_BDCHGIDX *bdchgidx)
static void computeSCTable(SCIP *scip, int nspcons, int nblocks, SCIP_Real **weights, int **cases, SCIP_Real **vals)
#define CONSHDLR_CHECKPRIORITY
SCIP_VAR * SCIPvarGetNegatedVar(SCIP_VAR *var)
SCIP_Bool SCIPisConflictAnalysisApplicable(SCIP *scip)
constraint handler for (partitioning/packing) orbitope constraints w.r.t. the full symmetric group ...
SCIP_VAR * SCIPfindVar(SCIP *scip, const char *name)
SCIP_Real SCIPvarGetUbGlobal(SCIP_VAR *var)
#define SCIPduplicateBlockMemoryArray(scip, ptr, source, num)
SCIP_RETCODE SCIPsetConshdlrCopy(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSHDLRCOPY((*conshdlrcopy)), SCIP_DECL_CONSCOPY((*conscopy)))
const char * SCIPconshdlrGetName(SCIP_CONSHDLR *conshdlr)
SCIP_Bool SCIPisLT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE resolvePropagation(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *infervar, int inferinfo, SCIP_BOUNDTYPE boundtype, SCIP_BDCHGIDX *bdchgidx, SCIP_RESULT *result)
#define CONSHDLR_NEEDSCONS
SCIP_Bool SCIPisEfficacious(SCIP *scip, SCIP_Real efficacy)
const char * SCIPconsGetName(SCIP_CONS *cons)
SCIP_RETCODE SCIPmarkDoNotMultaggrVar(SCIP *scip, SCIP_VAR *var)
SCIP_Bool SCIPconsIsPropagated(SCIP_CONS *cons)
const char * SCIPvarGetName(SCIP_VAR *var)
static SCIP_RETCODE separateSCIs(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS *cons, SCIP_CONSDATA *consdata, SCIP_Bool *infeasible, int *nfixedvars, int *ncuts)
static SCIP_DECL_CONSCOPY(consCopyOrbitope)
SCIP_Bool SCIPisSumEQ(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_DECL_CONSPROP(consPropOrbitope)
SCIP_RETCODE SCIPanalyzeConflictCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *success)
void SCIPverbMessage(SCIP *scip, SCIP_VERBLEVEL msgverblevel, FILE *file, const char *formatstr,...)
SCIP_Bool SCIPconsIsLocal(SCIP_CONS *cons)
static SCIP_DECL_CONSSEPASOL(consSepasolOrbitope)
SCIP_RETCODE SCIPsetConshdlrResprop(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSRESPROP((*consresprop)))
SCIP_RETCODE SCIPaddCut(SCIP *scip, SCIP_SOL *sol, SCIP_ROW *cut, SCIP_Bool forcecut, SCIP_Bool *infeasible)
struct SCIP_ConsData SCIP_CONSDATA
#define SCIPallocBufferArray(scip, ptr, num)
static SCIP_DECL_CONSHDLRCOPY(conshdlrCopyOrbitope)
SCIP_RETCODE SCIPcreateEmptyRowCons(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)
static SCIP_DECL_CONSDELETE(consDeleteOrbitope)
SCIP_Bool SCIPconsIsChecked(SCIP_CONS *cons)
#define CONSHDLR_PRESOLTIMING
SCIP_Bool SCIPconsIsInitial(SCIP_CONS *cons)
SCIP_RETCODE SCIPcreateConsOrbitope(SCIP *scip, SCIP_CONS **cons, const char *name, SCIP_VAR ***vars, SCIP_Bool ispart, int nspcons, int nblocks, SCIP_Bool resolveprop, SCIP_Bool initial, SCIP_Bool separate, SCIP_Bool enforce, SCIP_Bool check, SCIP_Bool propagate, SCIP_Bool local, SCIP_Bool modifiable, SCIP_Bool dynamic, SCIP_Bool removable, SCIP_Bool stickingatnode)
SCIP_Real SCIPvarGetObj(SCIP_VAR *var)
SCIP_RETCODE SCIPfixVar(SCIP *scip, SCIP_VAR *var, SCIP_Real fixedval, SCIP_Bool *infeasible, SCIP_Bool *fixed)
SCIP_RETCODE SCIPsetConshdlrPrint(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRINT((*consprint)))
static SCIP_DECL_CONSLOCK(consLockOrbitope)
SCIP_Bool SCIPisInfinity(SCIP *scip, SCIP_Real val)
SCIP_Bool SCIPinProbing(SCIP *scip)
static SCIP_RETCODE propagateCons(SCIP *scip, SCIP_CONS *cons, SCIP_Bool *infeasible, int *nfixedvars)
static SCIP_DECL_CONSTRANS(consTransOrbitope)
static SCIP_DECL_CONSCHECK(consCheckOrbitope)
SCIP_RETCODE SCIPreleaseRow(SCIP *scip, SCIP_ROW **row)
SCIP_Bool SCIPisGT(SCIP *scip, SCIP_Real val1, SCIP_Real val2)
static SCIP_RETCODE separateConstraints(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_CONS **conss, int nconss, int nusefulconss, SCIP_SOL *sol, SCIP_RESULT *result)
SCIP_Bool SCIPisIntegral(SCIP *scip, SCIP_Real val)
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)
SCIP_CONSDATA * SCIPconsGetData(SCIP_CONS *cons)
SCIP_Bool SCIPallowDualReds(SCIP *scip)
#define CONSHDLR_MAXPREROUNDS
SCIP_RETCODE SCIPsetConshdlrPresol(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPRESOL((*conspresol)), int maxprerounds, SCIP_PRESOLTIMING presoltiming)
SCIP_Bool SCIPconsIsModifiable(SCIP_CONS *cons)
SCIP_RETCODE SCIPaddVarsToRow(SCIP *scip, SCIP_ROW *row, int nvars, SCIP_VAR **vars, SCIP_Real *vals)
SCIP_RETCODE SCIPsetConshdlrGetNVars(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSGETNVARS((*consgetnvars)))
SCIP_Bool SCIPconsIsEnforced(SCIP_CONS *cons)
static SCIP_RETCODE consdataFree(SCIP *scip, SCIP_CONSDATA **consdata)
SCIP_Bool SCIPconsIsSeparated(SCIP_CONS *cons)
SCIP_VARTYPE SCIPvarGetType(SCIP_VAR *var)
SCIP_Bool SCIPisZero(SCIP *scip, SCIP_Real val)
struct SCIP_ConshdlrData SCIP_CONSHDLRDATA
static SCIP_DECL_CONSRESPROP(consRespropOrbitope)
SCIP_Real SCIPvarGetUbLocal(SCIP_VAR *var)
static SCIP_DECL_CONSGETNVARS(consGetNVarsOrbitope)
#define SCIPfreeBlockMemoryArrayNull(scip, ptr, num)
SCIP_Bool SCIPisFeasIntegral(SCIP *scip, SCIP_Real val)
SCIP_Real SCIPgetSolVal(SCIP *scip, SCIP_SOL *sol, SCIP_VAR *var)
#define CONSHDLR_EAGERFREQ
SCIP_RETCODE SCIPinferBinvarCons(SCIP *scip, SCIP_VAR *var, SCIP_Bool fixedval, SCIP_CONS *infercons, int inferinfo, SCIP_Bool *infeasible, SCIP_Bool *tightened)
static SCIP_RETCODE consdataCreate(SCIP *scip, SCIP_CONSDATA **consdata, SCIP_VAR ***vars, int nspcons, int nblocks, SCIP_Bool ispart, SCIP_Bool resolveprop)
#define CONSHDLR_DELAYSEPA
static SCIP_DECL_CONSSEPALP(consSepalpOrbitope)
SCIP_Bool SCIPvarIsNegated(SCIP_VAR *var)
#define SCIPreallocBufferArray(scip, ptr, num)
SCIP_RETCODE SCIPsetConshdlrProp(SCIP *scip, SCIP_CONSHDLR *conshdlr, SCIP_DECL_CONSPROP((*consprop)), int propfreq, SCIP_Bool delayprop, SCIP_PROPTIMING proptiming)