Ignore:
Timestamp:
Jul 16, 2014 5:29:16 AM (5 years ago)
Author:
forrest
Message:

First try at orbital branching

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/Cbc/src/CbcNode.cpp

    r2040 r2048  
    1010
    1111#include "CbcConfig.h"
     12#ifdef COIN_HAS_NTY
     13#include "CbcSymmetry.hpp"
     14#endif
    1215//#define DEBUG_SOLUTION
    1316#ifdef DEBUG_SOLUTION
     
    19561959    choice.possibleBranch = choiceObject;
    19571960    numberPassesLeft = CoinMax(numberPassesLeft, 2);
     1961#ifdef COIN_HAS_NTY
     1962    // 1 after, 2 strong, 3 subset
     1963    int orbitOption = (model->moreSpecialOptions2()&(128|256))>>7;
     1964#endif
    19581965    //#define DEBUG_SOLUTION
    19591966#ifdef DEBUG_SOLUTION
     
    28152822            }
    28162823#endif
     2824#ifdef COIN_HAS_NTY
     2825            const int * orbits = NULL;
     2826#endif
     2827#ifdef COIN_HAS_NTY
     2828            if (orbitOption>1) {
     2829              CbcSymmetry * symmetryInfo = model->symmetryInfo();
     2830              CbcNodeInfo * infoX = lastNode ? lastNode->nodeInfo() : NULL;
     2831              bool worthTrying = false;
     2832              if (infoX) {
     2833                CbcNodeInfo * info = infoX;
     2834                for (int i=0;i<NTY_BAD_DEPTH;i++) {
     2835                  if (!info->parent()) {
     2836                    worthTrying = true;
     2837                    break;
     2838                  }
     2839                  info = info->parent();
     2840                  if (info->symmetryWorked()) {
     2841                    worthTrying = true;
     2842                    break;
     2843                  }
     2844                }
     2845              } else {
     2846                worthTrying=true;
     2847              }
     2848              if (symmetryInfo && worthTrying) {
     2849                symmetryInfo->ChangeBounds(solver->getColLower(),
     2850                                            solver->getColUpper(),
     2851                                            solver->getNumCols(),false);
     2852                symmetryInfo->Compute_Symmetry();
     2853                symmetryInfo->fillOrbits();
     2854                orbits = symmetryInfo->whichOrbit();
     2855                int iColumn=-1;
     2856                if (orbits && symmetryInfo->numberUsefulObjects()) {
     2857                  bool doBranch=true;
     2858                  int numberUsefulOrbits = symmetryInfo->numberUsefulObjects();
     2859                  if (numberUsefulOrbits<2) {
     2860                    assert (numberUsefulOrbits);
     2861                    double largest=-1.0;
     2862                    for (int i=0;i<numberColumns;i++) {
     2863                      if (orbits[i]>=0) {
     2864                        if (saveSolution[i]>largest) {
     2865                          largest=saveSolution[i];
     2866                          iColumn=i;
     2867                        }
     2868                      }
     2869                    }
     2870                  } else {
     2871#if COIN_HAS_NTY2 == 1
     2872                    // take largest
     2873                    int iOrbit=symmetryInfo->largestOrbit(solver->getColLower(),
     2874                                                          solver->getColUpper());
     2875                    double largest=-1.0;
     2876                    for (int i=0;i<numberColumns;i++) {
     2877                      if (orbits[i]==iOrbit) {
     2878                        if (saveSolution[i]>largest) {
     2879                          largest=saveSolution[i];
     2880                          iColumn=i;
     2881                        }
     2882                      }
     2883                    }
     2884#endif
     2885                    if (orbitOption==2) {
     2886                      // strong
     2887                      int nDo=0;
     2888                      const double * lower = solver->getColLower();
     2889                      const double * upper = solver->getColUpper();
     2890                      for (int iOrbit = 0; iOrbit < numberUsefulOrbits; iOrbit++) {
     2891                        double distance=1.0;
     2892                        int iColumn = -1;
     2893                        for (int i=0;i<numberColumns;i++) {
     2894                          if (orbits[i]==iOrbit &&lower[i]==0.0&&upper[i]==1.0) {
     2895                            double away = fabs(saveSolution[i]-0.5);
     2896                            if (away<distance&&away<0.4999) {
     2897                              distance=away;
     2898                              iColumn=i;
     2899                            }
     2900                          }
     2901                        }
     2902                        if (iColumn>=0)
     2903                          whichObject[nDo++]=iColumn;
     2904                      }
     2905                      if (nDo)
     2906                        numberToDo=nDo;
     2907                      doBranch=false;
     2908                    } else if (orbitOption==3) {
     2909                      // subset
     2910                      int nDo=0;
     2911                      for (int iDo = 0; iDo < numberToDo; iDo++) {
     2912                        int iObject = whichObject[iDo];
     2913                        OsiObject * object = model->modifiableObject(iObject);
     2914                        CbcSimpleIntegerDynamicPseudoCost * dynamicObject =
     2915                          dynamic_cast <CbcSimpleIntegerDynamicPseudoCost *>(object) ;
     2916                        int iColumn = dynamicObject ? dynamicObject->columnNumber() : -1;
     2917                        if (iColumn<0||orbits[iColumn]>=0)
     2918                          whichObject[nDo++]=whichObject[iDo];
     2919                      }
     2920                      assert(nDo);
     2921                      //printf("nDo %d\n",nDo);
     2922                      numberToDo=nDo;
     2923                      doBranch=false;
     2924                      /* need NULL as if two in same orbit and strong branching fixes
     2925                         then we may be in trouble.
     2926                         Strong option should be OK as only one in set done.
     2927                       */
     2928                      orbits=NULL;
     2929                    }
     2930                  }
     2931                  if(doBranch) {
     2932                    orbitOption=0;
     2933                    branch_ = new CbcOrbitalBranchingObject(model,iColumn,1,0,NULL);
     2934                    if (infoX)
     2935                      infoX->setSymmetryWorked();
     2936                    numberToDo=0;
     2937                  }
     2938                }
     2939              }
     2940            }
     2941#endif
    28172942            for ( iDo = 0; iDo < numberToDo; iDo++) {
    28182943                int iObject = whichObject[iDo];
     
    28622987                  choice.downMovement = 0.1;
    28632988                }
    2864                   assert (choice.upMovement >= 0.0);
    2865                   assert (choice.downMovement >= 0.0);
     2989                assert (choice.upMovement >= 0.0);
     2990                assert (choice.downMovement >= 0.0);
    28662991                choice.fix = 0; // say not fixed
    28672992                // see if can skip strong branching
     
    29163041                    choice.possibleBranch->way(-1) ;
    29173042                    predictedChange = choice.possibleBranch->branch() ;
     3043#ifdef COIN_HAS_NTY
     3044                    if (orbits) {
     3045                      // can fix all in orbit
     3046                      int fixOrbit = orbits[iObject];
     3047                      if (fixOrbit>=0) {
     3048                        //printf("fixing all in orbit %d for column %d\n",fixOrbit,iObject);
     3049                        for (int i=0;i<numberColumns;i++) {
     3050                          if (orbits[i]==fixOrbit)
     3051                            solver->setColUpper(i,0.0);
     3052                        }
     3053                      }
     3054                    }
     3055#endif
    29183056                    solver->solveFromHotStart() ;
    29193057                    bool needHotStartUpdate = false;
     
    36933831      }
    36943832    }
     3833#ifdef COIN_HAS_NTY
     3834    if (orbitOption&&kColumn>=0) {
     3835      CbcSymmetry * symmetryInfo = model->symmetryInfo();
     3836      CbcNodeInfo * infoX = lastNode ? lastNode->nodeInfo() : NULL;
     3837      bool worthTrying = false;
     3838      if (infoX) {
     3839        CbcNodeInfo * info = infoX;
     3840        for (int i=0;i<NTY_BAD_DEPTH;i++) {
     3841          if (!info->parent()) {
     3842            worthTrying = true;
     3843            break;
     3844          }
     3845          info = info->parent();
     3846          if (info->symmetryWorked()) {
     3847            worthTrying = true;
     3848            break;
     3849          }
     3850        }
     3851      } else {
     3852        worthTrying=true;
     3853      }
     3854      if (symmetryInfo && worthTrying) {
     3855        if (orbitOption==1) {
     3856          symmetryInfo->ChangeBounds(solver->getColLower(),
     3857                                     solver->getColUpper(),
     3858                                     solver->getNumCols(),false);
     3859          symmetryInfo->Compute_Symmetry();
     3860          symmetryInfo->fillOrbits();
     3861        }
     3862        const int * orbits = symmetryInfo->whichOrbit();
     3863        if (orbits && orbits[kColumn]>=0) {
     3864          int numberUsefulOrbits = symmetryInfo->numberUsefulObjects();
     3865          if (numberUsefulOrbits<1000) {
     3866            delete branch_;
     3867            branch_ = new CbcOrbitalBranchingObject(model,kColumn,1,0,NULL);
     3868            if (infoX)
     3869              infoX->setSymmetryWorked();
     3870          }
     3871        }
     3872      }
     3873    }
     3874#endif
    36953875    if (model->logLevel()>1)
    36963876    printf ("Node %d depth %d unsatisfied %d sum %g obj %g guess %g branching on %d\n",
Note: See TracChangeset for help on using the changeset viewer.