source: trunk/Cbc/examples/fast0507b.cpp

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

formatting

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