← Back to branch summary

~ubuntu-branches/ubuntu/natty/coinor-cbc/natty

« back to all changes in this revision

Viewing changes to Cbc/src/CbcStrategy.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Soeren Sonnenburg
  • Date: 2009-08-26 16:57:29 UTC
  • Revision ID: james.westby@ubuntu.com-20090826165729-ybrezxdybg0hd1u6
Tags: upstream-2.3.0
Import upstream version 2.3.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
Cbc/src/CbcStrategy.cpp
 
1
// Copyright (C) 2005, International Business Machines
 
2
// Corporation and others.  All Rights Reserved.
 
3
#if defined(_MSC_VER)
 
4
// Turn off compiler warning about long names
 
5
#  pragma warning(disable:4786)
 
6
#endif
 
7
 
 
8
#include "CbcConfig.h"
 
9
 
 
10
#include <cassert>
 
11
#include <cstdlib>
 
12
#include <cmath>
 
13
#include <cfloat>
 
14
 
 
15
#include "OsiSolverInterface.hpp"
 
16
#ifdef COIN_HAS_CLP
 
17
#include "OsiClpSolverInterface.hpp"
 
18
#endif
 
19
#include "CbcModel.hpp"
 
20
#include "CbcMessage.hpp"
 
21
#include "CbcStrategy.hpp"
 
22
#include "CbcCutGenerator.hpp"
 
23
#include "CbcBranchActual.hpp"
 
24
#include "CbcNode.hpp"
 
25
#include "CoinWarmStart.hpp"
 
26
#include "CglPreProcess.hpp"
 
27
// Cuts
 
28
 
 
29
#include "CglGomory.hpp"
 
30
#include "CglProbing.hpp"
 
31
#include "CglKnapsackCover.hpp"
 
32
#include "CglOddHole.hpp"
 
33
#include "CglClique.hpp"
 
34
#include "CglFlowCover.hpp"
 
35
#include "CglMixedIntegerRounding2.hpp"
 
36
 
 
37
// Heuristics
 
38
 
 
39
#include "CbcHeuristic.hpp"
 
40
#include "CbcHeuristicLocal.hpp"
 
41
 
 
42
// Default Constructor
 
43
CbcStrategy::CbcStrategy() 
 
44
  :depth_(0),
 
45
   preProcessState_(0),
 
46
   process_(NULL)
 
47
{
 
48
}
 
49
 
 
50
// Destructor 
 
51
CbcStrategy::~CbcStrategy ()
 
52
{
 
53
  delete process_;
 
54
}
 
55
// Delete pre-processing object to save memory
 
56
void 
 
57
CbcStrategy::deletePreProcess()
 
58
{ 
 
59
  delete process_;
 
60
  process_=NULL;
 
61
}
 
62
// Return a new Full node information pointer (descendant of CbcFullNodeInfo)
 
63
CbcNodeInfo * 
 
64
CbcStrategy::fullNodeInfo(CbcModel * model,int numberRowsAtContinuous) const
 
65
{
 
66
  return new CbcFullNodeInfo(model,numberRowsAtContinuous);
 
67
}
 
68
// Return a new Partial node information pointer (descendant of CbcPartialNodeInfo)
 
69
CbcNodeInfo * 
 
70
CbcStrategy::partialNodeInfo(CbcModel * model, CbcNodeInfo * parent, CbcNode * owner,
 
71
                             int numberChangedBounds,const int * variables,
 
72
                             const double * boundChanges,
 
73
                             const CoinWarmStartDiff *basisDiff) const
 
74
{
 
75
  return new CbcPartialNodeInfo(parent, owner, numberChangedBounds, variables,
 
76
                            boundChanges,basisDiff);
 
77
}
 
78
/* After a CbcModel::resolve this can return a status
 
79
   -1 no effect
 
80
   0 treat as optimal
 
81
   1 as 0 but do not do any more resolves (i.e. no more cuts)
 
82
   2 treat as infeasible
 
83
*/
 
84
int
 
85
CbcStrategy::status(CbcModel * model, CbcNodeInfo * parent,int whereFrom)
 
86
{
 
87
  return -1;
 
88
}
 
89
 
 
90
// Default Constructor
 
91
CbcStrategyDefault::CbcStrategyDefault(int cutsOnlyAtRoot,
 
92
                                       int numberStrong,
 
93
                                       int numberBeforeTrust,
 
94
                                       int printLevel)
 
95
  :CbcStrategy(),
 
96
   cutsOnlyAtRoot_(cutsOnlyAtRoot),
 
97
   numberStrong_(numberStrong),
 
98
   numberBeforeTrust_(numberBeforeTrust),
 
99
   printLevel_(printLevel),
 
100
   desiredPreProcess_(0),
 
101
   preProcessPasses_(0)
 
102
{
 
103
}
 
104
 
 
105
 
 
106
// Destructor 
 
107
CbcStrategyDefault::~CbcStrategyDefault ()
 
108
{
 
109
}
 
110
 
 
111
// Clone
 
112
CbcStrategy *
 
113
CbcStrategyDefault::clone() const
 
114
{
 
115
  return new CbcStrategyDefault(*this);
 
116
}
 
117
 
 
118
// Copy constructor 
 
119
CbcStrategyDefault::CbcStrategyDefault(const CbcStrategyDefault & rhs)
 
120
:
 
121
  CbcStrategy(rhs),
 
122
  cutsOnlyAtRoot_(rhs.cutsOnlyAtRoot_),
 
123
  numberStrong_(rhs.numberStrong_),
 
124
  numberBeforeTrust_(rhs.numberBeforeTrust_),
 
125
  printLevel_(rhs.printLevel_),
 
126
  desiredPreProcess_(rhs.desiredPreProcess_),
 
127
  preProcessPasses_(rhs.preProcessPasses_)
 
128
{
 
129
  setNested(rhs.getNested());
 
130
}
 
131
 
 
132
// Setup cut generators
 
133
void 
 
134
CbcStrategyDefault::setupCutGenerators(CbcModel & model)
 
135
{
 
136
  if (cutsOnlyAtRoot_<0)
 
137
    return; // no cuts wanted
 
138
  // Set up some cut generators and defaults
 
139
  // Probing first as gets tight bounds on continuous
 
140
  int genFlags=63;
 
141
  //#define CBC_GENERATE_TEST  
 
142
#ifdef CBC_GENERATE_TEST
 
143
  int nNodes = model.getMaximumNodes();
 
144
  if (nNodes>=190000&&nNodes<190064)
 
145
    genFlags = nNodes-190000;
 
146
#endif
 
147
 
 
148
  CglProbing generator1;
 
149
  generator1.setUsingObjective(true);
 
150
  generator1.setMaxPass(1);
 
151
  generator1.setMaxPassRoot(1);
 
152
  // Number of unsatisfied variables to look at
 
153
  generator1.setMaxProbe(10);
 
154
  // How far to follow the consequences
 
155
  generator1.setMaxLook(10);
 
156
  // Only look at rows with fewer than this number of elements
 
157
  generator1.setMaxElements(200);
 
158
  generator1.setMaxElementsRoot(300);
 
159
  //generator1.setRowCuts(3);
 
160
 
 
161
  CglGomory generator2;
 
162
  // try larger limit
 
163
  generator2.setLimit(300);
 
164
 
 
165
  CglKnapsackCover generator3;
 
166
 
 
167
  //CglOddHole generator4;
 
168
  //generator4.setMinimumViolation(0.005);
 
169
  //generator4.setMinimumViolationPer(0.00002);
 
170
  // try larger limit
 
171
  //generator4.setMaximumEntries(200);
 
172
 
 
173
  CglClique generator5;
 
174
  generator5.setStarCliqueReport(false);
 
175
  generator5.setRowCliqueReport(false);
 
176
 
 
177
  CglMixedIntegerRounding2 mixedGen;
 
178
  CglFlowCover flowGen;
 
179
  
 
180
  // Add in generators
 
181
  int setting = cutsOnlyAtRoot_ ? -99 : -1;
 
182
  int numberGenerators = model.numberCutGenerators();
 
183
  int iGenerator;
 
184
  bool found;
 
185
  found=false;
 
186
  for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
 
187
    CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
 
188
    CglProbing * cgl = dynamic_cast<CglProbing *>(generator);
 
189
    if (cgl) {
 
190
      found=true;
 
191
      break;
 
192
    }
 
193
  }
 
194
  if (!found&&(genFlags&1)!=0)
 
195
    model.addCutGenerator(&generator1,setting,"Probing");
 
196
  found=false;
 
197
  for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
 
198
    CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
 
199
    CglGomory * cgl = dynamic_cast<CglGomory *>(generator);
 
200
    if (cgl) {
 
201
      found=true;
 
202
      break;
 
203
    }
 
204
  }
 
205
  if (!found&&(genFlags&2)!=0)
 
206
  model.addCutGenerator(&generator2,setting,"Gomory");
 
207
  found=false;
 
208
  for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
 
209
    CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
 
210
    CglKnapsackCover * cgl = dynamic_cast<CglKnapsackCover *>(generator);
 
211
    if (cgl) {
 
212
      found=true;
 
213
      break;
 
214
    }
 
215
  }
 
216
  if (!found&&(genFlags&4)!=0)
 
217
    model.addCutGenerator(&generator3,setting,"Knapsack");
 
218
  //model.addCutGenerator(&generator4,setting,"OddHole");
 
219
  found=false;
 
220
  for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
 
221
    CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
 
222
    CglClique * cgl = dynamic_cast<CglClique *>(generator);
 
223
    if (cgl) {
 
224
      found=true;
 
225
      break;
 
226
    }
 
227
  }
 
228
  if (!found&&(genFlags&8)!=0)
 
229
    model.addCutGenerator(&generator5,setting,"Clique");
 
230
  found=false;
 
231
  for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
 
232
    CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
 
233
    CglFlowCover * cgl = dynamic_cast<CglFlowCover *>(generator);
 
234
    if (cgl) {
 
235
      found=true;
 
236
      break;
 
237
    }
 
238
  }
 
239
  if (!found&&(genFlags&16)!=0)
 
240
    model.addCutGenerator(&flowGen,setting,"FlowCover");
 
241
  found=false;
 
242
  for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
 
243
    CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
 
244
    CglMixedIntegerRounding2 * cgl = dynamic_cast<CglMixedIntegerRounding2 *>(generator);
 
245
    if (cgl) {
 
246
      found=true;
 
247
      break;
 
248
    }
 
249
  }
 
250
  if (!found&&(genFlags&32)!=0)
 
251
    model.addCutGenerator(&mixedGen,setting,"MixedIntegerRounding2");
 
252
  // Say we want timings
 
253
  int newNumberGenerators = model.numberCutGenerators();
 
254
  for (iGenerator=numberGenerators;iGenerator<newNumberGenerators;iGenerator++) {
 
255
    CbcCutGenerator * generator = model.cutGenerator(iGenerator);
 
256
    generator->setTiming(true);
 
257
  }
 
258
  int currentPasses = model.getMaximumCutPassesAtRoot();
 
259
  if (currentPasses>=0) {
 
260
    if (model.getNumCols()<500)
 
261
      model.setMaximumCutPassesAtRoot(-CoinMax(100,currentPasses)); // always do 100 if possible
 
262
    else if (model.getNumCols()<5000)
 
263
      model.setMaximumCutPassesAtRoot(CoinMax(100,currentPasses)); // use minimum drop
 
264
    else
 
265
      model.setMaximumCutPassesAtRoot(CoinMax(20,currentPasses));
 
266
  } else {
 
267
    currentPasses=-currentPasses;
 
268
    if (model.getNumCols()<500)
 
269
      model.setMaximumCutPassesAtRoot(-CoinMax(100,currentPasses)); // always do 100 if possible
 
270
    else
 
271
      model.setMaximumCutPassesAtRoot(-CoinMax(20,currentPasses));
 
272
  }
 
273
}
 
274
// Setup heuristics
 
275
void 
 
276
CbcStrategyDefault::setupHeuristics(CbcModel & model)
 
277
{
 
278
  // Allow rounding heuristic
 
279
 
 
280
  CbcRounding heuristic1(model);
 
281
  heuristic1.setHeuristicName("rounding");
 
282
  int numberHeuristics = model.numberHeuristics();
 
283
  int iHeuristic;
 
284
  bool found;
 
285
  found=false;
 
286
  for (iHeuristic=0;iHeuristic<numberHeuristics;iHeuristic++) {
 
287
    CbcHeuristic * heuristic = model.heuristic(iHeuristic);
 
288
    CbcRounding * cgl = dynamic_cast<CbcRounding *>(heuristic);
 
289
    if (cgl) {
 
290
      found=true;
 
291
      break;
 
292
    }
 
293
  }
 
294
  if (!found)
 
295
    model.addHeuristic(&heuristic1);
 
296
#if 0
 
297
  // Allow join solutions
 
298
  CbcHeuristicLocal heuristic2(model);
 
299
  heuristic2.setHeuristicName("join solutions");
 
300
  heuristic2.setSearchType(1);
 
301
  found=false;
 
302
  for (iHeuristic=0;iHeuristic<numberHeuristics;iHeuristic++) {
 
303
    CbcHeuristic * heuristic = model.heuristic(iHeuristic);
 
304
    CbcHeuristicLocal * cgl = dynamic_cast<CbcHeuristicLocal *>(heuristic);
 
305
    if (cgl) {
 
306
      found=true;
 
307
      break;
 
308
    }
 
309
  }
 
310
  if (!found)
 
311
    model.addHeuristic(&heuristic2);
 
312
#endif
 
313
}
 
314
// Do printing stuff
 
315
void 
 
316
CbcStrategyDefault::setupPrinting(CbcModel & model,int modelLogLevel)
 
317
{
 
318
  if (!modelLogLevel) {
 
319
    model.solver()->setHintParam(OsiDoReducePrint,true,OsiHintTry);
 
320
    model.messageHandler()->setLogLevel(0);
 
321
    model.solver()->messageHandler()->setLogLevel(0);
 
322
  } else if (modelLogLevel==1) {
 
323
    model.solver()->setHintParam(OsiDoReducePrint,true,OsiHintTry);
 
324
    model.messageHandler()->setLogLevel(1);
 
325
    model.solver()->messageHandler()->setLogLevel(0);
 
326
  } else {
 
327
    model.messageHandler()->setLogLevel(CoinMax(2,model.messageHandler()->logLevel()));
 
328
    model.solver()->messageHandler()->setLogLevel(CoinMax(1,model.solver()->messageHandler()->logLevel()));
 
329
    model.setPrintFrequency(CoinMin(50,model.printFrequency()));
 
330
  }
 
331
}
 
332
// Other stuff e.g. strong branching
 
333
void 
 
334
CbcStrategyDefault::setupOther(CbcModel & model)
 
335
{
 
336
  // See if preprocessing wanted
 
337
  if (desiredPreProcess_) {
 
338
    delete process_;
 
339
    // solver_ should have been cloned outside
 
340
    CglPreProcess * process = new CglPreProcess();
 
341
    // Pass in models message handler
 
342
    process->passInMessageHandler(model.messageHandler());
 
343
    OsiSolverInterface * solver = model.solver();
 
344
#ifdef COIN_HAS_CLP
 
345
    OsiClpSolverInterface * clpSolver = dynamic_cast< OsiClpSolverInterface*> (solver);
 
346
    if (clpSolver&&false) {
 
347
      // see if all coefficients multiple of 0.01 (close enough)
 
348
      CoinPackedMatrix * matrix = clpSolver->getModelPtr()->matrix();
 
349
      double * element = matrix->getMutableElements();
 
350
      //const int * row = matrix->getIndices();
 
351
      const CoinBigIndex * columnStart = matrix->getVectorStarts();
 
352
      const int * columnLength = matrix->getVectorLengths();
 
353
      int numberInt=0;
 
354
      int numberNon=0;
 
355
      int numberClose=0;
 
356
      int numberColumns = clpSolver->getNumCols();
 
357
      int iColumn;
 
358
      for (iColumn=0;iColumn<numberColumns;iColumn++) {
 
359
        for (int j=columnStart[iColumn];
 
360
             j<columnStart[iColumn]+columnLength[iColumn];j++) {
 
361
          //int iRow = row[j];
 
362
          double value1 = element[j];
 
363
          double value = fabs(value1);
 
364
          if (value>1.0e7) {
 
365
            if(value!=floor(value)) 
 
366
              numberNon++;
 
367
            else
 
368
              numberInt++;
 
369
          } else {
 
370
            int iValue = static_cast<int>( 100*(value+0.005));
 
371
            double value2 = iValue;
 
372
            if (value2==100.0*value) {
 
373
              numberInt++;
 
374
            } else if (fabs(value2-100.0*value)<1.0e-5) {
 
375
              numberClose++;
 
376
            } else {
 
377
              numberNon++;
 
378
            }
 
379
          }
 
380
        }
 
381
      }
 
382
      if (!numberNon&&numberClose) {
 
383
        printf("Tidying %d multiples of 0.01, %d close\n",
 
384
               numberInt,numberClose);
 
385
        for (iColumn=0;iColumn<numberColumns;iColumn++) {
 
386
          for (int j=columnStart[iColumn];
 
387
               j<columnStart[iColumn]+columnLength[iColumn];j++) {
 
388
            //int iRow = row[j];
 
389
            double value1 = element[j];
 
390
            double value = fabs(value1);
 
391
            if (value<1.0e7) {
 
392
              int iValue = static_cast<int>( 100*(value+0.005));
 
393
              double value2 = iValue;
 
394
              if (value2!=100.0*value) {
 
395
                value2 *= 0.01;
 
396
                if (fabs(value-floor(value+0.5))<=1.0e-7)
 
397
                  value2 = floor(value+0.5);
 
398
                if (value1<0.0)
 
399
                  value2 = -value2;
 
400
                element[j]=value2;
 
401
              }
 
402
            }
 
403
          }
 
404
        }
 
405
      }
 
406
    }
 
407
#endif
 
408
    {
 
409
      // mark some columns as ineligible for presolve
 
410
      int numberColumns = solver->getNumCols();
 
411
      char * prohibited = new char[numberColumns];
 
412
      memset(prohibited,0,numberColumns);
 
413
      int numberProhibited=0;
 
414
      // convert to Cbc integers
 
415
      model.findIntegers(false);
 
416
      int numberObjects = model.numberObjects();
 
417
      if (numberObjects) { 
 
418
        OsiObject ** objects = model.objects();
 
419
        for (int iObject=0;iObject<numberObjects;iObject++) {
 
420
          CbcSOS * obj =
 
421
            dynamic_cast <CbcSOS *>(objects[iObject]) ;
 
422
          if (obj) {
 
423
            // SOS
 
424
            int n = obj->numberMembers();
 
425
            const int * which = obj->members();
 
426
            for (int i=0;i<n;i++) {
 
427
              int iColumn = which[i];
 
428
              prohibited[iColumn]=1;
 
429
              numberProhibited++;
 
430
            }
 
431
          }
 
432
        }
 
433
      }
 
434
      if (numberProhibited)
 
435
        process->passInProhibited(prohibited,numberColumns);
 
436
      delete [] prohibited;
 
437
    }
 
438
    int logLevel = model.messageHandler()->logLevel();
 
439
#ifdef COIN_HAS_CLP
 
440
    //OsiClpSolverInterface * clpSolver = dynamic_cast< OsiClpSolverInterface*> (solver);
 
441
    ClpSimplex * lpSolver=NULL;
 
442
    if (clpSolver) {
 
443
      if (clpSolver->messageHandler()->logLevel())
 
444
        clpSolver->messageHandler()->setLogLevel(1);
 
445
      if (logLevel>-1)
 
446
        clpSolver->messageHandler()->setLogLevel(CoinMin(logLevel,clpSolver->messageHandler()->logLevel()));
 
447
      lpSolver = clpSolver->getModelPtr();
 
448
      /// If user left factorization frequency then compute
 
449
      lpSolver->defaultFactorizationFrequency();
 
450
    }
 
451
#endif
 
452
    // Tell solver we are in Branch and Cut
 
453
    solver->setHintParam(OsiDoInBranchAndCut,true,OsiHintDo) ;
 
454
    // Default set of cut generators
 
455
    CglProbing generator1;
 
456
    generator1.setUsingObjective(true);
 
457
    generator1.setMaxPass(1);
 
458
    generator1.setMaxPassRoot(1);
 
459
    generator1.setMaxProbeRoot(CoinMin(3000,solver->getNumCols()));
 
460
    generator1.setMaxProbeRoot(123);
 
461
    generator1.setMaxElements(100);
 
462
    generator1.setMaxElementsRoot(200);
 
463
    generator1.setMaxLookRoot(50);
 
464
    generator1.setRowCuts(3);
 
465
    //generator1.messageHandler()->setLogLevel(logLevel);
 
466
    // Not needed with pass in process->messageHandler()->setLogLevel(logLevel);
 
467
    // Add in generators
 
468
    process->addCutGenerator(&generator1);
 
469
    int translate[]={9999,0,2,-2,3,4,4,4};
 
470
    OsiSolverInterface * solver2 = 
 
471
      process->preProcessNonDefault(*solver,
 
472
                                    translate[desiredPreProcess_],preProcessPasses_,6);
 
473
    // Tell solver we are not in Branch and Cut
 
474
    solver->setHintParam(OsiDoInBranchAndCut,false,OsiHintDo) ;
 
475
    if (solver2)
 
476
      solver2->setHintParam(OsiDoInBranchAndCut,false,OsiHintDo) ;
 
477
    bool feasible=true;
 
478
    if (!solver2) {
 
479
      feasible = false;
 
480
      //printf("Pre-processing says infeasible\n");
 
481
      delete process;
 
482
      preProcessState_=-1;
 
483
      process_=NULL;
 
484
    } else {
 
485
      // now tighten bounds
 
486
#ifdef COIN_HAS_CLP
 
487
      if (clpSolver) {
 
488
        // model has changed
 
489
        solver = model.solver();
 
490
        OsiClpSolverInterface * clpSolver = dynamic_cast< OsiClpSolverInterface*> (solver);
 
491
        ClpSimplex * lpSolver = clpSolver->getModelPtr();
 
492
        lpSolver->passInMessageHandler(solver->messageHandler());
 
493
        if (lpSolver->tightenPrimalBounds()==0) {
 
494
          lpSolver->dual();
 
495
        } else {
 
496
          feasible = false;
 
497
        }
 
498
      }
 
499
#endif
 
500
      if (feasible) {
 
501
        preProcessState_=1;
 
502
        process_=process;
 
503
        /* Note that original solver will be kept (with false)
 
504
           and that final solver will also be kept.
 
505
           This is for post-processing
 
506
        */
 
507
        OsiSolverInterface * solver3 = solver2->clone();
 
508
        model.assignSolver(solver3,false);
 
509
        if (process_->numberSOS()) {
 
510
          int numberSOS = process_->numberSOS();
 
511
          int numberIntegers = model.numberIntegers();
 
512
          /* model may not have created objects
 
513
             If none then create
 
514
             NOTE - put back to original column numbers as 
 
515
             CbcModel will pack down ALL as it doesn't know where from
 
516
          */
 
517
          bool someObjects = model.numberObjects()>0;
 
518
          if (!numberIntegers||!model.numberObjects()) {
 
519
            model.findIntegers(true);
 
520
            numberIntegers = model.numberIntegers();
 
521
          }
 
522
          OsiObject ** oldObjects = model.objects();
 
523
          // Do sets and priorities
 
524
          OsiObject ** objects = new OsiObject * [numberSOS];
 
525
          // set old objects to have low priority
 
526
          int numberOldObjects = model.numberObjects();
 
527
          int numberColumns = model.getNumCols();
 
528
          for (int iObj = 0;iObj<numberOldObjects;iObj++) {
 
529
            int oldPriority = oldObjects[iObj]->priority();
 
530
            oldObjects[iObj]->setPriority(numberColumns+oldPriority);
 
531
          }
 
532
          const int * starts = process_->startSOS();
 
533
          const int * which = process_->whichSOS();
 
534
          const int * type = process_->typeSOS();
 
535
          const double * weight = process_->weightSOS();
 
536
          int iSOS;
 
537
          for (iSOS =0;iSOS<numberSOS;iSOS++) {
 
538
            int iStart = starts[iSOS];
 
539
            int n=starts[iSOS+1]-iStart;
 
540
            objects[iSOS] = new CbcSOS(&model,n,which+iStart,weight+iStart,
 
541
                                       iSOS,type[iSOS]);
 
542
            // branch on long sets first
 
543
            objects[iSOS]->setPriority(numberColumns-n);
 
544
          }
 
545
          model.addObjects(numberSOS,objects);
 
546
          for (iSOS=0;iSOS<numberSOS;iSOS++)
 
547
            delete objects[iSOS];
 
548
          delete [] objects;
 
549
          if (!someObjects) {
 
550
            // put back old column numbers
 
551
            const int * originalColumns = process_->originalColumns();
 
552
            // use reverse lookup to fake it
 
553
            int n=originalColumns[numberColumns-1]+1;
 
554
            int * fake = new int[n];
 
555
            int i;
 
556
            // This was wrong (now is correct) - so could never have been called
 
557
            abort();
 
558
            for ( i=0;i<n;i++)
 
559
              fake[i]=-1;
 
560
            for (i=0;i<numberColumns;i++)
 
561
              fake[originalColumns[i]]=i;
 
562
            for (int iObject=0;iObject<model.numberObjects();iObject++) {
 
563
              // redo ids etc
 
564
              CbcSimpleInteger * obj =
 
565
                dynamic_cast <CbcSimpleInteger *>(model.modifiableObject(iObject)) ;
 
566
              if (obj) {
 
567
                obj->resetSequenceEtc(n,fake);
 
568
              } else {
 
569
                // redo ids etc
 
570
                CbcObject * obj =
 
571
                  dynamic_cast <CbcObject *>(model.modifiableObject(iObject)) ;
 
572
                assert (obj);
 
573
                obj->redoSequenceEtc(&model,n,fake);
 
574
              }
 
575
            }
 
576
            delete [] fake;
 
577
          }
 
578
        }
 
579
      } else {
 
580
        //printf("Pre-processing says infeasible\n");
 
581
        delete process;
 
582
        preProcessState_=-1;
 
583
        process_=NULL;
 
584
      }
 
585
    }
 
586
  }
 
587
  model.setNumberStrong(numberStrong_);
 
588
  model.setNumberBeforeTrust(numberBeforeTrust_);
 
589
}
 
590
// Create C++ lines to get to current state
 
591
void 
 
592
CbcStrategyDefault::generateCpp( FILE * fp) 
 
593
{
 
594
  fprintf(fp,"0#include \"CbcStrategy.hpp\"\n");
 
595
  fprintf(fp,"3  CbcStrategyDefault strategy(%s,%d,%d,%d);\n",
 
596
          cutsOnlyAtRoot_ ? "1" : "0",
 
597
          numberStrong_,
 
598
          numberBeforeTrust_,
 
599
          printLevel_);
 
600
  fprintf(fp,"3  strategy.setupPreProcessing(%d,%d);\n",
 
601
          desiredPreProcess_,preProcessPasses_);
 
602
}
 
603
// Default Constructor
 
604
CbcStrategyDefaultSubTree::CbcStrategyDefaultSubTree(CbcModel * parent ,
 
605
                                                     int cutsOnlyAtRoot,
 
606
                                       int numberStrong,
 
607
                                       int numberBeforeTrust,
 
608
                                       int printLevel)
 
609
  :CbcStrategy(),
 
610
   parentModel_(parent),
 
611
   cutsOnlyAtRoot_(cutsOnlyAtRoot),
 
612
   numberStrong_(numberStrong),
 
613
   numberBeforeTrust_(numberBeforeTrust),
 
614
   printLevel_(printLevel)
 
615
{
 
616
}
 
617
 
 
618
 
 
619
// Destructor 
 
620
CbcStrategyDefaultSubTree::~CbcStrategyDefaultSubTree ()
 
621
{
 
622
}
 
623
 
 
624
// Clone
 
625
CbcStrategy *
 
626
CbcStrategyDefaultSubTree::clone() const
 
627
{
 
628
  return new CbcStrategyDefaultSubTree(*this);
 
629
}
 
630
 
 
631
// Copy constructor 
 
632
CbcStrategyDefaultSubTree::CbcStrategyDefaultSubTree(const CbcStrategyDefaultSubTree & rhs)
 
633
:
 
634
  CbcStrategy(rhs),
 
635
  parentModel_(rhs.parentModel_),
 
636
  cutsOnlyAtRoot_(rhs.cutsOnlyAtRoot_),
 
637
  numberStrong_(rhs.numberStrong_),
 
638
  numberBeforeTrust_(rhs.numberBeforeTrust_),
 
639
  printLevel_(rhs.printLevel_)
 
640
{
 
641
  setNested(rhs.getNested());
 
642
}
 
643
 
 
644
// Setup cut generators
 
645
void 
 
646
CbcStrategyDefaultSubTree::setupCutGenerators(CbcModel & model)
 
647
{
 
648
  // Set up some cut generators and defaults
 
649
  if (cutsOnlyAtRoot_<0)
 
650
    return; // no cuts wanted
 
651
  // Probing first as gets tight bounds on continuous
 
652
 
 
653
  CglProbing generator1;
 
654
  generator1.setUsingObjective(true);
 
655
  generator1.setMaxPass(1);
 
656
  // Number of unsatisfied variables to look at
 
657
  generator1.setMaxProbe(10);
 
658
  // How far to follow the consequences
 
659
  generator1.setMaxLook(10);
 
660
  // Only look at rows with fewer than this number of elements
 
661
  generator1.setMaxElements(200);
 
662
  //generator1.setRowCuts(3);
 
663
 
 
664
  CglGomory generator2;
 
665
  // try larger limit
 
666
  generator2.setLimit(300);
 
667
 
 
668
  CglKnapsackCover generator3;
 
669
 
 
670
  //CglOddHole generator4;
 
671
  //generator4.setMinimumViolation(0.005);
 
672
  //generator4.setMinimumViolationPer(0.00002);
 
673
  // try larger limit
 
674
  //generator4.setMaximumEntries(200);
 
675
 
 
676
  CglClique generator5;
 
677
  generator5.setStarCliqueReport(false);
 
678
  generator5.setRowCliqueReport(false);
 
679
 
 
680
  CglMixedIntegerRounding2 mixedGen;
 
681
  CglFlowCover flowGen;
 
682
  
 
683
  // Add in generators
 
684
  int setting = cutsOnlyAtRoot_ ? -99 : -1;
 
685
  int numberGenerators = model.numberCutGenerators();
 
686
  int numberParentGenerators = parentModel_->numberCutGenerators();
 
687
  int iGenerator;
 
688
  bool found;
 
689
  found=false;
 
690
  int howOften=0;
 
691
  for (iGenerator=0;iGenerator<numberParentGenerators;iGenerator++) {
 
692
    CglCutGenerator * generator = parentModel_->cutGenerator(iGenerator)->generator();
 
693
    CglProbing * cgl = dynamic_cast<CglProbing *>(generator);
 
694
    if (cgl) {
 
695
      found=true;
 
696
      howOften = parentModel_->cutGenerator(iGenerator)->howOften();
 
697
      break;
 
698
    }
 
699
  }
 
700
 
 
701
  if (found&&(howOften>=-1||howOften==-98)) {
 
702
    found=false;
 
703
    for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
 
704
      CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
 
705
      CglProbing * cgl = dynamic_cast<CglProbing *>(generator);
 
706
      if (cgl) {
 
707
        found=true;
 
708
        break;
 
709
      }
 
710
    }
 
711
    if (!found) {
 
712
      if (howOften==-1)
 
713
        howOften=-98;
 
714
      else if (howOften==-98)
 
715
        howOften=-99;
 
716
      model.addCutGenerator(&generator1,setting,"Probing");
 
717
      CbcCutGenerator * generator = 
 
718
        model.cutGenerator(numberGenerators);
 
719
      generator->setHowOften(howOften);
 
720
      numberGenerators++;
 
721
    }
 
722
  }
 
723
  found=false;
 
724
  for (iGenerator=0;iGenerator<numberParentGenerators;iGenerator++) {
 
725
    CglCutGenerator * generator = parentModel_->cutGenerator(iGenerator)->generator();
 
726
    CglGomory * cgl = dynamic_cast<CglGomory *>(generator);
 
727
    if (cgl) {
 
728
      found=true;
 
729
      howOften = parentModel_->cutGenerator(iGenerator)->howOften();
 
730
      break;
 
731
    }
 
732
  }
 
733
  if (found&&howOften>=0) {
 
734
    found=false;
 
735
    for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
 
736
      CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
 
737
      CglGomory * cgl = dynamic_cast<CglGomory *>(generator);
 
738
      if (cgl) {
 
739
        found=true;
 
740
        break;
 
741
      }
 
742
    }
 
743
    if (!found)
 
744
      model.addCutGenerator(&generator2,setting,"Gomory");
 
745
  }
 
746
  found=false;
 
747
  for (iGenerator=0;iGenerator<numberParentGenerators;iGenerator++) {
 
748
    CglCutGenerator * generator = parentModel_->cutGenerator(iGenerator)->generator();
 
749
    CglKnapsackCover * cgl = dynamic_cast<CglKnapsackCover *>(generator);
 
750
    if (cgl) {
 
751
      found=true;
 
752
      howOften = parentModel_->cutGenerator(iGenerator)->howOften();
 
753
      break;
 
754
    }
 
755
  }
 
756
  if (found&&howOften>=0) {
 
757
    found=false;
 
758
    for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
 
759
      CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
 
760
      CglKnapsackCover * cgl = dynamic_cast<CglKnapsackCover *>(generator);
 
761
      if (cgl) {
 
762
        found=true;
 
763
        break;
 
764
      }
 
765
    }
 
766
    if (!found)
 
767
      model.addCutGenerator(&generator3,setting,"Knapsack");
 
768
  }
 
769
  found=false;
 
770
  for (iGenerator=0;iGenerator<numberParentGenerators;iGenerator++) {
 
771
    CglCutGenerator * generator = parentModel_->cutGenerator(iGenerator)->generator();
 
772
    CglClique * cgl = dynamic_cast<CglClique *>(generator);
 
773
    if (cgl) {
 
774
      found=true;
 
775
      howOften = parentModel_->cutGenerator(iGenerator)->howOften();
 
776
      break;
 
777
    }
 
778
  }
 
779
  if (found&&howOften>=0) {
 
780
    found=false;
 
781
    for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
 
782
      CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
 
783
      CglClique * cgl = dynamic_cast<CglClique *>(generator);
 
784
      if (cgl) {
 
785
        found=true;
 
786
        break;
 
787
      }
 
788
    }
 
789
    if (!found)
 
790
      model.addCutGenerator(&generator5,setting,"Clique");
 
791
  }
 
792
  found=false;
 
793
  for (iGenerator=0;iGenerator<numberParentGenerators;iGenerator++) {
 
794
    CglCutGenerator * generator = parentModel_->cutGenerator(iGenerator)->generator();
 
795
    CglFlowCover * cgl = dynamic_cast<CglFlowCover *>(generator);
 
796
    if (cgl) {
 
797
      found=true;
 
798
      howOften = parentModel_->cutGenerator(iGenerator)->howOften();
 
799
      break;
 
800
    }
 
801
  }
 
802
  if (found&&howOften>=0) {
 
803
    found=false;
 
804
    for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
 
805
      CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
 
806
      CglFlowCover * cgl = dynamic_cast<CglFlowCover *>(generator);
 
807
      if (cgl) {
 
808
        found=true;
 
809
        break;
 
810
      }
 
811
    }
 
812
    if (!found)
 
813
      model.addCutGenerator(&flowGen,setting,"FlowCover");
 
814
    found=false;
 
815
  }
 
816
  for (iGenerator=0;iGenerator<numberParentGenerators;iGenerator++) {
 
817
    CglCutGenerator * generator = parentModel_->cutGenerator(iGenerator)->generator();
 
818
    CglMixedIntegerRounding2 * cgl = dynamic_cast<CglMixedIntegerRounding2 *>(generator);
 
819
    if (cgl) {
 
820
      found=true;
 
821
      howOften = parentModel_->cutGenerator(iGenerator)->howOften();
 
822
      break;
 
823
    }
 
824
  }
 
825
  if (found&&howOften>=0) {
 
826
    found=false;
 
827
    for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
 
828
      CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
 
829
      CglMixedIntegerRounding2 * cgl = dynamic_cast<CglMixedIntegerRounding2 *>(generator);
 
830
      if (cgl) {
 
831
        found=true;
 
832
        break;
 
833
      }
 
834
    }
 
835
    if (!found)
 
836
      model.addCutGenerator(&mixedGen,setting,"MixedIntegerRounding2");
 
837
  }
 
838
#if 0
 
839
  // Say we want timings
 
840
  int newNumberGenerators = model.numberCutGenerators();
 
841
  for (iGenerator=numberGenerators;iGenerator<newNumberGenerators;iGenerator++) {
 
842
    CbcCutGenerator * generator = model.cutGenerator(iGenerator);
 
843
    generator->setTiming(true);
 
844
  }
 
845
#endif
 
846
  if (model.getNumCols()<500)
 
847
    model.setMaximumCutPassesAtRoot(-100); // always do 100 if possible
 
848
  else if (model.getNumCols()<5000)
 
849
    model.setMaximumCutPassesAtRoot(100); // use minimum drop
 
850
  else
 
851
    model.setMaximumCutPassesAtRoot(20);
 
852
}
 
853
// Setup heuristics
 
854
void 
 
855
CbcStrategyDefaultSubTree::setupHeuristics(CbcModel & model)
 
856
{
 
857
  // Allow rounding heuristic
 
858
 
 
859
  CbcRounding heuristic1(model);
 
860
  heuristic1.setHeuristicName("rounding");
 
861
  int numberHeuristics = model.numberHeuristics();
 
862
  int iHeuristic;
 
863
  bool found;
 
864
  found=false;
 
865
  for (iHeuristic=0;iHeuristic<numberHeuristics;iHeuristic++) {
 
866
    CbcHeuristic * heuristic = model.heuristic(iHeuristic);
 
867
    CbcRounding * cgl = dynamic_cast<CbcRounding *>(heuristic);
 
868
    if (cgl) {
 
869
      found=true;
 
870
      break;
 
871
    }
 
872
  }
 
873
  if (!found)
 
874
    model.addHeuristic(&heuristic1);
 
875
}
 
876
// Do printing stuff
 
877
void 
 
878
CbcStrategyDefaultSubTree::setupPrinting(CbcModel & model,int modelLogLevel)
 
879
{
 
880
  if (!modelLogLevel) {
 
881
    model.solver()->setHintParam(OsiDoReducePrint,true,OsiHintTry);
 
882
    model.messageHandler()->setLogLevel(0);
 
883
    model.solver()->messageHandler()->setLogLevel(0);
 
884
  } else if (modelLogLevel==1) {
 
885
    model.solver()->setHintParam(OsiDoReducePrint,true,OsiHintTry);
 
886
    model.messageHandler()->setLogLevel(1);
 
887
    model.solver()->messageHandler()->setLogLevel(0);
 
888
  } else {
 
889
    model.messageHandler()->setLogLevel(2);
 
890
    model.solver()->messageHandler()->setLogLevel(1);
 
891
    model.setPrintFrequency(50);
 
892
  }
 
893
}
 
894
// Other stuff e.g. strong branching
 
895
void 
 
896
CbcStrategyDefaultSubTree::setupOther(CbcModel & model)
 
897
{
 
898
  model.setNumberStrong(numberStrong_);
 
899
  model.setNumberBeforeTrust(numberBeforeTrust_);
 
900
}
 
901
// For uniform setting of cut and heuristic options
 
902
void 
 
903
setCutAndHeuristicOptions(CbcModel & model)
 
904
{
 
905
  int numberGenerators = model.numberCutGenerators();
 
906
  int iGenerator;
 
907
  for (iGenerator=0;iGenerator<numberGenerators;iGenerator++) {
 
908
    CglCutGenerator * generator = model.cutGenerator(iGenerator)->generator();
 
909
    CglProbing * cglProbing = dynamic_cast<CglProbing *>(generator);
 
910
    if (cglProbing) {
 
911
      cglProbing->setUsingObjective(1);
 
912
      cglProbing->setMaxPass(1);
 
913
      cglProbing->setMaxPassRoot(1);
 
914
      // Number of unsatisfied variables to look at
 
915
      cglProbing->setMaxProbe(10);
 
916
      cglProbing->setMaxProbeRoot(50);
 
917
      //cglProbing->setMaxProbeRoot(123);
 
918
      // How far to follow the consequences
 
919
      cglProbing->setMaxLook(5);
 
920
      cglProbing->setMaxLookRoot(50);
 
921
      cglProbing->setMaxLookRoot(10);
 
922
      // Only look at rows with fewer than this number of elements
 
923
      cglProbing->setMaxElements(200);
 
924
      cglProbing->setMaxElementsRoot(300);
 
925
      cglProbing->setRowCuts(3);
 
926
    }
 
927
#if 0
 
928
    CglGomory * cglGomory = dynamic_cast<CglGomory *>(generator);
 
929
    if (cglGomory) {
 
930
      // try larger limit
 
931
      cglGomory->setLimitAtRoot(1000);
 
932
      cglGomory->setLimit(50);
 
933
    }
 
934
    CglKnapsackCover * cglKnapsackCover = dynamic_cast<CglKnapsackCover *>(generator);
 
935
    if (cglKnapsackCover) {
 
936
    }
 
937
#endif
 
938
  }
 
939
}
 
940
 
 
941
 
 
942