source: trunk/Cbc/src/CbcClique.cpp

Last change on this file was 2467, checked in by unxusr, 6 months ago

spaces after angles

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 27.4 KB
Line 
1// $Id: CbcClique.cpp 2467 2019-01-03 21:26:29Z tkr $
2// Copyright (C) 2002, International Business Machines
3// Corporation and others.  All Rights Reserved.
4// This code is licensed under the terms of the Eclipse Public License (EPL).
5
6// Edwin 11/9/2009-- carved out of CbcBranchActual
7
8#if defined(_MSC_VER)
9// Turn off compiler warning about long names
10#pragma warning(disable : 4786)
11#endif
12#include <cassert>
13#include <cstdlib>
14#include <cmath>
15#include <cfloat>
16//#define CBC_DEBUG
17
18#include "CoinTypes.hpp"
19#include "OsiSolverInterface.hpp"
20#include "OsiSolverBranch.hpp"
21#include "CbcModel.hpp"
22#include "CbcMessage.hpp"
23#include "CbcClique.hpp"
24#include "CbcBranchActual.hpp"
25#include "CoinSort.hpp"
26#include "CoinError.hpp"
27//##############################################################################
28
29// Default Constructor
30CbcClique::CbcClique()
31  : CbcObject()
32  , numberMembers_(0)
33  , numberNonSOSMembers_(0)
34  , members_(NULL)
35  , type_(NULL)
36  , cliqueType_(-1)
37  , slack_(-1)
38{
39}
40
41// Useful constructor (which are integer indices)
42CbcClique::CbcClique(CbcModel *model, int cliqueType, int numberMembers,
43  const int *which, const char *type, int identifier, int slack)
44  : CbcObject(model)
45{
46  numberMembers_ = numberMembers;
47  int *backward = NULL;
48  if (identifier < 0) {
49    // which are variables in model - not in integers
50    identifier = -identifier;
51    int numberColumns = model->getNumCols();
52    int numberIntegers = model->numberIntegers();
53    const int *integerVariable = model->integerVariable();
54    backward = new int[numberColumns];
55    for (int i = 0; i < numberColumns; i++)
56      backward[i] = -1;
57    for (int i = 0; i < numberIntegers; i++) {
58      backward[integerVariable[i]] = i;
59    }
60  }
61  if (numberMembers_) {
62    members_ = new int[numberMembers_];
63    memcpy(members_, which, numberMembers_ * sizeof(int));
64    if (backward) {
65      for (int i = 0; i < numberMembers_; i++) {
66        int iColumn = which[i];
67        iColumn = backward[iColumn];
68        assert(iColumn >= 0);
69        members_[i] = iColumn;
70#ifdef FULL_PRINT
71        printf("%d column %d member %d\n", i, which[i], iColumn);
72#endif
73      }
74    }
75    type_ = new char[numberMembers_];
76    if (type) {
77      memcpy(type_, type, numberMembers_ * sizeof(char));
78    } else {
79      for (int i = 0; i < numberMembers_; i++)
80        type_[i] = 1;
81    }
82  } else {
83    members_ = NULL;
84    type_ = NULL;
85  }
86  // Find out how many non sos
87  int i;
88  numberNonSOSMembers_ = 0;
89  for (i = 0; i < numberMembers_; i++)
90    if (!type_[i])
91      numberNonSOSMembers_++;
92  cliqueType_ = cliqueType;
93  slack_ = slack;
94  delete[] backward;
95  id_ = identifier;
96}
97
98// Copy constructor
99CbcClique::CbcClique(const CbcClique &rhs)
100  : CbcObject(rhs)
101{
102  numberMembers_ = rhs.numberMembers_;
103  numberNonSOSMembers_ = rhs.numberNonSOSMembers_;
104  if (numberMembers_) {
105    members_ = new int[numberMembers_];
106    memcpy(members_, rhs.members_, numberMembers_ * sizeof(int));
107    type_ = new char[numberMembers_];
108    memcpy(type_, rhs.type_, numberMembers_ * sizeof(char));
109  } else {
110    members_ = NULL;
111    type_ = NULL;
112  }
113  cliqueType_ = rhs.cliqueType_;
114  slack_ = rhs.slack_;
115}
116
117// Clone
118CbcObject *
119CbcClique::clone() const
120{
121  return new CbcClique(*this);
122}
123
124// Assignment operator
125CbcClique &
126CbcClique::operator=(const CbcClique &rhs)
127{
128  if (this != &rhs) {
129    CbcObject::operator=(rhs);
130    delete[] members_;
131    delete[] type_;
132    numberMembers_ = rhs.numberMembers_;
133    numberNonSOSMembers_ = rhs.numberNonSOSMembers_;
134    if (numberMembers_) {
135      members_ = new int[numberMembers_];
136      memcpy(members_, rhs.members_, numberMembers_ * sizeof(int));
137      type_ = new char[numberMembers_];
138      memcpy(type_, rhs.type_, numberMembers_ * sizeof(char));
139    } else {
140      members_ = NULL;
141      type_ = NULL;
142    }
143    cliqueType_ = rhs.cliqueType_;
144    slack_ = rhs.slack_;
145  }
146  return *this;
147}
148
149// Destructor
150CbcClique::~CbcClique()
151{
152  delete[] members_;
153  delete[] type_;
154}
155/*
156  Unfortunately, that comment is untrue. And there are other issues. This
157  routine is clearly an unfinished work.
158*/
159double
160CbcClique::infeasibility(const OsiBranchingInformation * /*info*/,
161  int &preferredWay) const
162{
163  int numberUnsatis = 0, numberFree = 0;
164  int j;
165  const int *integer = model_->integerVariable();
166  OsiSolverInterface *solver = model_->solver();
167  const double *solution = model_->testSolution();
168  const double *lower = solver->getColLower();
169  const double *upper = solver->getColUpper();
170  double largestValue = 0.0;
171  double integerTolerance = model_->getDblParam(CbcModel::CbcIntegerTolerance);
172  double *sort = new double[numberMembers_];
173  /*
174      Calculate integer infeasibility and fill an array. Pick off the infeasibility
175      of the slack and the max infeasibility while we're at it. You can see here
176      the conversion of `non-SOS' (strong value of 0, negative coefficient) to
177      `SOS' (strong value of 1, positive coefficient). Also count the number of
178      variables that have integral values but are not fixed.
179    */
180  double slackValue = 0.0;
181  for (j = 0; j < numberMembers_; j++) {
182    int sequence = members_[j];
183    int iColumn = integer[sequence];
184    double value = solution[iColumn];
185    value = CoinMax(value, lower[iColumn]);
186    value = CoinMin(value, upper[iColumn]);
187    double nearest = floor(value + 0.5);
188    double distance = fabs(value - nearest);
189    if (distance > integerTolerance) {
190      if (!type_[j])
191        value = 1.0 - value; // non SOS
192      // if slack then choose that
193      if (j == slack_ && value > 0.05)
194        slackValue = value;
195      largestValue = CoinMax(value, largestValue);
196      sort[numberUnsatis++] = -value;
197    } else if (upper[iColumn] > lower[iColumn]) {
198      numberFree++;
199    }
200  }
201  /*
202      preferredWay will not change. The calculation of otherWay is an expensive
203      noop --- value is ultimately unused. Same for the sort of sort. It looks like
204      there was some notion of branching by splitting the set using even and odd
205      indices (as opposed to first and second half).
206    */
207  preferredWay = 1;
208  double otherWay = 0.0;
209  if (numberUnsatis) {
210    // sort
211    std::sort(sort, sort + numberUnsatis);
212    for (j = 0; j < numberUnsatis; j++) {
213      if ((j & 1) != 0)
214        otherWay += -sort[j];
215    }
216    // Need to think more
217    /*
218          Here we have the actual infeasibility calculation. Most previous work is
219          discarded, and we calculate a value using various counts, adjusted by the
220          max value and slack value. This is not scaled to [0, .5].
221        */
222
223    double value = 0.2 * numberUnsatis + 0.01 * (numberMembers_ - numberFree);
224    if (fabs(largestValue - 0.5) < 0.1) {
225      // close to half
226      value += 0.1;
227    }
228    if (slackValue) {
229      // branching on slack
230      value += slackValue;
231    }
232    // scale other way
233    otherWay *= value / (1.0 - otherWay);
234    delete[] sort;
235    return value;
236  } else {
237    delete[] sort;
238    return 0.0; // satisfied
239  }
240}
241
242// This looks at solution and sets bounds to contain solution
243void CbcClique::feasibleRegion()
244{
245  int j;
246  const int *integer = model_->integerVariable();
247  OsiSolverInterface *solver = model_->solver();
248  const double *solution = model_->testSolution();
249  const double *lower = solver->getColLower();
250  const double *upper = solver->getColUpper();
251#ifndef NDEBUG
252  double integerTolerance = model_->getDblParam(CbcModel::CbcIntegerTolerance);
253#endif
254  for (j = 0; j < numberMembers_; j++) {
255    int sequence = members_[j];
256    int iColumn = integer[sequence];
257    double value = solution[iColumn];
258    value = CoinMax(value, lower[iColumn]);
259    value = CoinMin(value, upper[iColumn]);
260    double nearest = floor(value + 0.5);
261#ifndef NDEBUG
262    double distance = fabs(value - nearest);
263    assert(distance <= integerTolerance);
264#endif
265    solver->setColLower(iColumn, nearest);
266    solver->setColUpper(iColumn, nearest);
267  }
268}
269// Redoes data when sequence numbers change
270void CbcClique::redoSequenceEtc(CbcModel *model, int numberColumns, const int *originalColumns)
271{
272  model_ = model;
273  int n2 = 0;
274  for (int j = 0; j < numberMembers_; j++) {
275    int iColumn = members_[j];
276    int i;
277    for (i = 0; i < numberColumns; i++) {
278      if (originalColumns[i] == iColumn)
279        break;
280    }
281    if (i < numberColumns) {
282      members_[n2] = i;
283      type_[n2++] = type_[j];
284    }
285  }
286  if (n2 < numberMembers_) {
287    //printf("** SOS number of members reduced from %d to %d!\n",numberMembers_,n2);
288    numberMembers_ = n2;
289  }
290  // Find out how many non sos
291  int i;
292  numberNonSOSMembers_ = 0;
293  for (i = 0; i < numberMembers_; i++)
294    if (!type_[i])
295      numberNonSOSMembers_++;
296}
297CbcBranchingObject *
298CbcClique::createCbcBranch(OsiSolverInterface *solver, const OsiBranchingInformation * /*info*/, int way)
299{
300  int numberUnsatis = 0;
301  int j;
302  int nUp = 0;
303  int nDown = 0;
304  int numberFree = numberMembers_;
305  const int *integer = model_->integerVariable();
306  //OsiSolverInterface * solver = model_->solver();
307  CoinWarmStartBasis *basis = dynamic_cast< CoinWarmStartBasis * >(solver->getWarmStart());
308  const double *solution = model_->testSolution();
309  const double *lower = solver->getColLower();
310  const double *upper = solver->getColUpper();
311  int *upList = new int[numberMembers_];
312  int *downList = new int[numberMembers_];
313  double *sort = new double[numberMembers_];
314  double integerTolerance = model_->getDblParam(CbcModel::CbcIntegerTolerance);
315
316  double slackValue = 0.0;
317  for (j = 0; j < numberMembers_; j++) {
318    int sequence = members_[j];
319    int iColumn = integer[sequence];
320    double value = solution[iColumn];
321    value = CoinMax(value, lower[iColumn]);
322    value = CoinMin(value, upper[iColumn]);
323    double nearest = floor(value + 0.5);
324    double distance = fabs(value - nearest);
325    if (distance > integerTolerance) {
326      if (!type_[j])
327        value = 1.0 - value; // non SOS
328      // if slack then choose that
329      if (j == slack_ && value > 0.05)
330        slackValue = value;
331      value = -value; // for sort
332      upList[numberUnsatis] = j;
333      sort[numberUnsatis++] = value;
334    } else if (upper[iColumn] > lower[iColumn]) {
335      upList[--numberFree] = j;
336      sort[numberFree] = 0.0;
337      if (basis && basis->getStructStatus(iColumn) == CoinWarmStartBasis::basic)
338        sort[numberFree] = -1.0;
339    }
340  }
341  assert(numberUnsatis);
342  if (!slackValue) {
343    // sort
344    CoinSort_2(sort, sort + numberUnsatis, upList);
345    // also try and spread out satisfied basic
346    CoinSort_2(sort + numberFree, sort + numberMembers_, upList + numberFree);
347    // put first in up etc
348    int kWay = 1;
349    for (j = 0; j < numberUnsatis; j++) {
350      if (kWay > 0)
351        upList[nUp++] = upList[j];
352      else
353        downList[nDown++] = upList[j];
354      kWay = -kWay;
355    }
356    for (j = numberFree; j < numberMembers_; j++) {
357      if (kWay > 0)
358        upList[nUp++] = upList[j];
359      else
360        downList[nDown++] = upList[j];
361      kWay = -kWay;
362    }
363  } else {
364    // put slack to 0 in first way
365    nUp = 1;
366    upList[0] = slack_;
367    for (j = 0; j < numberUnsatis; j++) {
368      downList[nDown++] = upList[j];
369    }
370    for (j = numberFree; j < numberMembers_; j++) {
371      downList[nDown++] = upList[j];
372    }
373  }
374  // create object
375  CbcBranchingObject *branch;
376  if (numberMembers_ <= 64)
377    branch = new CbcCliqueBranchingObject(model_, this, way,
378      nDown, downList, nUp, upList);
379  else
380    branch = new CbcLongCliqueBranchingObject(model_, this, way,
381      nDown, downList, nUp, upList);
382  delete[] upList;
383  delete[] downList;
384  delete[] sort;
385  return branch;
386}
387
388// Default Constructor
389CbcCliqueBranchingObject::CbcCliqueBranchingObject()
390  : CbcBranchingObject()
391{
392  clique_ = NULL;
393  downMask_[0] = 0;
394  downMask_[1] = 0;
395  upMask_[0] = 0;
396  upMask_[1] = 0;
397}
398
399// Useful constructor
400CbcCliqueBranchingObject::CbcCliqueBranchingObject(CbcModel *model,
401  const CbcClique *clique,
402  int way,
403  int numberOnDownSide, const int *down,
404  int numberOnUpSide, const int *up)
405  : CbcBranchingObject(model, clique->id(), way, 0.5)
406{
407  clique_ = clique;
408  downMask_[0] = 0;
409  downMask_[1] = 0;
410  upMask_[0] = 0;
411  upMask_[1] = 0;
412  int i;
413  for (i = 0; i < numberOnDownSide; i++) {
414    int sequence = down[i];
415    int iWord = sequence >> 5;
416    int iBit = sequence - 32 * iWord;
417    unsigned int k = 1 << iBit;
418    downMask_[iWord] |= k;
419  }
420  for (i = 0; i < numberOnUpSide; i++) {
421    int sequence = up[i];
422    int iWord = sequence >> 5;
423    int iBit = sequence - 32 * iWord;
424    unsigned int k = 1 << iBit;
425    upMask_[iWord] |= k;
426  }
427}
428
429// Copy constructor
430CbcCliqueBranchingObject::CbcCliqueBranchingObject(const CbcCliqueBranchingObject &rhs)
431  : CbcBranchingObject(rhs)
432{
433  clique_ = rhs.clique_;
434  downMask_[0] = rhs.downMask_[0];
435  downMask_[1] = rhs.downMask_[1];
436  upMask_[0] = rhs.upMask_[0];
437  upMask_[1] = rhs.upMask_[1];
438}
439
440// Assignment operator
441CbcCliqueBranchingObject &
442CbcCliqueBranchingObject::operator=(const CbcCliqueBranchingObject &rhs)
443{
444  if (this != &rhs) {
445    CbcBranchingObject::operator=(rhs);
446    clique_ = rhs.clique_;
447    downMask_[0] = rhs.downMask_[0];
448    downMask_[1] = rhs.downMask_[1];
449    upMask_[0] = rhs.upMask_[0];
450    upMask_[1] = rhs.upMask_[1];
451  }
452  return *this;
453}
454CbcBranchingObject *
455CbcCliqueBranchingObject::clone() const
456{
457  return (new CbcCliqueBranchingObject(*this));
458}
459
460// Destructor
461CbcCliqueBranchingObject::~CbcCliqueBranchingObject()
462{
463}
464double
465CbcCliqueBranchingObject::branch()
466{
467  decrementNumberBranchesLeft();
468  int iWord;
469  int numberMembers = clique_->numberMembers();
470  const int *which = clique_->members();
471  const int *integerVariables = model_->integerVariable();
472  int numberWords = (numberMembers + 31) >> 5;
473  // *** for way - up means fix all those in down section
474  if (way_ < 0) {
475#ifdef FULL_PRINT
476    printf("Down Fix ");
477#endif
478    for (iWord = 0; iWord < numberWords; iWord++) {
479      int i;
480      for (i = 0; i < 32; i++) {
481        unsigned int k = 1 << i;
482        if ((upMask_[iWord] & k) != 0) {
483          int iColumn = which[i + 32 * iWord];
484#ifdef FULL_PRINT
485          printf("%d ", i + 32 * iWord);
486#endif
487          // fix weak way
488          if (clique_->type(i + 32 * iWord)) {
489#ifdef FULL_PRINT
490            printf("member %d int %d matcol %d bound %g %g to 0.0\n",
491              i, iColumn, integerVariables[iColumn],
492              model_->solver()->getColLower()[integerVariables[iColumn]],
493              model_->solver()->getColUpper()[integerVariables[iColumn]]);
494#endif
495            model_->solver()->setColUpper(integerVariables[iColumn], 0.0);
496          } else {
497#ifdef FULL_PRINT
498            printf("member %d int %d matcol %d bound %g %g to 1.0\n",
499              i, iColumn, integerVariables[iColumn],
500              model_->solver()->getColLower()[integerVariables[iColumn]],
501              model_->solver()->getColUpper()[integerVariables[iColumn]]);
502#endif
503            model_->solver()->setColLower(integerVariables[iColumn], 1.0);
504          }
505        }
506      }
507    }
508    way_ = 1; // Swap direction
509  } else {
510#ifdef FULL_PRINT
511    printf("Up Fix ");
512#endif
513    for (iWord = 0; iWord < numberWords; iWord++) {
514      int i;
515      for (i = 0; i < 32; i++) {
516        unsigned int k = 1 << i;
517        if ((downMask_[iWord] & k) != 0) {
518          int iColumn = which[i + 32 * iWord];
519#ifdef FULL_PRINT
520          printf("%d ", i + 32 * iWord);
521#endif
522          // fix weak way
523          if (clique_->type(i + 32 * iWord)) {
524#ifdef FULL_PRINT
525            printf("member %d int %d matcol %d bound %g %g to 0.0\n",
526              i, iColumn, integerVariables[iColumn],
527              model_->solver()->getColLower()[integerVariables[iColumn]],
528              model_->solver()->getColUpper()[integerVariables[iColumn]]);
529#endif
530            model_->solver()->setColUpper(integerVariables[iColumn], 0.0);
531          } else {
532#ifdef FULL_PRINT
533            printf("member %d int %d matcol %d bound %g %g to 1.0\n",
534              i, iColumn, integerVariables[iColumn],
535              model_->solver()->getColLower()[integerVariables[iColumn]],
536              model_->solver()->getColUpper()[integerVariables[iColumn]]);
537#endif
538            model_->solver()->setColLower(integerVariables[iColumn], 1.0);
539          }
540        }
541      }
542    }
543    way_ = -1; // Swap direction
544  }
545#ifdef FULL_PRINT
546  printf("\n");
547#endif
548  return 0.0;
549}
550// Print what would happen
551void CbcCliqueBranchingObject::print()
552{
553  int iWord;
554  int numberMembers = clique_->numberMembers();
555  const int *which = clique_->members();
556  const int *integerVariables = model_->integerVariable();
557  int numberWords = (numberMembers + 31) >> 5;
558  // *** for way - up means fix all those in down section
559  if (way_ < 0) {
560    printf("Clique - Down Fix ");
561    for (iWord = 0; iWord < numberWords; iWord++) {
562      int i;
563      for (i = 0; i < 32; i++) {
564        unsigned int k = 1 << i;
565        if ((upMask_[iWord] & k) != 0) {
566          int iColumn = which[i + 32 * iWord];
567          printf("%d ", integerVariables[iColumn]);
568        }
569      }
570    }
571  } else {
572    printf("Clique - Up Fix ");
573    for (iWord = 0; iWord < numberWords; iWord++) {
574      int i;
575      for (i = 0; i < 32; i++) {
576        unsigned int k = 1 << i;
577        if ((downMask_[iWord] & k) != 0) {
578          int iColumn = which[i + 32 * iWord];
579          printf("%d ", integerVariables[iColumn]);
580        }
581      }
582    }
583  }
584  printf("\n");
585}
586
587static inline int
588CbcCompareCliques(const CbcClique *cl0, const CbcClique *cl1)
589{
590  if (cl0->cliqueType() < cl1->cliqueType()) {
591    return -1;
592  }
593  if (cl0->cliqueType() > cl1->cliqueType()) {
594    return 1;
595  }
596  if (cl0->numberMembers() != cl1->numberMembers()) {
597    return cl0->numberMembers() - cl1->numberMembers();
598  }
599  if (cl0->numberNonSOSMembers() != cl1->numberNonSOSMembers()) {
600    return cl0->numberNonSOSMembers() - cl1->numberNonSOSMembers();
601  }
602  return memcmp(cl0->members(), cl1->members(),
603    cl0->numberMembers() * sizeof(int));
604}
605
606/** Compare the original object of \c this with the original object of \c
607    brObj. Assumes that there is an ordering of the original objects.
608    This method should be invoked only if \c this and brObj are of the same
609    type.
610    Return negative/0/positive depending on whether \c this is
611    smaller/same/larger than the argument.
612*/
613int CbcCliqueBranchingObject::compareOriginalObject(const CbcBranchingObject *brObj) const
614{
615  const CbcCliqueBranchingObject *br = dynamic_cast< const CbcCliqueBranchingObject * >(brObj);
616  assert(br);
617  return CbcCompareCliques(clique_, br->clique_);
618}
619
620/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
621    same type and must have the same original object, but they may have
622    different feasible regions.
623    Return the appropriate CbcRangeCompare value (first argument being the
624    sub/superset if that's the case). In case of overlap (and if \c
625    replaceIfOverlap is true) replace the current branching object with one
626    whose feasible region is the overlap.
627*/
628CbcRangeCompare
629CbcCliqueBranchingObject::compareBranchingObject(const CbcBranchingObject *brObj, const bool /*replaceIfOverlap*/)
630{
631  const CbcCliqueBranchingObject *br = dynamic_cast< const CbcCliqueBranchingObject * >(brObj);
632  assert(br);
633  unsigned int *thisMask = way_ < 0 ? upMask_ : downMask_;
634  const unsigned int *otherMask = br->way_ < 0 ? br->upMask_ : br->downMask_;
635  const CoinUInt64 cl0 = (static_cast< CoinUInt64 >(thisMask[0]) << 32) | thisMask[1];
636  const CoinUInt64 cl1 = (static_cast< CoinUInt64 >(otherMask[0]) << 32) | otherMask[1];
637  if (cl0 == cl1) {
638    return CbcRangeSame;
639  }
640  const CoinUInt64 cl_intersection = (cl0 & cl1);
641  if (cl_intersection == cl0) {
642    return CbcRangeSuperset;
643  }
644  if (cl_intersection == cl1) {
645    return CbcRangeSubset;
646  }
647  const CoinUInt64 cl_xor = (cl0 ^ cl1);
648  if (cl_intersection == 0 && cl_xor == 0) {
649    return CbcRangeDisjoint;
650  }
651  const CoinUInt64 cl_union = (cl0 | cl1);
652  thisMask[0] = static_cast< unsigned int >(cl_union >> 32);
653  thisMask[1] = static_cast< unsigned int >(cl_union & 0xffffffff);
654  return CbcRangeOverlap;
655}
656
657//##############################################################################
658
659// Default Constructor
660CbcLongCliqueBranchingObject::CbcLongCliqueBranchingObject()
661  : CbcBranchingObject()
662{
663  clique_ = NULL;
664  downMask_ = NULL;
665  upMask_ = NULL;
666}
667
668// Useful constructor
669CbcLongCliqueBranchingObject::CbcLongCliqueBranchingObject(CbcModel *model,
670  const CbcClique *clique,
671  int way,
672  int numberOnDownSide, const int *down,
673  int numberOnUpSide, const int *up)
674  : CbcBranchingObject(model, clique->id(), way, 0.5)
675{
676  clique_ = clique;
677  int numberMembers = clique_->numberMembers();
678  int numberWords = (numberMembers + 31) >> 5;
679  downMask_ = new unsigned int[numberWords];
680  upMask_ = new unsigned int[numberWords];
681  memset(downMask_, 0, numberWords * sizeof(unsigned int));
682  memset(upMask_, 0, numberWords * sizeof(unsigned int));
683  int i;
684  for (i = 0; i < numberOnDownSide; i++) {
685    int sequence = down[i];
686    int iWord = sequence >> 5;
687    int iBit = sequence - 32 * iWord;
688    unsigned int k = 1 << iBit;
689    downMask_[iWord] |= k;
690  }
691  for (i = 0; i < numberOnUpSide; i++) {
692    int sequence = up[i];
693    int iWord = sequence >> 5;
694    int iBit = sequence - 32 * iWord;
695    unsigned int k = 1 << iBit;
696    upMask_[iWord] |= k;
697  }
698}
699
700// Copy constructor
701CbcLongCliqueBranchingObject::CbcLongCliqueBranchingObject(const CbcLongCliqueBranchingObject &rhs)
702  : CbcBranchingObject(rhs)
703{
704  clique_ = rhs.clique_;
705  if (rhs.downMask_) {
706    int numberMembers = clique_->numberMembers();
707    int numberWords = (numberMembers + 31) >> 5;
708    downMask_ = new unsigned int[numberWords];
709    memcpy(downMask_, rhs.downMask_, numberWords * sizeof(unsigned int));
710    upMask_ = new unsigned int[numberWords];
711    memcpy(upMask_, rhs.upMask_, numberWords * sizeof(unsigned int));
712  } else {
713    downMask_ = NULL;
714    upMask_ = NULL;
715  }
716}
717
718// Assignment operator
719CbcLongCliqueBranchingObject &
720CbcLongCliqueBranchingObject::operator=(const CbcLongCliqueBranchingObject &rhs)
721{
722  if (this != &rhs) {
723    CbcBranchingObject::operator=(rhs);
724    clique_ = rhs.clique_;
725    delete[] downMask_;
726    delete[] upMask_;
727    if (rhs.downMask_) {
728      int numberMembers = clique_->numberMembers();
729      int numberWords = (numberMembers + 31) >> 5;
730      downMask_ = new unsigned int[numberWords];
731      memcpy(downMask_, rhs.downMask_, numberWords * sizeof(unsigned int));
732      upMask_ = new unsigned int[numberWords];
733      memcpy(upMask_, rhs.upMask_, numberWords * sizeof(unsigned int));
734    } else {
735      downMask_ = NULL;
736      upMask_ = NULL;
737    }
738  }
739  return *this;
740}
741CbcBranchingObject *
742CbcLongCliqueBranchingObject::clone() const
743{
744  return (new CbcLongCliqueBranchingObject(*this));
745}
746
747// Destructor
748CbcLongCliqueBranchingObject::~CbcLongCliqueBranchingObject()
749{
750  delete[] downMask_;
751  delete[] upMask_;
752}
753double
754CbcLongCliqueBranchingObject::branch()
755{
756  decrementNumberBranchesLeft();
757  int iWord;
758  int numberMembers = clique_->numberMembers();
759  const int *which = clique_->members();
760  const int *integerVariables = model_->integerVariable();
761  int numberWords = (numberMembers + 31) >> 5;
762  // *** for way - up means fix all those in down section
763  if (way_ < 0) {
764#ifdef FULL_PRINT
765    printf("Down Fix ");
766#endif
767    for (iWord = 0; iWord < numberWords; iWord++) {
768      int i;
769      for (i = 0; i < 32; i++) {
770        unsigned int k = 1 << i;
771        if ((upMask_[iWord] & k) != 0) {
772          int iColumn = which[i + 32 * iWord];
773#ifdef FULL_PRINT
774          printf("%d ", i + 32 * iWord);
775#endif
776          // fix weak way
777          if (clique_->type(i + 32 * iWord))
778            model_->solver()->setColUpper(integerVariables[iColumn], 0.0);
779          else
780            model_->solver()->setColLower(integerVariables[iColumn], 1.0);
781        }
782      }
783    }
784    way_ = 1; // Swap direction
785  } else {
786#ifdef FULL_PRINT
787    printf("Up Fix ");
788#endif
789    for (iWord = 0; iWord < numberWords; iWord++) {
790      int i;
791      for (i = 0; i < 32; i++) {
792        unsigned int k = 1 << i;
793        if ((downMask_[iWord] & k) != 0) {
794          int iColumn = which[i + 32 * iWord];
795#ifdef FULL_PRINT
796          printf("%d ", i + 32 * iWord);
797#endif
798          // fix weak way
799          if (clique_->type(i + 32 * iWord))
800            model_->solver()->setColUpper(integerVariables[iColumn], 0.0);
801          else
802            model_->solver()->setColLower(integerVariables[iColumn], 1.0);
803        }
804      }
805    }
806    way_ = -1; // Swap direction
807  }
808#ifdef FULL_PRINT
809  printf("\n");
810#endif
811  return 0.0;
812}
813void CbcLongCliqueBranchingObject::print()
814{
815  int iWord;
816  int numberMembers = clique_->numberMembers();
817  const int *which = clique_->members();
818  const int *integerVariables = model_->integerVariable();
819  int numberWords = (numberMembers + 31) >> 5;
820  // *** for way - up means fix all those in down section
821  if (way_ < 0) {
822    printf("Clique - Down Fix ");
823    for (iWord = 0; iWord < numberWords; iWord++) {
824      int i;
825      for (i = 0; i < 32; i++) {
826        unsigned int k = 1 << i;
827        if ((upMask_[iWord] & k) != 0) {
828          int iColumn = which[i + 32 * iWord];
829          printf("%d ", integerVariables[iColumn]);
830        }
831      }
832    }
833  } else {
834    printf("Clique - Up Fix ");
835    for (iWord = 0; iWord < numberWords; iWord++) {
836      int i;
837      for (i = 0; i < 32; i++) {
838        unsigned int k = 1 << i;
839        if ((downMask_[iWord] & k) != 0) {
840          int iColumn = which[i + 32 * iWord];
841          printf("%d ", integerVariables[iColumn]);
842        }
843      }
844    }
845  }
846  printf("\n");
847}
848
849/** Compare the original object of \c this with the original object of \c
850    brObj. Assumes that there is an ordering of the original objects.
851    This method should be invoked only if \c this and brObj are of the same
852    type.
853    Return negative/0/positive depending on whether \c this is
854    smaller/same/larger than the argument.
855*/
856int CbcLongCliqueBranchingObject::compareOriginalObject(const CbcBranchingObject *brObj) const
857{
858  const CbcLongCliqueBranchingObject *br = dynamic_cast< const CbcLongCliqueBranchingObject * >(brObj);
859  assert(br);
860  return CbcCompareCliques(clique_, br->clique_);
861}
862
863/** Compare the \c this with \c brObj. \c this and \c brObj must be os the
864    same type and must have the same original object, but they may have
865    different feasible regions.
866    Return the appropriate CbcRangeCompare value (first argument being the
867    sub/superset if that's the case). In case of overlap (and if \c
868    replaceIfOverlap is true) replace the current branching object with one
869    whose feasible region is the overlap.
870*/
871CbcRangeCompare
872CbcLongCliqueBranchingObject::compareBranchingObject(const CbcBranchingObject *brObj, const bool /*replaceIfOverlap*/)
873{
874  const CbcLongCliqueBranchingObject *br = dynamic_cast< const CbcLongCliqueBranchingObject * >(brObj);
875  assert(br);
876  const int numberMembers = clique_->numberMembers();
877  const int numberWords = (numberMembers + 31) >> 5;
878  unsigned int *thisMask = way_ < 0 ? upMask_ : downMask_;
879  const unsigned int *otherMask = br->way_ < 0 ? br->upMask_ : br->downMask_;
880
881  if (memcmp(thisMask, otherMask, numberWords * sizeof(unsigned int)) == 0) {
882    return CbcRangeSame;
883  }
884  bool canBeSuperset = true;
885  bool canBeSubset = true;
886  int i;
887  for (i = numberWords - 1; i >= 0 && (canBeSuperset || canBeSubset); --i) {
888    const unsigned int both = (thisMask[i] & otherMask[i]);
889    canBeSuperset &= (both == thisMask[i]);
890    canBeSubset &= (both == otherMask[i]);
891  }
892  if (canBeSuperset) {
893    return CbcRangeSuperset;
894  }
895  if (canBeSubset) {
896    return CbcRangeSubset;
897  }
898
899  for (i = numberWords - 1; i >= 0; --i) {
900    if ((thisMask[i] ^ otherMask[i]) != 0) {
901      break;
902    }
903  }
904  if (i == -1) { // complement
905    return CbcRangeDisjoint;
906  }
907  // must be overlap
908  for (i = numberWords - 1; i >= 0; --i) {
909    thisMask[i] |= otherMask[i];
910  }
911  return CbcRangeOverlap;
912}
913
914/* vi: softtabstop=2 shiftwidth=2 expandtab tabstop=2
915*/
Note: See TracBrowser for help on using the repository browser.