1 | // (C) Copyright International Business Machines (IBM) 2006 |
---|
2 | // All Rights Reserved. |
---|
3 | // This code is published under the Common Public License. |
---|
4 | // |
---|
5 | // Authors : |
---|
6 | // P. Bonami, International Business Machines |
---|
7 | // |
---|
8 | // Date : 12/07/2006 |
---|
9 | |
---|
10 | #ifndef BonOaDecBase_HPP |
---|
11 | #define BonOaDecBase_HPP |
---|
12 | #include "CglCutGenerator.hpp" |
---|
13 | #include "BonBabSetupBase.hpp" |
---|
14 | #include "BonOAMessages.hpp" |
---|
15 | #include "CbcModel.hpp" |
---|
16 | |
---|
17 | #include "CbcStrategy.hpp" |
---|
18 | |
---|
19 | #include "CoinTime.hpp" |
---|
20 | #include "OsiAuxInfo.hpp" |
---|
21 | #include "OsiBranchingObject.hpp" |
---|
22 | |
---|
23 | |
---|
24 | /* forward declarations.*/ |
---|
25 | class OsiClpSolverInterface; |
---|
26 | class OsiCpxSolverInterface; |
---|
27 | |
---|
28 | namespace Bonmin |
---|
29 | { |
---|
30 | /** Base class for OA algorithms.*/ |
---|
31 | class OaDecompositionBase : public CglCutGenerator |
---|
32 | { |
---|
33 | public: |
---|
34 | /** Small class to perform the solution of sub-mips.*/ |
---|
35 | class SubMipSolver |
---|
36 | { |
---|
37 | public: |
---|
38 | /** Constructor */ |
---|
39 | SubMipSolver(OsiSolverInterface * lp = NULL, |
---|
40 | const CbcStrategy * strategy = NULL); |
---|
41 | |
---|
42 | ~SubMipSolver(); |
---|
43 | |
---|
44 | /** Assign lp solver. */ |
---|
45 | void setLpSolver(OsiSolverInterface * lp); |
---|
46 | |
---|
47 | /** Assign a strategy. */ |
---|
48 | void setStrategy(CbcStrategy * strategy) |
---|
49 | { |
---|
50 | if (strategy_) delete strategy_; |
---|
51 | strategy_ = strategy->clone(); |
---|
52 | } |
---|
53 | /** get the solution found in last local search (return NULL if no solution). */ |
---|
54 | const double * getLastSolution() |
---|
55 | { |
---|
56 | return integerSolution_; |
---|
57 | } |
---|
58 | |
---|
59 | double getLowerBound() |
---|
60 | { |
---|
61 | return lowBound_; |
---|
62 | } |
---|
63 | /** update cutoff and perform a new local search. */ |
---|
64 | void performLocalSearch(double cutoff, |
---|
65 | int loglevel, |
---|
66 | double maxTime); |
---|
67 | |
---|
68 | /** Returns lower bound. */ |
---|
69 | inline double lowBound() |
---|
70 | { |
---|
71 | return lowBound_; |
---|
72 | } |
---|
73 | |
---|
74 | /** returns optimality status. */ |
---|
75 | inline bool optimal() |
---|
76 | { |
---|
77 | return optimal_; |
---|
78 | } |
---|
79 | |
---|
80 | /** Returns number of nodes in last solve.*/ |
---|
81 | inline int nodeCount() |
---|
82 | { |
---|
83 | return nodeCount_; |
---|
84 | } |
---|
85 | |
---|
86 | /** Returns number of simplex iterations in last solve.*/ |
---|
87 | inline int iterationCount() |
---|
88 | { |
---|
89 | return iterationCount_; |
---|
90 | } |
---|
91 | |
---|
92 | |
---|
93 | /** Register options for that Oa based cut generation method. */ |
---|
94 | void registerOptions(Ipopt::SmartPtr<Ipopt::RegisteredOptions> roptions) |
---|
95 | {} |
---|
96 | private: |
---|
97 | /** lp (potentially mip solver). */ |
---|
98 | OsiSolverInterface * lp_; |
---|
99 | /** If lp solver is clp (then have to use Cbc).*/ |
---|
100 | OsiClpSolverInterface *clp_; |
---|
101 | /** If lp solver is cpx this points to it. */ |
---|
102 | OsiCpxSolverInterface * cpx_; |
---|
103 | /** If cbc is used pointer to CbcModel. */ |
---|
104 | CbcModel * cbc_; |
---|
105 | /** lower bound obtained */ |
---|
106 | double lowBound_; |
---|
107 | /** Is optimality proven? */ |
---|
108 | bool optimal_; |
---|
109 | /** Has an integer solution? then it is here*/ |
---|
110 | double * integerSolution_; |
---|
111 | /** Strategy for solving sub mips with cbc. */ |
---|
112 | CbcStrategy * strategy_; |
---|
113 | /** number of nodes in last mip solved.*/ |
---|
114 | int nodeCount_; |
---|
115 | /** number of simplex iteration in last mip solved.*/ |
---|
116 | int iterationCount_; |
---|
117 | }; |
---|
118 | |
---|
119 | /** Small class to manipulatee various things in an OsiSolverInterface and restore them. |
---|
120 | The OsiSolverInterface manipulated may already exist or may be cloned from another one.*/ |
---|
121 | class solverManip |
---|
122 | { |
---|
123 | public: |
---|
124 | /** Constructor. */ |
---|
125 | solverManip(OsiSolverInterface *si , bool saveNumRows=true, |
---|
126 | bool saveBasis=true, bool saveBounds=false, |
---|
127 | bool saveCutoff = false, bool resolve=true); |
---|
128 | |
---|
129 | /** Constructor which clone an other interface. */ |
---|
130 | solverManip(const OsiSolverInterface & si); |
---|
131 | /** Destructor. */ |
---|
132 | ~solverManip(); |
---|
133 | /** Restore solver. */ |
---|
134 | void restore(); |
---|
135 | |
---|
136 | /** Clone the state of another solver (bounds, cutoff, basis).*/ |
---|
137 | void cloneOther(const OsiSolverInterface &si); |
---|
138 | /** Check for integer feasibility of a solution return true if it is feasible. |
---|
139 | \todo Handle SOS Type 2 constraints. */ |
---|
140 | bool integerFeasible(const OsiBranchingInformation & info) const; |
---|
141 | |
---|
142 | /** Fix integer variables in si to their values in colsol. |
---|
143 | \remark colsol is assumed to be integer on the integer constrained variables. |
---|
144 | \todo Handle SOS type 2.*/ |
---|
145 | void fixIntegers(const OsiBranchingInformation & info); |
---|
146 | |
---|
147 | /** Check if solution in solver is the same as colsol on integer variables. */ |
---|
148 | bool isDifferentOnIntegers(const double * colsol); |
---|
149 | |
---|
150 | /** Check if two solutions are the same on integer variables. */ |
---|
151 | bool isDifferentOnIntegers(const double * colsol, const double * other); |
---|
152 | |
---|
153 | /** Install cuts in solver. */ |
---|
154 | void installCuts(const OsiCuts& cs, int numberCuts); |
---|
155 | |
---|
156 | /** Get pointer to solver interface. */ |
---|
157 | OsiSolverInterface * si() |
---|
158 | { |
---|
159 | return si_; |
---|
160 | } |
---|
161 | |
---|
162 | /** Set objects.*/ |
---|
163 | void setObjects(OsiObject ** objects, int nObjects) |
---|
164 | { |
---|
165 | objects_ = objects; |
---|
166 | nObjects_ = nObjects; |
---|
167 | } |
---|
168 | |
---|
169 | void setIntegerTolerance(double v) |
---|
170 | { |
---|
171 | integerTolerance_ = v; |
---|
172 | } |
---|
173 | private: |
---|
174 | /** Interface saved. */ |
---|
175 | OsiSolverInterface * si_; |
---|
176 | /** Initial number of rows (-1 if don't save). */ |
---|
177 | int initialNumberRows_; |
---|
178 | |
---|
179 | /** Initial lower bounds. */ |
---|
180 | double * colLower_; |
---|
181 | |
---|
182 | /** Initial Upper bounds.*/ |
---|
183 | double * colUpper_; |
---|
184 | |
---|
185 | /** Inital basis. */ |
---|
186 | CoinWarmStart * warm_; |
---|
187 | |
---|
188 | /** Initial cutoff. */ |
---|
189 | double cutoff_; |
---|
190 | |
---|
191 | /** delete si_ ? */ |
---|
192 | bool deleteSolver_; |
---|
193 | |
---|
194 | /// Some objects the feasiblitiy of which to verify. |
---|
195 | OsiObject * * objects_; |
---|
196 | /// Number of objects.*/ |
---|
197 | int nObjects_; |
---|
198 | /** \name Cached info from solver interface.*/ |
---|
199 | /** @{ */ |
---|
200 | /** Number of columns. */ |
---|
201 | int numcols_; |
---|
202 | /** Number of rows. */ |
---|
203 | int numrows_; |
---|
204 | /** Lower bounds on variables.*/ |
---|
205 | const double * siColLower_; |
---|
206 | /** Upper bounds on variables. */ |
---|
207 | const double * siColUpper_; |
---|
208 | |
---|
209 | void getCached(); |
---|
210 | /** @} */ |
---|
211 | double integerTolerance_; |
---|
212 | }; |
---|
213 | /// Old usefull constructor |
---|
214 | OaDecompositionBase(OsiTMINLPInterface * nlp = NULL, |
---|
215 | OsiSolverInterface * si = NULL, |
---|
216 | CbcStrategy * strategy = NULL, |
---|
217 | double cbcCutoffIncrement_=1e-07, |
---|
218 | double cbcIntegerTolerance = 1e-05, |
---|
219 | bool leaveSiUnchanged = 0 |
---|
220 | ); |
---|
221 | /// New usefull constructor |
---|
222 | OaDecompositionBase(BabSetupBase &b, bool leaveSiUnchanged, |
---|
223 | bool reassignLpsolver); |
---|
224 | |
---|
225 | /// Copy constructor |
---|
226 | OaDecompositionBase(const OaDecompositionBase & copy); |
---|
227 | |
---|
228 | |
---|
229 | /// Destructor |
---|
230 | virtual ~OaDecompositionBase(); |
---|
231 | |
---|
232 | /** Standard cut generation methods. */ |
---|
233 | virtual void generateCuts(const OsiSolverInterface &si, OsiCuts & cs, |
---|
234 | const CglTreeInfo info = CglTreeInfo()) const; |
---|
235 | |
---|
236 | /// Assign an OsiTMINLPInterface |
---|
237 | void assignNlpInterface(OsiTMINLPInterface * nlp) |
---|
238 | { |
---|
239 | nlp_ = nlp; |
---|
240 | } |
---|
241 | |
---|
242 | /// Assign an OsiTMINLPInterface |
---|
243 | void assignLpInterface(OsiSolverInterface * si) |
---|
244 | { |
---|
245 | lp_ = si; |
---|
246 | } |
---|
247 | |
---|
248 | bool reassignLpsolver() |
---|
249 | { |
---|
250 | return reassignLpsolver_; |
---|
251 | } |
---|
252 | /** Set objects.*/ |
---|
253 | void setObjects(OsiObject ** objects, int nObjects) |
---|
254 | { |
---|
255 | objects_ = objects; |
---|
256 | nObjects_ = nObjects; |
---|
257 | } |
---|
258 | /// Set whether to leave the solverinterface unchanged |
---|
259 | inline void setLeaveSiUnchanged(bool yesno) |
---|
260 | { |
---|
261 | leaveSiUnchanged_ = yesno; |
---|
262 | } |
---|
263 | |
---|
264 | /** Parameters for algorithm. */ |
---|
265 | struct Parameters |
---|
266 | { |
---|
267 | /// Add cuts as global |
---|
268 | bool global_; |
---|
269 | /// Add only violated OA inequalities |
---|
270 | bool addOnlyViolated_; |
---|
271 | /// cutoff min increase (has to be intialized trhough Cbc) |
---|
272 | double cbcCutoffIncrement_; |
---|
273 | /// integer tolerance (has to be the same as Cbc's) |
---|
274 | double cbcIntegerTolerance_; |
---|
275 | ///Total max number of local searches |
---|
276 | int maxLocalSearch_; |
---|
277 | /// maximum time for local searches |
---|
278 | double maxLocalSearchTime_; |
---|
279 | /** sub milp log level.*/ |
---|
280 | int subMilpLogLevel_; |
---|
281 | /** Frequency of log. */ |
---|
282 | double logFrequency_; |
---|
283 | |
---|
284 | /** Constructor with default values */ |
---|
285 | Parameters(); |
---|
286 | |
---|
287 | /** Copy constructor */ |
---|
288 | Parameters(const Parameters & other); |
---|
289 | |
---|
290 | /** Destructor */ |
---|
291 | ~Parameters() |
---|
292 | { |
---|
293 | if (!strategy_) delete strategy_; |
---|
294 | } |
---|
295 | |
---|
296 | /** Strategy to apply when using Cbc as MILP sub-solver.*/ |
---|
297 | void setStrategy(const CbcStrategy & strategy) |
---|
298 | { |
---|
299 | if (strategy_) delete strategy_; |
---|
300 | strategy_ = strategy.clone(); |
---|
301 | } |
---|
302 | |
---|
303 | const CbcStrategy * strategy() const |
---|
304 | { |
---|
305 | return strategy_; |
---|
306 | } |
---|
307 | private: |
---|
308 | /** Strategy to apply when using Cbc as MILP sub-solver.*/ |
---|
309 | CbcStrategy * strategy_; |
---|
310 | |
---|
311 | }; |
---|
312 | |
---|
313 | Parameters& parameter() |
---|
314 | { |
---|
315 | return parameters_; |
---|
316 | } |
---|
317 | |
---|
318 | const Parameters& parameter()const |
---|
319 | { |
---|
320 | return parameters_; |
---|
321 | } |
---|
322 | |
---|
323 | void setLogLevel(int level) |
---|
324 | { |
---|
325 | handler_->setLogLevel(level); |
---|
326 | } |
---|
327 | |
---|
328 | void passInMessageHandler(CoinMessageHandler * handler); |
---|
329 | protected: |
---|
330 | /// \name Protected helper functions |
---|
331 | /**@{ */ |
---|
332 | |
---|
333 | /** Solve the nlp and do output. |
---|
334 | \return true if feasible*/ |
---|
335 | bool solveNlp(OsiBabSolver * babInfo, double cutoff) const; |
---|
336 | /** @} */ |
---|
337 | |
---|
338 | /// virtual method which performs the OA algorithm by modifying lp and nlp. |
---|
339 | virtual double performOa(OsiCuts &cs, solverManip &nlpManip, solverManip &lpManip, |
---|
340 | SubMipSolver * &subMip, OsiBabSolver * babInfo, double &) const = 0; |
---|
341 | /// virutal method to decide if local search is performed |
---|
342 | virtual bool doLocalSearch() const = 0; |
---|
343 | |
---|
344 | /// \name Protected members |
---|
345 | /** @{ */ |
---|
346 | /// Pointer to nlp interface |
---|
347 | mutable OsiTMINLPInterface * nlp_; |
---|
348 | ///Number of nlp solved done |
---|
349 | mutable int nSolve_; |
---|
350 | /// A linear solver |
---|
351 | mutable OsiSolverInterface * lp_; |
---|
352 | /// Some objects the feasiblitiy of which to verify. |
---|
353 | OsiObject * * objects_; |
---|
354 | /// Number of objects.*/ |
---|
355 | int nObjects_; |
---|
356 | ///number of local searches performed |
---|
357 | mutable int nLocalSearch_; |
---|
358 | /** messages handler. */ |
---|
359 | CoinMessageHandler * handler_; |
---|
360 | /** Messages for OA */ |
---|
361 | CoinMessages messages_; |
---|
362 | /** Wether or not we should remove cuts at the end of the procedure */ |
---|
363 | bool leaveSiUnchanged_; |
---|
364 | /** Do we need to reassign the lp solver with Cbc.*/ |
---|
365 | bool reassignLpsolver_; |
---|
366 | /** time of construction*/ |
---|
367 | double timeBegin_; |
---|
368 | |
---|
369 | /** Parameters.*/ |
---|
370 | Parameters parameters_; |
---|
371 | |
---|
372 | /** @} */ |
---|
373 | |
---|
374 | #ifdef OA_DEBUG |
---|
375 | class OaDebug |
---|
376 | { |
---|
377 | public: |
---|
378 | bool checkInteger(const OsiSolverInterface&nlp, std::ostream & os) const; |
---|
379 | |
---|
380 | void printEndOfProcedureDebugMessage(const OsiCuts &cs, |
---|
381 | bool foundSolution, |
---|
382 | double solValue, |
---|
383 | double milpBound, |
---|
384 | bool isInteger, |
---|
385 | bool feasible, |
---|
386 | std::ostream & os) const; |
---|
387 | }; |
---|
388 | |
---|
389 | /** debug object. */ |
---|
390 | OaDebug debug_; |
---|
391 | |
---|
392 | #endif |
---|
393 | }; |
---|
394 | } |
---|
395 | #endif |
---|
396 | |
---|