scipopt
The workable and reproducible examples of using column generation (branch & price) via PySCIPopt
Dear support team,
I would like to know if, there exists any workable and executable example that uses column generation, specifically branch&price, to solve a MILP? (As far as I know, there exists an unfinished example, but it contained some issues and did not work properly. I am not aware of if the support team could fix that).
All the best Abbas
Hello, @abb-omidi!
You can try looking at test_pricer.py. It's a test, not an example, so you'll have some assertions there. For branch-and-price, you would then need to add a branching rule yourself. @mmghannam is working on a tutorial video for branch-and-price, so your question came at the right time :) The video will still take some time, but it should be helpful.
The unfinished examples is really something we need to take a look into because most problems seem to be easy fixes. I just need to get around to doing it.
Dear @Joao-Dionisio,
Thank you so much for your comments. It would be great if we could see a tutorial video for branch-and-price by PySCIPopt. Please. inform us when it will be published.
Best wishes Abbas
Hey @abb-omidi. This is still a work in progress, but me and @mmghannam (mostly Mo) worked on solving bin-packing via Branch and Price on Saturday. We'll probably record the video next week, in the meantime you can see the code here: repo-link.
We think it's working, but please do make sure that the results are correct. The relevant file is bnp.py (and then the pricer, branching rule, and event handler). For generating the instances you can look at generator, and the compact formulation is in compact.py.
Dear @Joao-Dionisio,
Thank you so much for your prompt response. I definitely will see that and get back to you.
All the best
Dear @Joao-Dionisio,
I can run the provided model without throwing an error. Also, as $\text{BP}$ is new to me, before digging into the code, I need to check and ask some sort of questions regarding DW reformulation as well as the column generation algorithm and will get back to you. Also, for ease of use let me add questions in this issue.
Regards
Dear support team,
I have some issues distinguishing how to select the variables and also convexifing those in the context of D-W reformulation. Let me explain more:
In a one-dimensional cutting stock problem, as its mechanism is very similar to a bin-packing problem, the variable $x_{i,k}$, in the Kantrovich model, is declared of the number of items final of width $w_{i}$ is cut in roll $k$. For that, we need to introduce the variable $\lambda_{k}^p$, where the set $p$ defines the extreme points of the original solution space. Now, by substituting the variable $x_{i,k}$ by whose reformulated parameter, $a_{i,k}^p$, to capture the added columns coefficients, we can rewrite the demand constraint as, ($\sum_k \sum_p a_{i,k}^p \lambda_{k}^p \geq r_i \ , \forall i$).
A trick that was used here is to transform the variable $y_{k}$ based on the variable $\lambda_{k}^p$. As far as I know, when the width of master rolls, $W$, are the same we can aggregate ($\sum_{p} \sum_{k} \lambda_{k}^p = \sum_{p} \lambda_{}^p$). Also, as long as we minimize the original and already the master problems we can ommit the convexity constraint. Now, my questions are:
-
Why do we select the variable $x_{i,k}$ and why not go ahead with the variable $y_{k}$?
-
How actually may the variable $y_{k}$ be interpreted by the variable $\lambda_{k}^p$? ($y_{k}$ is a binary while $\lambda_{k}^p$ is a general integer. Also, $\lambda_{k}^p$ is used to select the number of a specific feasible pattern that came from the sub-problem. I am a bit confused to understand the idea!).
-
In order to define the convexifing variable $\lambda_{k}^p$ , why do we select index $k$ instead of index $i$? Is it correct to select an index we ask to decompose the problem based on it? (e.g. if we have a variable $s_{i,j,k}$ in the constraint of the form ($\sum_{j,k} s_{i,j,k} \leq c_{i}, \ \forall i$), and would like to decompose the problem w.r.t the index $i$, should we declare the convexifing variable as $a_{i,j,k}^p \lambda_{i}^p$ and rewrite the constraint as $\sum_{p} \sum_{j,k} a_{i,j,k}^p \lambda_{i}^p \leq c_{i}, \ \forall i$?)
-
Can the mentioned trick for aggregating the variables be applied in all the cases as long as we have the same resources like identical machines, stations, vehicles, etc.?
I am looking forward to hearing from you (Also, if you need more info please, let me know) Regards
Hey @abb-omidi! I'm very sorry, but we feel like these more theoretical questions don't really fit the repo (unless it's something small, of course). We would prefer the content here to be more PySCIPOpt-specific.
Would you mind posting these questions on OR SE? I'd gladly try to answer them over there :) This has the added benefit of reaching a wider audience, which might be more interested in this.
Dear @Joao-Dionisio,
Thanks for your attention. In many cases, I cannot get/see the proper answer for these kinds of questions in OR.SE, but I will try that ASAP. Do you think is it possible to send that on the SCIP mailing list?
Regards
Hey @abb-omidi, I'm sorry, I completely missed that you asked a question in your comment. You can send it, yeah, maybe someone will have an extra spare time.
Dear @Joao-Dionisio,
Many thanks for your comments. I could resolve my above questions and many parts of my current missing puzzle are found.
To fully understand the code as well as play around with that, I need to learn more advanced skills to use the hidden DNA of the SCIP regarding branch & bound, Ryan-Foster branching, pricer mechanism, etc.
I will manage to ask some related questions still w.r.t your comment: We would prefer the content here to be more PySCIPOpt-specific..
All the best
@abb-omidi next week at ZIB (where SCIP is primarily developed) the CO@Work Summer School will start. On the 19th (Thursday), Mo and I will give a tutorial on Branch-and-Price. I think there might have been an option to attend online (don't know if that's still available), but the contents of the tutorial will be available for future consultation.
We won't be going super deep into the mechanism of SCIP, but maybe it can still be helpful for you.
Dear @Joao-Dionisio,
Thank you so much for your informative comments and help.
Abbas