Forum Discussion
Implementation of B&B with python
HI!
I'm trying to implement a branc-and-bound solver by using the python interface of Xpress.
I implemented a MINLP model, and I am trying to solve the linearization with the B&B algorithm.
Even though there is quite a huge documentation, I am facing some problems; thus I have some questions:
1 - how is the cutoff updated throughout the algorithm? is there a way to get a message every time it changes?
1b- the cutoff rises to some value which should not be possible (the MINLP finds a smaller value than the bound of the MILP). Is it possible that it comes from the fact that I refused some LP solution because some constraints of the reformulation are violated?
2 - I wanted to get the information on the solution process by setting the control MIPLOG to 3, but I get only the logs in the first node.
3 - is there a way to print the list of the active nodes (I know I can get their numbers with the attirbute ACTIVENODES, but I would like to see the list to understand better the B&B tree)?
4 - the branching decision is a specific decision after the solution score function to get the "most violated" variable (I create the branches within the callback addChangeBranchObjectCallback
). However, in some cases, even though I set the new bounds (both with bo.addbounds and with bo.addrows) the branch is not created/updated. There are several children nodes in which is performed the same branching of the parent node (i.e., the bounds generated are not considered in the children). I can share the code (since showing here the logs probably do not help), in case let me know how.
5 - I saw that the problem has the attributes BRANCHVALUE and BRANCHVAR. I tried to use them insider the addChangeBranchObjectCallback but it didn't work. Can they be used only with default branching (e.g., the Xpress one).
Some info on the version/parameters: I use Xpress 9.8, and I set PRESOLVE to 0 and THREADS to 1.
Thanks a lot if you can help me! Best regards,
Nicolò
4 Replies
Sorry, I did not receive any email from you yet. Maybe some mailer intercepts source code?
About point 5: I think the prenode callback would be a good place to check branchvar and branchval.
Dear Daniel and Imre,
thanks to both of you for the answers.
I am trying to implement a specific B&B because the problem is highly nonlinear with some very nasty constraints and the global optimizer has troubles in solving the problem.
- perfect, I will try with both the intsol and the preintsol callbacks. For the gapnotify it does not work because in my problem I do not find a a feasible (for the original problem, before linear reformulation) solution, so it never changes.
- Yes, I'm sure. If I leave MIPLOG set to -n I get output every n-th node, but setting it to 3 I get the information only on the first node. I sent you the codes, so you can see it.
- I have a procedure that tells me whether new nodes are created or nodes are closed (either optimal, infeasible or cutoff). After your answer (thanks) I added also the prenode callback, to have an info on the currently processed node. I was curious whether there was something automatic, since there is the attribute ACTIVENODES I thought it was possible to print the string of those nodes.
- I used it, and the nodes are created from the branches that I defined. I sent you the code (with some explanation) so you can check.
- Ok, thanks for the detailed answer. So in which callback should I call them to see the info on my branching? (I wanted to use them ot check the correctness of point 4)
Thanks a lot for your answer, and I hope you can help me with the codes I sent you!
Expanding on Imre's answer:
- There is no explicit way to track the cutoff. However, the cutoff should only be updated from new feasible solution, so you could look at the CURRMIPCUTOFF attribute from the intsol callback.Or you could use the cutoff passed into the preintsol callback. You could also use the gapnotify callback, that notifies about changes in the gap.
- Are you sure you processed more than one node?
- There is no way to print a list of active nodes. But you can follow the B&B process by means of different callbacks and attributes. For example, you can use a prenode callbackto get notified about new node being started. At that point it the branchvar and branchvalue should tell you the branching decision that led to this node.Or use the newnode callback to get notified about any node being created (which may be way before it is actually processed).
- Could you use the newnode callback to double check which nodes are actually created? If this does not help, can you please share your code with danieljunglas(at)fico(dot)com?
- In the change branch object callback there is no branching decision made yet. The callback only tells which branches Xpress should create, not which branch to follow next. So the branchvalue and branchvar attributes are meaningless in this context.
Hi Nicolò,
Is there any reason you aren't using the MINLP solver in Xpress? We offer both a local and a global MINLP solver. What is your specific application?
In any case, here are a few answers (my colleagues will answer the rest)?
The cutoff is updated in several ways, based on incumbents, but also the GCD in the objective coefficients, the relative gap required, etc. We don't provide a message or information about it.
We aren't providing information on the active nodes or the solution logs for all the nodes (whether in serial or parallel mode).
The branching attributes are to be queried after the branching decision has been taken. If I understand you correctly you are trying to make the decision yourself. Note that these are attributes and not controls.
