Changeset 967 for trunk

Timestamp:

Jun 24, 2013 6:13:05 AM (6 years ago)

Author:

fmargot

Message:

fix bug in checkNLP2 and handling of non-var objects in strong branching

Location:

trunk/Couenne/src

Files:

• branch/CouenneChooseStrong.cpp (modified) (16 diffs)
• problem/checkNLP.cpp (modified) (6 diffs)

trunk/Couenne/src/branch/CouenneChooseStrong.cpp

@@ -99 +99 @@
 
 /***********************************************************************/
+// returns
+// 4 if not a variable object (deemed good)
+// 3 if variable object and is good
+// 2 if variable object and is not good (i.e. fixed variable)
+// 1 if OsiSimpleBranchingObject and not good (deprecated)
 int CouenneChooseStrong::goodCandidate(OsiSolverInterface *solver,
                                        OsiBranchingInformation *info,
@@ -106 +111 @@
   int vInd = object [iObject] -> columnNumber ();
 
-  if (vInd < 0) return 3;  // not a variable object, so deem it good
+  if (vInd < 0) return 4;  // not a variable object, so deem it good
 
   bool varIsInt = solver -> isInteger (vInd);
@@ -211 +216 @@
      We can pick up a forced branch (can change bound) from whichForcedObject() and whichForcedWay()
      If we have a solution then we can pick up from goodObjectiveValue() and goodSolution()
+
+Note: Must not return 4 for a non variable object
   */
   int CouenneChooseStrong::chooseVariable (OsiSolverInterface * solver,
@@ -255 +262 @@
 
     if (isRoot) {
-      numberStrong = CoinMax(numberStrong_, numberStrongRoot_);
+      numberStrong = numberStrongRoot_;
     }
 
@@ -272 +279 @@
 
       results_.clear();
-      int returnCode = 0;
+
+      // All look satisfied;
+      //useful if all objects considered for strong branching use pseudo costs
+      int returnCode = 1;
+
       int returnCodeSB = 0;
       bestObjectIndex_ = -1;
@@ -466 +477 @@
             }
 
-            if((needBranch == 3) &&
+            if((needBranch >= 3) &&
                saveBestCand(object, iObject, value, upEstimate, downEstimate,
                             bestTrustedVal1, 
@@ -546 +557 @@
           
           // store bad candidates in secondary best
-          if(needBranch != 3) {
+          if(needBranch < 3) {
             if(saveBestCand(object, iObject, value, 
                             upEstimate, downEstimate,
@@ -566 +577 @@
                             bestTrustedVal1, 
                             bestTrustedVal2, bestObjectIndex_, bestWhichWay_)) {
+              if(returnCode == 1) { // first saved object
+                                    // is using pseudo-cost
+                returnCode = 0;
+              }
+
               returnCode = (returnCode ? 3 : 0); // if returnCode was 2 or 3
                                                  // it becomes 3
@@ -582 +598 @@
           bestWhichWay_ = bestWhichWay2;
           bestTrustedVal1 = bestTrusted2Val1;
-          returnCode = 4;
+          if(goodCandidate(solver, info, object,  
+                           bestObjectIndex_, prec) != 4) {
+            returnCode = 4;
+          }
+          else {
+            returnCode = 3;
+          }
         }
       }
@@ -604 +626 @@
           if(objectVarInd >= 0) {
             double vUb = solver->getColUpper()[objectVarInd];
-            double vLb = solver->getColLower()[objectVarInd];
+            char strUb[400], strLb[400];
+            if(vUb > 1e50) {
+              sprintf(strUb, "+inf");
+            }
+            else {
+              sprintf(strUb, "%f", vUb);
+            }
+            double vLb = solver->getColLower()[objectVarInd];
+            if(vLb < -1e50) {
+              sprintf(strLb, "-inf");
+            }
+            else {
+              sprintf(strLb, "%f", vLb);
+            }
             double vSolI = info->solution_[objectVarInd];
             double vSolS = solver->getColSolution()[objectVarInd];
-            printf("Branch on object %d (var: %d): solInfo: %10.4f  SolSolver: %10.4f low: %10.4f  up: %10.4f\n",
-                   bestObjectIndex_, objectVarInd, vSolI, vSolS, vLb, vUb);
+            printf("Branch on object %d (var: %d): solInfo: %10.4f  SolSolver: %10.4f low: %s  up: %s\n",
+                   bestObjectIndex_, objectVarInd, vSolI, vSolS, strLb, strU
+
+b);
           }
           else {
@@ -618 +655 @@
       message(CHOSEN_VAR)<<bestObjectIndex_<<CoinMessageEol;
     
-      if (numberFixed==numberUnsatisfied_&&numberFixed)
-        returnCode=4;
+      if((numberFixed==numberUnsatisfied_&&numberFixed) &&
+         (goodCandidate(solver, info, object, bestObjectIndex_, prec) != 4)) {
+        returnCode = 4;
+      }
 
       if((returnCode == 2) || (returnCode == 3)) {
         if((objectVarInd > -1) && 
-           (goodCandidate(solver, info, object, bestObjectIndex_, prec) != 2)) {
+           (goodCandidate(solver, info, object, bestObjectIndex_, prec) != 4)) {
           // Can occur: two objects for same var, first scanned object
           // has both branches feasible and is saved as bestObjectIndex_,
@@ -703 +742 @@
 
 #ifdef TRACE_STRONG
+    printf("Start CouenneChooseStrong::setupList()\n");
     OsiObject ** object = info->solver_->objects();
     if(problem_->doPrint_) {
@@ -759 +799 @@
 #ifdef TRACE_STRONG
     if(problem_->doPrint_) {
-      printf("Strong list: (obj_ind var_ind priority useful)\n");
+      printf("Strong list: (obj_ind var_ind priority useful viol)\n");
       printf("numberStrong: %d  numberStrongRoot: %d  retval: %d\n", 
              numberStrong_, numberStrongRoot_, retval);
@@ -769 +809 @@
         // }
         // else {
-          objectInd = object[list_[i]]->columnNumber();
+        objectInd = object[list_[i]]->columnNumber();
         // }
-        printf(" (%d %d %d %6.4f)", list_[i], objectInd, 
-               object[list_[i]]->priority(), useful_[i]);
-      }
-      printf("\n");
-    }
+
+        int wayprint;
+        double violprint = object[list_[i]]->infeasibility(info, wayprint);
+        if(violprint < COIN_DBL_MAX / 100) {
+          printf(" (%d %d %d %6.4f %6.4f)", list_[i], objectInd, 
+                 object[list_[i]]->priority(), useful_[i], 
+                 violprint);
+        }
+        else {
+          printf(" (%d %d %d %6.4f +inf)", list_[i], objectInd, 
+                 object[list_[i]]->priority(), useful_[i]);
+        }
+        printf("\n");
+      }
 #endif
 
@@ -785 +834 @@
     jnlst_ -> Printf (J_ITERSUMMARY, J_BRANCHING, 
                       "----------------- (strong) setup list done - %d infeasibilities\n", retval);
+
+#if (defined TRACE_STRONG)
+    printf("Done CouenneChooseStrong::setupList()\n");
+#endif
 
     problem_ -> domain () -> pop ();
@@ -876 +929 @@
     }
     printf("\nmaxViol: %g  minPosViol: %g\n", maxViol, minPosViol);
-
   } /* printObjViol */
 

trunk/Couenne/src/problem/checkNLP.cpp

@@ -419 +419 @@
 
       double 
-        v = (*(variables_ [i])) (), 
-        f = (*(variables_ [i] -> Image ())) ();
-
-      printf ("[%g,%g]\n", v, f);
-
-      printf ("checking aux -- %+.12e = %+.12e [%+.12e] ", v, f, v-f);
-      variables_ [i] -> print ();             printf (" := ");
+        vdb = (*(variables_ [i])) (), 
+        fdb = (*(variables_ [i] -> Image ())) ();
+
+      double
+        del = 
+        ((v -> sign () == expression::AUX_GEQ) && (vdb >= fdb)) ? 0. : 
+        ((v -> sign () == expression::AUX_LEQ) && (vdb <= fdb)) ? 0. : 
+        fabs (vdb - fdb);
+
+      printf ("[%g,%g]\n", vdb, fdb);
+
+      printf ("checking aux -- %+.12e = %+.12e [%+.12e] ", vdb, fdb, del);
+      variables_ [i] -> print ();
+      if(v->sign()== expression::AUX_GEQ) printf(" >= ");
+      if(v->sign()== expression::AUX_LEQ) printf(" <= ");
+      if(v->sign()== expression::AUX_EQ) printf(" := ");
       variables_ [i] -> Image () -> print (); printf ("\n");
     }
@@ -629 +638 @@
     for (int i=0; i<nOrigVars_ - ndefined_; i++)
       printf ("%.12e ", solution [i]);
-    printf ("\nCouenneProblem::checkNLP2(): Start checking computed_solution\n");
+    printf ("\nCouenneProblem::checkNLP2(): Start checking recomputed_solution\n");
   }
 
@@ -642 +651 @@
 
   if (stopAtFirstViol && !isFeasRec && Jnlst () -> ProduceOutput (Ipopt::J_ALL, J_PROBLEM)) 
-    printf("CouenneProblem::checkNLP2(): modified_solution is infeasible (some orig vars not integer feasible; violation: %12.10g)\n", maxViolRecSol);
+    printf("CouenneProblem::checkNLP2(): recomputed_solution is infeasible (some orig vars not integer feasible; violation: %12.10g)\n", maxViolRecSol);
 
 #ifdef CHECK
@@ -659 +668 @@
   // install NL solution candidate and original bounds in evaluation structure
   // bounds are important so that getAuxs below works properly
-  domain_.push(nVars(), domain_.x(), getRecordBestSol()->getInitDomLb(), 
+  domain_.push(nVars(), solution, getRecordBestSol()->getInitDomLb(), 
                getRecordBestSol()->getInitDomUb(), false);
 
@@ -678 +687 @@
     double maxDelta = 0;
     for (int i=0; i<nVars (); i++) {
-      printf ("%4d %+e %+e [%+e %+e] %+e\n", i, solution[i], domain_.x (i), domain_.lb (i), domain_.ub (i), solution[i] - domain_.x (i));
-      if (maxDelta < fabs(solution[i] - domain_.x(i))) maxDelta = fabs (solution[i] - domain_.x(i));
-    }
-    printf ("maxDelta: %.12g\n", maxDelta);
+      exprVar *v = variables_ [i];
+      if (v -> Multiplicity () <= 0) 
+        continue;
+      if(i < nOrigVars_ - ndefined_) {
+        double soli = solution[i];
+        double domi = domain_.x (i);
+        double domlbi = domain_.lb (i);
+        double domubi = domain_.ub (i);
+        printf ("%4d %+e %+e [%+e %+e] %+e\n", i, solution[i], domain_.x (i), domain_.lb (i), domain_.ub (i), solution[i] - domain_.x (i));
+        if (maxDelta < fabs(solution[i] - domain_.x(i))) maxDelta = fabs (solution[i] - domain_.x(i));
+      }
+      else {
+        if(v -> Type() == AUX) {
+          printf ("%4d  ------     %+e [%+e %+e]\n", i, domain_.x (i), domain_.lb (i), domain_.ub (i));
+        }
+      }
+      printf ("maxDelta: %.12g\n", maxDelta);
+    }
   }
 
@@ -912 +935 @@
       // printf ("]\n");
 
-      printf ("checkNLP2(): RETURN: selected solution is feasible (maxViol: %g)\n", maxViol);
+      printf ("checkNLP2(): RETURN: feasible (maxViol: %g)\n", maxViol);
     }
     else {
-      printf ("checkNLP2(): RETURN: modified_solution and solution are infeasible\n");
+      printf ("checkNLP2(): RETURN: recomputed_solution and solution are infeasible\n");
       if(!stopAtFirstViol) {
         printf("(maxViol: %g)\n", maxViol);