Search code examples
scip

how to update a node's lower and upper bound

I am trying to write a new scip relaxation handler. For each node, I want to update its lower and upper bounds with values that I come up with. Then I want scip to naturally use these better bounds in its solving process. But I am getting strange results.

My question is how do I update the lower and upper bounds of the current node in branch and bound?

Inside my relation handler, I have this debug code:

double l = -100;
double u = -15;
cout << "SCIP STAGE " << (scip->set->stage) << std::endl;
cout << SCIPgetNNodes(scip) << " min scip  " << SCIPgetLocalLowerbound(scip) << " <= " << SCIPgetUpperbound(scip) << endl;
cout << SCIPgetNNodes(scip) << " min my b  " << l             << " <= " << u << endl;

SCIPupdateLocalLowerbound(scip, l);

cout << SCIPgetNNodes(scip) << " min scip  " << SCIPgetLocalLowerbound(scip) << " <= " << SCIPgetUpperbound(scip) << endl;

The output is

SCIP STAGE 9
1 min scip  -1e+14 <= -100000
1 min my b  -100 <= -15
1 min scip  1e+20 <= -10000

scip stage 9 is the SCIP_STAGE_SOLVING, which looks good.

The lines with "scip" are scip's bounds for the node. The middle line with "my b" refers to my new bounds.

I am calling SCIPupdateLocalLowerbound(scip, -10) while the current lowerbound is -1e14, so the new lowerbound should be 10 after that call. However, the lower bound changes to 1e20 which is a huge error.

I would expect that SCIPupdateLocalLowerbound(scip, -10); would make SCIPgetLocalLowerbound(scip) return -10 not 1e20. What am I doing wrong?

Also, I do not see a function called SCIPupdateLocalUpperbound(), so how do I update the upperbound of a node?

EDIT 2015/03/13 Thank you Gregor for explaining that part of scip. I have one small question left.

For completeness, I am setting the lower bound of a local node's minimization problem by

SCIPupdateLocalLowerbound(scip, l)

and I am setting the global upper bound of the minimization problem by

if ( newUpperBound < scip->primal->upperbound)
    {
        SCIPprimalSetUpperbound(scip->primal, scip->mem->probmem, scip->set, scip->stat, scip->eventqueue, scip->transprob, scip->tree, scip->lp, newUpperBound);
    }

The second parameter to SCIPprimalSetUpperbound takes a 

BMS_BLKMEM*           blkmem,             /**< block memory */

and I am passing a blkmem that I found in scip->mem. Is this correct, or should I be passing some other clean block memory? Am I overwriting something important?

Edit 2015/03/19

Now I do not understand the output when setting the objective functions. As a reminder (to me), the original master problem is a maximization problem, and scip's transformed problem is minimization. If I look at the results of 

cout << SCIPgetNNodes(scip) << " min scip  " << SCIPgetLocalLowerbound(scip) << " <= " << SCIPgetUpperbound(scip) << endl;
cout << SCIPgetNNodes(scip) << " min my b  " << newLowerBound             << " <= " << newUpperBound << endl;


cout << "SCIPgetObjlimit " << SCIPgetObjlimit(scip) << endl;
cout << "SCIPretransformObj " << SCIPretransformObj(scip,newUpperBound) << endl;

the output is:

7 min scip  -1.10142e+08 <= 100000
7 min my b  -1.37597e+08 <= 2.11197e+08
SCIPgetObjlimit -1.97183e+08
SCIPretransformObj -2.11197e+08

So scip's bounds for the minimum of this node is -1.10142e+08 <= 100000, and my bounds for the minimum for this node is -1.37597e+08 <= 2.11197e+08, which is worse in this case.

Why is SCIPgetObjlimit = -1.97183e+08? Why is it not -100000? If 100000 is the current upper bound in the transformed space (minimization), then -100000 is my current global lower bound for my original problem.

Solution

  • While lower bounds are a local property special to each node (since they are usually inferred from the optimal LP-relaxation objective at this node, or the node children lower bounds in case they have already been solved, upper bounds come from primal solutions for your problem and are therefore globally valid.

    From SCIP's point of view, every node with a lower bound greater than or equal to the global upper bound can be pruned, and such nodes get +infinity (i.e., 1e+20 with default SCIP settings) as lower bound. A close look at the values reveals that you force this node to be pruned, because the global bound is -100000 when you set the local bound to l=-100, so SCIP's behavior is intended here.

    EDIT Concerning the second part of your question: It is actually forbidden in a sense to use such methods as, e.g., SCIPprimalSetUpperBound(), which originates from primal.h, from within plugins as, eg., your relaxator. The reason is exactly the problem you are now facing, concerning SCIP-internals that you do not need to care about.

    I would recommend to set an objective limit instead via SCIPsetObjlimit(). Please note that an objective limit must be given in original space, ie. if you wanted to pass an upper bound before, use ub = SCIPretransformObj(scip, ub) and afterwards SCIPsetObjlimit(scip, ub).

    EDIT Primal bounds in the original and transformed problem:

    1. SCIPgetUpperBound(scip) : Current upper bound in transformed problem space, minimimum of best solution objective and the (transformed) objective limit
    2. SCIPgetPrimalBound(scip) : the value of SCIPgetUpperBound(scip) in the original problem space, ie. under consideration of both the best solution and the user objective limit, if any.
    3. SCIPgetObjlimit(scip): The value of the objective limit set by the user, not respecting primal solution objectives.

    I assume that you set an objective limit, but SCIP found a primal solution which is better.