Where communities thrive


  • Join over 1.5M+ people
  • Join over 100K+ communities
  • Free without limits
  • Create your own community
People
Activity
  • Oct 02 09:23

    spoorendonk on master

    Update README.md (compare)

  • Sep 21 08:57

    spoorendonk on master

    xpress example (compare)

  • Sep 08 14:46

    spoorendonk on master

    rm drawing (compare)

  • Aug 31 08:49
    spoorendonk closed #2
  • Aug 31 08:49
    spoorendonk closed #3
  • Aug 31 08:45
    spoorendonk commented #3
  • Aug 31 06:39

    spoorendonk on master

    Update vrptw_mip.py (compare)

  • Aug 29 20:32
    fuglede labeled #3
  • Aug 29 20:32
    fuglede opened #3
  • Aug 29 19:55

    spoorendonk on test-mip

    (compare)

  • Aug 29 19:54

    spoorendonk on master

    model fix and test black update test and 1 more (compare)

  • Aug 29 19:54
    spoorendonk closed #5
  • Aug 29 19:52
    spoorendonk synchronize #5
  • Aug 29 19:52

    spoorendonk on test-mip

    update test (compare)

  • Aug 29 10:08
    spoorendonk synchronize #5
  • Aug 29 10:08

    spoorendonk on test-mip

    black (compare)

  • Aug 29 10:07
    spoorendonk opened #5
  • Aug 29 10:07

    spoorendonk on test-mip

    model fix and test (compare)

  • Aug 25 09:43
    spoorendonk labeled #2
  • Aug 24 07:06
    spoorendonk labeled #2
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
Erik Hellsten
@erohe_gitlab
Ok, managed to download it. Though I didn't see the GitHub invite. Which account did you invite?
Simon Spoorendonk
@spoorendonk
@ErikOrm
Erik Hellsten
@erohe_gitlab
ok, thanks! found it
Simon Spoorendonk
@spoorendonk
does it make sense to initialize the master with some nice columns?
Erik Hellsten
@erohe_gitlab
Oh look at that! =) For the FCMCFP? I mean, I suppose, if there would be a good way to generate them. Ofc one could solve a shortest path for each commoodity and add that, but I don't think that would make any major difference. What I believe is good practice, for many problems, including the FCMCFP, is to initialise the problem with artificial rejection "slack variables" for the commodities (or for each separate subproblem in the general case), with a high cost. And then generate columns until all the slack variables are 0, meaning that we have sufficient columns to find a feasible solution to the problem. I think this is generelly more likely to find a good initial column pool than generating them straight from Farkas lemma. Don't know how big the difference is, but maybe this can be applied as a general setting, to handle problems whose master problems are infeasible with empty column pools. Maybe you already do this? Just a thought.
Simon Spoorendonk
@spoorendonk
Artificial columns to begin with is already done. It is called phase1 in the output. Phase2 is where the real cost is used. Didn’t think initialisation would make a big difference. For other problems it may make more sense
Erik Hellsten
@erohe_gitlab
sweet! Yeah, no, I would certainly believe that that would be sufficient. =)
Simon Spoorendonk
@spoorendonk
long time. I have updated to version 0.2. Not many big new things performance wise. But you can read/write instances for path mips. And you can add packing sets SS where iSxi1\sum_{i \in S} x_i \leq 1 to hint good branching decisions. Not super useful in MCF but good in routing.
Erik Hellsten
@erohe_gitlab
Hi Simon, good to hear from you! Time goes so quickly once one gets caught up in something. In the midst of a few things I'm trying to finish up right now, but hopefully I will be able to come back and write the code for the cuts soon enough. =)
Simon Spoorendonk
@spoorendonk
No problem. Maybe I will beat you to it