source: trunk/Cbc/examples/fast0507.cpp

Last change on this file was 2469, checked in by unxusr, 6 weeks ago

formatting

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 11.6 KB
Line 
1// $Id: fast0507.cpp 2469 2019-01-06 23:17:46Z unxusr $
2// Copyright (C) 2005, 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 <cassert>
7#include <iomanip>
8
9#include "CoinPragma.hpp"
10
11// For Branch and bound
12#include "OsiSolverInterface.hpp"
13#include "CbcModel.hpp"
14#include "CbcBranchActual.hpp"
15#include "CbcBranchUser.hpp"
16#include "CbcBranchCut.hpp"
17#include "CbcBranchToFixLots.hpp"
18#include "CbcCompareUser.hpp"
19#include "CbcCutGenerator.hpp"
20#include "CbcHeuristicGreedy.hpp"
21#include "OsiClpSolverInterface.hpp"
22#include "CbcSolver3.hpp"
23
24// Cuts
25
26#include "CglGomory.hpp"
27#include "CglProbing.hpp"
28#include "CglKnapsackCover.hpp"
29#include "CglOddHole.hpp"
30#include "CglClique.hpp"
31#include "CglFlowCover.hpp"
32#include "CglMixedIntegerRounding.hpp"
33#include "CglMixedIntegerRounding2.hpp"
34// Preprocessing
35#include "CglPreProcess.hpp"
36
37#include "CoinTime.hpp"
38
39//#############################################################################
40
41/************************************************************************
42
43This main program reads in an integer model from an mps file.
44
45It then sets up some Cgl cut generators and calls branch and cut.
46
47Branching is simple binary branching on integer variables.
48
49Node selection is depth first until first solution is found and then
50based on objective and number of unsatisfied integer variables.
51In this example the functionality is the same as default but it is
52a user comparison function.
53
54Variable branching selection is on maximum minimum-of-up-down change
55after strong branching on 5 variables closest to 0.5.
56
57A simple rounding heuristic is used.
58
59
60************************************************************************/
61
62// ****** define comparison to choose best next node
63
64int main(int argc, const char *argv[])
65{
66
67  CbcSolver3 solver1;
68
69  // Read in model using argv[1]
70  // and assert that it is a clean model
71  std::string mpsFileName;
72  if (argc >= 2)
73    mpsFileName = argv[1];
74  int numMpsReadErrors = solver1.readMps(mpsFileName.c_str(), "");
75  if (numMpsReadErrors != 0) {
76    printf("%d errors reading MPS file\n", numMpsReadErrors);
77    return numMpsReadErrors;
78  }
79  double time1 = CoinCpuTime();
80
81  /* Options are:
82     preprocess to do preprocessing
83     time in minutes
84     if 2 parameters and numeric taken as time
85  */
86  bool preProcess = false;
87  double minutes = -1.0;
88  int nGoodParam = 0;
89  for (int iParam = 2; iParam < argc; iParam++) {
90    if (!strcmp(argv[iParam], "preprocess")) {
91      preProcess = true;
92      nGoodParam++;
93    } else if (!strcmp(argv[iParam], "time")) {
94      if (iParam + 1 < argc && isdigit(argv[iParam + 1][0])) {
95        minutes = atof(argv[iParam + 1]);
96        if (minutes >= 0.0) {
97          nGoodParam += 2;
98          iParam++; // skip time
99        }
100      }
101    }
102  }
103  if (nGoodParam == 0 && argc == 3 && isdigit(argv[2][0])) {
104    // If time is given then stop after that number of minutes
105    minutes = atof(argv[2]);
106    if (minutes >= 0.0)
107      nGoodParam = 1;
108  }
109  if (nGoodParam != argc - 2) {
110    printf("Usage <file> [preprocess] [time <minutes>] or <file> <minutes>\n");
111    exit(1);
112  }
113  solver1.initialSolve();
114  // Reduce printout
115  solver1.setHintParam(OsiDoReducePrint, true, OsiHintTry);
116  // Say we want scaling
117  //solver1.setHintParam(OsiDoScale,true,OsiHintTry);
118  //solver1.setCleanupScaling(1);
119  // See if we want preprocessing
120  OsiSolverInterface *solver2 = &solver1;
121  CglPreProcess process;
122  if (preProcess) {
123    /* Do not try and produce equality cliques and
124       do up to 5 passes */
125    solver2 = process.preProcess(solver1, false, 5);
126    if (!solver2) {
127      printf("Pre-processing says infeasible\n");
128      exit(2);
129    }
130    solver2->resolve();
131  }
132  CbcModel model(*solver2);
133  // Point to solver
134  OsiSolverInterface *solver3 = model.solver();
135  CbcSolver3 *osiclp = dynamic_cast< CbcSolver3 * >(solver3);
136  assert(osiclp);
137  const double fractionFix = 0.985;
138  osiclp->initialize(&model, NULL);
139  osiclp->setAlgorithm(2);
140  osiclp->setMemory(1000);
141  osiclp->setNested(fractionFix);
142  //osiclp->setNested(1.0); //off
143  // Set up some cut generators and defaults
144  // Probing first as gets tight bounds on continuous
145
146  CglProbing generator1;
147  generator1.setUsingObjective(true);
148  generator1.setMaxPass(3);
149  // Number of unsatisfied variables to look at
150  generator1.setMaxProbe(10);
151  // How far to follow the consequences
152  generator1.setMaxLook(50);
153  // Only look at rows with fewer than this number of elements
154  generator1.setMaxElements(200);
155  generator1.setRowCuts(3);
156
157  CglGomory generator2;
158  // try larger limit
159  generator2.setLimit(300);
160
161  CglKnapsackCover generator3;
162
163  CglOddHole generator4;
164  generator4.setMinimumViolation(0.005);
165  generator4.setMinimumViolationPer(0.00002);
166  // try larger limit
167  generator4.setMaximumEntries(200);
168
169  CglClique generator5;
170  generator5.setStarCliqueReport(false);
171  generator5.setRowCliqueReport(false);
172
173  CglMixedIntegerRounding mixedGen;
174  /* This is same as default constructor -
175     (1,true,1)
176      I presume if maxAggregate larger then slower but maybe better
177      criterion can be  1 through 3
178      Reference:
179      Hugues Marchand and Laurence A. Wolsey
180      Aggregation and Mixed Integer Rounding to Solve MIPs
181      Operations Research, 49(3), May-June 2001.
182   */
183  int maxAggregate = 1;
184  bool multiply = true;
185  int criterion = 1;
186  CglMixedIntegerRounding2 mixedGen2(maxAggregate, multiply, criterion);
187  CglFlowCover flowGen;
188
189  // Add in generators
190  // Experiment with -1 and -99 etc
191  model.addCutGenerator(&generator1, -99, "Probing");
192  //model.addCutGenerator(&generator2,-1,"Gomory");
193  //model.addCutGenerator(&generator3,-1,"Knapsack");
194  //model.addCutGenerator(&generator4,-1,"OddHole");
195  //model.addCutGenerator(&generator5,-1,"Clique");
196  //model.addCutGenerator(&flowGen,-1,"FlowCover");
197  //model.addCutGenerator(&mixedGen,-1,"MixedIntegerRounding");
198  //model.addCutGenerator(&mixedGen2,-1,"MixedIntegerRounding2");
199  // Say we want timings
200  int numberGenerators = model.numberCutGenerators();
201  int iGenerator;
202  for (iGenerator = 0; iGenerator < numberGenerators; iGenerator++) {
203    CbcCutGenerator *generator = model.cutGenerator(iGenerator);
204    generator->setTiming(true);
205  }
206
207  // Allow rounding heuristic
208
209  CbcRounding heuristic1(model);
210  model.addHeuristic(&heuristic1);
211
212  // And Greedy heuristic
213
214  CbcHeuristicGreedyCover heuristic2(model);
215  // Use original upper and perturb more
216  heuristic2.setAlgorithm(11);
217  model.addHeuristic(&heuristic2);
218
219  // Redundant definition of default branching (as Default == User)
220  CbcBranchUserDecision branch;
221  model.setBranchingMethod(&branch);
222
223  // Definition of node choice
224  CbcCompareUser compare;
225  model.setNodeComparison(compare);
226
227  int iColumn;
228  int numberColumns = solver3->getNumCols();
229  // do pseudo costs
230  CbcObject **objects = new CbcObject *[numberColumns + 1];
231  const CoinPackedMatrix *matrix = solver3->getMatrixByCol();
232  // Column copy
233  const int *columnLength = matrix->getVectorLengths();
234  const double *objective = model.getObjCoefficients();
235  int n = 0;
236  for (iColumn = 0; iColumn < numberColumns; iColumn++) {
237    if (solver3->isInteger(iColumn)) {
238      double costPer = objective[iColumn] / ((double)columnLength[iColumn]);
239      CbcSimpleIntegerPseudoCost *newObject = new CbcSimpleIntegerPseudoCost(&model, n, iColumn,
240        costPer, costPer);
241      newObject->setMethod(3);
242      objects[n++] = newObject;
243    }
244  }
245  // and special fix lots branch
246  objects[n++] = new CbcBranchToFixLots(&model, -1.0e-6, fractionFix + 0.01, 1, 0, NULL);
247  model.addObjects(n, objects);
248  for (iColumn = 0; iColumn < n; iColumn++)
249    delete objects[iColumn];
250  delete[] objects;
251  // High priority for odd object
252  int followPriority = 1;
253  model.passInPriorities(&followPriority, true);
254
255  // Do initial solve to continuous
256  model.initialSolve();
257
258  // Could tune more
259  model.setMinimumDrop(CoinMin(1.0,
260    fabs(model.getMinimizationObjValue()) * 1.0e-3 + 1.0e-4));
261
262  if (model.getNumCols() < 500)
263    model.setMaximumCutPassesAtRoot(-100); // always do 100 if possible
264  else if (model.getNumCols() < 5000)
265    model.setMaximumCutPassesAtRoot(100); // use minimum drop
266  else
267    model.setMaximumCutPassesAtRoot(20);
268  //model.setMaximumCutPasses(1);
269
270  // Do more strong branching if small
271  //if (model.getNumCols()<5000)
272  //model.setNumberStrong(10);
273  // Switch off strong branching if wanted
274  model.setNumberStrong(0);
275
276  model.solver()->setIntParam(OsiMaxNumIterationHotStart, 100);
277
278  // If time is given then stop after that number of minutes
279  if (minutes >= 0.0) {
280    std::cout << "Stopping after " << minutes << " minutes" << std::endl;
281    model.setDblParam(CbcModel::CbcMaximumSeconds, 60.0 * minutes);
282  }
283  // Switch off most output
284  if (model.getNumCols() < 300000) {
285    model.messageHandler()->setLogLevel(1);
286    //model.solver()->messageHandler()->setLogLevel(0);
287  } else {
288    model.messageHandler()->setLogLevel(2);
289    model.solver()->messageHandler()->setLogLevel(1);
290  }
291  //model.messageHandler()->setLogLevel(2);
292  //model.solver()->messageHandler()->setLogLevel(2);
293  //model.setPrintFrequency(50);
294#define DEBUG_CUTS
295#ifdef DEBUG_CUTS
296  // Set up debugger by name (only if no preprocesing)
297  if (!preProcess) {
298    std::string problemName;
299    //model.solver()->getStrParam(OsiProbName,problemName) ;
300    //model.solver()->activateRowCutDebugger(problemName.c_str()) ;
301    model.solver()->activateRowCutDebugger("cap6000a");
302  }
303#endif
304
305  // Do complete search
306  try {
307    model.branchAndBound();
308  } catch (CoinError e) {
309    e.print();
310    if (e.lineNumber() >= 0)
311      std::cout << "This was from a CoinAssert" << std::endl;
312    exit(0);
313  }
314  //void printHowMany();
315  //printHowMany();
316  std::cout << mpsFileName << " took " << CoinCpuTime() - time1 << " seconds, "
317            << model.getNodeCount() << " nodes with objective "
318            << model.getObjValue()
319            << (!model.status() ? " Finished" : " Not finished")
320            << std::endl;
321
322  // Print more statistics
323  std::cout << "Cuts at root node changed objective from " << model.getContinuousObjective()
324            << " to " << model.rootObjectiveAfterCuts() << std::endl;
325
326  for (iGenerator = 0; iGenerator < numberGenerators; iGenerator++) {
327    CbcCutGenerator *generator = model.cutGenerator(iGenerator);
328    std::cout << generator->cutGeneratorName() << " was tried "
329              << generator->numberTimesEntered() << " times and created "
330              << generator->numberCutsInTotal() << " cuts of which "
331              << generator->numberCutsActive() << " were active after adding rounds of cuts";
332    if (generator->timing())
333      std::cout << " ( " << generator->timeInCutGenerator() << " seconds)" << std::endl;
334    else
335      std::cout << std::endl;
336  }
337  // Print solution if finished - we can't get names from Osi!
338
339  if (model.getMinimizationObjValue() < 1.0e50) {
340    // post process
341    if (preProcess)
342      process.postProcess(*model.solver());
343    int numberColumns = model.solver()->getNumCols();
344
345    const double *solution = model.solver()->getColSolution();
346
347    int iColumn;
348    std::cout << std::setiosflags(std::ios::fixed | std::ios::showpoint) << std::setw(14);
349
350    std::cout << "--------------------------------------" << std::endl;
351    for (iColumn = 0; iColumn < numberColumns; iColumn++) {
352      double value = solution[iColumn];
353      if (fabs(value) > 1.0e-7 && model.solver()->isInteger(iColumn))
354        std::cout << std::setw(6) << iColumn << " " << value << std::endl;
355    }
356    std::cout << "--------------------------------------" << std::endl;
357
358    std::cout << std::resetiosflags(std::ios::fixed | std::ios::showpoint | std::ios::scientific);
359  }
360  return 0;
361}
Note: See TracBrowser for help on using the repository browser.