Originally posted by: Lessi

I use a branch callback to stop branching. To do so, I get a list of binary variables that are fixed using getLBs and getUBs; (https://www.ibm.com/developerworks/community/forums/html/topic?id=55024998-927c-446d-bef8-bb77bdfb4397 ) and then checking if some conditions are met or not.

And if the condition is met, I stop branching by using prune() method. However, the log shows that the check is called on a set many times.

we stop branching here because of an invalid set: 0 54 65 71 72 101 at the node 144
we stop branching here because of an invalid set: 0 54 65 71 72 101 at the node 144
we stop branching here because of an invalid set: 0 54 65 71 72 101 at the node 144

....

How can I stop everything at the node 144 when the checking condition fails?

Does it seem that I need to use a SolveCallBack + UserCutCallBack to achieve what I want?

P/s: I tried solvecallback + usercutcallback but it still happens:

we stop branching here because of an invalid set: 5 13 21 71 72 at the node 0
we stop branching here because of an invalid set: 5 13 21 71 72 at the node 0
we stop branching here because of an invalid set: 5 13 21 71 72 at the node 0

....

https://www.ibm.com/support/knowledgecenter/en/SSSA5P_12.6.3/ilog.odms.cplex.help/refcppcplex/html/classes/IloCplex_ControlCallbackI.html

Thanks.
/Lessi

Originally posted by: Lessi

Hi, I want to understand the manual a little bit more, 

Regarding control callback, ( https://www.ibm.com/support/knowledgecenter/en/SSSA5P_12.6.3/ilog.odms.cplex.help/refcppcplex/html/classes/IloCplex_ControlCallbackI.html ) ,

If the cut callback added new cuts to the node relaxation, the node relaxation will be solved again using the solve callback, if used.

What does it refer to with respect to "if used", does it mean we use solve() method of the solve callback? 

Regarding solve callback, https://www.ibm.com/support/knowledgecenter/SSSA5P_12.6.3/ilog.odms.cplex.help/refcppcplex/html/classes/IloCplex_SolveCallbackI.html?view=kc - the solve callback has a Solve() method, under which circumstance could we use it?

Regarding usercutcallback,  https://www.ibm.com/support/knowledgecenter/SSSA5P_12.6.3/ilog.odms.cplex.help/refcppcplex/html/classes/IloCplex_UserCutCallbackI.html, how and under which circumstance could we use abortCutLoop() and isAfterCutLoop() 

Anyway, during branching, I will check whether a set A of variables (e.g. 0 54 65 71 72 101)  which are fixed to 1 meet a condition or not.  I only have binary variables. What should I do to stop branching/solving .. if the checking condition is not met?  

we stop branching here because of an invalid set: 0 54 65 71 72 101 at the node 144
we stop branching here because of an invalid set: 0 54 65 71 72 101 at the node 144
we stop branching here because of an invalid set: 0 54 65 71 72 101 at the node 144
 

 

 

I have tested several options:
a) checking while in a ILOBRANCHCALLBACK + prune()
b) checking while in a ILOSOLVECALLBACK + add cuts to either ILOLAZYCUTCALLBACK or ILOUSERCUTCALLBACK to exclude any violated set.
c) checking while in a ILOINCUMBENTCALLBACK  + ILOLAZYCUTCALLBACK to exclude any violated set.

c) is the best choice and a) is the worst at the moment.  The following table includes 3 instances (i2, i3, i4) that b) with USERCUTCALLBACK fails while c) can solve. it seems that many checkings (third column) are performed regarding those instances, while the remaining instances (i1, and i5), only a few thousand are performed.  Does it happen because of USERCUTCALLBACK forces SOLVECALLBACK solve the same node again and again (and I count the number of times the checking step in the SOLVECALLBACK is called). 

i1.txt    401    2415    3    228    31    112    31    262    228.969    2650.48
i2.txt    400    5105634    4    181    33    130    33    222    191.357    3606.45
i3.txt    973    4043326    10    191    1    9    1    276    229.591    3600.04
i4.txt    501    2216367    9    184    33    68    33    240    200.623    3609.52
i5.txt    483    1452    6    183    3335    43    169    249    216.032    3669.08

This is the link where I put the log for i2.txt : https://ideone.com/1kMn3a

BranchCallbackI::prune() should cut off the current node, so that should be enough, no need to involve a user cut or solve callback. Provided that prune() is the last thing you do in your branch callback! If you call makeBranch() after prune() then the pruning is overwritten. The best thing is to explicitly return from the callback right after calling prune().

How do you find that "144" in "at node 144"? Are you sure this is correct? The branch callback should be invoked at most once per node, so it seems odd that in your case the callback seems to be invoked more than once per node.

Originally posted by: Lessi

Thank you, Daniel, for the explanation. I do not call makeBranch() in my code. And I use this->getNodeId() to get the value 144. Let me check the code and report what I observe.

That both sounds correct.

If you cannot find a problem in your code, maybe you can post your code or an outline of it here?

Originally posted by: Lessi

I'm not sure why but the problem still appears.  I sent you an email to your ibm account to ask for help because I sent you the whole code. Now, some nodes are being checked repeatedly.

we stop branching here because of infeasible POIs: 2 4 6 at the node 466
we stop branching here because of infeasible POIs: 2 6 8 21 49 at the node 638
we stop branching here because of infeasible POIs: 2 6 8 21 57 at the node 650
we stop branching here because of infeasible POIs: 2 4 6 at the node 466
we stop branching here because of infeasible POIs: 2 6 8 21 49 at the node 638
we stop branching here because of infeasible POIs: 2 6 8 21 57 at the node 650

This is the code template :

ILOBRANCHCALLBACK0(stopBranching)
{
    if (this->getBestObjValue() < slnBest + 1 && this->getObjValue() < slnBest + 1)
    {
 
        this->abort();
        return;
    }
    if (this->getObjValue() < slnBest + 1)
    {
       
        nbReject++;
        this->prune();
        return;
       
    }

    IloNumArray lbYmaster(this->getEnv());
    IloNumArray ubYmaster(this->getEnv());

    this->getLBs(lbYmaster, yMaster);
    this->getUBs(ubYmaster, yMaster);

    IloNumArray y_valBC(this->getEnv(), ttdp.N);
    vector<int> fixedNodes;

    long long h = 0;
    for (int i = 0;i < ttdp.N;i++)
        if (lbYmaster[i] == 1 && ubYmaster[i] == 1)
        {
            y_valBC[i] = 1;
             
            fixedNodes.push_back(i);

        }
        else
            y_valBC[i] = 0;

    if (fixedNodes.size() == 2)
        return;

    updateSlaveModel(y_valBC);

    cplexSlave.solve();

    if (cplexSlave.getStatus() == IloAlgorithm::Infeasible)
    {
        cout << "we stop branching here because of infeasible POIs: ";
        for (int i = 1;i + 1 < ttdp.N;i++)
            if (y_valBC[i] == 1)
                cout << i << " ";
 

       cout << "at the node " << this->getNodeId() << endl;
        nbReject++;

        this->prune();

        return;
    }
 
}

/Lessi
 

Originally posted by: EdKlotz

While I don't see it mentioned in the forum here, Daniel mentioned to me that your code uses the populate()  method rather than the solve() method().   The prune() method only applies to solve() not populate().  This is because pruning is not distinctly defined given the way populate() processes nodes in the tree.    I see you are using version 12.6.3; the 12.8 documentation for IloCplex::BranchCallbackI and the other branch callback APIs, was modified to explicitly point this out.   From https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.cplex.help/refcppcplex/html/classes/IloCplex_BranchCallbackI.html we have:

prune

Originally posted by: Lessi

I am not sure why it still happens when I use solve(). It now happens with another input, not my previous input.

we stop branching here because of infeasible POIs: 0 16 63 71 74 101 at the node 54 with 34 unfixed variables
we stop branching here because of infeasible POIs: 0 16 63 71 74 101 at the node 54 with 34 unfixed variables
we stop branching here because of infeasible POIs: 0 16 63 71 74 101 at the node 54 with 34 unfixed variables
we stop branching here because of infeasible POIs: 0 16 63 71 74 101 at the node 54 with 34 unfixed variables
we stop branching here because of infeasible POIs: 0 16 63 71 74 101 at the node 54 with 34 unfixed variables
we stop branching here because of infeasible POIs: 0 16 63 71 74 101 at the node 54 with 34 unfixed variables

M.

The problem is that in your code you still set the solution pool intensity to 4. That basically has the same limitations as populate: CPLEX is forced to keep solutions that could be cut off or pruned since the subtree rooted at them may contain more feasible solutions.

Can you please try setting the solution pool intensity to 0 (default) or 1? With that setting I did not longer get duplicate nodes here.

Originally posted by: Lessi

Thank you, Daniel, it works.

As I understand, solve() will ignore all nodes for which it knows that those nodes cannot give better solutions if feasible solutions are found. Is it right? While populate() tries to keep all nodes.

Correct, solve() will discard nodes as soon as possible -- provided the configured solution pool strategy allows this. This is because the primary goal of solve() is to find the optimal solution, hence nodes with alternate non-optimal solutions are not interesting.

populate() instead may keep nodes even if they can be proved to not contain a better or the optimal solution. Then it may re-process those nodes later to find alternative solutions.

Originally posted by: Lessi

Thank both of you, your comment are helpful. Let me check if I can use solve() instead of populate().