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
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.
Simon Spoorendonk
@spoorendonk
Cool. Awesome
Simon Spoorendonk
@spoorendonk
are your results single threaded? Just for comparison
and they are with the strong flow inequalities right?
Erik Hellsten
@erohe_gitlab
they are with dynamic strong inequalities, yes =)
ehm, yeah. more or less at least. I solve almost everything single core, except for when I solve the integer problem with the root node columns to generate an intial upper bound, which I by some reason solve with 4 cores. But that makes up but a sliver of the runtime, so don't think that would have any major impact
Simon Spoorendonk
@spoorendonk
need to do some optimizations I can see :)
Erik Hellsten
@erohe_gitlab
You bloody better don't beat me ;) I've spent too much time on this ^^
Simon Spoorendonk
@spoorendonk
Me too 😀
Simon Spoorendonk
@spoorendonk
boom. No optimizations yet. But now I can do callbacks to initialization, solution feasibility check, primal heuristic, and your very own pricing algorithm. Some docs and then a new version comming up
Erik Hellsten
@erohe_gitlab
Sweet As! The development of tomorrow is underway =) Good to hear!
Simon Spoorendonk
@spoorendonk
moved to github now. They support build on windows. Added you to my example project to see callback (and other) functionality. New version is available with the callbacks