Originally posted by: SystemAdmin

Hi,

In the branch and bound tree, at each node, is it possible to know which variables have been valued so far and what are their values (for that specific branch) and also which variables are to branch at the current node.
Could some one please tell me what to do? (in C++ concert tech.)

Cheers,
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

I think you can tell which variables are fixed, either explicitly or implicitly, by grabbing the upper and lower bounds of the integer variables (in a callback) and checking which ones have lower bound equal to upper bound.

In a branch callback, you can ask CPLEX how it is planning to branch (and then you can let it have its way by doing no branching yourself in the callback).

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)
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

Thanks Paul. I think I get it. Very naive question from me. I think I always can use getValue to see if a variable is set to 0 or 1!

Cheers.
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

Yes, getValue() will give you the value of that variable in the current solution at the current node.
Note that there are several threads in this Forum that show how to use a BranchCallback to keep track of the branching decisions that CPLEX made. You may find them helpful.
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

Thanks.
I looked for my original problem (mentioned below) in the forum but I could not find any relevant solution.
My question: I want to add another criterion to pruning roles (in addition the lower bound).
Meaning that if by the lower bound it is OK to carry on a branch but by my new criterion it is not OK, I want to prune that node.
How can I do it?
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: chintasunny

Apart from lower bounds, you can think of coming up with dominance rules to prune nodes. Depending upon your problem structure, there will be some way to come up with such rules. Dominance rules were widely employed in B&B methods for Machine scheduling, Vehicle routing, etc
You can refer to some of those papers.
Thanks
Sunil
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

Thanks Sunil for your. I was wondering if you could introduce me some papers on the dominance rules.

Also, in terms of implementation in CPLEX (C++), how can I introduce new criterion (in addition to the lower bound) that can be performed as I described in my previous question? (if by the lower bound it is OK to carry on a branch but by my new criterion it is not OK, I want to prune that node.)

Cheers,
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: chintasunny

You can start looking at the paper "A Branch-and-Bound Procedure to Minimize Total Tardiness on One Machine with Arbitrary Release Dates" by Philippe Baptiste, et al. It also talks about several other papers that employed dominance rules. All these papers talk about dominance rules in customized branch & bound methods (i.e. these branch & bound methods do not employ Math. formulations or CPLEX to solve the problem in hand).
You may be employing CPLEX to solve the problem. But depending on problem structure and the way you are employing cplex to solve your problem, there may or may not be a possibility of employing dominance rules
By the way, what is the problem that you are attempting to solve and how you are employing CPLEX?

Thanks
Sunil
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

Thanks for your responses and also the paper.
It is a general IP problem I am working on.
Let assume that we have a simple problem Max{x_1+3x_2: 2x_1+x_2<=2 and -x_1+2x_2<=1 and x_1,x_2\in {0,1}}
If in BranchCallback, we just write "prune();". it means that it prunes every branch. So it terms of IP solutions, should it give a infeasible message?
I tried it. Cplex solves it as if I have not invoked prune() to its IP solution. An I right?
My question is what I should do to prune a node completely.
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

Thanks for your responses and also the paper.
It is a general IP problem I am working on.
Let assume that we have a simple problem Max{x_1+3x_2: 2x_1+x_2<=2 and -x_1+2x_2<=1 and x_1,x_2\in {0,1}}
If in BranchCallback, we just write "prune();". it means that it prunes every branch. So it terms of IP solutions, should it give a infeasible message?
I tried it. Cplex solves it as if I have not invoked prune() to its IP solution. Am I right?
My question is what I should do to prune a node completely.
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

Can you show us a log file of such a solve?
Just writing prune() in a branch callback will prune every node. However, if CPLEX already solves the problem at the root node then this will have no effect as the branch callback is never called in this case.
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

Here is the log file for the default setting:
IBM ILOG License Manager: "IBM ILOG Optimization Suite for Academic Initiative" is accessing CPLEX 12 with option(s): "e m b q ".
Tried aggregator 1 time.
MIP Presolve eliminated 2 rows and 3 columns.
MIP Presolve modified 4 coefficients.
All rows and columns eliminated.
Presolve time = 0.00 sec.
Solution value = 1

and this is the logfile when every node is pruned ("ILOBRANCHCALLBACK1(MyBranch) {prune();} ")

IBM ILOG License Manager: "IBM ILOG Optimization Suite for Academic Initiative" is accessing CPLEX 12 with option(s): "e m b q ".
Tried aggregator 1 time.
MIP Presolve eliminated 2 rows and 2 columns.
MIP Presolve modified 6 coefficients.
Reduced MIP has 0 rows, 1 columns, and 0 nonzeros.
Reduced MIP has 1 binaries, 0 generals, 0 SOSs, and 0 indicators.
Probing time = 0.00 sec.
Tried aggregator 1 time.
Presolve time = 0.00 sec.
Probing time = 0.00 sec.
MIP emphasis: balance optimality and feasibility.
MIP search method: traditional branch-and-cut.
Parallel mode: none, using 1 thread.
Root relaxation solution time = 0.00 sec.

Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap Variable B NodeID Parent Depth

• 0+ 0 1.0000 0 ---

0 0 cutoff 1.0000 1.0000 0 0.00%

Root node processing (before b&c):
Real time = 0.00
Sequential b&c:
Real time = 0.00

---

Total (root+branch&cut) = 0.00 sec.
Solution value = 1

In this simple example, does CPLEX solve the problem in the root node?
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

In either case CPLEX solves the problem at the root node. The problem is so simple that CPLEX does not even need to branch. Hence the branch callback is never invoked. If you want to see the branch callback in action you need to use a more difficult problem that is not solved at the root node.
#DecisionOptimization
#MathematicalProgramming-General

Originally posted by: SystemAdmin

If you are asking how to prune a node, you can invoke the prune() method in a branch callback.

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)
#DecisionOptimization
#MathematicalProgramming-General