source: trunk/Cbc/examples/sample3.cpp @ 2469

Last change on this file since 2469 was 2469, checked in by unxusr, 10 months ago

formatting

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 13.7 KB
Line 
1// $Id: sample3.cpp 2469 2019-01-06 23:17:46Z unxusr $
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#include "CbcConfig.h"
7
8#include "CoinPragma.hpp"
9
10#include <assert.h>
11#include <iomanip>
12
13// For Branch and bound
14#include "OsiSolverInterface.hpp"
15#include "CbcModel.hpp"
16#include "CbcBranchUser.hpp"
17#include "CbcCompareUser.hpp"
18#include "CbcTreeLocal.hpp"
19#include "CbcCutGenerator.hpp"
20#include "CbcHeuristicLocal.hpp"
21#include "OsiClpSolverInterface.hpp"
22
23// Cuts
24
25#include "CglGomory.hpp"
26#include "CglProbing.hpp"
27#include "CglKnapsackCover.hpp"
28#include "CglOddHole.hpp"
29#include "CglClique.hpp"
30
31// Heuristics
32
33#include "CbcHeuristic.hpp"
34#include "CoinTime.hpp"
35
36//#############################################################################
37
38/************************************************************************
39
40This main program reads in an integer model from an mps file.
41
42It then sets up some Cgl cut generators and calls branch and cut.
43
44Branching is simple binary branching on integer variables.
45
46Node selection is depth first until first solution is found and then
47based on objective and number of unsatisfied integer variables.
48In this example the functionality is the same as default but it is
49a user comparison function.
50
51Variable branching selection is on maximum minimum-of-up-down change
52after strong branching on 5 variables closest to 0.5.
53
54A simple rounding heuristic is used.
55
56
57************************************************************************/
58// See if option there and return integer value - or -123456
59bool option(int argc, const char *argv[], const char *check, int &value)
60{
61  value = -123456;
62  for (int i = 1; i < argc; i++) {
63    if (const char *x = strstr(argv[i], check)) {
64      // see if at beginning
65      if (x == argv[i] || (x == argv[i] + 1 && argv[i][0] == '-')) {
66        // see if =
67        x = strchr(argv[i], '=');
68        if (x) {
69          value = atoi(x + 1);
70        } else if (i < argc - 1) {
71          value = atoi(argv[i + 1]);
72        }
73        return true;
74      }
75    }
76  }
77  return false;
78}
79
80// ****** define comparison to choose best next node
81
82int main(int argc, const char *argv[])
83{
84
85  // Define your favorite OsiSolver
86
87  OsiClpSolverInterface solver1;
88  //solver1.messageHandler()->setLogLevel(0);
89  solver1.getModelPtr()->setDualBound(1.0e10);
90
91  if (argc <= 1) {
92    printf("using %s <modelfile>\n", argv[0]);
93    return 1;
94  }
95
96  // Read in model using argv[1]
97  // and assert that it is a clean model
98  int numMpsReadErrors = solver1.readMps(argv[1], "");
99  if (numMpsReadErrors != 0) {
100    printf("%d errors reading MPS file\n", numMpsReadErrors);
101    return numMpsReadErrors;
102  }
103  // do here so integers correct
104  CbcModel model(solver1);
105  model.solver()->setHintParam(OsiDoReducePrint, true, OsiHintTry);
106
107  // Set up some cut generators and defaults
108  // Probing first as gets tight bounds on continuous
109
110  CglProbing generator1;
111  generator1.setUsingObjective(true);
112  generator1.setMaxPass(3);
113  generator1.setMaxProbe(100);
114  generator1.setMaxLook(50);
115  generator1.setRowCuts(3);
116
117  CglGomory generator2;
118  // try larger limit
119  generator2.setLimit(300);
120
121  CglKnapsackCover generator3;
122
123  CglOddHole generator4;
124  generator4.setMinimumViolation(0.005);
125  generator4.setMinimumViolationPer(0.00002);
126  // try larger limit
127  generator4.setMaximumEntries(200);
128
129  CglClique generator5;
130
131  // Add in generators
132  model.addCutGenerator(&generator1, -1, "Probing");
133  // You may want to switch these off for local search on some problems
134  //model.addCutGenerator(&generator2,-1,"Gomory");
135  model.addCutGenerator(&generator2, -99, "Gomory");
136  //model.addCutGenerator(&generator3,-1,"Knapsack");
137  model.addCutGenerator(&generator4, -99, "OddHole");
138  model.addCutGenerator(&generator5, -99, "Clique");
139
140  // Allow rounding heuristic
141
142  CbcRounding heuristic1(model);
143  model.addHeuristic(&heuristic1);
144
145  // Redundant definition of default branching (as Default == User)
146  CbcBranchUserDecision branch;
147  model.setBranchingMethod(&branch);
148
149  // Definition of node choice
150  CbcCompareUser compare;
151  model.setNodeComparison(compare);
152
153  // Do initial solve to continuous
154  model.initialSolve();
155  //model.solver()->setHintParam(OsiDoScale,false,OsiHintTry);
156
157  // Could tune more
158  model.setMinimumDrop(CoinMin(1.0,
159    fabs(model.getMinimizationObjValue()) * 1.0e-3 + 1.0e-4));
160
161  if (model.getNumCols() < 500)
162    model.setMaximumCutPassesAtRoot(-100); // always do 100 if possible
163  else if (model.getNumCols() < 5000)
164    model.setMaximumCutPassesAtRoot(100); // use minimum drop
165  else
166    model.setMaximumCutPassesAtRoot(20);
167  //model.setMaximumCutPasses(5);
168
169  // Do more strong branching if small
170  if (model.getNumCols() < 5000)
171    model.setNumberStrong(10);
172  // Switch off strong branching if wanted
173  //model.setNumberStrong(0);
174
175  model.solver()->setIntParam(OsiMaxNumIterationHotStart, 100);
176
177  // If time is given then stop after that number of minutes
178  if (argc == 3) {
179    int minutes = atoi(argv[2]);
180    if (minutes > 0 && minutes < 1000000) {
181      std::cout << "Stopping after " << minutes << " minutes" << std::endl;
182      model.setDblParam(CbcModel::CbcMaximumSeconds, 60.0 * minutes);
183      argc = 0; // stop other options
184    }
185  }
186  int optionValue;
187  if (option(argc, argv, "minute", optionValue)) {
188    int minutes = optionValue;
189    if (minutes > 0 && minutes < 1000000) {
190      std::cout << "Stopping after " << minutes << " minutes" << std::endl;
191      model.setDblParam(CbcModel::CbcMaximumSeconds, 60.0 * minutes);
192    }
193  }
194
195  // Switch off most output
196  if (model.getNumCols() < 3000) {
197    model.messageHandler()->setLogLevel(1);
198    //model.solver()->messageHandler()->setLogLevel(0);
199  } else {
200    model.messageHandler()->setLogLevel(2);
201    model.solver()->messageHandler()->setLogLevel(1);
202  }
203  if (option(argc, argv, "print", optionValue)) {
204    if (optionValue == 3) {
205      model.messageHandler()->setLogLevel(3);
206      model.solver()->messageHandler()->setLogLevel(3);
207    } else {
208      model.messageHandler()->setLogLevel(2);
209      model.solver()->messageHandler()->setLogLevel(1);
210    }
211  }
212  //model.setPrintFrequency(50);
213
214  double time1 = CoinCpuTime();
215
216  if (option(argc, argv, "clique", optionValue)) {
217    printf("Finding cliques\n");
218    // Find cliques
219    int numberColumns = model.getNumCols();
220    int numberIntegers = 0;
221    int *integerVariable = new int[numberColumns];
222    int i;
223    for (i = 0; i < numberColumns; i++) {
224      if (model.isInteger(i)) {
225        integerVariable[numberIntegers++] = i;
226        //model.solver()->setContinuous(i);
227      }
228    }
229    model.findCliques(false, 2, 1000);
230    // give cliques high priority but leave integers to improve time
231    int numberCliques = model.numberObjects() - numberIntegers;
232    int *priority = new int[numberIntegers + numberCliques];
233    for (i = 0; i < numberIntegers; i++)
234      priority[i] = 10000 + i;
235    for (; i < numberIntegers + numberCliques; i++)
236      priority[i] = i;
237    model.passInPriorities(priority, false);
238    delete[] priority;
239    delete[] integerVariable;
240    model.messageHandler()->setLogLevel(2);
241  }
242  if (option(argc, argv, "presolvelocal", optionValue)) {
243    // integer presolve
244    CbcModel *model2 = model.integerPresolve();
245    if (model2) {
246      // Do complete search
247      model2->branchAndBound();
248      // get back solution
249      model.originalModel(model2, false);
250    } else {
251      // infeasible
252      exit(1);
253    }
254  } else if (option(argc, argv, "presolve", optionValue)) {
255    // integer presolve
256    CbcModel *model2 = model.integerPresolve();
257    if (model2) {
258      int maxNodes = 2000;
259      int k = 10;
260      CbcTreeLocal localTree(model2, NULL, k, 0, 1, 10000, maxNodes);
261      model2->passInTreeHandler(localTree);
262      // Do complete search
263      model2->branchAndBound();
264      // get back solution
265      model.originalModel(model2, false);
266    } else {
267      // infeasible
268      exit(1);
269    }
270  } else if (option(argc, argv, "localprove", optionValue)) {
271    int maxNodes = 2000;
272    int k = 10;
273    CbcTreeLocal localTree(&model, NULL, k, 0, 1, 10000, maxNodes);
274    model.passInTreeHandler(localTree);
275    model.branchAndBound();
276  } else if (option(argc, argv, "local", optionValue)) {
277    int maxNodes = 2000;
278    int k = 10;
279    double *solution = NULL;
280    // trying to get best solution to fast0507
281    // (so we can debug why localTree (prove) cut off solution!
282    int numberColumns = model.getNumCols();
283    if (numberColumns == 63009) {
284      solution = new double[numberColumns];
285      memset(solution, 0, numberColumns * sizeof(double));
286      int seq[] = {
287        245, 246, 395, 582, 813, 1432, 2009, 2063, 2455, 2879,
288        3027, 3116, 3154, 3258, 3675, 5548, 5890, 6229, 6318, 6595,
289        6852, 6859, 7279, 7565, 7604, 7855, 9160, 9259, 9261, 9296,
290        9318, 10080, 10339, 10349, 10652, 10874, 11046, 11396, 11812, 11968,
291        12129, 12321, 12495, 12650, 13182, 13350, 14451, 15198, 15586, 17876,
292        18537, 19742, 19939, 19969, 20646, 20667, 20668, 23810, 25973, 27238,
293        27510, 27847, 30708, 31164, 33189, 36506, 36881, 38025, 38070, 38216,
294        38381, 39076, 39397, 39708, 40770, 40831, 41017, 41164, 41195, 41227,
295        41384, 41743, 42451, 42776, 42833, 43991, 44904, 45045, 45718, 47860,
296        47896, 48180, 48257, 48461, 48961, 49227, 51278, 52534, 53275, 54856,
297        55672, 55674, 55760, 55822, 56641, 56703, 56892, 56964, 57117, 57556,
298        57905, 59936, 61649, 62319, 62387
299      };
300      double intSolnV[] = {
301        1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
302        1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
303        1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
304        1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
305        1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
306        1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
307        1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
308        1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
309        1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
310        1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
311        1., 1., 1., 1., 1., 1., 1., 1., 1., 1.,
312        1., 1., 1., 1., 1.
313      };
314      int n = sizeof(seq) / sizeof(int);
315      for (int i = 0; i < n; i++)
316        solution[seq[i]] = intSolnV[i];
317      k = 50;
318    }
319    CbcTreeLocal localTree(&model, solution, k, 0, 50, 10000, maxNodes);
320    delete[] solution;
321    model.passInTreeHandler(localTree);
322    model.branchAndBound();
323  } else if (option(argc, argv, "1local", optionValue)) {
324    // test giving cbc a solution
325    CbcModel model2 = model;
326    model2.setMaximumSolutions(1);
327    model2.branchAndBound();
328    if (model2.status() && model2.getMinimizationObjValue() < 1.0e50) {
329      // Definition of local search
330      const double *solution = model2.solver()->getColSolution();
331      CbcTreeLocal localTree(&model, solution, 2);
332      model.passInTreeHandler(localTree);
333      model.branchAndBound();
334    } else {
335      model = model2;
336    }
337  } else {
338    // Do complete search
339
340    model.branchAndBound();
341  }
342
343  std::cout << argv[1] << " took " << CoinCpuTime() - time1 << " seconds, "
344            << model.getNodeCount() << " nodes with objective "
345            << model.getObjValue()
346            << (!model.status() ? " Finished" : " Not finished")
347            << std::endl;
348
349  // Print more statistics
350  std::cout << "Cuts at root node changed objective from " << model.getContinuousObjective()
351            << " to " << model.rootObjectiveAfterCuts() << std::endl;
352
353  int numberGenerators = model.numberCutGenerators();
354  for (int iGenerator = 0; iGenerator < numberGenerators; iGenerator++) {
355    CbcCutGenerator *generator = model.cutGenerator(iGenerator);
356    std::cout << generator->cutGeneratorName() << " was tried "
357              << generator->numberTimesEntered() << " times and created "
358              << generator->numberCutsInTotal() << " cuts of which "
359              << generator->numberCutsActive() << " were active after adding rounds of cuts"
360              << std::endl;
361  }
362  if (model.numberGlobalViolations())
363    std::cout << "Global cuts were active " << model.numberGlobalViolations() << " times" << std::endl;
364  // Print solution if finished - we can't get names from Osi!
365
366  if (model.getMinimizationObjValue() < 1.0e50) {
367    int numberColumns = model.solver()->getNumCols();
368
369    const double *solution = model.solver()->getColSolution();
370
371    int iColumn;
372    std::cout << std::setiosflags(std::ios::fixed | std::ios::showpoint) << std::setw(14);
373
374    std::cout << "--------------------------------------" << std::endl;
375    for (iColumn = 0; iColumn < numberColumns; iColumn++) {
376      double value = solution[iColumn];
377      if (fabs(value) > 1.0e-7 && model.solver()->isInteger(iColumn))
378        std::cout << std::setw(6) << iColumn << " " << value << std::endl;
379    }
380    std::cout << "--------------------------------------" << std::endl;
381
382    std::cout << std::resetiosflags(std::ios::fixed | std::ios::showpoint | std::ios::scientific);
383    int n = 0;
384    int i;
385    bool comma = false;
386    bool newLine = false;
387    for (i = 0; i < numberColumns; i++) {
388      if (solution[i] > 0.5 && model.solver()->isInteger(i)) {
389        if (comma)
390          printf(",");
391        if (newLine)
392          printf("\n");
393        printf("%d ", i);
394        comma = true;
395        newLine = false;
396        n++;
397        if (n == 10) {
398          n = 0;
399          newLine = true;
400        }
401      }
402    }
403    printf("};\n");
404    n = 0;
405    comma = false;
406    newLine = false;
407    printf("\tdouble intSolnV[]={\n");
408    for (i = 0; i < numberColumns; i++) {
409      if (solution[i] > 0.5 && model.solver()->isInteger(i)) {
410        if (comma)
411          printf(",");
412        if (newLine)
413          printf("\n");
414        int value = (int)(solution[i] + 0.5);
415        printf("%d. ", value);
416        comma = true;
417        newLine = false;
418        n++;
419        if (n == 10) {
420          n = 0;
421          newLine = true;
422        }
423      }
424    }
425    printf("};\n");
426  }
427  return 0;
428}
Note: See TracBrowser for help on using the repository browser.