1 | /*===========================================================================* |
---|
2 | * This file is part of the Abstract Library for Parallel Search (ALPS). * |
---|
3 | * * |
---|
4 | * ALPS is distributed under the Common Public License as part of the * |
---|
5 | * COIN-OR repository (http://www.coin-or.org). * |
---|
6 | * * |
---|
7 | * Authors: Yan Xu, SAS Institute Inc. * |
---|
8 | * Ted Ralphs, Lehigh University * |
---|
9 | * Laszlo Ladanyi, IBM T.J. Watson Research Center * |
---|
10 | * Matthew Saltzman, Clemson University * |
---|
11 | * * |
---|
12 | * * |
---|
13 | * Copyright (C) 2001-2004, International Business Machines * |
---|
14 | * Corporation, Lehigh University, Yan Xu, Ted Ralphs, Matthew Salzman and * |
---|
15 | * others. All Rights Reserved. * |
---|
16 | *===========================================================================*/ |
---|
17 | |
---|
18 | #ifndef AbcModel_h_ |
---|
19 | #define AbcModel_h_ |
---|
20 | |
---|
21 | //############################################################################# |
---|
22 | // This file is modified from SbbModel.hpp |
---|
23 | //############################################################################# |
---|
24 | |
---|
25 | #include <cmath> |
---|
26 | |
---|
27 | #include "CoinMessageHandler.hpp" |
---|
28 | #include "CoinWarmStartBasis.hpp" |
---|
29 | #include "OsiCuts.hpp" |
---|
30 | #include "OsiSolverInterface.hpp" |
---|
31 | |
---|
32 | #include "AbcBranchActual.h" |
---|
33 | #include "AbcCutGenerator.h" |
---|
34 | #include "AbcHeuristic.h" |
---|
35 | #include "AbcMessage.h" |
---|
36 | #include "AlpsModel.h" |
---|
37 | |
---|
38 | #include "AbcParams.h" |
---|
39 | |
---|
40 | class CglCutGenerator; |
---|
41 | |
---|
42 | class AbcBranchDecision; |
---|
43 | class AlpsTreeNode; |
---|
44 | class AbcNodeDesc; |
---|
45 | class AbcTreeNode; |
---|
46 | |
---|
47 | //############################################################################# |
---|
48 | |
---|
49 | /** Model class for ALPS Branch and Cut. */ |
---|
50 | class AbcModel : public AlpsModel { |
---|
51 | |
---|
52 | public: |
---|
53 | enum AbcIntParam { |
---|
54 | /** The maximum number of nodes before terminating */ |
---|
55 | AbcMaxNumNode=0, |
---|
56 | /** The maximum number of solutions before terminating */ |
---|
57 | AbcMaxNumSol, |
---|
58 | /** Fathoming discipline |
---|
59 | Controls objective function comparisons for purposes of |
---|
60 | fathoming by bound or determining monotonic variables. |
---|
61 | If 1, action is taken only when the current objective is |
---|
62 | strictly worse than the target. Implementation is handled |
---|
63 | by adding a small tolerance to the target. |
---|
64 | */ |
---|
65 | AbcFathomDiscipline, |
---|
66 | /** Just a marker, so that a static sized array can store parameters.*/ |
---|
67 | AbcLastIntParam |
---|
68 | }; |
---|
69 | |
---|
70 | enum AbcDblParam { |
---|
71 | /** The maximum amount the value of an integer variable can vary from |
---|
72 | integer and still be considered feasible. */ |
---|
73 | AbcIntegerTolerance = 0, |
---|
74 | /** The objective is assumed to worsen by this amount for each |
---|
75 | integer infeasibility. */ |
---|
76 | AbcInfeasibilityWeight, |
---|
77 | /** The amount by which to tighten the objective function cutoff when |
---|
78 | a new solution is discovered. */ |
---|
79 | AbcCutoffIncrement, |
---|
80 | /** Stop when the gap between the objective value of the best known |
---|
81 | solution and the best bound on the objective of any solution |
---|
82 | is less than this. |
---|
83 | This is an absolute value. Conversion from a percentage is left |
---|
84 | to the client. |
---|
85 | */ |
---|
86 | AbcAllowableGap, |
---|
87 | /** \brief The maximum number of seconds before terminating. |
---|
88 | A double should be adequate! */ |
---|
89 | AbcMaximumSeconds, |
---|
90 | /** Just a marker, so that a static sized array can store parameters.*/ |
---|
91 | AbcLastDblParam |
---|
92 | }; |
---|
93 | |
---|
94 | private: |
---|
95 | /**@name Shared problem data |
---|
96 | */ |
---|
97 | //@{ |
---|
98 | /// |
---|
99 | /// Number of rows at continuous |
---|
100 | int numberRowsAtContinuous_; |
---|
101 | /// Number of integers in problem |
---|
102 | int numberIntegers_; |
---|
103 | /// Indices of integer variables |
---|
104 | int* integerVariable_; |
---|
105 | /** Pointer to a warm start basis. */ |
---|
106 | CoinWarmStartBasis* sharedBasis_; |
---|
107 | //@} |
---|
108 | |
---|
109 | /// Message handler |
---|
110 | CoinMessageHandler * handler_; |
---|
111 | |
---|
112 | /** Flag to say if handler_ is the default handler. |
---|
113 | The default handler is deleted when the model is deleted. Other |
---|
114 | handlers (supplied by the client) will not be deleted. |
---|
115 | */ |
---|
116 | bool defaultHandler_; |
---|
117 | |
---|
118 | /// Abc messages |
---|
119 | CoinMessages messages_; |
---|
120 | |
---|
121 | /// Array for integer parameters |
---|
122 | int intParam_[AbcLastIntParam]; |
---|
123 | |
---|
124 | /// Array for double parameters |
---|
125 | double dblParam_[AbcLastDblParam]; |
---|
126 | |
---|
127 | /** The solver associated with this model. */ |
---|
128 | OsiSolverInterface* solver_; |
---|
129 | |
---|
130 | /** Ownership of the solver object |
---|
131 | The convention is that AbcModel owns the null solver. Currently there |
---|
132 | is no public method to give AbcModel a solver without giving ownership, |
---|
133 | but the hook is here. */ |
---|
134 | bool ourSolver_; |
---|
135 | |
---|
136 | /// A copy of the solver, taken at the continuous (root) node. |
---|
137 | OsiSolverInterface * continuousSolver_; |
---|
138 | |
---|
139 | /** Pointer to a warm start basis. */ |
---|
140 | CoinWarmStartBasis* basis_; |
---|
141 | |
---|
142 | /** Pointer to last warm basis. */ |
---|
143 | CoinWarmStartBasis* lastws_; |
---|
144 | |
---|
145 | /// Minimum degradation in objective value to continue cut generation |
---|
146 | double minimumDrop_; |
---|
147 | |
---|
148 | /// Best objective |
---|
149 | double bestObjective_; |
---|
150 | |
---|
151 | /// Array holding the incumbent (best) solution. |
---|
152 | double * bestSolution_; |
---|
153 | |
---|
154 | /** Array holding the current solution. |
---|
155 | This array is used more as a temporary. |
---|
156 | */ |
---|
157 | double * currentSolution_; |
---|
158 | |
---|
159 | /// Global cuts |
---|
160 | OsiCuts globalCuts_; |
---|
161 | |
---|
162 | /// Cumulative number of nodes |
---|
163 | int numberNodes_; |
---|
164 | /// Cumulative number of iterations |
---|
165 | int numberIterations_; |
---|
166 | /// Status of problem - 0 finished, 1 stopped, 2 difficulties |
---|
167 | int status_; |
---|
168 | /// Number of entries in #addedCuts_ |
---|
169 | int currentNumberCuts_; |
---|
170 | /// Maximum number of cuts |
---|
171 | int maximumNumberCuts_; |
---|
172 | /// How often to scan global cuts |
---|
173 | int howOftenGlobalScan_; |
---|
174 | |
---|
175 | /** Current limit on search tree depth |
---|
176 | |
---|
177 | The allocated size of #walkback_. Increased as needed. |
---|
178 | */ |
---|
179 | int maximumDepth_; |
---|
180 | |
---|
181 | /** Maximum number of candidates to consider for strong branching. |
---|
182 | To disable storng branching and use pseudocost branching, |
---|
183 | set this to 0. |
---|
184 | */ |
---|
185 | int numberStrong_; |
---|
186 | /// Number of cut generators |
---|
187 | int numberCutGenerators_; |
---|
188 | // Cut generators |
---|
189 | AbcCutGenerator ** generator_; |
---|
190 | /// Number of heuristics |
---|
191 | int numberHeuristics_; |
---|
192 | // Heuristic solvers |
---|
193 | AbcHeuristic ** heuristic_; |
---|
194 | |
---|
195 | /// Maximum number of cut passes at root |
---|
196 | int maximumCutPassesAtRoot_; |
---|
197 | /// Maximum number of cut passes |
---|
198 | int maximumCutPasses_; |
---|
199 | |
---|
200 | /// Variable selection function |
---|
201 | AbcBranchDecision * branchingMethod_; |
---|
202 | /// Number of solutions |
---|
203 | int numberSolutions_; |
---|
204 | /// Number of heuristic solutions |
---|
205 | int numberHeuristicSolutions_; |
---|
206 | /// Priorities |
---|
207 | int * priority_; |
---|
208 | /// |
---|
209 | AbcPseudocost **pseudoList_; |
---|
210 | /// |
---|
211 | int *pseudoIndices_; |
---|
212 | |
---|
213 | /** Abc parameters. */ |
---|
214 | AbcParams *AbcPar_; |
---|
215 | |
---|
216 | public: |
---|
217 | AbcModel() |
---|
218 | { |
---|
219 | init(); |
---|
220 | } |
---|
221 | |
---|
222 | AbcModel(const OsiSolverInterface &rhs) |
---|
223 | { |
---|
224 | init(); |
---|
225 | solver_ = rhs.clone(); |
---|
226 | ourSolver_ = true ; |
---|
227 | continuousSolver_ = NULL; |
---|
228 | int numberColumns = solver_->getNumCols(); |
---|
229 | int iColumn; |
---|
230 | if (numberColumns) { |
---|
231 | // Space for current solution |
---|
232 | currentSolution_ = new double[numberColumns]; |
---|
233 | for (iColumn = 0; iColumn < numberColumns; ++iColumn) { |
---|
234 | if( solver_->isInteger(iColumn)) |
---|
235 | numberIntegers_++; |
---|
236 | } |
---|
237 | } else { |
---|
238 | // empty model |
---|
239 | currentSolution_=NULL; |
---|
240 | } |
---|
241 | if (numberIntegers_) { |
---|
242 | integerVariable_ = new int [numberIntegers_]; |
---|
243 | numberIntegers_=0; |
---|
244 | for (iColumn=0;iColumn<numberColumns;iColumn++) { |
---|
245 | if( solver_->isInteger(iColumn)) |
---|
246 | integerVariable_[numberIntegers_++]=iColumn; |
---|
247 | } |
---|
248 | } else { |
---|
249 | integerVariable_ = NULL; |
---|
250 | } |
---|
251 | } |
---|
252 | |
---|
253 | ~AbcModel() |
---|
254 | { |
---|
255 | if ( handler_ != 0){ |
---|
256 | delete handler_; |
---|
257 | handler_ = 0; |
---|
258 | } |
---|
259 | if (priority_ != 0) { |
---|
260 | delete [] priority_; |
---|
261 | priority_ = 0; |
---|
262 | } |
---|
263 | if (currentSolution_ != 0) { |
---|
264 | delete [] currentSolution_; |
---|
265 | currentSolution_ = 0; |
---|
266 | } |
---|
267 | if (bestSolution_ != 0) { |
---|
268 | delete [] bestSolution_; |
---|
269 | bestSolution_ = 0; |
---|
270 | } |
---|
271 | if (generator_ != 0) { |
---|
272 | for (int i = 0; i < numberCutGenerators_; ++i) |
---|
273 | delete generator_[i]; |
---|
274 | delete [] generator_; |
---|
275 | generator_ = 0; |
---|
276 | } |
---|
277 | if (heuristic_ != 0) { |
---|
278 | //for (int i = 0; i < numberHeuristics_; ++i) { |
---|
279 | // if (heuristic_[i] != 0) { |
---|
280 | //delete heuristic_[i]; |
---|
281 | //heuristic_[i] = 0; |
---|
282 | // } |
---|
283 | //} |
---|
284 | delete [] heuristic_; |
---|
285 | heuristic_ = 0; |
---|
286 | } |
---|
287 | |
---|
288 | if (integerVariable_ != 0) { |
---|
289 | delete [] integerVariable_; |
---|
290 | integerVariable_ = 0; |
---|
291 | } |
---|
292 | if (sharedBasis_ != 0) { |
---|
293 | delete sharedBasis_; |
---|
294 | sharedBasis_ = 0; |
---|
295 | } |
---|
296 | if (basis_ != 0) { |
---|
297 | delete basis_; |
---|
298 | basis_ = 0; |
---|
299 | } |
---|
300 | if (pseudoList_ != NULL) { |
---|
301 | int i = getNumCols() - 1; |
---|
302 | for (; i >= 0; --i) { |
---|
303 | //printf("i = %d\n", i); |
---|
304 | delete pseudoList_[i]; |
---|
305 | } |
---|
306 | delete [] pseudoList_; |
---|
307 | } |
---|
308 | if (pseudoIndices_ != NULL) { |
---|
309 | delete [] pseudoIndices_; |
---|
310 | } |
---|
311 | /* Last thing is to delete solver */ |
---|
312 | if (ourSolver_) { |
---|
313 | delete solver_ ; |
---|
314 | solver_ = 0; |
---|
315 | } |
---|
316 | if (continuousSolver_ != 0) { |
---|
317 | delete continuousSolver_ ; |
---|
318 | continuousSolver_ = 0; |
---|
319 | } |
---|
320 | delete AbcPar_; |
---|
321 | } |
---|
322 | |
---|
323 | /** Initialize member data */ |
---|
324 | void init() |
---|
325 | { |
---|
326 | numberRowsAtContinuous_ = 0; |
---|
327 | numberIntegers_ = 0; |
---|
328 | integerVariable_ = NULL; |
---|
329 | sharedBasis_ = NULL; |
---|
330 | handler_ = new CoinMessageHandler(); |
---|
331 | handler_->setLogLevel(2); |
---|
332 | defaultHandler_ = true; |
---|
333 | messages_ = AbcMessage(); |
---|
334 | solver_ = NULL; |
---|
335 | ourSolver_ = false; |
---|
336 | basis_ = 0; |
---|
337 | minimumDrop_ = 1.0e-4; |
---|
338 | bestObjective_ = 1.0e100; |
---|
339 | bestSolution_ = 0; |
---|
340 | currentSolution_ = 0; |
---|
341 | numberNodes_ = 0; |
---|
342 | numberIterations_ = 0; |
---|
343 | status_ = 0; |
---|
344 | currentNumberCuts_ = 0; |
---|
345 | maximumNumberCuts_ = 1000; |
---|
346 | howOftenGlobalScan_ = 1; |
---|
347 | numberStrong_ = 0; |
---|
348 | numberCutGenerators_ =0; |
---|
349 | generator_ = NULL; |
---|
350 | numberHeuristics_ = 0; |
---|
351 | heuristic_ = NULL; |
---|
352 | maximumCutPassesAtRoot_ = 20; |
---|
353 | maximumCutPasses_ = 10; |
---|
354 | branchingMethod_ = NULL; |
---|
355 | numberSolutions_ = 0; |
---|
356 | numberHeuristicSolutions_ = 0; |
---|
357 | priority_ = NULL; |
---|
358 | pseudoList_ = NULL; |
---|
359 | pseudoIndices_ = NULL; |
---|
360 | |
---|
361 | // Set values for parameters |
---|
362 | intParam_[AbcMaxNumNode] = 9999999; |
---|
363 | intParam_[AbcMaxNumSol] = 9999999; |
---|
364 | intParam_[AbcFathomDiscipline] = 0; |
---|
365 | |
---|
366 | dblParam_[AbcIntegerTolerance] = 1e-6; |
---|
367 | dblParam_[AbcInfeasibilityWeight] = 0.0; |
---|
368 | dblParam_[AbcCutoffIncrement] = 1e-5; |
---|
369 | dblParam_[AbcAllowableGap] = 1.0e-10; |
---|
370 | dblParam_[AbcMaximumSeconds] = 1.0e100; |
---|
371 | AbcPar_ = new AbcParams; |
---|
372 | } |
---|
373 | |
---|
374 | /** Read in the problem data */ |
---|
375 | virtual void readInstance(const char* dataFile) |
---|
376 | { |
---|
377 | solver()->readMps(dataFile, ""); |
---|
378 | } |
---|
379 | |
---|
380 | /** Read in Alps and Abc parameters. */ |
---|
381 | void readParameters(const int argnum, const char * const * arglist) { |
---|
382 | std::cout << "Reading in ALPS parameters ..." << std::endl; |
---|
383 | AlpsPar_->readFromArglist(argnum, arglist); |
---|
384 | std::cout << "Reading in ABC parameters ..." << std::endl; |
---|
385 | AbcPar_->readFromArglist(argnum, arglist); |
---|
386 | } |
---|
387 | |
---|
388 | AbcParams *AbcPar() { return AbcPar_; } |
---|
389 | |
---|
390 | /// Returns solver - has current state |
---|
391 | OsiSolverInterface * solver() const |
---|
392 | { return solver_; } |
---|
393 | |
---|
394 | /** Assign a solver to the model (model assumes ownership) |
---|
395 | On return, \p solver will be NULL. |
---|
396 | \note Parameter settings in the outgoing solver are not inherited by |
---|
397 | the incoming solver. */ |
---|
398 | void assignSolver(OsiSolverInterface *&solver); |
---|
399 | |
---|
400 | /** Return an empty basis object of the specified size |
---|
401 | A useful utility when constructing a basis for a subproblem |
---|
402 | from scratch. The object returned will be of the requested |
---|
403 | capacity and appropriate for the solver attached to the model. */ |
---|
404 | CoinWarmStartBasis *getEmptyBasis(int ns = 0, int na = 0) const; |
---|
405 | |
---|
406 | /// Number of integers in problem |
---|
407 | inline int numberIntegers() const |
---|
408 | { return numberIntegers_; } |
---|
409 | |
---|
410 | /// Integer variables |
---|
411 | inline const int * integerVariable() const |
---|
412 | { return integerVariable_; } |
---|
413 | |
---|
414 | //------------------------------------------------------------------------- |
---|
415 | ///@name Solve methods |
---|
416 | //@{ |
---|
417 | /** \brief Solve the initial LP relaxation |
---|
418 | Invoke the solver's %initialSolve() method. |
---|
419 | */ |
---|
420 | void initialSolve(); |
---|
421 | |
---|
422 | /** \brief Evaluate a subproblem using cutting planes and heuristics |
---|
423 | The method invokes a main loop which generates cuts, applies heuristics, |
---|
424 | and reoptimises using the solver's native %resolve() method. |
---|
425 | It returns true if the subproblem remains feasible at the end of the |
---|
426 | evaluation. |
---|
427 | */ |
---|
428 | bool solveWithCuts( OsiCuts & cuts, int numberTries, |
---|
429 | AbcTreeNode * node, int & numberOldActiveCuts, |
---|
430 | int & numberNewCuts, int & maximumWhich, |
---|
431 | int *& whichGenerator, const bool cutDuringRampup, |
---|
432 | int & found ); |
---|
433 | |
---|
434 | /** \brief Reoptimise an LP relaxation |
---|
435 | Invoke the solver's %resolve() method. |
---|
436 | */ |
---|
437 | bool resolve(); |
---|
438 | //@} |
---|
439 | |
---|
440 | //------------------------------------------------------------------------- |
---|
441 | ///@name Methods returning info on how the solution process terminated |
---|
442 | //@{ |
---|
443 | /// Are there a numerical difficulties? |
---|
444 | bool isAbandoned() const; |
---|
445 | /// Is optimality proven? |
---|
446 | bool isProvenOptimal() const; |
---|
447 | /// Is infeasiblity proven (or none better than cutoff)? |
---|
448 | bool isProvenInfeasible() const; |
---|
449 | /// Node limit reached? |
---|
450 | bool isNodeLimitReached() const; |
---|
451 | /// Solution limit reached? |
---|
452 | bool isSolutionLimitReached() const; |
---|
453 | /// Get how many iterations it took to solve the problem. |
---|
454 | int getIterationCount() const |
---|
455 | { return solver_->getIterationCount(); } |
---|
456 | /// Get how many Nodes it took to solve the problem. |
---|
457 | int getNodeCount() const |
---|
458 | { return numberNodes_; } |
---|
459 | /// Increment the count of nodes |
---|
460 | void incrementNodeCount(int s = 1) |
---|
461 | { numberNodes_ += s; } |
---|
462 | |
---|
463 | /** Final status of problem |
---|
464 | 0 finished, 1 stopped, 2 difficulties |
---|
465 | */ |
---|
466 | inline int status() const |
---|
467 | { return status_; } |
---|
468 | //@} |
---|
469 | |
---|
470 | //------------------------------------------------------------------------- |
---|
471 | /**@name Problem information methods |
---|
472 | |
---|
473 | These methods call the solver's query routines to return |
---|
474 | information about the problem referred to by the current object. |
---|
475 | Querying a problem that has no data associated with it result in |
---|
476 | zeros for the number of rows and columns, and NULL pointers from |
---|
477 | the methods that return vectors. |
---|
478 | |
---|
479 | Const pointers returned from any data-query method are valid as |
---|
480 | long as the data is unchanged and the solver is not called. |
---|
481 | */ |
---|
482 | //@{ |
---|
483 | /// Number of rows in continuous (root) problem. |
---|
484 | int numberRowsAtContinuous() const |
---|
485 | { return numberRowsAtContinuous_; } |
---|
486 | |
---|
487 | void setNumberRowsAtContinous(const int value) |
---|
488 | { |
---|
489 | numberRowsAtContinuous_ = value; |
---|
490 | } |
---|
491 | |
---|
492 | |
---|
493 | /// Get number of columns |
---|
494 | int getNumCols() const |
---|
495 | { return solver_->getNumCols(); } |
---|
496 | |
---|
497 | /// Get number of rows |
---|
498 | int getNumRows() const |
---|
499 | { return solver_->getNumRows(); } |
---|
500 | |
---|
501 | /// Get number of nonzero elements |
---|
502 | int getNumElements() const |
---|
503 | { return solver_->getNumElements(); } |
---|
504 | |
---|
505 | /// Get pointer to array[getNumCols()] of column lower bounds |
---|
506 | const double * getColLower() const |
---|
507 | { return solver_->getColLower(); } |
---|
508 | |
---|
509 | /// Get pointer to array[getNumCols()] of column upper bounds |
---|
510 | const double * getColUpper() const |
---|
511 | { return solver_->getColUpper(); } |
---|
512 | |
---|
513 | /** Get pointer to array[getNumRows()] of row constraint senses. |
---|
514 | <ul> |
---|
515 | <li>'L': <= constraint |
---|
516 | <li>'E': = constraint |
---|
517 | <li>'G': >= constraint |
---|
518 | <li>'R': ranged constraint |
---|
519 | <li>'N': free constraint |
---|
520 | </ul> |
---|
521 | */ |
---|
522 | const char * getRowSense() const |
---|
523 | { return solver_->getRowSense(); } |
---|
524 | |
---|
525 | /** Get pointer to array[getNumRows()] of rows right-hand sides |
---|
526 | <ul> |
---|
527 | <li> if rowsense()[i] == 'L' then rhs()[i] == rowupper()[i] |
---|
528 | <li> if rowsense()[i] == 'G' then rhs()[i] == rowlower()[i] |
---|
529 | <li> if rowsense()[i] == 'R' then rhs()[i] == rowupper()[i] |
---|
530 | <li> if rowsense()[i] == 'N' then rhs()[i] == 0.0 |
---|
531 | </ul> |
---|
532 | */ |
---|
533 | const double * getRightHandSide() const |
---|
534 | { return solver_->getRightHandSide(); } |
---|
535 | |
---|
536 | /** Get pointer to array[getNumRows()] of row ranges. |
---|
537 | <ul> |
---|
538 | <li> if rowsense()[i] == 'R' then |
---|
539 | rowrange()[i] == rowupper()[i] - rowlower()[i] |
---|
540 | <li> if rowsense()[i] != 'R' then |
---|
541 | rowrange()[i] is 0.0 |
---|
542 | </ul> |
---|
543 | */ |
---|
544 | const double * getRowRange() const |
---|
545 | { return solver_->getRowRange(); } |
---|
546 | |
---|
547 | /// Get pointer to array[getNumRows()] of row lower bounds |
---|
548 | const double * getRowLower() const |
---|
549 | { return solver_->getRowLower(); } |
---|
550 | |
---|
551 | /// Get pointer to array[getNumRows()] of row upper bounds |
---|
552 | const double * getRowUpper() const |
---|
553 | { return solver_->getRowUpper(); } |
---|
554 | |
---|
555 | /// Get pointer to array[getNumCols()] of objective function coefficients |
---|
556 | const double * getObjCoefficients() const |
---|
557 | { return solver_->getObjCoefficients(); } |
---|
558 | |
---|
559 | /// Get objective function sense (1 for min (default), -1 for max) |
---|
560 | double getObjSense() const |
---|
561 | { return solver_->getObjSense(); } |
---|
562 | /// |
---|
563 | AbcPseudocost ** getPseudoList() { return pseudoList_; } |
---|
564 | |
---|
565 | /// |
---|
566 | int *getPseudoIndices() { return pseudoIndices_; } |
---|
567 | |
---|
568 | /// Return true if variable is continuous |
---|
569 | bool isContinuous(int colIndex) const |
---|
570 | { return solver_->isContinuous(colIndex); } |
---|
571 | |
---|
572 | /// Return true if variable is binary |
---|
573 | bool isBinary(int colIndex) const |
---|
574 | { return solver_->isBinary(colIndex); } |
---|
575 | |
---|
576 | /** Return true if column is integer. |
---|
577 | Note: This function returns true if the the column |
---|
578 | is binary or a general integer. |
---|
579 | */ |
---|
580 | bool isInteger(int colIndex) const |
---|
581 | { return solver_->isInteger(colIndex); } |
---|
582 | |
---|
583 | /// Return true if variable is general integer |
---|
584 | bool isIntegerNonBinary(int colIndex) const |
---|
585 | { return solver_->isIntegerNonBinary(colIndex); } |
---|
586 | |
---|
587 | /// Return true if variable is binary and not fixed at either bound |
---|
588 | bool isFreeBinary(int colIndex) const |
---|
589 | { return solver_->isFreeBinary(colIndex); } |
---|
590 | |
---|
591 | /// Get pointer to row-wise copy of matrix |
---|
592 | const CoinPackedMatrix * getMatrixByRow() const |
---|
593 | { return solver_->getMatrixByRow(); } |
---|
594 | |
---|
595 | /// Get pointer to column-wise copy of matrix |
---|
596 | const CoinPackedMatrix * getMatrixByCol() const |
---|
597 | { return solver_->getMatrixByCol(); } |
---|
598 | |
---|
599 | /// Get solver's value for infinity |
---|
600 | double getInfinity() const |
---|
601 | { return solver_->getInfinity(); } |
---|
602 | //@} |
---|
603 | |
---|
604 | /**@name Methods related to querying the solution */ |
---|
605 | //@{ |
---|
606 | /** Call this to really test if a valid solution can be feasible |
---|
607 | Solution is number columns in size. |
---|
608 | If fixVariables true then bounds of continuous solver updated. |
---|
609 | Returns objective value (worse than cutoff if not feasible) |
---|
610 | */ |
---|
611 | double checkSolution(double cutoff, |
---|
612 | const double * solution, |
---|
613 | bool fixVariables); |
---|
614 | |
---|
615 | /// Record a new incumbent solution and update objectiveValue |
---|
616 | bool setBestSolution(ABC_Message how, |
---|
617 | double & objectiveValue, |
---|
618 | const double *solution, |
---|
619 | bool fixVariables = false); |
---|
620 | |
---|
621 | /** Test the current solution for feasiblility. |
---|
622 | Scan all objects for indications of infeasibility. This is broken down |
---|
623 | into simple integer infeasibility (\p numberIntegerInfeasibilities) |
---|
624 | and all other reports of infeasibility (\pnumberObjectInfeasibilities). |
---|
625 | */ |
---|
626 | bool feasibleSolution(int & numberIntegerInfeasibilities); |
---|
627 | |
---|
628 | /** Solution to the most recent lp relaxation. |
---|
629 | |
---|
630 | The solver's solution to the most recent lp relaxation. |
---|
631 | */ |
---|
632 | inline double * currentSolution() const |
---|
633 | { return currentSolution_; } |
---|
634 | |
---|
635 | /// Get pointer to array[getNumCols()] of primal solution vector |
---|
636 | const double * getColSolution() const |
---|
637 | { return solver_->getColSolution(); } |
---|
638 | |
---|
639 | /// Get pointer to array[getNumRows()] of dual prices |
---|
640 | const double * getRowPrice() const |
---|
641 | { return solver_->getRowPrice(); } |
---|
642 | |
---|
643 | /// Get a pointer to array[getNumCols()] of reduced costs |
---|
644 | const double * getReducedCost() const |
---|
645 | { return solver_->getReducedCost(); } |
---|
646 | |
---|
647 | /// Get pointer to array[getNumRows()] of row activity levels. |
---|
648 | const double * getRowActivity() const |
---|
649 | { return solver_->getRowActivity(); } |
---|
650 | |
---|
651 | /// Get current objective function value |
---|
652 | double getCurrentObjValue() const |
---|
653 | { return solver_->getObjValue(); } |
---|
654 | |
---|
655 | /// Get best objective function value |
---|
656 | double getObjValue() const |
---|
657 | { return bestObjective_; } |
---|
658 | |
---|
659 | /** Set the best objective value. It is not necessary the value from |
---|
660 | the bestSolution_. It can be get from other processes. */ |
---|
661 | void setObjValue(double obj) |
---|
662 | { bestObjective_ = obj; } |
---|
663 | |
---|
664 | /** The best solution to the integer programming problem. |
---|
665 | |
---|
666 | The best solution to the integer programming problem found during |
---|
667 | the search. If no solution is found, the method returns null. |
---|
668 | */ |
---|
669 | const double * bestSolution() const |
---|
670 | { return bestSolution_; } |
---|
671 | |
---|
672 | /// Get number of solutions |
---|
673 | int getSolutionCount() const |
---|
674 | { return numberSolutions_; } |
---|
675 | |
---|
676 | /// Set number of solutions (so heuristics will be different) |
---|
677 | void setSolutionCount(int value) |
---|
678 | { numberSolutions_=value; } |
---|
679 | |
---|
680 | /// Get number of heuristic solutions |
---|
681 | int getNumberHeuristicSolutions() const |
---|
682 | { return numberHeuristicSolutions_; } |
---|
683 | |
---|
684 | /// Set objective function sense (1 for min (default), -1 for max,) |
---|
685 | void setObjSense(double s) { solver_->setObjSense(s); } |
---|
686 | |
---|
687 | /** Set the maximum number of cut passes at root node (default 20) |
---|
688 | Minimum drop can also be used for fine tuning */ |
---|
689 | inline void setMaximumCutPassesAtRoot(int value) |
---|
690 | {maximumCutPassesAtRoot_ = value; } |
---|
691 | /** Get the maximum number of cut passes at root node */ |
---|
692 | inline int getMaximumCutPassesAtRoot() const |
---|
693 | { return maximumCutPassesAtRoot_; } |
---|
694 | |
---|
695 | /** Set the maximum number of cut passes at other nodes (default 10) |
---|
696 | Minimum drop can also be used for fine tuning */ |
---|
697 | inline void setMaximumCutPasses(int value) |
---|
698 | { maximumCutPasses_ = value; } |
---|
699 | /** Get the maximum number of cut passes at other nodes (default 10) */ |
---|
700 | inline int getMaximumCutPasses() const |
---|
701 | { return maximumCutPasses_; } |
---|
702 | /// Number of entries in the list returned by #addedCuts() |
---|
703 | int currentNumberCuts() const |
---|
704 | { return currentNumberCuts_; } |
---|
705 | void setCurrentNumberCuts(int value) |
---|
706 | { |
---|
707 | currentNumberCuts_ += value; |
---|
708 | } |
---|
709 | |
---|
710 | //@} |
---|
711 | |
---|
712 | //------------------------------------------------------------------------- |
---|
713 | |
---|
714 | /** \name Branching Decisions |
---|
715 | |
---|
716 | See the AbcBranchDecision class for additional information. |
---|
717 | */ |
---|
718 | //@{ |
---|
719 | /// Get the current branching decision method. |
---|
720 | inline AbcBranchDecision * branchingMethod() const |
---|
721 | { return branchingMethod_; } |
---|
722 | /// Set the branching decision method. |
---|
723 | inline void setBranchingMethod(AbcBranchDecision * method) |
---|
724 | { branchingMethod_ = method; } |
---|
725 | /** Set the branching method |
---|
726 | \overload |
---|
727 | */ |
---|
728 | inline void setBranchingMethod(AbcBranchDecision & method) |
---|
729 | { branchingMethod_ = &method; } |
---|
730 | //@} |
---|
731 | |
---|
732 | //------------------------------------------------------------------------- |
---|
733 | |
---|
734 | /**@name Message handling */ |
---|
735 | //@{ |
---|
736 | /// Pass in Message handler (not deleted at end) |
---|
737 | void passInMessageHandler(CoinMessageHandler * handler) |
---|
738 | { |
---|
739 | if (defaultHandler_) { |
---|
740 | delete handler_; |
---|
741 | handler_ = NULL; |
---|
742 | } |
---|
743 | defaultHandler_ = false; |
---|
744 | handler_ = handler; |
---|
745 | } |
---|
746 | |
---|
747 | /// Set language |
---|
748 | void newLanguage(CoinMessages::Language language) |
---|
749 | { messages_ = AbcMessage(language); } |
---|
750 | void setLanguage(CoinMessages::Language language) |
---|
751 | { newLanguage(language); } |
---|
752 | /// Return handler |
---|
753 | CoinMessageHandler * messageHandler() const |
---|
754 | { return handler_; } |
---|
755 | /// Return messages |
---|
756 | CoinMessages messages() |
---|
757 | { return messages_; } |
---|
758 | /// Return pointer to messages |
---|
759 | CoinMessages * messagesPointer() |
---|
760 | { return &messages_; } |
---|
761 | //@} |
---|
762 | |
---|
763 | //------------------------------------------------------------------------- |
---|
764 | |
---|
765 | bool checkInteger(double value) const |
---|
766 | { |
---|
767 | double integerTolerance = |
---|
768 | getDblParam(AbcModel::AbcIntegerTolerance); |
---|
769 | double nearest = floor(value + 0.5); |
---|
770 | if (fabs(value - nearest) <= integerTolerance) |
---|
771 | return true; |
---|
772 | else |
---|
773 | return false; |
---|
774 | } |
---|
775 | |
---|
776 | /** \brief Identify integer variables and create corresponding objects. |
---|
777 | |
---|
778 | Record integer variables and create an integer object for each one. |
---|
779 | If \p startAgain is true, a new scan is forced, overwriting any |
---|
780 | existing integer variable information. |
---|
781 | */ |
---|
782 | void findIntegers(bool startAgain); |
---|
783 | |
---|
784 | /** Add one generator - up to user to delete generators. |
---|
785 | howoften affects how generator is used. 0 or 1 means always, |
---|
786 | >1 means every that number of nodes. Negative values have same |
---|
787 | meaning as positive but they may be switched off (-> -100) by code if |
---|
788 | not many cuts generated at continuous. -99 is just done at root. |
---|
789 | Name is just for printout |
---|
790 | */ |
---|
791 | void addCutGenerator(CglCutGenerator * generator, |
---|
792 | int howOften=1, const char * name=NULL, |
---|
793 | bool normal=true, bool atSolution=false, |
---|
794 | bool infeasible=false); |
---|
795 | /** \name Heuristics and priorities */ |
---|
796 | //@{ |
---|
797 | /// Add one heuristic |
---|
798 | void addHeuristic(AbcHeuristic * generator); |
---|
799 | //@} |
---|
800 | |
---|
801 | /** Perform reduced cost fixing |
---|
802 | Fixes integer variables at their current value based on reduced cost |
---|
803 | penalties. |
---|
804 | */ |
---|
805 | void reducedCostFix() ; |
---|
806 | |
---|
807 | /** Remove inactive cuts from the model |
---|
808 | |
---|
809 | An OsiSolverInterface is expected to maintain a valid basis, but not a |
---|
810 | valid solution, when loose cuts are deleted. Restoring a valid solution |
---|
811 | requires calling the solver to reoptimise. If it's certain the solution |
---|
812 | will not be required, set allowResolve to false to suppress |
---|
813 | reoptimisation. |
---|
814 | */ |
---|
815 | //void takeOffCuts(OsiCuts &cuts, int *whichGenerator, |
---|
816 | // int &numberOldActiveCuts, int &numberNewCuts, |
---|
817 | // bool allowResolve); |
---|
818 | void takeOffCuts(); |
---|
819 | |
---|
820 | /// Set an integer parameter |
---|
821 | inline bool setIntParam(AbcIntParam key, int value) { |
---|
822 | intParam_[key] = value; |
---|
823 | return true; |
---|
824 | } |
---|
825 | |
---|
826 | /// Set a double parameter |
---|
827 | inline bool setDblParam(AbcDblParam key, double value) { |
---|
828 | dblParam_[key] = value; |
---|
829 | return true; |
---|
830 | } |
---|
831 | |
---|
832 | /// Get an integer parameter |
---|
833 | inline int getIntParam(AbcIntParam key) const { |
---|
834 | return intParam_[key]; |
---|
835 | } |
---|
836 | |
---|
837 | /// Get a double parameter |
---|
838 | inline double getDblParam(AbcDblParam key) const { |
---|
839 | return dblParam_[key]; |
---|
840 | } |
---|
841 | |
---|
842 | /*! \brief Set cutoff bound on the objective function. |
---|
843 | When using strict comparison, the bound is adjusted by a tolerance to |
---|
844 | avoid accidentally cutting off the optimal solution. |
---|
845 | */ |
---|
846 | void setCutoff(double value); |
---|
847 | |
---|
848 | /// Get the cutoff bound on the objective function - always as minimize |
---|
849 | inline double getCutoff() const |
---|
850 | { |
---|
851 | double value ; |
---|
852 | solver_->getDblParam(OsiDualObjectiveLimit, value) ; |
---|
853 | return value * solver_->getObjSense() ; |
---|
854 | } |
---|
855 | |
---|
856 | /// Set the \link AbcModel::AbcMaxNumNode maximum node limit \endlink |
---|
857 | inline bool setMaximumNodes( int value) |
---|
858 | { return setIntParam(AbcMaxNumNode,value); } |
---|
859 | |
---|
860 | /// Get the \link AbcModel::AbcMaxNumNode maximum node limit \endlink |
---|
861 | inline int getMaximumNodes() const |
---|
862 | { return getIntParam(AbcMaxNumNode); } |
---|
863 | |
---|
864 | /** Set the |
---|
865 | \link AbcModel::AbcMaxNumSol maximum number of solutions \endlink |
---|
866 | desired. |
---|
867 | */ |
---|
868 | inline bool setMaximumSolutions( int value) { |
---|
869 | return setIntParam(AbcMaxNumSol,value); |
---|
870 | } |
---|
871 | /** Get the |
---|
872 | \link AbcModel::AbcMaxNumSol maximum number of solutions \endlink |
---|
873 | desired. |
---|
874 | */ |
---|
875 | inline int getMaximumSolutions() const { |
---|
876 | return getIntParam(AbcMaxNumSol); |
---|
877 | } |
---|
878 | |
---|
879 | /** Set the |
---|
880 | \link AbcModel::AbcIntegerTolerance integrality tolerance \endlink |
---|
881 | */ |
---|
882 | inline bool setIntegerTolerance( double value) { |
---|
883 | return setDblParam(AbcIntegerTolerance,value); |
---|
884 | } |
---|
885 | /** Get the |
---|
886 | \link AbcModel::AbcIntegerTolerance integrality tolerance \endlink |
---|
887 | */ |
---|
888 | inline double getIntegerTolerance() const { |
---|
889 | return getDblParam(AbcIntegerTolerance); |
---|
890 | } |
---|
891 | |
---|
892 | /** Set the |
---|
893 | \link AbcModel::AbcInfeasibilityWeight |
---|
894 | weight per integer infeasibility \endlink |
---|
895 | */ |
---|
896 | inline bool setInfeasibilityWeight( double value) { |
---|
897 | return setDblParam(AbcInfeasibilityWeight,value); |
---|
898 | } |
---|
899 | /** Get the |
---|
900 | \link AbcModel::AbcInfeasibilityWeight |
---|
901 | weight per integer infeasibility \endlink |
---|
902 | */ |
---|
903 | inline double getInfeasibilityWeight() const { |
---|
904 | return getDblParam(AbcInfeasibilityWeight); |
---|
905 | } |
---|
906 | |
---|
907 | /** Set the \link AbcModel::AbcAllowableGap allowable gap \endlink |
---|
908 | between the best known solution and the best possible solution. |
---|
909 | */ |
---|
910 | inline bool setAllowableGap( double value) { |
---|
911 | return setDblParam(AbcAllowableGap,value); |
---|
912 | } |
---|
913 | /** Get the \link AbcModel::AbcAllowableGap allowable gap \endlink |
---|
914 | between the best known solution and the best possible solution. |
---|
915 | */ |
---|
916 | inline double getAllowableGap() const { |
---|
917 | return getDblParam(AbcAllowableGap); |
---|
918 | } |
---|
919 | |
---|
920 | /// Set the minimum drop to continue cuts |
---|
921 | inline void setMinimumDrop(double value) |
---|
922 | { minimumDrop_=value; } |
---|
923 | /// Get the minimum drop to continue cuts |
---|
924 | inline double getMinimumDrop() const |
---|
925 | { return minimumDrop_; } |
---|
926 | |
---|
927 | //------------------------------------------------------------------------- |
---|
928 | |
---|
929 | /** Do necessary work to make model usable. Return success or not. */ |
---|
930 | virtual bool setupSelf(); |
---|
931 | |
---|
932 | int numberStrong() const |
---|
933 | { return numberStrong_; } |
---|
934 | |
---|
935 | void setNumberStrong(int number) |
---|
936 | { |
---|
937 | if (number<0) |
---|
938 | numberStrong_=0; |
---|
939 | else |
---|
940 | numberStrong_=number; |
---|
941 | } |
---|
942 | |
---|
943 | /// Priorities |
---|
944 | inline const int * priority() const { return priority_;}; |
---|
945 | |
---|
946 | /// Returns priority level for an object (or 1000 if no priorities exist) |
---|
947 | inline int priority(int sequence) const |
---|
948 | { |
---|
949 | if (priority_) |
---|
950 | return priority_[sequence]; |
---|
951 | else |
---|
952 | return 1000; |
---|
953 | }; |
---|
954 | |
---|
955 | /** The method that encodes the model into a encoded object. */ |
---|
956 | virtual AlpsEncoded* encode() const; |
---|
957 | |
---|
958 | /** The method that decodes the model from a encoded object. */ |
---|
959 | virtual void decodeToSelf(AlpsEncoded&); |
---|
960 | |
---|
961 | }; |
---|
962 | |
---|
963 | //############################################################################# |
---|
964 | |
---|
965 | #endif |
---|