Where communities thrive


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

    spoorendonk on master

    vrptw time before demand (compare)

  • Mar 31 06:58

    spoorendonk on master

    format (compare)

  • Mar 30 16:03

    spoorendonk on use-knapsack

    (compare)

  • Mar 30 16:03

    spoorendonk on master

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

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

    spoorendonk on use-knapsack

    update knapsack value (compare)

  • Mar 30 16:01

    spoorendonk on use-knapsack

    (compare)

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

    spoorendonk on use-knapsack

    workflow (compare)

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

    spoorendonk on use-knapsack

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

  • Mar 30 13:30

    spoorendonk on master

    remove an optimize (compare)

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

    spoorendonk on use-knapsack

    update workflow (compare)

  • Mar 30 11:09
    spoorendonk opened #7
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 dkd^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 dkd^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 λkpZ[0,dk]\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 λZ \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 kKxijkyij\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
Erik Hellsten
@erohe_gitlab
I'm looking forward to see it =)
Simon Spoorendonk
@spoorendonk
me too :)
Simon Spoorendonk
@spoorendonk

tt_r10.1_12.csv

objval: 200126.99999999336

real 0m15.888s
user 4m6.219s
sys 0m4.533s

@erohe_gitlab ^
Simon Spoorendonk
@spoorendonk

Ok. The big one is hard

Process Node 514 (algo = PRICE_AND_CUT, phaseLast = PHASE_CUT) gLB = 56379.5 gUB = 59044 gap = 0.04726 time = 861.580

5 % after 15 min

tt_r18.1_12.csv

objval: 372254.0000000172

real 1m14.640s
user 15m30.381s
sys 0m10.323s

60 seconds without std::out
Simon Spoorendonk
@spoorendonk
On strong inequalities. Are we not talking xijkyijx_{ij}^k \leq y_{ij}
Simon Spoorendonk
@spoorendonk
and xijkdkyijx_{ij}^k \leq d^k y_{ij} for the other model
Simon Spoorendonk
@spoorendonk

with and without cuts in 06 example

Alps0208I Search completed.
Alps0261I Best solution found had quality 250351 and was found at depth 32
Alps0265I Number of nodes fully processed: 20
Alps0266I Number of nodes partially processed: 15
Alps0267I Number of nodes branched: 17
Alps0268I Number of nodes pruned before processing: 0
Alps0270I Number of nodes left: 0
Alps0272I Tree depth: 7
Alps0274I Search CPU time: 143.07 seconds
Alps0278I Search wall-clock time: 83.62 seconds

================ DECOMP Statistics [BEGIN]: ===============
Total Decomp = 83.60 100.00 35 3.51
Total Solve Relax = 0.00 0.00 0 0.00
Total Solve Relax App = 0.00 0.00 0 0.00
Total Solution Update = 0.79 0.94 109 0.05
Total Generate Cuts = 72.43 86.63 48 1.59
Total Generate Vars = 6.59 7.88 82 0.10
Total Compress Cols = 0.04 0.05 14 0.01
================ DECOMP Statistics [END ]: ===============

Node 32 process stopping on bound. This LB= 250366 Global UB= 250351.

Alps0208I Search completed.
Alps0261I Best solution found had quality 250351 and was found at depth 30
Alps0265I Number of nodes fully processed: 18
Alps0266I Number of nodes partially processed: 15
Alps0267I Number of nodes branched: 16
Alps0268I Number of nodes pruned before processing: 0
Alps0270I Number of nodes left: 0
Alps0272I Tree depth: 7
Alps0274I Search CPU time: 48.34 seconds
Alps0278I Search wall-clock time: 3.56 seconds

================ DECOMP Statistics [BEGIN]: ===============
Total Decomp = 3.54 100.00 33 0.31
Total Solve Relax = 0.00 0.00 0 0.00
Total Solve Relax App = 0.00 0.00 0 0.00
Total Solution Update = 0.86 24.17 134 0.05
Total Generate Cuts = 0.00 0.00 49 0.00
Total Generate Vars = 0.66 18.52 97 0.01
Total Compress Cols = 0.06 1.70 21 0.00
================ DECOMP Statistics [END ]: ===============

room for improvement
wonder why the pricing became so hard
Simon Spoorendonk
@spoorendonk

tt_r18.1_12.csv

objval: 372254.0000000172

real 1m14.640s
user 15m30.381s
sys 0m10.323s

Erik Hellsten
@erohe_gitlab
Hi!
I pushed some intital results for the smaller instances. Still need to run some of the bigger ones but I'll do it tonight.