Where communities thrive

• Join over 1.5M+ people
• Join over 100K+ communities
• Free without limits
• Create your own community
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

• 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

• 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
Erik Hellsten
@erohe_gitlab
I get 74079 =)
Simon Spoorendonk
@spoorendonk
yeah. me too
seems like I have found 485406 also, but it branches for ever so need to check
Erik Hellsten
@erohe_gitlab
yeah, but speed is fine (maybe?). I haven't added the strong constraints, so the model is terrible. Though 01.1_12 is teeny weeny
Ok, as a reference, I solve 03.1_12 without strong constraints in 2s
Simon Spoorendonk
@spoorendonk
Think I found the bug. Fixing too many columns in master when branching so regenerating columns. 2s is my mark ...
Simon Spoorendonk
@spoorendonk
where I should be fixing nothing because it is continuous
got it :). Debug running time single-threaded = 13s
Erik Hellsten
@erohe_gitlab
alright! it is shaping up =)
tell me when it is my turn to do something again ;)
Simon Spoorendonk
@spoorendonk
yep. need to implement something that works for the integer version also
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 \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 $\lambda_p - u_p \eta_p \leq 0$ and $\sum_{P \in P^k} \eta_p \leq L$ for each commodity
Then she replaces the $\eta$ variables so the constraints above become $\sum_{p \in P} \frac {\lambda_p} {u_p} \leq L$
Erik Hellsten
@erohe_gitlab
$\sum_{P\in P^k}\eta_p\le L$, right?