[WizardsBlade]

just to make sure I am looking at the br17.atsp and it apears that 9999 means distance to itsself, and 0 means no path? is this the annotation I should be expecting?

[AlexV]

Originally Posted by WizardsBlade

Could you also include time on the mentioned matriciesto give us at least an idea of how we are doing before anyone turns them in.

Originally Posted by WizardsBlade

just to make sure I am looking at the br17.atsp and it apears that 9999 means distance to itsself, and 0 means no path? is this the annotation I should be expecting?

Originally Posted by WizardsBlade

Are there some easy (and hard) tsp files with known solution so that we can test how well our programs are wokring? (preferably something small for basic testing and at least one as large as the largest one you plan on testing.)

Starting with the last point, there's now a sample that also includes test TSPs and data about their optimal tours. I'll place emphasis that the largest ones are (notably) smaller than the problems we'll use - problems sized close to the maximum node count we have made public are just one download away in the TSPLIB collection, amongst other places.

In terms of parsing br17, I'd say that 0 means an ideal, 0 cost path, for avoiding some special casing (and factoring in that it is a distance/cost matrix after all). However, note that we won't have 0 cost edges in the batch of problems we'll use for scoring.

With regards to the first point, as people submit their solvers we'll publish a ranking, so you'd get to see where everybody's positioned. I'm not sure what relevant measuring stick one could put there otherwise in terms of time...time it takes for Concorde to solve it? That would miss the point, the only important metric is the distance from other competitors. Hope this helps.

[Bernd Paradies]

Hello Alex,

The Sample Solver is great!

I am wondering whether it would be allowed to extend the Tsp_container struct and add a pbl_coords field that contains the original coordinates (x1,y1,x2,y2,…xn,yn) if points are provided by the TSP file:

struct Tsp_container {
std::vector<float> pbl_dist_mtx;
std::vector<float> pbl_coords;
std::string pbl_name;
std::string pbl_type;
unsigned int pbl_dim;
};

The changes in Sample Solver’s make_adj_mtx() would be trivial. I understand that the TSP files for Asymmetric TSPs (*.atsp) don’t provide points. But as far as I know Symmetrical TSP files do. My code would not assume that pbl_coords are always provided. If necessary, I can explain why I think that providing the original point lists is important.

Would the jury disqualify my submission if I added optional original coordinates to Tsp_container?

Thanks,

- Bernd

[AlexV]

Originally Posted by Bernd Paradies

Hello Alex,

The Sample Solver is great!

I am wondering whether it would be allowed to extend the Tsp_container struct and add a pbl_coords field that contains the original coordinates (x1,y1,x2,y2,…xn,yn) if points are provided by the TSP file:

struct Tsp_container {
std::vector<float> pbl_dist_mtx;
std::vector<float> pbl_coords;
std::string pbl_name;
std::string pbl_type;
unsigned int pbl_dim;
};

The changes in Sample Solver’s make_adj_mtx() would be trivial. I understand that the TSP files for Asymmetric TSPs (*.atsp) don’t provide points. But as far as I know Symmetrical TSP files do. My code would not assume that pbl_coords are always provided. If necessary, I can explain why I think that providing the original point lists is important.

Would the jury disqualify my submission if I added optional original coordinates to Tsp_container?

Thanks,

- Bernd

You're being far too kind on the sample, really - lingering bugs hide there! On the topic of the coords you wouldn't be disqualified for that, however there's also no guarantee that we'll feed in anything but FULL_MATRIX stored data (which of course, is not necessarily the best way to go about things, as Naurava kulkuri also illustrated above, but it's just a choice we made for this particular contest) - which is to say that as long as your code still works in the absence of the coords, feel free to chip a bit at the struct.

Note that I'm not on the refereeing board, but if anybody has any objection they'll definitely chime in and everyone will be informed in due time.

[Bernd Paradies]

Hi Alex,

I have one more question...

I noticed that in the ACO in AMP sample the "winning" tour is not saved. (Or I missed that.)
Does that mean that submitted solutions don't have to report the actual tour that produces the best known length?

How would you know that the calculated length is correct?

The rules don't mention any details on this topic.

Thanks again,

- Bernd

[AlexV]

Originally Posted by Bernd Paradies

Hi Alex,

I have one more question...

I noticed that in the ACO in AMP sample the "winning" tour is not saved. (Or I missed that.)
Does that mean that submitted solutions don't have to report the actual tour that produces the best known length?

How would you know that the calculated length is correct?

The rules don't mention any details on this topic.

Thanks again,

- Bernd

That's a failing of the sample (otherwise stated mine) - the winning tour should be written out as well.

[Bernd Paradies]

Shall the winning tour be written out into a file, i.e. a280.opt.tour, or can I add a std::vector<int> pbl_out_tour member to pbl::Tsp_container ?

BTW, pbl::Tsp_container in the sample's problem.hpp differs from the struct that is posted in the rules.
I am going to use the one from the sample if that's ok.

Cheers,

- Bernd

[AlexV]

Originally Posted by Bernd Paradies

Shall the winning tour be written out into a file, i.e. a280.opt.tour, or can I add a std::vector<int> pbl_out_tour member to pbl::Tsp_container ?

BTW, pbl::Tsp_container in the sample's problem.hpp differs from the struct that is posted in the rules.
I am going to use the one from the sample if that's ok.

Cheers,

- Bernd

Using either is fine. Writing it out to a file of returning a vector<int> are both acceptable. If you don't mind, avoid padding the pbl::Tsp_container struct - think of it as an opaque pimpled thing that is only guaranteed to provide you with the documented members and not much else

[Ethatron]

LOL, everyone's going to make you win, Alex (being all modified or optimized versions of the example-codebase). Just kidding.

I play with the idea to just dump my own codebase to github so someone can pick it up, though. I doubt I can get back enough motivation together to take the fight up with the ATI-driver again ...

Just finished BC7 squish yesterday, and I'd prefer to work on the AMP/compute version of it (which I abandoned for this contest ) and try to get the whole thing into The Compressonator. Theoretically squish compute should peak at 700 MB/s compression, quite motivating.

[Naurava kulkuri]

Hi!

It starts to look like I managed to get something worth of a submission. A few questions, though.

1)
I wrote a TSPLib reader that reads most of the formats (EUC_2D, CEIL_2D, explicit full weight matrices TSP, ATSP), except ATT currently. Does ATT calculation need to be included? The data is parsed and saved into object format for later manipulation, but the elements aren't currently written into the (square) matrix as I didn't have the time to write the routines.

2)
I don't currently use the struct that's being provided here, as the same data is available in the object I parse with my reader. Would not using the provided struct be considered a clear disadvantage in "grading"? The reader is quite quick (and robust, it would look like), only a few seconds even on big instances when a matrix is ready for calculation. Or would you prefer to see the code before answering to that?

2)
Can I assume the computer has available free memory for the various matrix sizes? I happen to use vectors and blatantly just allocate (sizeof(float) * 8192 * 8192) + (sizeof(int) * 8192) for the route information) + (some vector constants) bytes of memory for the maximum problem size. It could be the test machine doesn't have such a chunks available on every run. Thus far I haven't considered any other arrangements (as they probably would require some serious re-engineering effort).

3)
Which one is more important: speed or quality? I have knob that increases speed, but most likely it will sacrifice quality (after some point, at least). Someone just have to turn it to experiment effects, but I could write a few ps1 or bat scripts to illustrate the usage.

4)
Do I still have time to have quick feedback if there's something minor to be corrected?

On the plus side could be I haven't used any ant stuff or the contest provided code, though adding it would be a definite plus (maybe someone does that). It looks my implementation and approach is mostly competitive regarding speed and quality on the instances I tested, though my asymmetric stuff could ware somewhat worse (I'll work that out on Friday and try to submit after that). The bigger .tsp and most of the TSPLib atsp instances just crash the demo solver, so I'm not sure about them.

Ugh. It has been a rough crunch, now I just need to last squeeze...

[AlexV]

Originally Posted by Naurava kulkuri

Hi!

It starts to look like I managed to get something worth of a submission. A few questions, though.

1)
I wrote a TSPLib reader that reads most of the formats (EUC_2D, CEIL_2D, explicit full weight matrices TSP, ATSP), except ATT currently. Does ATT calculation need to be included? The data is parsed and saved into object format for later manipulation, but the elements aren't currently written into the (square) matrix as I didn't have the time to write the routines.

2)
I don't currently use the struct that's being provided here, as the same data is available in the object I parse with my reader. Would not using the provided struct be considered a clear disadvantage in "grading"? The reader is quite quick (and robust, it would look like), only a few seconds even on big instances when a matrix is ready for calculation. Or would you prefer to see the code before answering to that?

2)
Can I assume the computer has available free memory for the various matrix sizes? I happen to use vectors and blatantly just allocate (sizeof(float) * 8192 * 8192) + (sizeof(int) * 8192) for the route information) + (some vector constants) bytes of memory for the maximum problem size. It could be the test machine doesn't have such a chunks available on every run. Thus far I haven't considered any other arrangements (as they probably would require some serious re-engineering effort).

3)
Which one is more important: speed or quality? I have knob that increases speed, but most likely it will sacrifice quality (after some point, at least). Someone just have to turn it to experiment effects, but I could write a few ps1 or bat scripts to illustrate the usage.

4)
Do I still have time to have quick feedback if there's something minor to be corrected?

On the plus side could be I haven't used any ant stuff or the contest provided code, though adding it would be a definite plus (maybe someone does that). It looks my implementation and approach is mostly competitive regarding speed and quality on the instances I tested, though my asymmetric stuff could ware somewhat worse (I'll work that out on Friday and try to submit after that). The bigger .tsp and most of the TSPLib atsp instances just crash the demo solver, so I'm not sure about them.

Ugh. It has been a rough crunch, now I just need to last squeeze...

Thanks for crunching! In the order of asking:
1) No, it is not absolutely necessary, it might save us some work (be nice to us!) but it is not absolutely necessary;
2) No, you are not graded based on usage of the struct or the scaffolding, although again it might save us some work; the purpose of it was to give people something easy to use in terms of loading data (admittedly it came later than wanted);
3) Yes, memory is available;
4) Balanced, with a slight but very slight bias towards speed - however an awful solution won't be saved by being speedy; the batch files would be helpful, or at least documentation explaining how to parameterize your work;
5) That would depend, but the possibility (in no way certainty) exists.
Cheers!

[AlexV]

I'll take this opportunity to remind everyone that on Monday the submission process closes, so if you're in the process of crunching at a solution please make it so that by Monday at the latest you'll have submitted it to the contest's dedicated email address.

[Naurava kulkuri]

Originally Posted by AlexV

I'll take this opportunity to remind everyone that on Monday the submission process closes, so if you're in the process of crunching at a solution please make it so that by Monday at the latest you'll have submitted it to the contest's dedicated email address.

Regarding Monday, does it suffice to send on Monday on any time zone?

I have an improved version on the works, so perhaps it's in order to hint one shouldn't put too much effort on my latest submission. Albeit, of course, the basic solution is the same, just some cleaning and tweaks (which make the code messier, of course) here and there.

In that vein, should I assume the asymmetric cases are as important as the symmetric ones and their maximum size is 8192 cities too?

[AlexV]

Originally Posted by Naurava kulkuri

Regarding Monday, does it suffice to send on Monday on any time zone?

I have an improved version on the works, so perhaps it's in order to hint one shouldn't put too much effort on my latest submission. Albeit, of course, the basic solution is the same, just some cleaning and tweaks (which make the code messier, of course) here and there.

In that vein, should I assume the asymmetric cases are as important as the symmetric ones and their maximum size is 8192 cities too?

Monday 23:59 GMT would be the limit...but nobody will be kicked out if it's actually Tuesday 00:01 GMT.

Weights in the final score are close for ATSP versus TSP, and maximum size is 4096. Cheers!

[AlexV]

Also, as a quick note for people who have already submitted to the initial email destination (alex.at.beyond3d.com), if you have time and feel so inclined please also send to the current email destination (contest.at.beyond3d.com), just in case the overeager spam-filter that sometimes touches the first did some mean things to your good work. Cheers.

[Naurava kulkuri]

Hi!

I suppose we hear from the result in the near future, but now after defragmenting myself a bit, stepping back and indeed sleeping a few nights, how does it affect the grading if there's a blatant, easily correctable, massive, performance problem like re-creating a staging array on every run instead of just chaning its contents?

It got into a bit of hassle towards the end and somehow I just could make that into nightmarish reality at some point. The solver would run blisteringly faster if one staging array wouldn't be re-created on every instance of loop, something that's easily fixed.

Aaarrghh!

[Naurava kulkuri]

Originally Posted by Naurava kulkuri

Hi!
... re-creating a staging array on every run of a hot loop instead of just chaning its contents...

A clarification to my previous sentence (I didn't see how to edit a post).

[Naurava kulkuri]

To further post my thinking aloud, it looks like if the outcome of this performance bug isn't that dramatic. At least if there's believing quick results after fixing this bug. Or then there's also a way to avoid copying data explicitly to staging array from the underlying data source and manipulating the underlying staging array data by standard C++ libraries. But that I wasn't aware of.

[Naurava kulkuri]

Anu news regarding results? It probably is difficult to be objective, but I'm a bit impatient, or keen, to learn learn the results.

[AlexV]

Notifications will be sent out tomorrow - so not much time left to wait (for news!).

[Naurava kulkuri]

Great!

[Naurava kulkuri]

It looks like the rules and regulations etc. pdf files aren't available on-line anymore. How could I obtain them?

Nice to know I'm in for the final rounds. Though, let's see now if I can make some time (well, Saturday-Sunday nights is usually free ).

[Bernd Paradies]

Congratulations, Naurava!

Have the rankings of the finalists been posted yet?

Cheers,

- Bernd

[AlexV]

Naurava: will be back up hopefully today.
Bernd: not yet, minor delay, many apologies.

[Naurava kulkuri]

Originally Posted by Bernd Paradies

Congratulations, Naurava!

Hey, thanks, Bernd! Should I congratulate you, too?

About the results and standings, I wonder if they had any bearing to my efforts, as I ran a bit out of steam already (witness all my typos).

At least I fixed the minor performance degration I lamented about already. Then I think I have multiple options for performance tweaks, but I would need to evaluate my options and try to make just try and see if I get around to implement the easiest ones.