Originally posted by: SystemAdmin

Dear all,

I used a B&C. At some node of the B&B tree, I output the node file and solved it separately by CPLEX. The solution to this node lp was different from the one returned by CPXgetcallbacknodex. These two solution have same objective values.

Solving node lp gave an inteter solution. But CPXgetcallbacknodex returned continuous solution.
Acutally I prefer to the integer solution since it is a new incumbent.
Thanks.

Shaon
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

When an LP has multiple optima, almost anything (including a stiff breeze) can change which one you get. In particular, if you exported the node LP in LP file format (rather than SAV file format), that can make a difference. Even if you export it as a SAV file, you may work from a different starting solution in the interactive optimizer. Also, in the interactive optimizer, did you use the same algorithm (probably dual simplex) that CPLEX used at the node?

I suspect the real underlying question here is not why the solutions differ but whether you can somehow coax CPLEX to pick the integer-feasible solution when it solves the node LP during the course of solving the MIP. I don't know of any inducements you can offer, but maybe someone else does.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thanks, Paul.

Yes, if I output the node LP into SAV file format, the same continuous solutions came up.
I did not chagne default parameter for continuous optimizer in CPLEX and its iterative optimizer.
Yes, you are right. How to coax CPLEX to pick the integer-feasible solution is the import issue. But I do not how to figure it out.
For my case, the node file have multiple solutions. And the integer-feasible LP solution was also the optimal soluiton. It is strange, if CPLEX chose continuous soluiton and ignored the inteter-feasible and optimal solution at this node, my B&C would never see this optimal soluiton in the following iterations. Thus, the B&C finally reached a wrong optimal soluiton.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> shaonli wrote:
> It is strange, if CPLEX chose continuous soluiton and ignored the inteter-feasible and optimal solution at this node, my B&C would never see this optimal soluiton in the following iterations. Thus, the B&C finally reached a wrong optimal soluiton.

That sounds like a bug in your code. If CPLEX chooses the non-integer solution at the node, it should branch on the node, and one of the children will contain the integer-feasible alternate solution. Barring your hitting a time or node limit, or something else stopping the solution prematurely, it will eventually find the solution -- not necessarily immediately, but eventually.

Paul

Mathematicians are like Frenchmen: whenever you say something to them, they translate it into their own language, and at once it is something entirely different. (Goethe)
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thanks.

I track the solution course and find

At the node where the LP soluiton is also integer-feasible, no violated cut was found in the cutcallback. Then the code just went out the cutcallback and let CPLEX do by itself. Now CPLEX should do branching. I found CPLEX did not call branchcallback, but went to a new node and call cutcallback.

I do not know the reason. At other nodes in B&B tree, this case did not happen.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Continue with last response.

I encounter the same probelm in several instances.

At the node where the LP solution is also integer-feasible, the code did not call incumbentcallback, but went to to examine a new node.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

OK, trying to summarize:

• You have a node that has an integral optimal solution to its LP relaxation.
• CPLEX does not find that integral optimal solution. Instead it finds another solution (which is fractional) with the same objective function value.
• For this solution CPLEX invokes the cut callback.
• The cut callback returns eventually.
• After the cut callback returns the branch callback is not invoked for that node.

Is that correct?
Questions:

• What is the sense of your objective function (min or max)?
• What is the last objective function value you observe in the cut callback of the node in question? I.e., what does CPXgetcallbacknodeinfo(env, cbdata, wherefrom, 0, CPX_CALLBACK_INFO_NODE_OBJVAL, &obj) return in 'obj' right before you return from the callback?
• Does the cut callback add any cut?
• What is the optimal objective function value for your problem?
• What is the value that CPLEX claims to be the optimal solution?
• How do you check that the branch callback is not invoked for the node in question? Do you track the sequence number of nodes in the cut and branch callback?

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

DanielJunglas
trying to summarize
->1.You have a node that has an integral optimal solution to its LP relaxation.
Yes.

->2.CPLEX does not find that integral optimal solution. Instead it finds another solution (which is fractional) with the same objective function value.
Yes, CPLEX chose another fractional soluiton with same obj value.
->3.For this solution CPLEX invokes the cut callback.
Yes the cut callback is invoked to find violiated cuts.
->4. The cut callback returns eventually.
Yes, plese look at iteration information at node 4 in the attached file. x
->5. After the cut callback returns the branch callback is not invoked for that node.
Yes, CPLEX did not invoke branchcallback after the cutcallback at node 4. Plese refer to the attached file.
Questions:
->1. What is the sense of your objective function (min or max)?
I solved a minimization problem.

->2. What is the last objective function value you observe in the cut callback of the node in question? I.e., what does CPXgetcallbacknodeinfo(env, cbdata, wherefrom, 0, CPX_CALLBACK_INFO_NODE_OBJVAL, &obj) return in 'obj' right before you return from the callback?

Please refer to the attached file. The last objective value in the cutcallback is 2247350000 returned by CPXgetcallbacknodeobjval. CPXgetcallbacknodeinfo(env, cbdata, wherefrom, 0, CPX_CALLBACK_INFO_NODE_OBJVAL, &obj) return 'obj' with 2050748782.215820 right before I returned from the cut callback. CPXgetcallbacknodeobjval and CPXgetcallbacknodeinfo returned different node obj values. Actually CPXgetcallbacknodeinfo got same values of 2050748782.21582 at the beginning and end of the cutcallback.
At this node, I output the node file and solved it. The obj value was 2247350000.
->3.Does the cut callback add any cut?
At that node (say node 4), no cut was found.

->4.What is the optimal objective function value for your problem?
The optimal soluiton value is 2247350000.

->5.What is the value that CPLEX claims to be the optimal solution?
CPLEX calimed 2689650000 to the optimal soluiotn.

->6. How do you check that the branch callback is not invoked for the node in question? Do you track the sequence number of nodes in the cut and branch callback?
Yes, I tracked the course of soluiton. You may see from the attached file, I output some information when CPLEX invoked a callback.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I think you are misinterpreting the log here.
Cuts are separated in a loop and a cut callback may be invoked multiple times at the same node. When it is invoked with wherefrom=CPX_CALLBACK_MIP_CUT_LOOP (106) then this indicates that CPLEX is still planning to continue the cut loop. When the callback is invoked with wherefrom=CPX_CALLBACK_MIP_CUT_LAST (114) then this indicates that CPLEX is planning to stop the cut loop after the cut callback. As you can see the last invocation of the callback on a node is always with CPX_CALLBACK_MIP_CUT_LAST.
Now at node 4 the cut callback also gets invoked with wherefrom=CPX_CALLBACK_MIP_CUT_FEAS (115). This means that CPLEX found an integer feasible solution at the current node (I think it is at node 4) and wants the cut callback to validate this.
It seems to me as if you are registering your callback using CPXsetcutcallbackfunc()? This method is deprecated. Instead you should use CPXsetusercutcallbackfunc() to register a callback for cuts and CPXsetlazyconstraintcallbackfunc() to register a lazy constraint callback.
If you use CPXsetusercutcallback() then your cut callback should no longer be invoked with wherefrom=CPX_CALLBACK_MIP_CUT_FEAS and a cut callback should be followed by a branch callback, just as you expect.
If you intend to separate lazy constraints instead of cuts then you should of course use CPXsetlazyconstraintcallbackfunc().

Just to be sure, in order to get the node number in a callback you use

CPXgetcallbacknodeinfo(env, cbdata, wherefrom, 0, CPX_CALLBACK_INFO_NODE_SEQNUM, &nodenumber);

Correct?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I think you are misinterpreting the log here.
Cuts are separated in a loop and a cut callback may be invoked multiple times at the same node. When it is invoked with wherefrom=CPX_CALLBACK_MIP_CUT_LOOP (106) then this indicates that CPLEX is still planning to continue the cut loop. When the callback is invoked with wherefrom=CPX_CALLBACK_MIP_CUT_LAST (114) then this indicates that CPLEX is planning to stop the cut loop after the cut callback. As you can see the last invocation of the callback on a node is always with CPX_CALLBACK_MIP_CUT_LAST.
Now at node 4 the cut callback also gets invoked with wherefrom=CPX_CALLBACK_MIP_CUT_FEAS (115). This means that CPLEX found an integer feasible solution at the current node (I think it is at node 4) and wants the cut callback to validate this.
It seems to me as if you are registering your callback using CPXsetcutcallbackfunc()? This method is deprecated. Instead you should use CPXsetusercutcallbackfunc() to register a callback for cuts and CPXsetlazyconstraintcallbackfunc() to register a lazy constraint callback.
If you use CPXsetusercutcallback() then your cut callback should no longer be invoked with wherefrom=CPX_CALLBACK_MIP_CUT_FEAS and a cut callback should be followed by a branch callback, just as you expect.
If you intend to separate lazy constraints instead of cuts then you should of course use CPXsetlazyconstraintcallbackfunc().

Just to be sure, in order to get the node number in a callback you use

CPXgetcallbacknodeinfo(env, cbdata, wherefrom, 0, CPX_CALLBACK_INFO_NODE_SEQNUM, &nodenumber);

Correct?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thanks.

• First I have replaced CPXsetcutcallbackfunc by CPXsetusercutcallbackfunc, and used CPXgetcallbacknodeinfo(env, cbdata, wherefrom, 0, CPX_CALLBACK_INFO_NODE_SEQNUM, &nodenumber) to find the index of current node.*

I do not know why CPXgetcallbacknodeobjval (env, cbdata, wherefrom, &objval) and CPXgetcallbacknodeinfo(env,cbdata,wherefrom, 0, CPX_CALLBACK_INFO_NODE_OBJVAL, &objval) got different node objective value.
Second, response to your points.

-> Instead you should use CPXsetusercutcallbackfunc() to register a callback for cuts and ->CPXsetlazyconstraintcallbackfunc() to register a lazy constraint callback.
->If you use CPXsetusercutcallback() then your cut callback should no longer be invoked with ->wherefrom=CPX_CALLBACK_MIP_CUT_FEAS and a cut callback should be followed by a branch callback, just as -> you expect. If you intend to separate lazy constraints instead of cuts then you should of course use ->CPXsetlazyconstraintcallbackfunc().

I did not used lazy constraints in my cut.
You will see CPLEX still cannot reach the real optimal solution(Pleas refer to the attached log file).

The problems I mentioned in last response came up again.
Now please look at node 5 (previpous node 4). This node has an integral optimal solution to its LP relaxation(refer to node lp file). CPLEX did not choose this integer LP soluiton.

At this node, the cutcallback was called twice and no cut was found. Then no branchcallback was followed.
Alternatively, CPLEX went to node 6 where an integer-feasible LP soluiton was found. The incumbentcallback was invoked to accept this integer-feasible soluiton. Then branch callback was invoked at node 6 to prune this node.
But in the following interations, no branch occured at node 5.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Hm, I'm still trying to understand what is going on/wrong.
What is the value of CPX_PARAM_MIPCBREDLP? Did you change that from its default setting?
Could you also attach your original problem (the one you submit to CPXmipopt()) as SAV file here?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

I gave you a new instances.

same probem as before (look at logfile1)
(1) Node 6 has an integer-feasible soluiton to the node LP (this solution is also optimal). But CPLEX chose a continuous soluiton. At this node, a cut was found. Then CPLEX did not invoke cutcallback again and a branch callback, alternatively, it went to a new node (say node 2).

(2) Look at node 5. When a cut was found and added, then the cutback was not invoked again, and not followed by a branch callback. Alternatively, CPLEX went to a new node 6. Why?

new questions
(3) where to find documents related to exact meaning of values of returned wherefrom in the branch and incumbent callback? For example, how to know a branch callback immediately follows a cut callback or a incumbent callback? When CPLEX came to branch callback, I need to decide prune this node (followed incumbent) or do general branching?

(4) why CPXgetcallbacknodeobjval (env, cbdata, wherefrom, &objval) and CPXgetcallbacknodeinfo(env,cbdata,wherefrom, 0, CPX_CALLBACK_INFO_NODE_OBJVAL, &objval) got different node objective value.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> same probem as before (look at logfile1)
> (1) Node 6 has an integer-feasible soluiton to the node LP (this solution is also optimal). But CPLEX chose a continuous soluiton. At this node, a cut was found. Then CPLEX did not invoke cutcallback again and a branch callback, alternatively, it went to a new node (say node 2).
>
According to logfile1.txt node 6 is infeasible. This infeasibility may have been introduced by one of the local cuts that were introduced before. As you can see CPLEX uses a local cut at this node.
> (2) Look at node 5. When a cut was found and added, then the cutback was not invoked again, and not followed by a branch callback. Alternatively, CPLEX went to a new node 6. Why?
>
That is indeed weird. Could you please set the MIPDISPLAY parameter to 5 so that we can see in more detail what is going on? Maybe also add a node selection callback with code as simple as

int status; 

int seqnum = -1;   status = CPXgetcallbacknodeinfo (env, cbdata, wherefrom, 0, CPX_CALLBACK_INFO_NODE_SEQNUM, &seqnum); 

assert(status == 0); printf(
"NEXT NODE %d\n", seqnum);

so that we can explicitly see when CPLEX decides to switch to a different node.

> new questions
> (3) where to find documents related to exact meaning of values of returned wherefrom in the branch and incumbent callback? For example, how to know a branch callback immediately follows a cut callback or a incumbent callback? When CPLEX came to branch callback, I need to decide prune this node (followed incumbent) or do general branching?
>
A good source is here (and the reference documentation of course). Note that the flow chart is for an older version of CPLEX and may be slightly inaccurate (or may silently change in the future) but it should give you the general picture.
> (4) why CPXgetcallbacknodeobjval (env, cbdata, wherefrom, &objval) and CPXgetcallbacknodeinfo(env,cbdata,wherefrom, 0, CPX_CALLBACK_INFO_NODE_OBJVAL, &objval) got different node objective value.
>
They return two different things. CPXgetcallbacknodeobjval() returns the objective function value of the continuous relaxation. CPX_CALLBACK_INFO_NODE_OBJVAL returns just a valid dual bound for the node. This is badly documented and I files a bug report to rectify the documentation.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thanks. I still couldn't figure out the problem.
Could you please give me your email address so that I can send you my code?
> (2) Look at node 5. When a cut was found and added, then the cutback was not invoked again, and not followed by a branch callback. Alternatively, CPLEX went to a new node 6. Why?
> That is indeed weird. Could you please set the MIPDISPLAY parameter to 5 so that we can see in more detail what is going on? Maybe also add a node selection callback with code as simple as..... so that we can explicitly see when CPLEX decides to switch to a different node.
I have added a node selection callback. I saw the node in selected in this callback is same as the one I checked in the cut callback.
The problem came up again:
At node 7, CPLEX did not call the cut callback and then branch callback.
It just went into the node selection callback and chose 8. But then CPLEX did nothing(without invoking cut and branch callback)and chose a new node 5.
Please refer to my code.
> (3) where to find documents related to exact meaning of values of returned wherefrom in the branch and incumbent callback? For example, how to know a branch callback immediately follows a cut callback or a incumbent callback? When CPLEX came to branch callback, I need to decide prune this node (followed incumbent) or do general branching?
> A good source is here (and the reference documentation of course). Note that the flow chart is for an older version of CPLEX and may be slightly inaccurate (or may silently change in the future) but it should give you the general picture.

The material you mentioned just gave a B&C picture. Actually I want to know what the value of wherefrom (e.g., 114, 116 etc.) I got in each callback represents?
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

> Thanks. I still couldn't figure out the problem.
> Could you please give me your email address so that I can send you my code?
>
My address is daniel(dot)junglas(at)de(dot)ibm(dot)com. To avoid IP issues please don't send your full code. Just send the implementation of the callback functions without the separation code (but include the code that adds the cuts). Also include the code that registers the callback functions.

> > (3) where to find documents related to exact meaning of values of returned wherefrom in the branch and incumbent callback? For example, how to know a branch callback immediately follows a cut callback or a incumbent callback? When CPLEX came to branch callback, I need to decide prune this node (followed incumbent) or do general branching?
> > A good source is here (and the reference documentation of course). Note that the flow chart is for an older version of CPLEX and may be slightly inaccurate (or may silently change in the future) but it should give you the general picture.
>
> The material you mentioned just gave a B&C picture. Actually I want to know what the value of wherefrom (e.g., 114, 116 etc.) I got in each callback represents?
>
You can find the definition of symbolic constants in ilcplex/cpxconst.h. The names of the symbolic constants should be descriptive.
#CPLEXOptimizers
#DecisionOptimization