Restricted Resources Challenge: Rules 3.3 and 3.4
Dear Organizers,

could you please clarify the rules 3.3 and 3.4. Given some computer C and a timelimit T, a solver produces a trajectory (C,T) in the search space. Given another computer C' and an infinite timelimit, does rule 3.3. require that the trajectory (C,T) is a prefix of trajectory (C',inf), i.e. is the time limit's sole purpose to halt the solver?

Thanks in advance, kind regards
bg
<hidden> - January 15, 2019 4:53 PM
7 Replies:
Dear bg/ UOS team,
as another participant, I cannot give an official response. However, it's not my first rodeo, so I can tell you this, hoping that you find it useful:

My best guess is that, from the _organizers' perspective_, the time limit is only relevant for stopping the solver. They will need to assess the quality of the obtained results, re-start the solvers with another instance, etc. Other competitions implement this in a different way, i.e., by sending a (UNIX) signal to your application prompting it to stop. See the PACE-Challenges for this. In our case here, the running time is given as a parameter when executing the program.
<hidden> - January 17, 2019 11:30 AM ( 6 years ago )
From _your_ (our) perspective however, my guess is that the trajectory (C,T) is not necessarily "only" a prefix of (C',inf). It might make sense setting some internal parameters depending on T. This can be relevant in case you are pre-computing a lot of helpful sub-problems before solving the actual problem. The time allocated for the pre-processing phase therefore will depend on T, so the exhibited behavior of the algorithm is influenced by the parameter (T).

Sincerely,
MJG
<hidden> - January 17, 2019 11:32 AM ( 6 years ago )
Dear MJG,
first, thank you for your reply.

Let me add some thoughts regarding T influencing the exhibited behavior:

The processing speed of the machine is unknown, providing a timelimit f(T) < T for external solvers (assuming deterministic mode) like CPLEX etc. will be inconsistent across platforms even for equal seeds and time limits. Therefore T can be only used to estimate some sort of other computational budget not related to time at all (e.g. iterations). Same holds for "allocating time" for pre-processing, which can only happen in the form of estimating some other deterministic time-independent budget.

<hidden> - January 17, 2019 1:22 PM ( 6 years ago )
...
Estimating a time-independent budget from a time limit is meaningless if nothing is known about the machine or the scaling behavior of the benchmark-derived factor. If the trajectory was influenced by T this would violate my interpretation of rule 3.3. So I'm rather interested in what the Organizers actually meant.

Regards
bg
<hidden> - January 17, 2019 1:26 PM ( 6 years ago )
True. It will be impossible to guarantee that the exact outcome can be reproduced.
My best guess is that rule 3.3, which reads "... should code ...", means that this is a desirable property, but, given the this discussion above, not a requirement.

MJG
<hidden> - January 18, 2019 6:37 AM ( 6 years ago )
Dear BG, MJG,

Thank you very much for raising and feeding the discussion.
We agree to all that has been assumed above, and can add the following:
- The running environment will be setup as a single processor/single core machine. Instances are validated with your solver sequentially, so only one solver process runs at each time.
- The parameter T given to the process at startup is computed with respect to the calibration factor of that machine, in the way specified by rule 3.4. The solver process can therefore estimate the calibration factor: an instance with n orders that results in a time budget of T = ceil( f * ( n + 10 ) ) leads to f being approximately T / ( n + 10 ).
- We expect the solver process to stop graciously at latest T seconds after being spawned, otherwise we kill the process. Even in case the process is killed, the solution written during execution is taken. This solution can be rewritten as often as desired until the process stops or is stopped.
- The process of rewriting the solution file should preferably be atomic to avoid the possibility of file corruption. A practical way is to write a new file and replace the solution file by the new file. This has atomic implementations in the Windows OS, the exact function depends on your programming language.
We hope that this helps clarifying the issue,

with our best regards, VSC2019.
VSC 2019 Organization - January 18, 2019 2:25 PM ( 6 years ago )
Dear Organizers,

thank you for the answers.

Regards
bg
<hidden> - January 22, 2019 1:11 PM ( 6 years ago )