sorry for spamming you :)
@erohe_gitlab ^
@ErikOrm ^
Hey! Ehm, hmm. I should first say that for my purposes, integer demand is not that interesting, it is more for the generality of your framework. We could say that that integrality comes in three tiers. The top tier, which is what generally tak about when I talk about integer flows, is that each commodity has to follow a single path. This is generally modelled using binary flow variables (which means that we have to multiply with the amount everywhere, as cost etc. is in $/unit.) So basically, we would just replace the continuous lambda variables with binary ones, and then we'll have to change our branching strategy a bit as branching only on design variables is no longer sufficient. The second tier, is (I believe) less common, and that is the one you are talking about. Here the flows have take integer values. So if a commodity contains 7 units, we can send 3 along one path and 4 along another, but not 3.5 and 3.5. This is of course intuitively interesting, as containers and such are technically integer, but in most applications, the loss in just treating them as continuous is very small when each commodity contains many units, which is most often the case. This is normally modelled with integer flow variables lambda_kp in {0, Q_k}, where Q_k is the number of units in commodity k. And then, yes, naturally we remove the multiplication by Q_k, as we have now rescaled the variable. Solving the subproblem, for both of those models is the same as when using continuous flow, except that we can preprocess and remove arcs with insufficient capacitiy
... to flow all/a single unit, for the two models respectively. Then we just deal with integrality through branching in the master problem. It is probably not great to branch on the lambda variables immediately, so I suppose one would start with branching on arc commodity pairs, which I think won't affect the subproblem structure. The last tier is just the continuous flow we normally talk about.
I suppose you can model it by adding a binary opening-variable eta, in the master problem, for each commodity, with the constraints "sum(eta) <= k" and "lambda<= eta"
I talked to mette gamst about it https://backend.orbit.dtu.dk/ws/portalfiles/portal/6418543/Mette_Gamst_article.pdf
but it is unclear how it fits my framework when you model in edge variables
and each path can carry some flow
double $
do we have any more elegant approaches? what does Mette do in their paper?
:(
probably not. Replacing the constraints is a relaxation of the original k-splittalbe problem. Then you need to do some fancy branching to get a valid IP solution
hmm. I will stick with the integer flows for now. And the k=1 case
hmm. I will stick with the integer flows for now. And the k=1 case
Seems reasonable = )
The first model seems fine. Though it is very hard to write the transit time constraints for the edge formulation. I'm also a bit curious to whether limiting the flow on each arc for a commodity to be integer, is strictly identical to limiting the flow on each path to be integer. It is easy to find a counter-example, but I could be that they have the same space of optimal solutions
so for an integer variable in subproblem you always get {0,1} lambdas, however if discretize the suproblem and introduce identical suproblems with binary variables you get integer lambdas
for continuous you can do the same with [0,1] intervals (assuming your variable ub is integer)
I think...
that would be how you end up in model 2
what counts as an integer variable in the subproblem? For us the subproblems are RCSPPs, so they are always integer, no? but that doesn't meant that lambda naturally becomes integer, right?