1 : /* _________________________________________________________________________
2 : *
3 : * PICO: A C++ library of scalable branch-and-bound and related methods.
4 : * Copyright (c) 2001, Sandia National Laboratories.
5 : * This software is distributed under the GNU Lesser General Public License.
6 : * For more information, see the README file in the top PICO directory.
7 : * _________________________________________________________________________
8 : */
9 : //
10 : // milpNode.cpp
11 : //
12 : // Basic serial code for MILP solving in PICO (subproblem level code).
13 : //
14 : // Cindy Phillips
15 : //
16 :
17 : #include <acro_config.h>
18 : #include <utilib/_math.h>
19 : #include <utilib/DUniform.h>
20 : #include <utilib/seconds.h>
21 : #include <pebbl/gRandom.h>
22 : #include <pebbl/fundamentals.h>
23 : #include <pico/milpNode.h>
24 : #include <pico/BasisArray.h>
25 : #include <pico/mipHeuristic.h>
26 :
27 : #include <iostream>
28 : #include <iomanip>
29 : #include <vector>
30 : #include <utility>
31 :
32 : using namespace std;
33 : using namespace utilib;
34 :
35 : /* CAP: I hope this just goes away and the new intialization will work. Keep this through the
36 : next attempt to run on Janus
37 : #if defined(COUGAR)
38 :
39 : namespace utilib {
40 :
41 : template<>
42 : int EnumBitArray<1,pico::basisState>::enum_count = 4;
43 :
44 : template<>
45 : char* EnumBitArray<1,pico::basisState>::enum_labels = "oLBU";
46 :
47 : template<>
48 : pico::basisState EnumBitArray<1,pico::basisState>::enum_vals[] = { pico::other, pico::atLower, pico::basic, pico::atUpper };
49 :
50 : }
51 : #endif
52 :
53 : */
54 :
55 : namespace pico {
56 :
57 :
58 : int MILPNode::numChildren = 2;
59 :
60 :
61 : // For making the root
62 :
63 17 : void MILPNode::MILPNodeFromMILP(MILP* master)
64 : {
65 17 : lp = master->lp;
66 17 : globalPtr = master;
67 17 : bound = -(mGlobal()->sense)*MAXDOUBLE;
68 17 : MILPNodeInit();
69 :
70 : // For heuristic -- mfValue unknown, use HUGE_VAL and inform the heuristic
71 17 : if (mGlobal()->mipHeuristicPtr)
72 : {
73 0 : mfValue = HUGE_VAL;
74 0 : mGlobal()->mipHeuristicPtr->inform(this);
75 : }
76 17 : }
77 :
78 : // For making a nonroot node
79 :
80 184076 : void MILPNode::MILPNodeAsChildOf(MILPNode *parent, bool initVB)
81 : {
82 184076 : if (initVB)
83 184076 : branchSubAsChildOf(parent);
84 184076 : lp = parent->mGlobal()->lp;
85 184076 : globalPtr = parent->mGlobal();
86 :
87 : // Use mfValue from the parent, until this
88 : // subproblem has been bounded
89 184076 : if (mGlobal()->mipHeuristicPtr)
90 : {
91 0 : mfValue = parent->mfValue;
92 0 : mGlobal()->mipHeuristicPtr->inform(this);
93 : }
94 :
95 184076 : MILPNodeInit();
96 184076 : }
97 :
98 184093 : void MILPNode::MILPNodeInit()
99 : {
100 : //
101 : // Initialize the local LP solver
102 : //
103 : // Try doing this directly in the constructor to avoid exessive make/deletes
104 : //lp &= mGlobal()->lp;
105 :
106 : //DEBUGPR(4, ucout << "Entering MILPNode::MILPNode" << endl;);
107 :
108 : // get local reference to lp and mip()
109 184093 : MILPProblem* localMipRef = mip();
110 :
111 : // We use this a lot for this routine, so keep local.
112 184093 : int numInts = localMipRef->numIntegerVars();
113 184093 : basisValid=false;
114 184093 : basis.resize(initialBasisSize());
115 184093 : solVector.resize(numInts); // This is enlarged later for terminal nodes...
116 184093 : fixed.resize(numInts); // ... otherwise we don't care about cts variables
117 184093 : if (localMipRef->numBinaryVars() > 0)
118 184093 : binary_vals.resize(numInts);
119 :
120 184093 : intLowerBounds.resize(localMipRef->numGeneralIntVars());
121 184093 : intUpperBounds.resize(localMipRef->numGeneralIntVars());
122 :
123 184093 : size_type num_sets = (size_type)localMipRef->numSets();
124 184093 : spSetLowerBounds.resize(num_sets);
125 184093 : spSetUpperBounds.resize(num_sets);
126 184093 : setCandidateNdx.resize(num_sets);
127 184093 : spSetBranchValues.resize(num_sets);
128 :
129 : // nFrac is not valid until the problem is solved
130 184093 : nFrac = localMipRef->numIntegerVars() + 1;
131 184093 : nSetCandidates = 0; // also not valid, but if we aren't using sets, we'll want a reasonable number.
132 184093 : FracVarNdx.resize(numInts);
133 184093 : reducedCosts.resize(numInts);
134 :
135 184093 : branchType = no_branch;
136 184093 : branchValue = -999.0; // This should never be used, but...
137 184093 : lpBound = MAXDOUBLE * globalPtr->sense;
138 184093 : }
139 :
140 :
141 : // This is to make the root node (no parent). It assumes the LP is loaded.
142 :
143 17 : void MILPNode::setRootComputation()
144 : {
145 : // Note that basis is not valid till the problem is solved.
146 :
147 17 : binary_vals.reset();
148 :
149 : // Root starts with just the bounds from the original problem.
150 17 : if (!mip()->getbounds(fixed,intLowerBounds,intUpperBounds,binary_vals, spSetLowerBounds, spSetUpperBounds))
151 0 : setState(dead);
152 :
153 : // Root has no parent. We can make this value a named constant
154 : // if it makes sense.
155 :
156 17 : parentId.setEmpty();
157 :
158 : // branchVariable also not valid initially
159 17 : branchVariable = -1; // valid entries should be 0 to numInts - 1
160 17 : recordPCost = FALSE; // no parent value to compare to
161 :
162 17 : DEBUGPR(10, ucout << "MILPNode::setRootComputation() invoked.\n");
163 17 : };
164 :
165 :
166 :
167 : //---------------------------------------------
168 : // Create a child node
169 : //---------------------------------------------
170 :
171 0 : pebbl::branchSub * MILPNode::makeChild(int whichChild)
172 : {
173 : MEMDEBUG_START_NEW("MILPNode")
174 0 : MILPNode *child = new MILPNode();
175 : #ifdef ACRO_VALIDATING
176 : if (child == NULL)
177 : EXCEPTION_MNGR(runtime_error, "Failed to allocate new MILPNode\n");
178 : #endif
179 0 : child->MILPNodeAsChildOf(this);
180 : MEMDEBUG_END_NEW("MILPNode")
181 :
182 : MEMDEBUG_START_RESIZE("MILPNode")
183 0 : childInit(child, whichChild);
184 : MEMDEBUG_END_RESIZE("MILPNode")
185 :
186 0 : return(child);
187 : }
188 :
189 : // Branches in preferred direction for child 0 and in opposite direction
190 : // for child 1. If a higher number is given, this will duplicate child
191 : // 1. Assume there are checks elsewhere for generation of too many children.
192 :
193 : // Remember, if you add a field to the milp node (e.g. initialized here),
194 : // you also have to initialize in packChild, and add to pack, unpack, and sp
195 : // (subproblem) sizing routine (the one that estimates the packed size of
196 : // a subproblem.
197 :
198 184076 : void MILPNode::childInit(MILPNode *child, int whichChild)
199 : {
200 184076 : child->lpBound = lpBound;
201 184076 : child->recordPCost = recordPCost;
202 184076 : child->basis << basis; // This should be a copy, not a link
203 :
204 184076 : child->fixed << fixed;
205 184076 : child->binary_vals << binary_vals;
206 :
207 : // This is true for starters. At least one more will be restricted later.
208 184076 : child->intLowerBounds << intLowerBounds;
209 184076 : child->intUpperBounds << intUpperBounds;
210 184076 : if (mGlobal()->useSets)
211 : {
212 184076 : child->spSetLowerBounds << spSetLowerBounds;
213 184076 : child->spSetUpperBounds << spSetUpperBounds;
214 : }
215 :
216 184076 : child->branchVariable = branchVariable;
217 184076 : child->branchValue = branchValue;
218 :
219 : // Update the branch type and upper/lower bounds. If we have
220 : // fractional variables, we use adjustNodeBounds in the usual way.
221 : // Otherwise, we must be enumerating, which requires branch and cut,
222 : // so we'll let BCMip::childInit handle the bounds and setting the
223 : // branch type.
224 :
225 184076 : if (nFrac > 0)
226 : {
227 184076 : child->branchType = childBranchType(child, whichChild);
228 184076 : child->adjustNodeBounds(branchVariable, child->branchType);
229 : }
230 :
231 : // Pretty much done now...
232 :
233 184076 : if (mGlobal()->debug >= 10) {
234 : ucout << "parent= " << id << ", child = " << child->id
235 : << ", branchVar = " << branchVariable << ", type = "
236 0 : << (int)(child->branchType) << "\n";
237 : }
238 :
239 184076 : child->parentId = id;
240 :
241 : // verbosity tag
242 :
243 184076 : DEBUGPR(10, ucout << "Created child of " << this << '\n');
244 184076 : }
245 :
246 :
247 184076 : branch_type MILPNode::childBranchType(MILPNode *child, int whichChild)
248 : {
249 : // branchType indicates preferred branch direction, which is defined to
250 : // be child 0.
251 184076 : if (whichChild == 0)
252 92038 : return(branchType);
253 : else {
254 92038 : if (branchType == branch_up) return(branch_down);
255 74961 : else if (branchType == branch_down) return(branch_up);
256 0 : else EXCEPTION_MNGR(runtime_error,"Trying to create a child for a "
257 : "parent without branching indicator");
258 0 : return(no_branch); // to keep compiler happy
259 : }
260 : }
261 :
262 :
263 :
264 : // Presumably all the arrays are automatically collected, since weren't
265 : // allocated with new() (done with vector mechanism).
266 184090 : MILPNode::~MILPNode()
267 : {
268 184090 : }
269 :
270 : // For heuristic, delete mfValue of this subproblem from the
271 : // population, then call the original method
272 :
273 184090 : void MILPNode::recycle()
274 : {
275 184090 : if (mGlobal()->mipHeuristicPtr)
276 0 : mGlobal()->mipHeuristicPtr->remove(this);
277 :
278 184090 : branchSub::recycle();
279 184090 : }
280 :
281 : //
282 : // Use LP to compute the lower bound. Has to work for root too with
283 : // current search framework.
284 : //
285 184093 : void MILPNode::boundComputation(double* controlParam)
286 : {
287 :
288 184093 : DEBUGPR(5, ucout << "Bounding problem "
289 : << this << " branchVariable=" << branchVariable
290 : << " branchType=" << branchType << "\n");
291 :
292 : #ifdef ACRO_VALIDATING
293 : DEBUGPR(2,if (mGlobal()->mipHeuristicPtr)
294 : mGlobal()->mipHeuristicPtr->checkLP("boundComputation"));
295 : #endif
296 :
297 : // Added by JE. Says we're doing one subproblem. Later, we may
298 : // change this to be the number of pivots executed (set after calling solver)
299 184093 : *controlParam = 1;
300 :
301 184093 : makeActiveLP();
302 :
303 : // TODO: temp
304 : // cout << "In boundComputation: \n";
305 : // printIntegerVariableSettings();
306 :
307 184093 : double parent_bound = lpBound;
308 :
309 184093 : PicoLPInterface::problemState solvedState = boundComputationGuts();
310 :
311 184091 : if (solvedState == PicoLPInterface::solved) {
312 :
313 92155 : setState(bounded);
314 :
315 : // Do some post-LP calculations and lock variables. Don't bother
316 : // if this solution will be thrown away
317 :
318 : // As long as we're not enumerating (in which case the node could live
319 : // on), I think it's OK to not deactivate this, since it will be
320 : // eliminated as soon as the candidate is recorded (no children.
321 : // No need to store cuts, increment reference counts, etc, just to
322 : // undo that). If noLongerActiveLP gains new functionality,
323 : // consider changes here.
324 :
325 92155 : if (candidateSolution())
326 : {
327 10 : if (bGlobal()->enumerating)
328 0 : noLongerActiveLP();
329 : else
330 10 : return;
331 : }
332 92145 : else if (!canFathom())
333 : {
334 :
335 : // Need the solution for the integer variables to see how many integer
336 : // variables are fractional
337 :
338 92126 : lockVariables();
339 92126 : noLongerActiveLP();
340 :
341 : // JE -- this should probably go away once the E-N heuristic
342 : // is moved into the general heuristic framework.
343 :
344 92126 : if (mGlobal()->mipHeuristicPtr)
345 0 : mGlobal()->mipHeuristicPtr->update(this);
346 : }
347 :
348 92145 : return;
349 : }
350 :
351 : // Serious problems would have been detected in boundComputationGuts().
352 : // Otherwise the problem is infeasible or past the cutoff, both of which
353 : // are valid reasons to fathom the problem (i.e. make it dead without error)
354 91936 : setState(dead);
355 91936 : if (!recordPCost) {
356 1 : return;
357 : }
358 91935 : if (solvedState == PicoLPInterface::infeasible) {
359 91935 : mGlobal()->updateFromInfeasible(branchVariable, branchType);
360 : }
361 : // hit cutoff; for update use the LP cutoff, which may not correspond
362 : // to the incumbent at this time
363 : else
364 : mGlobal()->updateFromCutoff(branchVariable,
365 : branchType,
366 : branchValue,
367 : parent_bound,
368 0 : lp->getDualCutoff());
369 91935 : return;
370 : }
371 :
372 : // Set the LP solver environment to reflect this subproblem
373 :
374 184246 : void MILPNode::makeActiveLP()
375 : {
376 : // Cut off set to incumbent value in the updateIncumbent routine of MILP
377 184246 : if (isRoot()) {
378 51 : if (mGlobal()->useSavedRootSolution)
379 0 : setSolverMethod(mGlobal()->warmSimplexMethod);
380 : else
381 51 : setSolverMethod(mGlobal()->rootSimplexMethod);
382 51 : allowWarmStart();
383 51 : updateLastID();
384 51 : return;
385 : }
386 : // Only done if necessary
387 184195 : setBounds();
388 184195 : if (isWarmStart()) {
389 6209 : setSolverMethod(mGlobal()->warmSimplexMethod);
390 : } else {
391 177986 : setSolverMethod(mGlobal()->nonwarmSimplexMethod);
392 177986 : setBasis();
393 : }
394 : // Have to do this at the end to make sure we update bounds, etc, correctly.
395 184195 : allowWarmStart();
396 184195 : updateLastID();
397 : }
398 :
399 : // Set LP bounds to reflect this subproblem. Bounds in this subproblem already reflect
400 : // any differences from the parent.
401 :
402 184085 : void MILPNode::setBounds() {
403 184085 : if (!isWarmStart()) {
404 177986 : setAllLPBounds(fixed, intLowerBounds, intUpperBounds, binary_vals);
405 177986 : return;
406 : }
407 : // For now, a child differs from its parent in only one variable.
408 6099 : DEBUGPR(150, ucout << "warm start\n");
409 :
410 6099 : MILPProblem* localMipRef = mip();
411 6099 : if (mGlobal()->useSets && branchVariable >= localMipRef->numIntegerVars())
412 : {
413 : // Branching on a set. Set variables in the set outside the indicated index range to 0.
414 0 : int setNum = branchVariable - localMipRef->numIntegerVars();
415 0 : IntVector& thisSet = localMipRef->specialSets[setNum];
416 : size_type k;
417 : size_type setStart, setEnd; // range of variables (indices into set) to be adjusted
418 0 : if (branchType == branch_up)
419 : {
420 0 : setStart = (size_type) parentSetBound;
421 0 : setEnd = (size_type) floor(branchValue);
422 : }
423 : else
424 : {
425 0 : setStart = (size_type) ceil(branchValue);
426 0 : setEnd = (size_type) parentSetBound;
427 : }
428 : // Only one variable allowed to receive the 1, so set it
429 0 : if (spSetLowerBounds[setNum] == spSetUpperBounds[setNum])
430 0 : lp->setColLower(localMipRef->integerVarNdx[thisSet[spSetUpperBounds[setNum]]], 1.0);
431 :
432 0 : for (k= setStart; k <= setEnd; k++)
433 0 : lp->setColUpper(localMipRef->integerVarNdx[thisSet[k]], 0.0);
434 0 : return;
435 : }
436 : // get LP variable number
437 6099 : int thisVarIndex = localMipRef->integerVarNdx[branchVariable];
438 6099 : if (localMipRef->vtype[thisVarIndex] == generalInteger) {
439 5786 : if (branchType == branch_up)
440 : lp->setColLower(thisVarIndex,
441 550 : intLowerBounds[localMipRef->reverseBoundsNdx[branchVariable]]);
442 : else
443 : lp->setColUpper(thisVarIndex,
444 5236 : intUpperBounds[localMipRef->reverseBoundsNdx[branchVariable]]);
445 313 : } else if (localMipRef->vtype[thisVarIndex] == binary) {
446 313 : if (branchType == branch_up)
447 139 : lp->setColLower(thisVarIndex, (double) 1);
448 : else
449 174 : lp->setColUpper(thisVarIndex, (double) 0);
450 : }
451 0 : else EXCEPTION_MNGR(runtime_error,"*** Trying to branch on noninteger variable");
452 : }
453 :
454 : // Adjust some bounds in the LP associated with a single branch choice
455 : // (one variable or one set). This is used during pseudocost
456 : // initialization, so we assume the node has the full ranges reflected
457 : // in its variable/set bounds. branchChoice is encoded the way the
458 : // MILP class encodes branching choices: the first # integers values
459 : // are for variables, the next # sets values are for the sets. If
460 : // reset is true, then this actually *undoes* a branch (e.g. after
461 : // "fake" branching for pseudocost initialization).
462 :
463 : // Note -- JE -- added ability to modify an arbitrary LP instead of the
464 : // usual one.
465 :
466 : void MILPNode::adjustLPBounds(OsiSolverInterface* whichLP,
467 : int branchChoice,
468 : branch_type direction,
469 653 : bool reset)
470 : {
471 653 : DEBUGPR(200,ucout << "MILPNode::adjustLPBounds invoked"
472 : << (reset ? " (reset flag)" : "") << endl);
473 :
474 653 : MILPProblem* localMipRef = mip();
475 :
476 653 : if (mGlobal()->useSets && branchChoice >= localMipRef->numIntegerVars())
477 : {
478 : // Branching on a set. Set variables in the set
479 : // outside the indicated index range to 0.
480 :
481 0 : DEBUGPR(200,ucout << "SOS set "
482 : << branchChoice - localMipRef->numIntegerVars()<<endl);
483 :
484 0 : int setNum = branchChoice - localMipRef->numIntegerVars();
485 0 : IntVector& thisSet = localMipRef->specialSets[setNum];
486 : size_type k;
487 : size_type setStart; // Range of variables (indices into set)
488 : size_type setEnd; // to be adjusted
489 :
490 0 : if (direction == branch_up)
491 : {
492 0 : setStart = (size_type) spSetLowerBounds[setNum];
493 0 : setEnd = (size_type) floor(spSetBranchValues[setNum]);
494 : }
495 : else
496 : {
497 0 : setStart = (size_type) ceil(spSetBranchValues[setNum]);
498 0 : setEnd = (size_type) spSetUpperBounds[setNum];
499 : }
500 : #ifdef ACRO_VALIDATING
501 : if (setEnd > 10000)
502 : cout << "milpNode.cpp:471: heres a bad set: " << setNum<<endl;
503 : #endif
504 : int intVarNum;
505 0 : for (k=setStart; k<=setEnd; k++)
506 : {
507 0 : intVarNum = thisSet[k];
508 : // Some of the variables in a special set range
509 : // could already be fixed (in this case to 0)
510 0 : if (!fixed(intVarNum))
511 : {
512 : whichLP->setColUpper(localMipRef->integerVarNdx[intVarNum],
513 0 : (reset ? 1.0 : 0.0));
514 0 : DEBUGPR(200,ucout << "Set upper bound of variable "
515 : << intVarNum << '/'
516 : << localMipRef->integerVarNdx[intVarNum]
517 : << " to " << (reset ? 1.0 : 0.0) << endl);
518 : }
519 : }
520 0 : return;
521 : }
522 :
523 : // Regular variable. Get LP variable number
524 :
525 653 : int thisLPVarIndex = localMipRef->integerVarNdx[branchChoice];
526 :
527 653 : if (localMipRef->vtype[thisLPVarIndex] == generalInteger)
528 : {
529 187 : int genIntNum = localMipRef->reverseBoundsNdx[branchChoice];
530 : int newVal;
531 :
532 : // Could do this with ? : syntax too, but it would make
533 : // it a bit harder to read
534 :
535 187 : if (direction == branch_up)
536 : {
537 92 : if (reset)
538 46 : newVal = intLowerBounds[genIntNum];
539 46 : else newVal = (int) ceil(solVector[branchChoice]);
540 92 : whichLP->setColLower(thisLPVarIndex, newVal);
541 92 : DEBUGPR(200,ucout << "Set lower bound of general variable "
542 : << branchChoice << '/' << thisLPVarIndex
543 : << " to " << newVal << ", solVector[" << branchChoice
544 : << "]=" << solVector[branchChoice] << endl);
545 : }
546 : else
547 : {
548 95 : if (reset)
549 46 : newVal = intUpperBounds[genIntNum];
550 49 : else newVal = (int) floor(solVector[branchChoice]);
551 95 : whichLP->setColUpper(thisLPVarIndex, newVal);
552 95 : DEBUGPR(100,ucout << "Set upper bound of general variable "
553 : << branchChoice << '/' << thisLPVarIndex
554 : << " to " << newVal << "solVector[" << branchChoice
555 : << "]=" << solVector[branchChoice] << endl);
556 : }
557 : }
558 : else //binary
559 : {
560 466 : if (direction == branch_up)
561 : {
562 224 : whichLP->setColLower(thisLPVarIndex, reset ? 0.0: 1.0);
563 224 : DEBUGPR(100,ucout << "Set lower bound of binary variable "
564 : << branchChoice << '/' << thisLPVarIndex
565 : << " to " << (reset ? 0.0: 1.0) << endl);
566 : }
567 : else
568 : {
569 242 : whichLP->setColUpper(thisLPVarIndex, reset ? 1.0 : 0.0);
570 242 : DEBUGPR(100,ucout << "Set upper bound of binary variable "
571 : << branchChoice << '/' << thisLPVarIndex
572 : << " to " << (reset ? 1.0 : 0.0) << endl);
573 : }
574 : }
575 : }
576 :
577 :
578 : // Runs the LP. If the problem has serious problems, signal an error, which
579 : // is assumed to abort the computation. Otherwise, return the state (either
580 : // solved, infeasible, or past cut-off).
581 :
582 184678 : PicoLPInterface::problemState MILPNode::runLP()
583 : {
584 184678 : if (!isRoot())
585 184562 : lp->solve(true); // know the primal is bounded
586 : else // doing pseudocost init on the root if the state is bounded (hence primal bounded)
587 116 : lp->solve(state==beingSeparated);
588 :
589 184678 : PicoLPInterface::problemState solvedState = lp->state();
590 :
591 184678 : if (solvedState == PicoLPInterface::unsolved)
592 0 : EXCEPTION_MNGR(runtime_error, "LP Returned Unsolved State");
593 184678 : if (solvedState == PicoLPInterface::unbounded)
594 : {
595 0 : EXCEPTION_MNGR(runtime_error, "LP Instance Unbounded");
596 : }
597 184678 : if (solvedState == PicoLPInterface::broken) {
598 : // printMILPNode();
599 : // lp->testLP();
600 : // DELETE THIS FIRST ONE
601 0 : lp->write("bad.mps", mps_format);
602 0 : lp->printBrokenInfo();
603 0 : checkLPBounds();
604 0 : EXCEPTION_MNGR(runtime_error, "LP Instance Broken");
605 : }
606 :
607 184678 : return(solvedState);
608 : }
609 :
610 : // Warning: changes here should be propagated to
611 : // parMILPNode::boundingSolve(). TODO: can we clean
612 : // these methods up and avoid code duplication?
613 :
614 184368 : PicoLPInterface::problemState MILPNode::boundingSolve()
615 : {
616 : PicoLPInterface::problemState solvedState;
617 184368 : double parent_bound = lpBound;
618 184368 : if (useSavedSolutionNow())
619 : {
620 0 : solvedState = retrieveRootSolution();
621 0 : if (solvedState != PicoLPInterface::solved)
622 0 : return(solvedState);
623 : // Make the LP solver look as though it has just finished this bounding
624 0 : restoreLPSolver();
625 : }
626 : else
627 : {
628 184368 : solvedState = runLP();
629 184368 : if (solvedState != PicoLPInterface::solved)
630 91931 : return(solvedState);
631 92437 : lpBound = lp->getObjValue();
632 92437 : getSolution();
633 : // cout << "Ran LP for problem " << id << ". New solution is: " << solution << "\n";
634 92437 : getBasis(basis);
635 : // Temporary for basis experiments
636 92437 : if (mGlobal()->recordBasisInfo)
637 : {
638 0 : *(mGlobal()->basisOutfile) << basis << "\n";
639 : // cout << "New basis is: " << basis << "\n";
640 : // use serial numbers produced as a surrogate for # of bases output. Most problems are
641 : // bounded before they're stored I think.
642 0 : if (mGlobal()->probCounter > mGlobal()->earlyStopBasisInfoCount)
643 0 : EXCEPTION_MNGR(runtime_error, "Hit the limit for basis recording. Stopping computation\n");
644 : }
645 : }
646 : // LP value could improve the bound
647 92437 : if (lround(lp->getObjSense()) == pebbl::minimize)
648 92432 : bound = max(bound, lpBound);
649 5 : else bound = min(bound, lpBound);
650 92437 : nFrac = computeFracVars(); // Also sets FracVarNdx, and computes set candidates
651 :
652 : // This should be true except for the root (which has no parent for
653 : // comparison) and cases where pseudocosts were recorded during a
654 : // pseudocost initialization phase and then the parent is separated
655 : // using one of these newly-initialized variables (i.e. this check
656 : // prevents a double recording).
657 :
658 92437 : if (updatePCFromBoundingSolve())
659 : updatePseudoCosts(lpBound, parent_bound, branchType,
660 92158 : branchVariable, branchValue);
661 :
662 92437 : return(PicoLPInterface::solved);
663 : }
664 :
665 : // Get the root solution from a file (e.g. when the root subproblem has been solved by
666 : // another solver, perhaps on another platform). This is particularly useful for
667 : // parallel runs when the root solve is much more expensive than a re-solve.
668 :
669 0 : PicoLPInterface::problemState MILPNode::retrieveRootSolution()
670 : {
671 : PicoLPInterface::problemState solvedState;
672 : int tempState;
673 : // Just to be sure...
674 0 : forceColdStart();
675 0 : string rootSolFileName(mGlobal()->problemName);
676 0 : if (rootSolFileName.length() > 0)
677 0 : rootSolFileName += "-bounding-info.bin";
678 0 : else rootSolFileName = "root-bounding-info.bin";
679 0 : ifstream savedSolution(rootSolFileName.c_str());
680 0 : if (savedSolution.bad())
681 0 : EXCEPTION_MNGR(runtime_error, "Can't open the saved root solution");
682 0 : savedSolution >> tempState;
683 0 : solvedState = (PicoLPInterface::problemState) tempState;
684 0 : if (solvedState != PicoLPInterface::solved)
685 0 : return(solvedState);
686 0 : savedSolution >> lpBound;
687 0 : savedSolution >> solVector;
688 : // Till we have the CLP basis problems fixed
689 : int basisAvailInt;
690 0 : savedSolution >> basisAvailInt;
691 0 : if (basisAvailInt == 1)
692 0 : basisValid = true;
693 0 : else basisValid = false;
694 0 : savedSolution >> basis;
695 0 : return(PicoLPInterface::solved);
696 : }
697 :
698 184400 : void MILPNode::setSolverMethod(MILP::LPMethodType method)
699 : {
700 184400 : if (method == MILP::dual)
701 184349 : lp->setLPMethod(PicoLPInterface::dualSimplex);
702 51 : else if (method == MILP::primal)
703 51 : lp->setLPMethod(PicoLPInterface::primalSimplex);
704 : // Shouldn't happen if we really have an LPMethodType passed in
705 0 : else EXCEPTION_MNGR(runtime_error, "Illegal LP method: %d\n");
706 184400 : }
707 :
708 :
709 : //---------------------------------------------
710 : // Decide how many children to compute
711 : // Also, decide how children are generated
712 : //---------------------------------------------
713 :
714 92038 : int MILPNode::splitComputation()
715 : {
716 92038 : DEBUGPRX(100,bGlobal(),"In MILPNode::splitComputation\n");
717 :
718 : // get local reference to mip()
719 92038 : MILPProblem* localMipRef = mip();
720 :
721 : // This compiles, but doesn't actually appear to turn on debugging.
722 : //if (id.serial==5) localMipRef->setDebug(100);
723 :
724 92038 : int numInts = localMipRef->numIntegerVars();
725 :
726 : // JE: if we actually have a terminal node being branched for
727 : // enumeration, do a different computation instead of the usual one
728 : // by calling terminalSplit. This routine will throw an exception
729 : // unless we have cuts.
730 :
731 92038 : if (nFrac == 0)
732 0 : return terminalSplit();
733 :
734 : double minBenefit; // dummy for this (used to track quality of branching)
735 : // Note: branchtype passed by reference; will be filled in
736 92038 : branchVariable = chooseBranchVariable(branchType, minBenefit);
737 92038 : if (state == dead) return(0);
738 :
739 92038 : if (mGlobal()->useSets && (branchVariable >= numInts))
740 0 : branchValue = spSetBranchValues[branchVariable-numInts];
741 92038 : else branchValue = solVector[branchVariable];
742 : // For now, we are assuming only two children, even for general integer vars
743 : // childrenLeft is set in branchSub::splitProblem
744 92038 : setState(separated); // Added by JE when beingSeparated state introduced.
745 92038 : return 2;
746 : }
747 :
748 : // Initialize some of the pseudocosts. numBranches is the number of
749 : // variables/sets to initialize. It should never be 0, but the code
750 : // will work even if it is. initVars has indices into the full set of
751 : // branching choices. If the entry is < # integer variables, it's a
752 : // variable. Otherwise it's a set. If dontRemoveAllBranchChoices is true, then
753 : // even if all the choices are half infeasible, make sure that one
754 : // still has its original bounds so we can legitimately branch on a
755 : // choice with highest priority (at least for now, all these variables
756 : // have the highest priority among all branching
757 : // choices). removeBranchChoiceNow=false suppresses actions on half-infeasible
758 : // branching choices (i.e. bounds narrowing and removal from branching
759 : // consideration). This is false for derived parallel methods and when there is
760 : // a possibility of overlapping SOS among the branch choices.
761 : // The boolean parameter stopOnInfeasible set to true means that as soon as
762 : // this method detects subproblem infeasibility (both branches of a branch choice
763 : // are LP infeasible), then it stops computing any more pseudocosts. This is
764 : // default. The only time it is false is in parallel ramp up when the processor
765 : // would otherwise be idle.
766 :
767 :
768 : void MILPNode::pseudoCostInit(IntVector &initVars,
769 : int numBranches,
770 : bool dontRemoveAllBranchChoices,
771 : bool removeBranchChoiceNow,
772 153 : bool stopOnInfeasible)
773 : {
774 : double upBound, downBound, bestBound;
775 : // TODO: remove
776 : // ucout << "Initializing " << numBranches << " branches.\n";
777 : /* ucout << "pseudoCostInit, " << numBranches << " to init. Vars are: \n";
778 : for (int tempry = 0; tempry < numBranches; tempry++)
779 : ucout << initVars[tempry] << ", ";
780 : ucout << "\n"; */
781 :
782 : int branchChoice;
783 : bool upRunInfeasible, downRunInfeasible;
784 :
785 : #ifdef ACRO_VALIDATING
786 : double PCStart = CPUSeconds();
787 : #endif
788 :
789 153 : makeActiveLP();
790 :
791 150 : do {
792 154 : branchChoice = initVars[--numBranches];
793 : // Reset to this subproblem's basis for each run. For some problems, we were
794 : // getting numerical problems on subsequent down branching. On all iterations after
795 : // the first, the up branch will also have two variable changes. See if this improves
796 : // stability.
797 154 : setBasis();
798 :
799 154 : adjustLPBounds(branchChoice, branch_up);
800 :
801 154 : upRunInfeasible = boundAndRecord(branch_up, branchChoice);
802 :
803 154 : postPseudoBranch(branchChoice, branch_up);
804 154 : upBound = lp->getObjValue();
805 :
806 :
807 : // Restore bounds in LP
808 154 : adjustLPBounds(branchChoice, branch_up, true);
809 :
810 : // Set variable bounds for the down branch.
811 154 : adjustLPBounds(branchChoice, branch_down);
812 :
813 154 : setSolverMethod((MILP::LPMethodType)(mGlobal()->warmSimplexMethod));
814 : // Reset to this subproblem's basis for each run. For some problems, we were
815 : // getting numerical problems on subsequent down branching.
816 154 : setBasis();
817 154 : downRunInfeasible = boundAndRecord(branch_down, branchChoice);
818 154 : postPseudoBranch(branchChoice, branch_down);
819 154 : downBound = lp->getObjValue();
820 :
821 : // restore LP bounds
822 154 : adjustLPBounds(branchChoice, branch_down, true);
823 :
824 154 : if (upRunInfeasible)
825 : {
826 33 : upBound = bGlobal()->sense * MAXDOUBLE;
827 33 : mGlobal()->updateFromInfeasible(branchChoice, branch_up);
828 :
829 33 : if (downRunInfeasible) // subproblem can be fathomed
830 : {
831 4 : setState(dead);
832 4 : downBound = bGlobal()->sense * MAXDOUBLE;
833 4 : mGlobal()->updateFromInfeasible(branchChoice, branch_down);
834 4 : if (stopOnInfeasible)
835 4 : break;
836 : }
837 : // Take advantage of the half infeasibility by narrowing ranges and removing from consideration
838 : // for branching. We cannot do this if this is the last initialization
839 : // and all previous ones have been half infeasible too.
840 29 : else if ((!dontRemoveAllBranchChoices || numBranches > 0) && removeBranchChoiceNow)
841 : {
842 29 : removeBranchChoice(branchChoice);
843 : // This is necessary for B&C, and no harm for straight B&B
844 29 : adjustLPBounds(branchChoice, branch_down);
845 : // Have to adjust LP bounds first since that relies on node bounds
846 29 : adjustNodeBounds(branchChoice, branch_down);
847 : }
848 : }
849 :
850 121 : else if (downRunInfeasible)
851 : {
852 : // See above similar case for explanation
853 9 : if ((!dontRemoveAllBranchChoices || numBranches > 0) && removeBranchChoiceNow)
854 : {
855 8 : removeBranchChoice(branchChoice);
856 8 : adjustLPBounds(branchChoice, branch_up);
857 : // Have to adjust LP bounds first since that relies on node bounds
858 8 : adjustNodeBounds(branchChoice, branch_up);
859 : }
860 9 : downBound = bGlobal()->sense * MAXDOUBLE;
861 9 : mGlobal()->updateFromInfeasible(branchChoice, branch_down);
862 : }
863 : /*
864 : ucout << "Branch Choice = " << branchChoice << " upBound = " << upBound << ", downBound = " << downBound << ", bound = " << bound << "\n";
865 : */
866 150 : if (lround(lp->getObjSense()) == pebbl::minimize)
867 : {
868 150 : bestBound = min(upBound, downBound); // valid bound for the subproblem
869 150 : bound = max(bestBound, bound); // could have seen a better one in other
870 : // subproblems
871 : }
872 : else
873 : {
874 0 : bestBound = max(upBound, downBound);
875 0 : bound = min(bestBound, bound);
876 : }
877 : // ucout << ", new bound = " << bound << "\n";
878 : } while (numBranches > 0);
879 153 : if (state == beingSeparated) // in branch & cut world, might still be active
880 20 : noLongerActiveLP();
881 : /* mGlobal()->printPseudoCosts();
882 : ucout << Flush; */
883 : #ifdef ACRO_VALIDATING
884 : mGlobal()->MIPTimingInfo[PCInit] += CPUSeconds() - PCStart;
885 : #endif
886 153 : }
887 :
888 : // Used in initializing pseudocosts. The LP has been set already. Returns
889 : // 0 if the problem solved and 1 if the problem is infeasible or otherwise
890 : // fathomable. Major errors will result in an abort at the time of the solve.
891 :
892 308 : int MILPNode::boundAndRecord(branch_type branchDirection, int branchingVar)
893 : {
894 308 : PicoLPInterface::problemState solvedState = PCInitSolve();
895 :
896 308 : if (solvedState == PicoLPInterface::solved) {
897 : // ucout << "BAR calling UPC\n";
898 262 : int numInts = mip()->numIntegerVars();
899 : double branchingVal;
900 262 : if (branchingVar >= numInts) // a set
901 : {
902 0 : branchingVal = spSetBranchValues[branchingVar-numInts];
903 : // the integer part encodes a place in the set list. The
904 : // real branching part is just the fractional piece.
905 0 : branchingVal -= floor(branchingVal);
906 : }
907 262 : else branchingVal = solVector[branchingVar];
908 :
909 : updatePseudoCosts(lp->getObjValue(), lpBound, branchDirection,
910 262 : branchingVar, branchingVal);
911 262 : return(0);
912 : }
913 46 : else return(1);
914 : }
915 :
916 : // Adjust the bounds within a MILPNode to implement a branch. Used to
917 : // create children, in locking variables, and when infeasible branches
918 : // are discovered during the computation of pseudocosts. This
919 : // functionality is duplicated in packChild (changes should be
920 : // propagated).
921 :
922 : void MILPNode::adjustNodeBounds(const int thisBranchVariable,
923 184113 : branch_type branch_flag)
924 : {
925 184113 : MILPProblem* localMipRef = mip();
926 : double thisBranchVal;
927 :
928 : // branching on a special set
929 184113 : if (mGlobal()->useSets &&
930 : thisBranchVariable >= localMipRef->numIntegerVars())
931 : {
932 0 : int setNum = thisBranchVariable - localMipRef->numIntegerVars();
933 0 : if (state == boundable)
934 0 : thisBranchVal = branchValue;
935 0 : else thisBranchVal = spSetBranchValues[setNum];
936 : // Branching on a set. Set variables in the set outside the
937 : // indicated index range to 0.
938 0 : IntVector& thisSet = localMipRef->specialSets[setNum];
939 : size_type k, setStart, setEnd;
940 : int thisSetVar;
941 : // Figure out which binary variables will be forced to 0.
942 : // This are delimited by setStart and setEnd.
943 0 : if (branch_flag == branch_up)
944 : {
945 0 : setStart = (size_type) spSetLowerBounds[setNum];
946 : // Next step not necessary if this is for infeasibility during
947 : // pseudocost computation, but in that case, this value won't be
948 : // used anymore.
949 0 : parentSetBound = setStart;
950 0 : setEnd = (size_type) floor(thisBranchVal);
951 0 : spSetLowerBounds[setNum] = setEnd+1;
952 : #ifdef ACRO_VALIDATING
953 : if ((size_type) spSetUpperBounds[setNum] < setEnd+1)
954 : EXCEPTION_MNGR(runtime_error,"Inconsistent set bounds for set"
955 : << setNum << " (" << setEnd+1
956 : << "," << spSetUpperBounds[setNum]
957 : << "), branching up. setStart = " << setStart
958 : << ", branchValue = " << thisBranchVal
959 : << ". Node " << id << ". parent: " << parentId << "\n");
960 : #endif
961 : // Only one variable allowed to receive the 1, so fix it
962 0 : if (spSetUpperBounds[setNum] == (int) setEnd+1)
963 : {
964 0 : thisSetVar = thisSet[setEnd+1];
965 0 : fixed.set(thisSetVar);
966 0 : binary_vals.set(thisSetVar);
967 : }
968 : }
969 : else // branching down
970 : {
971 0 : setStart = (size_type) ceil(thisBranchVal);
972 0 : setEnd = (size_type) spSetUpperBounds[setNum];
973 0 : parentSetBound = setEnd;
974 0 : spSetUpperBounds[setNum] = setStart - 1;
975 : #ifdef ACRO_VALIDATING
976 : if ((size_type) spSetLowerBounds[setNum] > setStart-1)
977 : EXCEPTION_MNGR(runtime_error,"Inconsistent set bounds for set" << setNum << " (" << spSetLowerBounds[setNum] << "," << setStart-1 << "). branching down. setEnd = " << setEnd << "branch value = " << thisBranchVal << "\n");
978 : #endif
979 :
980 : // Only one variable allowed to receive the 1, so fix it
981 0 : if (spSetLowerBounds[setNum] == (int) setStart-1)
982 : {
983 0 : thisSetVar = thisSet[setStart-1];
984 0 : fixed.set(thisSetVar);
985 0 : binary_vals.set(thisSetVar);
986 : }
987 : }
988 0 : for (k= setStart; k <= setEnd; k++)
989 : {
990 0 : thisSetVar = thisSet[k];
991 : #ifdef ACRO_VALIDATING
992 : if (fixed(thisSetVar) && binary_vals(thisSetVar))
993 : {
994 : printMILPNode();
995 : EXCEPTION_MNGR(runtime_error, "MilpNode::fix: branching on set"
996 : << thisBranchVariable - localMipRef->numIntegerVars()
997 : << " when member var " << thisSetVar
998 : << " already fixed to 1\n");
999 : }
1000 : #endif
1001 :
1002 : // It's OK to redo this if already fixed to 0 (this is possible)
1003 0 : fixed.set(thisSetVar);
1004 0 : binary_vals.reset(thisSetVar);
1005 : }
1006 0 : return;
1007 : }
1008 :
1009 : //
1010 : // branching on a variable
1011 : //
1012 184113 : if (localMipRef->vtype[localMipRef->integerVarNdx[thisBranchVariable]] == binary) {
1013 19838 : fixed.set(thisBranchVariable);
1014 19838 : if (branch_flag == branch_up)
1015 9910 : binary_vals.set(thisBranchVariable);
1016 : else
1017 9928 : binary_vals.reset(thisBranchVariable);
1018 : }
1019 : else {
1020 164275 : if (state == boundable)
1021 164272 : thisBranchVal = branchValue;
1022 3 : else thisBranchVal = solVector[thisBranchVariable];
1023 164275 : int genIntVarNumber = localMipRef->reverseBoundsNdx[thisBranchVariable];
1024 164275 : if (branch_flag == branch_up)
1025 82136 : intLowerBounds[genIntVarNumber] = (int) ceil(thisBranchVal);
1026 : else
1027 82139 : intUpperBounds[genIntVarNumber] = (int) floor(thisBranchVal);
1028 164275 : if (intLowerBounds[genIntVarNumber] == intUpperBounds[genIntVarNumber])
1029 81465 : fixed.set(thisBranchVariable);
1030 : #ifdef ACRO_VALIDATING
1031 : if (intLowerBounds[genIntVarNumber] > intUpperBounds[genIntVarNumber])
1032 : EXCEPTION_MNGR(runtime_error,
1033 : "MilpNode::fix: general variable with infeasible bounds."
1034 : "Integer Variable: " << genIntVarNumber << ", ("
1035 : << intLowerBounds[genIntVarNumber] << ","
1036 : << intUpperBounds[genIntVarNumber] << ")");
1037 : #endif
1038 : }
1039 : }
1040 :
1041 : // Called when the pseudocost initialization routine finds that a branch
1042 : // can be fathomed. Since the range will be narrowed, don't allow branching
1043 : // on this variable (remove from fractional variable list).
1044 :
1045 : // TODO: also have to remove individual variables as choices when a set is removed
1046 : // (at least one side; that may need another argument).
1047 :
1048 37 : void MILPNode::removeBranchChoice(int branchChoice)
1049 : {
1050 : int i;
1051 37 : if (branchChoice >= mip()->numIntegerVars())
1052 : {
1053 : #ifdef ACRO_VALIDATING
1054 : bool found = false;
1055 : #endif
1056 0 : int setNum = branchChoice - mip()->numIntegerVars();
1057 0 : for (i = 0; i < nSetCandidates; i++)
1058 0 : if (setCandidateNdx[i] == setNum)
1059 : {
1060 0 : setCandidateNdx[i] = setCandidateNdx[nSetCandidates-1];
1061 : #ifdef ACRO_VALIDATING
1062 : found = true;
1063 : #endif
1064 0 : break;
1065 : }
1066 : #ifdef ACRO_VALIDATING
1067 : if (!found)
1068 : EXCEPTION_MNGR(runtime_error, "Trying to remove branchChoice " << branchChoice << " (set " << setNum << "). Not found\n");
1069 : #endif
1070 0 : nSetCandidates--;
1071 0 : return;
1072 : }
1073 115 : for (i = 0; i < nFrac; i++) {
1074 115 : if (FracVarNdx[i] == branchChoice) {
1075 : // Note: if only 1 left, its index will still be in FracVarNdx[0]
1076 37 : FracVarNdx[i] = FracVarNdx[nFrac-1];
1077 37 : break;
1078 : }
1079 : }
1080 37 : nFrac--;
1081 : }
1082 :
1083 :
1084 0 : double MILPNode::improveIncumbent()
1085 : {
1086 : // verbosity tag
1087 0 : DEBUGPR(10, ucout << "Trying to improve incumbent...\n");
1088 :
1089 0 : if (state == beingBounded)
1090 0 : return incumbentValue();
1091 :
1092 0 : if (nFrac == 0)
1093 0 : EXCEPTION_MNGR(runtime_error, "Trying to improve terminal solution");
1094 :
1095 : // A heuristic could go here, but not in the present approach
1096 :
1097 0 : return incumbentValue();
1098 : };
1099 :
1100 :
1101 : // Not called unless this is a candidate solution (e.g. no fractional
1102 : // variables), in which case solution should be valid. But with a
1103 : // high integer tolerance, this may not be the case, so we check.
1104 : // Also set the integer variables to their exact integer values.
1105 : // Among other things, this makes it easier to compare solutions
1106 : // using, eg, standard utilib ==. Node solution only contains integer
1107 : // variables, but the incumbent contains them all, so need to pull in
1108 : // the full solution now.
1109 :
1110 : // JE: CP had this code in updateIncumbent() -- now it is extractSolution()
1111 :
1112 2 : pebbl::solution* MILPNode::extractSolution()
1113 : {
1114 2 : MILPProblem* localMipRef = mip();
1115 :
1116 2 : DEBUGPR(300,ucout << "MILPNode::extractSolution" << endl);
1117 2 : int numVars = localMipRef->numAllVars();
1118 2 : DoubleVector fullSolution(numVars);
1119 2 : lp->getColSolution(fullSolution.data());
1120 2 : DEBUGPR(300,ucout << "Got solution" << endl);
1121 : int j;
1122 : int intVal;
1123 2 : int numInts = localMipRef->numIntegerVars();
1124 : // round all the integer variables (already tested for integrality)
1125 118 : for (int i=0; i < numInts; i++) {
1126 116 : j = localMipRef->integerVarNdx[i]; // get LP var# for this int var #
1127 116 : intVal = lround(fullSolution[j]);
1128 116 : fullSolution[j] = intVal;
1129 : // Fix lower and upper bounds (doesn't matter if general or binary)
1130 : // bounds of continuous variables are never changed
1131 116 : lp->setColLower(j, intVal);
1132 116 : lp->setColUpper(j, intVal);
1133 : }
1134 :
1135 : bool feasible;
1136 2 : if (numInts == numVars) // pure integer
1137 0 : feasible = lp->checkFeasibility(fullSolution);
1138 : else
1139 : {
1140 2 : PicoLPInterface::problemState solvedState = runLPWithIntsSet();
1141 2 : if (solvedState == PicoLPInterface::solved)
1142 2 : feasible = true;
1143 0 : else feasible = false;
1144 : }
1145 :
1146 : // If we really have a solution, this node is now dead unless we are
1147 : // enumerating.
1148 :
1149 2 : if (feasible && !(bGlobal()->enumerating))
1150 2 : setState(dead);
1151 :
1152 : // JE: the end of the routine is different from the old updateIncumbent...
1153 :
1154 2 : if (feasible)
1155 : {
1156 : // JE: not sure that this code does or if it's in the right
1157 : // place any more.
1158 2 : if (state == beingBounded)
1159 0 : mGlobal()->needPruning = false;
1160 :
1161 2 : DEBUGPR(1,ucout << "***** " << "Terminal node yielded solution "
1162 : << lpBound << " *****\n");
1163 :
1164 2 : return new MILPSolution(fullSolution,mGlobal(),lpBound);
1165 : }
1166 :
1167 : // Something is fishy...
1168 :
1169 0 : if (!(mGlobal()->suppressWarnings))
1170 : ucout << "Warning: Not recording infeasible incumbent candidate,"
1171 0 : << " id: " << id << "\n";
1172 :
1173 0 : return NULL; // PEBBL will ignore this value
1174 : }
1175 :
1176 :
1177 : // Verify that the candidate solution is still feasible when integer
1178 : // values are set exactly. Updates continuous variables via LP. Also
1179 : // update lpBound (if the solution is valid).
1180 :
1181 2 : PicoLPInterface::problemState MILPNode::runLPWithIntsSet()
1182 : {
1183 2 : DEBUGPR(300,ucout << "Integer variables rounded.\n" << Flush);
1184 2 : lp->setLPMethod(PicoLPInterface::primalSimplex);
1185 2 : DEBUGPR(300,ucout << "Method set" << endl << Flush);
1186 :
1187 : // Setting the basis at this point could cause some problems with
1188 : // the B&C derived class (don't know or care what cuts are loaded),
1189 : // so let's not set the basis for now. Hopefully won't be a problem
1190 : // because all the variables are fixed.
1191 :
1192 : // setBasis(); // presumably the final basis of the solve.
1193 : // DEBUGPR(300,ucout << "Basis set" << endl << Flush);
1194 : // if this is infeasible, hope the LP solver won't bomb.
1195 :
1196 2 : PicoLPInterface::problemState recheckState = runLP();
1197 2 : if (recheckState == PicoLPInterface::solved)
1198 2 : lpBound = lp->getObjValue();
1199 :
1200 2 : return(recheckState);
1201 : }
1202 :
1203 :
1204 184181 : void MILPNode::incumbentHeuristic(void)
1205 : {
1206 184181 : DEBUGPR(20,ucout << "In MILPNode::incumbentHeuristic\n");
1207 :
1208 : // Call all enabled incumbent heuristics in order.
1209 : // They are expected to police themselves. This should
1210 : // not be called if all heuristics are disabled.
1211 184181 : if (mGlobal()->stopPICOHeuristicsOnIncumbent && mGlobal()->haveIncumbent())
1212 0 : return;
1213 :
1214 : #ifdef ACRO_VALIDATING
1215 : double MHStart;
1216 : #endif
1217 :
1218 : // This will generally require a valid LP bound. For now,
1219 : // assume it's called at an appropriate time
1220 184181 : mGlobal()->runHeuristicsOnSubproblem(this);
1221 :
1222 : //This code used to activate randomized rounding. Turn off, since
1223 : //we're trying to activate randomized rounding through the new
1224 : //general framework.
1225 : // if (mGlobal()->RRTrialsPerCall > 0 && mGlobal()->maxRRDepth > 0)
1226 : // {
1227 : // #ifdef ACRO_VALIDATING
1228 : // MHStart = CPUSeconds();
1229 : // #endif
1230 : // RRheuristic();
1231 : // #ifdef ACRO_VALIDATING
1232 : // mGlobal()->MIPTimingInfo[MIPHeur] += CPUSeconds() - MHStart;
1233 : // #endif
1234 : // }
1235 : // Right now, remaining heuristics still run piecemeal...
1236 :
1237 184178 : if (mGlobal()->stopPICOHeuristicsOnIncumbent && mGlobal()->haveIncumbent())
1238 0 : return;
1239 :
1240 184178 : if (mGlobal()->mipHeuristicPtr)
1241 : {
1242 : #ifdef ACRO_VALIDATING
1243 : MHStart = CPUSeconds();
1244 : #endif
1245 0 : BBHincumbentHeuristic();
1246 : #ifdef ACRO_VALIDATING
1247 : mGlobal()->MIPTimingInfo[MIPHeur] += CPUSeconds() - MHStart;
1248 : #endif
1249 : }
1250 : }
|
