Against all common sense I attempted (a special type of) branch-and-price. How am I shooting myself in the foot, exactly?
進行中
I know that Gurobi does not support branch-and-price via its API. You cannot add new variables during the exploration of the B&B tree. However, against all common sense, I attempted a very special case of branch-and-price, and apparently, it's doing something. With this question, I would like to know if I am correctly abusing Gurobi's API.
In my very special case, I have two types of variables: a few integer ones, which I want Gurobi to branch on (and I add all of them from the beginning) and many more continuous ones, which I want to add via column generation. Columns added in one tree node are valid in any tree node.
My original problem looks like this (\(y\) are the exponentially many variables):
\[\begin{align} \max c^\top y \\ Ax + By \leq r \\ x \text{ integer} \\ y \text{ binary} \end{align}\]
What I used to do, in compliance with all the rules of the optimisation gods, was to:
- Solve the continuous relaxation of my problem (\(x \geq 0, \; y \geq 0\)) via column generation, thus obtaining a dual bound UB.
- Once solved, change all variables to integer/binary and solve with the columns \(y\) added during column generation. This is usually called a restricted master heuristic and provides a primal bound LB.
Now this idea came to my mind: what if I can tighten UB by solving an "intermediate" relaxation of the problem with \(x \text{ integer}\) and \(y \geq 0\)? And then another disturbing thought popped up from the deepest recesses of the unconscious: what if I could do this without writing a single line of code to manage the B&B tree?
If you are sensitive about users abusing APIs, stop reading here because what I did truly is unholy.
- I set the \(x\) variables to \(\texttt{GRB_INTEGER}\).
- I start solving this problem with Gurobi's MIP solver.
- I add a callback which acts on \(\texttt{MIPNODE}\). I hope it gets called every time the LP relaxation is solved at a tree node.
- When \(\texttt{MIPNODE_STATUS}\) is \(\texttt{OPTIMAL}\), I get the value of the continuous relaxation via \(\texttt{MIPNODE_REL}\).
- I solve a "shadow" copy of the model with all variables fixed to the values I get from \(\texttt{MIPNODE_REL}\). This way, I get the dual variables associated with the constraints where \(y\) appears.
- I solve the pricing subproblem and price new \(y\) variables.
- I add these new variables calling \(\texttt{model.addVar}\). This raises a \(\texttt{GRBException}\), but I ignore it. (It hurts, I know.)
- It turns out that, despite the exception, the variables are actually added to the model!
- I am not sure that the continuous relaxation at the given tree node would now be solved again (to continue with my homemade column generation algorithm). Therefore, I call \(\texttt{addLazy}\) with a trivially true valid constraint (each time a different one). My idea is that adding a cut should trigger a reoptimisation of the LP relaxation at that node... otherwise, how would one implement Branch-And-Cut?
If you have read up to this point without fainting, congratulations! Now, my question: is there any chance that what I am doing in 1-9 is implementing the "branch-and-price" algorithm I wanted? Is there an easier way to obtain the same result?
I am open to insults and suggestions alike.
-
正式なコメント
You are adding variables with model.addVar() from within your callback? This just cannot work. What you have in your hand as a user is the original user model. But the branch-and-cut is performend on a different model, namely the presolved model. Moreover, the LP relaxation is yet another model. Even if you could modify the user model from within your callback, there is nothing in Gurobi's source code that would then transfer the changes to the presolved model and to the LP relaxation.
I would claim that the model.addVar() call is just doing nothing (except raising the exception). How do you see that the variables are added to the model (your point 8)?
Regards,
Tobias
-
Hi Tobias.
First of all, thanks for replying and the explanation. I was checking point 8. from calling \(\texttt{model.write()}\) at the end, but then I must have been mistaken.
So, just to be clear: there is no way (hacky or legitimate) to add a variable to a model once it's being solved, even if this variable is continuous and valid in all nodes of the tree, right? Even if I add a callback, copy the model, fix the variables, get the duals and solve a pricing subproblem, then I have absolutely no way to insert the resulting column back into the model while it is solved, right? If I were to abort the optimisation, add the column, and call \(\texttt{optimize()}\) again, would I lose all information about the B&B tree generated up to that point?
0
サインインしてコメントを残してください。
コメント
2件のコメント