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

Questions:

For you to be able to debug your model how important is

  • being able to read/write models
  • get some output while running the model (what output?)
Simon Spoorendonk
@spoorendonk
try pip install --index-url https://test.pypi.org/simple/ --no-deps --upgrade flowty
Erik Hellsten
@erohe_gitlab
It works! =D for the continuous flow at least. For integer flow it seems to get stuck. I suppose you could get a reasonable performance increase if you'd manage to turn off some of the prints.
Erik Hellsten
@erohe_gitlab
Hmm, that is a good question actually. I export the model, somewhat often, to make sure that it looks like it supposed to, when cplex does something unexpected. But I think it comes down to personal taste. And regarding the output, it depends on what error you run into. I suppose at least some basic info would be sweet - where does the error occur (in branching, in the subproblem, in solving the master problem, in separating a cut..), if it is in the subproblem, I would want to query the currently generated columns, the values of the variables in the latest solution to the MP, the dual values, and preferably the reduced costs, some rudimentary information about the branching tree, number of open nodes, LB, UB etc.. But in the end, I suppose there are a million things once one gets down in the nitty gritty details. I suppose less would be required in your framework, cause the user wouldn't have to deal with Farkas Certificates etc themselves but that would just work below the surface.
Simon Spoorendonk
@spoorendonk
Just to make sure about integer flow. In that case you would expect the lambda variables to be integer not continuous? Hence not multiply with the demand in cost, obj and capacity constraints and have rhs of demand in demand constraints?
Lambda = columns
Simon Spoorendonk
@spoorendonk
I am actually not sure how to model integer flows. Perhaps a graph with U = demand and then integer var type on the edges? That would be kind of intuitive
Simon Spoorendonk
@spoorendonk
i did a merge request to your repo erohe/ttcfcmcf_erik!1
I needed to rename the file because of circular dependencies. Added some cross platform paths
Simon Spoorendonk
@spoorendonk
right now we are solving model 1 with cont flows. I guess we want to goto model 2. Can you have a look at my modelling of integer flows in model 1. Does it make sense
modelling in 5 lines of code :)
Simon Spoorendonk
@spoorendonk
I am battling a little with the mapping of the model into a general MIP. I am thinking that in general you would be able to map a fractional model into a time discretized model so to take care of the transit time constraints and similar path resource? For integer flows probably the same. For binary flows one can use MTZ like constraints on the resources to ensure feasibility on path (not sure about non-disposable resource, ie., hard time windows but I think so). Comments?
I am thinking to do this under the hood and only ever expose the edge variables in the graph as you would expect for the path MIP. It would be quite inefficient for the MIP as-is but it can be improved later one and would serve as a solution checker for small examples
sorry for spamming you :)
@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