Forum Discussion
What is the correct syntax of the function branchobj.addrows?
I am implementing a branch-and-bound algorithm in Python using the Xpress package. In this algorithm, I create multiple child nodes with different added constraints. I use the
addcbchgbranchobject callback function to create new branching objects with their corresponding constraints. However, I am not quite sure how the function
branchobj.addrows works, as the documentation at FICO Xpress Documentation seems to be incorrect. The only example of this function is in implementing spatial branching to solve MIQCQP problems, written as bo.addrows(side, [sign], [rhs3], [0, len(ind3)], ind3, coe3). The fourth argument is particularly confusing to me, and I am not sure why we need to use [0, len(ind3)]. In my case, I have three variables x, y, and w. If I need to add a constraint of the form aw≥0 to branch i, how can I implement this code? My guess is bo.addrows(i, ['G'], [0], [0, len(w_variables_idxs)], w_variables_idxs, a), but it is not working.
Thank you
3 Replies
Hi,
Sorry about the mistake in the documentation, I will get that fixed. Your guess about the syntax is correct. Could it be that the variable you are branching on has been eliminated during presolve? You could test this by disabling presolve, by setting "problem.controls.presolve = 0". If that does not fix the problem, could you provide a complete example that shows how this is not working as you would expect?
The [0, len(ind3)] argument to addrows is to allow one side of the branch to enforce several inequalities. This array indicates where the coefficients of each inequality begin, in the rowtype, rhs, colind and rowcoef arrays. The last element in the array is a pointer past the end of the last coefficient - this is a vestige from the C API where the total number of coefficients must be explicitly specified somewhere.
Below is a complete, working example, where you should see from the "Solution at node x" log lines that the second variable has been branched on using the inequalities specified in the callback.
import xpress as xp def optnode(cbprob, data): lpsol = [] cbprob.getlpsol(lpsol) print(f'Solution at node {cbprob.attributes.currentnode}: {lpsol}') def chgbranchobject(cbprob, data, orig_branch): # Only add our custom branch at the root node if cbprob.attributes.currentnode == 1: b = xp.branchobj(cbprob) b.addbranches(2) col = 1 # index of variable 'large' coef = 1 # coefficient of 'large' in the inequalities b.addrows(0, ['L'], [20], [0, 1], [col], [coef]) # large <= 20 b.addrows(1, ['G'], [30], [0, 1], [col], [coef]) # large >= 30 return b # Small example problem, manufacturing chess sets p = xp.problem() small = p.addVariable(vartype=xp.integer) # number of small sets to manufacture large = p.addVariable(vartype=xp.integer) # number or large sets to manufacture p.addConstraint(3 * small + 2 * large <= 400) # limit on available machine time p.addConstraint(small + 3 * large <= 200) # limit on available wood p.setObjective(5 * small + 7 * large, sense=xp.maximize) # Disable presolve so that the indices of the variables are preserved p.controls.presolve = 0 # Turn off cutting and heuristics to ensure a tree search takes place p.controls.cutstrategy = 0 p.controls.heuremphasis = 0 p.addcboptnode(optnode) p.addcbchgbranchobject(chgbranchobject) p.optimize() print(p.getSolution())(My original answer stated that variable indices needed to be in the presolved space. That was incorrect: variable indices are in the original space unless you pass False to the xp.branchobj constructor. I have edited my answer to make it correct. Sorry about that.)
Another suggestion: have you tried setting the priority of your new branch object by calling e.g. bo.setpriority(100)? Branches created by the Optimizer have priority 400-500, so you should use a lower number than that to ensure that your branch object is selected.
