Where communities thrive


  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
People
Activity
  • Sep 29 2021 12:20
    ErikOrm removed as member
  • Jun 08 2021 17:45
    fhk starred flowty/flowty
  • Apr 07 2021 11:38
    spoorendonk closed #4
  • Apr 07 2021 11:38
    spoorendonk commented #4
  • Mar 31 2021 07:03

    spoorendonk on master

    vrptw time before demand (compare)

  • Mar 31 2021 06:58

    spoorendonk on master

    format (compare)

  • Mar 30 2021 16:03

    spoorendonk on use-knapsack

    (compare)

  • Mar 30 2021 16:03

    spoorendonk on master

    knapsack less output num customers from arg and 5 more (compare)

  • Mar 30 2021 16:03
    spoorendonk closed #7
  • Mar 30 2021 16:01
    spoorendonk synchronize #7
  • Mar 30 2021 16:01

    spoorendonk on use-knapsack

    update knapsack value (compare)

  • Mar 30 2021 16:01

    spoorendonk on use-knapsack

    (compare)

  • Mar 30 2021 14:45
    spoorendonk synchronize #7
  • Mar 30 2021 14:45

    spoorendonk on use-knapsack

    workflow (compare)

  • Mar 30 2021 14:41
    spoorendonk synchronize #7
  • Mar 30 2021 14:41

    spoorendonk on use-knapsack

    knapsack less output num customers from arg and 2 more (compare)

  • Mar 30 2021 13:30

    spoorendonk on master

    remove an optimize (compare)

  • Mar 30 2021 11:20
    spoorendonk synchronize #7
  • Mar 30 2021 11:20

    spoorendonk on use-knapsack

    update workflow (compare)

  • Mar 30 2021 11:09
    spoorendonk opened #7
Simon Spoorendonk
@spoorendonk
@erohe_gitlab ^
@ErikOrm ^
Erik Hellsten
@erohe_gitlab
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
Erik Hellsten
@erohe_gitlab
... 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.
Simon Spoorendonk
@spoorendonk
I believe your case with a single path is the k-splitable MCF with k=1? For k =1 it can be done by putting type='B' on the graph variables. For the general k I am not sure how to model it
Erik Hellsten
@erohe_gitlab
Hmm, that is a good question actually.
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"
Simon Spoorendonk
@spoorendonk
Erik Hellsten
@erohe_gitlab
But I don't know how that affects the subproblem structure etc. also seems a bit clumsy
Simon Spoorendonk
@spoorendonk
that is kind of of what she does and then the eta's are replaced
but it is unclear how it fits my framework when you model in edge variables
Erik Hellsten
@erohe_gitlab
shouldn't that be fine-ish? eta lives purely in the MP, and only comes as an additional flat increase in the reduced cost for new paths?
Simon Spoorendonk
@spoorendonk
as I read your proposal you have an eta per lambda, ie., a design variable per path? Then you limit the number of paths?
Erik Hellsten
@erohe_gitlab
did I misunderstand it? isn't the k-splittable MCF just that you limit the number of paths for eacdh commodity?
Simon Spoorendonk
@spoorendonk
yes
and each path can carry some flow 0λdk0 \leq \lambda \leq d^k
double $
Erik Hellsten
@erohe_gitlab
;)
Simon Spoorendonk
@spoorendonk
so a design varaible per path that you can count is the "normal" way of doing it
Erik Hellsten
@erohe_gitlab
I shall be honest and say that I don't know what the normal way is. It would work, in theory, but it might not be viable in practice. It is a lot of additional integer variables, which are painful to branch on
do we have any more elegant approaches? what does Mette do in their paper?
Simon Spoorendonk
@spoorendonk
she has λpupηp0\lambda_p - u_p \eta_p \leq 0 and PPkηpL\sum_{P \in P^k} \eta_p \leq L for each commodity
Then she replaces the η\eta variables so the constraints above become pPλpupL \sum_{p \in P} \frac {\lambda_p} {u_p} \leq L
Erik Hellsten
@erohe_gitlab
PPkηpL\sum_{P\in P^k}\eta_p\le L, right?
Simon Spoorendonk
@spoorendonk
yes
Erik Hellsten
@erohe_gitlab
ok, so she does just that. Probably means that there are no easy other way
:(
Simon Spoorendonk
@spoorendonk
up=minue,epu_p = \min_{u_e, e \in p}
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
Erik Hellsten
@erohe_gitlab
I cannot yet see the brilliance in replacing the eta-variables

hmm. I will stick with the integer flows for now. And the k=1 case

Seems reasonable = )

Simon Spoorendonk
@spoorendonk

I cannot yet see the brilliance in replacing the eta-variables

you get a lambda only problem, but it is a ralxation

Erik Hellsten
@erohe_gitlab
haha, sweet. I started writing some comments on the models you sent in the link, but it changed as I wrote ^^
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
Erik Hellsten
@erohe_gitlab
in the second model, starting with "under the hood", the first constraint is probably unnecessary, and z should be integer, not binary, right?
Simon Spoorendonk
@spoorendonk
the transit time constraints are crap in a edge formulation. The good thin with flowty is you never need to actually write them, just fill in the m.addResourceDisposable function when modelling.
Erik Hellsten
@erohe_gitlab
yeah, exactly =) the main reason I'm working with CG in the first place = )
Simon Spoorendonk
@spoorendonk
not entirely sure about the integer bounds n edges either
Erik Hellsten
@erohe_gitlab
without transit times, I feel rather certain that any solution that satisfies integrality on every edge, has an equivalen solution which satisfies integraility for every path. With transit-time constraints, it is less obvious
Simon Spoorendonk
@spoorendonk
yep change z to Z
Simon Spoorendonk
@spoorendonk
On Dantzig-Wolfe decomposition in integer programming and ways to perform branching in a branch-and-price algorithm_Vanderbeck.pdf
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
Erik Hellsten
@erohe_gitlab
I am not quite following ':D
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?
Erik Hellsten
@erohe_gitlab
I also accepted the merge request. But you have developer status in the project, right? So if you want to, also feel free to go wild and just change things as you desire.
Simon Spoorendonk
@spoorendonk
with developer status I cannot change the master branch by default. Yuo can change it in settings -> repository -> protected branches. Otherwise I just do merge reqs