2
$\begingroup$

Assume we are given MILP where $y \in (\mathbb{R}^+)^n$, $x_1, x_2 \in \{0, 1\}$ are the integer variables. It is obvious that this problem when solved via branch and bound has a 2 deep b&b-tree.

For the sake of notation let $\min_{(0,1),(0,1)}$ be the minimum of relaxation at the root node and $\arg\min_{(0,1),(0,1)}$ the corresponding minimizer (which assumed not be integer). $\min_{1,(0,1)}$ would be the minimum of the relaxation at b&b tree node where $x_1$ is set to 1 and no decision has been made about $x_2$.

Now to the question:

Given $\min_{(0,1),(0,1)}$, $\arg\min_{(0,1),(0,1)}$, $\min_{0,(0,1)}$, $\arg\min_{0,(0,1)}$, $\min_{1,(0,1)}$, $\arg\min_{1,(0,1)}$ what does that tell me about $\min_{(0,1),0}$, $\arg\min_{(0,1),0}$, $\min_{(0,1),1}$ or $\arg\min_{(0,1),1}$ beside $\min_{(0,1),(0,1)} \leq \min_{(0,1),0}$ and $\min_{(0,1),(0,1)} \leq \min_{(0,1),1}$?

Or with a picture of directed acyclic graph that contains all search trees of this 2 level deep tree. Does having calculate the relaxations of all red encircled nodes tell me more about the possible values the yellow encircled nodes then the orange encircled root node tells me about the relaxation yellow encircled nodes

enter image description here

And if that tells me something useful:

I have solved a MILP (of integer variables) and saved the search tree and nodes with their $\min$ and $\arg\min$ and I want resolve the same MILP using different branching heuristics to compare such heuristics. Can I do better with saving calculation time then looking up whether I solved this node in the previous solve, if so use the cached results and if not calculate the relaxation normally?

(It might be that even if nothing in general holds, under separability in the problem one might be able to infer the value of the relaxation at some B&B nodes. If you know of such results they are welcome too)

$\endgroup$
4
  • $\begingroup$ Is there any specific reason to illustrate the $B\text{&} B$ tree as you described? Many of the MILP solvers represents this in the meaningful scheme. AFAIK, some of the special software has been developed to show that what you want for any investigating? (E.g. vbctool). $\endgroup$
    – A.Omidi
    Aug 28 at 6:47
  • $\begingroup$ @A.Omidi I don't quiet understand what you are asking for me. Do you want me to illustrate the B&B trees instead of the notation i choose? I don't think that will add value as it should be quiet obvious what i am doing. Given i branched both ways on the first variable does that tell me more about what would have happened if i branched on the second variable instead then i already knew when relaxing the root node ? $\endgroup$ Aug 28 at 8:18
  • $\begingroup$ Would you see this link? What I proposed is the symbol you mentioned is a bit complicated, specifically, when the size of the B&B tree is being large. The standard schematic which can be seen in the standard MILP solvers is a suitable way to do that. $\endgroup$
    – A.Omidi
    Aug 28 at 8:31
  • $\begingroup$ @A.Omidi I saw this link before and failed to see how this software a) is worth learning for a two level deep tree and b) is able to represent node specific information as none of example pictures i found did that. I hope this illustration will help you. I didn't consider creating an illustration at first because i have no problem imagining such a shallow tree. $\endgroup$ Aug 28 at 11:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.