Conflict graph-based algorithms

[Rolf527]

I came across a very interesting and promising 2021 paper by Brito and Santos titled "Preprocessing and Cutting Planes with Conflict Graphs". This paper discusses the integration of conflict graph-based algorithms and data structures into CBC.

Could anyone clarify whether these features are already implemented in CBC 2.10.12?

Thanks in advance for your help!

[svigerske]

No. This is on branch master only.

[h-g-s]

W.r.t. to this, pushed some recent improvements for the code.

The code should detect more conflicts now as constraints including other types of variables (not only binary) are also processed.

One usability improvement for explaining infeasible models is that, when two different constraints imply a different bound for a given binary variable we'll report the contradictory constraints.

Doing some additional tests to check if everything is ok.

[jjhforrest]

Nothing to do with recent changes, but I found that with some optimization levels (and maybe cpu) tests using -
std::numeric_limits< double >::quiet_NaN() were failing (this is used in CoinKnapsackRow.cpp). Apparently treatment of nan varies.
This showed up solving miplib3/pk1 which got wrong result.

These are the changes I suggest - which fix the problem. I will put them in master if nobody comes up with a better solution.

--- a/src/CoinDynamicConflictGraph.cpp
+++ b/src/CoinDynamicConflictGraph.cpp
@@ -51,7 +51,13 @@
 #define CGRAPH_DEEP_DIVE_COLUMN_NAME "C1583"
 #define CGRAPH_DEEP_DIVE_ROW_INDEX 6849
 #endif // CGRAPH_DEEP_DIVE
-
+// Tests involving nan seem to fail with some optimizations and cpu's
+// This should be safe
+inline bool isGoodNumber(double rhs)
+{
+  return (rhs<=std::numeric_limits<double>::max()&&
+	  rhs>=std::numeric_limits<double>::min());
+}
 /**
  * @brief Locates the earliest column index that must belong to a clique.
  *
@@ -198,7 +204,7 @@ CoinDynamicConflictGraph::CoinDynamicConflictGraph(
       const double *twoLargest = knapsackRow.twoLargest();
       const double *twoSmallest = knapsackRow.twoSmallest();
 
-      if ((nz <= 1) || (twoLargest[0] + twoLargest[1] <= rhs + primalTolerance)) {
+      if ((nz <= 1) || (twoLargest[0] + twoLargest[1] <= rhs + primalTolerance) || !isGoodNumber(rhs)) {
         continue; // no conflicts to search here
       }
 
@@ -226,7 +232,9 @@ CoinDynamicConflictGraph::CoinDynamicConflictGraph(
 
   // detecting cliques in less-structured constraints
   for (size_t idxTR = 0; (idxTR < tRowElements.size()); ++idxTR) {
-    cliqueDetection(tRowElements[idxTR], tRowElements[idxTR].size(), tRowRHS[idxTR] + primalTolerance);
+    double rhs = tRowRHS[idxTR];
+    if (isGoodNumber(rhs))
+      cliqueDetection(tRowElements[idxTR], tRowElements[idxTR].size(), rhs + primalTolerance);
   }
 

[svigerske]

std::isfinite() may do the same as isGoodNumber()?

[jjhforrest]

It should have but did not!