Flowty/community

https://flowty.ai https://docs.flowty.ai

Erik Hellsten

@erohe_gitlab

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

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

Erik Hellsten

@erohe_gitlab

oh, ok. Well, that should do it. =)

Simon Spoorendonk

@spoorendonk

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
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?

in relation to the above. If edge flow variables are integers in can ultimately result in integer path variables.

so the RCSPP can be seen as solving a discretized version with binary flows for

d^k

identical subproblems, and thereby result in integer path variables

Erik Hellsten

@erohe_gitlab

But all "paths" are already integer in all of our models. The question is just regarding the integrality of the lambda flow-decision variables. And of course, we could split our lambda into

d^k

binary variables, but that would just introduce unnecessary symmetry issuses, wouldn't it? We would still need to relax those binary variables in the CG framework and branch to make them take integer variables. It would work equally well to just have

\lambda_{kp}\in \mathcal{Z}\cup[0, d^k]

Simon Spoorendonk

@spoorendonk

I think I get what you are saying. Setting integer on the edge variables does not guarantee a path but only integer flow. To have integer flow on paths one would need to solve a path problem per unit flow and add them up (the discretization wth identical subproblem approach). When the identical subproblems are aggregated that is when symmetry is disappears. Due to aggregation we have

\lambda \in \mathbb{Z}

Modelling this with type="I" is maybe not super clear

Erik Hellsten

@erohe_gitlab

Yeah, something like that. I'm still a little confused, it feels like we talk a little about different things, but seems fair enough. If you want, we could have a call sometime, and discuss it further.

Erik Hellsten

@erohe_gitlab

I also added the strong constraints to the model. The next step would be to se if we can add them dynamically with some sort of callback =)

Simon Spoorendonk

@spoorendonk

Yeah, something like that. I'm still a little confused, it feels like we talk a little about different things, but seems fair enough. If you want, we could have a call sometime, and discuss it further.

I think you are right :). A call next week maube

I also added the strong constraints to the model. The next step would be to se if we can add them dynamically with some sort of callback =)

working on it, got could up in some multi threading for solving subproblems in parallel

Erik Hellsten

@erohe_gitlab

Sweet! =D

Simon Spoorendonk

@spoorendonk

hmm, got it working with cont flows in domain [0,d^k] but for integer flows (not k-splitable) the branching is off. It is a bigger rewrite so shelved for now

Erik Hellsten

@erohe_gitlab

ok, cool! =)

Simon Spoorendonk

@spoorendonk

what are the constraints you add in the ttfcmcf?

the user cuts

^ @erohe_gitlab

Erik Hellsten

@erohe_gitlab

The first set of user cuts are the so called strong constraints of the form

\sum_{k\in K}x_{ij}^k \le y_{ij}

, separated by inspection. The next are the lifted cover inequalities (though maybe the framwork already does that?)

Simon Spoorendonk

@spoorendonk

I will try and add the strong constraints in my test. Then I will look at what cuts I can get the framework to separate

found another branching bug to fix first though ...

Erik Hellsten

@erohe_gitlab

hehe, I know the feeling. Finding bugs seems to be a dominant part of my life at the moment..

but ok, yeah, whenever I could be of any help, you just say so =)

Simon Spoorendonk

@spoorendonk

and it just continues. Maybe that is why people become managers at some point!

Erik Hellsten

@erohe_gitlab

Yeah, I suppose ^^

Or professors

Simon Spoorendonk

@spoorendonk

same same

Erik Hellsten

@erohe_gitlab

yeah, I suppose so

Simon Spoorendonk

@spoorendonk

but ok, yeah, whenever I could be of any help, you just say so =)

I don't know how much time you have on your hands? And what kind of help you would find interesting?
Setting up models to expose stuff that does/doesn't work helps me a lot - like the ttfcmcf. In that direction I am locking into https://github.com/GregorCH/ipet to thoroughly test and track running times.

It could also go deeper into the c++ if you feel really confident!

It could also go deeper into the c++ if you feel really confident!

in digging in my well documented codebase...

Erik Hellsten

@erohe_gitlab

It would of course be interesting, and maybe (hopefully) one day I'll have time for that, but for now I already have 3 projects in queue somehow, and I have a tendency to dig myself deep in, once I begin with something. So for now I'll wait a bit with having a look at the c++ code =) But I would be happy to write a cover inequality separator in the python interface once you have the user cut-interface running, for example.

Simon Spoorendonk

@spoorendonk

:+1:

Simon Spoorendonk

@spoorendonk

I am thinking this would make ok sense

def callback(cb: CallbackModel, where: Where):
    if where == Where.PathMipCuts:
        relax = cb.relaxation

        for y in y_vars:
            e = (arcs[y.id].start, arcs[y.id].end)            
            xEdges = [x for k in range(k) for x in x_vars[k] if x.edge = e]
            xksum = sum([relax[x.id] for x in xEdges])

            if xksum > relax[y.id]:
                cb.addCut(xsum([ 1*x for x in xEdges]) <= y)

Erik Hellsten

@erohe_gitlab

Yeah, it seems great =) you want a capital K in "range(k)" on line 7. Maybe you want an error margin, and only add the cut if xksum > y +

\epsilon

? These programs tend to have some minor precision issues (just so you don't add a cut which is already in the model).

Simon Spoorendonk

@spoorendonk

:+1: I will see if I can get it ready for the presentation tomorrow. It's gonna be close

Where communities thrive

People

Repo info

Activity