arman/science-ation
1
1
Fork 0
forked from science-ation/science-ation
Code Pull Requests Activity
master
science-ation/admin/anneal.inc.php

364 lines
9.4 KiB
PHP
Raw Permalink Normal View History

The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
<?php
Update the annealer to recompute the cost of multiple affected buckets on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
2010-02-22 18:45:58 +00:00
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
class annealer {
var $num_buckets;
var $bucket;
var $bucket_cost;
Update the annealer to recompute the cost of multiple affected buckets on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
2010-02-22 18:45:58 +00:00
var $bucket_cost_new;
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
var $cost;
var $start_temp, $start_moves;
var $cost_function_callback;
Use the annealer to assign projects and judges to timeslots. This should prevent a project from getting too many judges in a row, and also a judge from judging 2 projects at the same time (which would be more of a problem). Still need to write a verifier to check all the results. But the annealer tests look pretty good. Unfortunately it takes a pretty long time to run. :(
2006-08-08 03:21:08 +00:00
var $pick_move_callback;
- Add status output to the judge scheduler in the form of 2 variables. Completely untested because I don't have judge data here. Will test when I get home and debug.
2006-10-25 00:53:02 +00:00
var $update_callback;
Update the annealer to recompute the cost of multiple affected buckets on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
2010-02-22 18:45:58 +00:00
var $delta_cost_bucket_ids_callback;
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
var $iterations;
var $items_per_bucket;
Use array_splice to compute new lists... much shorter code, and probably a lot faster.
2010-02-22 18:13:11 +00:00
var $max_items_per_bucket;
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
var $rate;
Update the annealer to recompute the cost of multiple affected buckets on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
2010-02-22 18:45:58 +00:00
var $move_bucket_ids;
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
function annealer($num_buckets, $start_temp, $start_moves, $rate,
$cost_function_cb, $items)
{
$this->num_buckets = $num_buckets;
$this->start_temp = $start_temp;
$this->start_moves = $start_moves;
$this->cost_function_callback = $cost_function_cb;
Use the annealer to assign projects and judges to timeslots. This should prevent a project from getting too many judges in a row, and also a judge from judging 2 projects at the same time (which would be more of a problem). Still need to write a verifier to check all the results. But the annealer tests look pretty good. Unfortunately it takes a pretty long time to run. :(
2006-08-08 03:21:08 +00:00
unset($this->pick_move_callback);
- Add status output to the judge scheduler in the form of 2 variables. Completely untested because I don't have judge data here. Will test when I get home and debug.
2006-10-25 00:53:02 +00:00
unset($this->update_callback);
Update the annealer to recompute the cost of multiple affected buckets on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
2010-02-22 18:45:58 +00:00
unset($this->delta_cost_bucket_ids_callback);
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
$this->bucket_cost = array();
Update the annealer to recompute the cost of multiple affected buckets on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
2010-02-22 18:45:58 +00:00
$this->bucket_cost_old = array();
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
$this->bucket = array();
$this->iterations = 0;
Update the annealer to recompute the cost of multiple affected buckets on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
2010-02-22 18:45:58 +00:00
$this->items_per_bucket = ceil(count($items) / $num_buckets);
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
$this->rate = $rate;
Use array_splice to compute new lists... much shorter code, and probably a lot faster.
2010-02-22 18:13:11 +00:00
$this->max_items_per_bucket = 0;
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
$ipb = ceil($this->items_per_bucket);
$i=0;
$this->cost = 0;
Update the annealer to recompute the cost of multiple affected buckets on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
2010-02-22 18:45:58 +00:00
/* Assign to buckets */
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
for($x=0; $x<$num_buckets; $x++) {
unset($b);
$b = array();
for($y=0;$y<$ipb; $y++) {
if($i == count($items)) break;
$b[] = $items[$i];
$i++;
}
$this->bucket[] = $b;
Update the annealer to recompute the cost of multiple affected buckets on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
2010-02-22 18:45:58 +00:00
}
/* Then do costs after all bucket assignments are done */
for($x=0; $x<$num_buckets; $x++) {
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
$c = $this->cost_function($x);
$this->bucket_cost[] = $c;
$this->cost += $c;
}
TRACE("Annealer setup: T={$this->start_temp}, ".
"M={$this->start_moves}, Bkts={$this->num_buckets}, ".
"Cost={$this->cost}\n");
}
Use the annealer to assign projects and judges to timeslots. This should prevent a project from getting too many judges in a row, and also a judge from judging 2 projects at the same time (which would be more of a problem). Still need to write a verifier to check all the results. But the annealer tests look pretty good. Unfortunately it takes a pretty long time to run. :(
2006-08-08 03:21:08 +00:00
function set_pick_move($func)
{
$this->pick_move_callback = $func;
}
- Add status output to the judge scheduler in the form of 2 variables. Completely untested because I don't have judge data here. Will test when I get home and debug.
2006-10-25 00:53:02 +00:00
function set_update_callback($func)
{
$this->update_callback = $func;
}
Update the annealer to recompute the cost of multiple affected buckets on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
2010-02-22 18:45:58 +00:00
function set_delta_cost_bucket_ids_callback($func)
{
$this->delta_cost_bucket_ids_callback = $func;
}
Use array_splice to compute new lists... much shorter code, and probably a lot faster.
2010-02-22 18:13:11 +00:00
function set_max_items_per_bucket($num)
{
$this->max_items_per_bucket = $num;
}
- Add status output to the judge scheduler in the form of 2 variables. Completely untested because I don't have judge data here. Will test when I get home and debug.
2006-10-25 00:53:02 +00:00
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
Update the annealer to recompute the cost of multiple affected buckets on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
2010-02-22 18:45:58 +00:00
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
function pick_move()
{
/* Pick a bucket and item */
while(1) {
$b1 = rand(0, $this->num_buckets - 1);
if(count($this->bucket[$b1]) > 0) break;
}
$i1 = rand(0, count($this->bucket[$b1]) -1);
Use array_splice to compute new lists... much shorter code, and probably a lot faster.
2010-02-22 18:13:11 +00:00
/* Pick a second bucket that is different than the first */
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
$b2 = rand(0, $this->num_buckets - 2);
if($b2 >= $b1) $b2++;
Use array_splice to compute new lists... much shorter code, and probably a lot faster.
2010-02-22 18:13:11 +00:00
if($this->max_items_per_bucket > 0 && count($this->bucket[$b2]) >= $this->max_items_per_bucket) {
/* Can't move b1 into b2, it would exceed the max items per bucket, pick an
* item to swap with */
$i2 = rand(0, count($this->bucket[$b2])-1);
} else {
/* Pick an item, or a blank, in the second bucket */
$i2 = rand(0, count($this->bucket[$b2]));
if($i2 == count($this->bucket[$b2])) $i2 = -1;
}
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
// TRACE("Move ($b1,$i1)<->($b2,$i2)\n");
return array($b1, $i1, $b2, $i2);
}
function cost_function($b)
{
$bkt = $this->bucket[$b];
$cb = $this->cost_function_callback;
$c = $cb($this, $b, $bkt);
// $this->print_bucket($b);
// print("Computed cost to be: $c\n");
return $c;
}
function compute_delta_cost($move)
{
list($b1, $i1, $b2, $i2) = $move;
Use the annealer to assign projects and judges to timeslots. This should prevent a project from getting too many judges in a row, and also a judge from judging 2 projects at the same time (which would be more of a problem). Still need to write a verifier to check all the results. But the annealer tests look pretty good. Unfortunately it takes a pretty long time to run. :(
2006-08-08 03:21:08 +00:00
if($b1 == $b2) {
Update the annealer to recompute the cost of multiple affected buckets on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
2010-02-22 18:45:58 +00:00
echo "Called on same bucket, not supported!\n";
exit;
// return $this->compute_delta_cost_same_bucket($move);
Use the annealer to assign projects and judges to timeslots. This should prevent a project from getting too many judges in a row, and also a judge from judging 2 projects at the same time (which would be more of a problem). Still need to write a verifier to check all the results. But the annealer tests look pretty good. Unfortunately it takes a pretty long time to run. :(
2006-08-08 03:21:08 +00:00
}
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
$cost = 0;
Update the annealer to recompute the cost of multiple affected buckets on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
2010-02-22 18:45:58 +00:00
/* Save the old lists for easy restore */
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
$b1_old = $this->bucket[$b1];
$b2_old = $this->bucket[$b2];
Update the annealer to recompute the cost of multiple affected buckets on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
2010-02-22 18:45:58 +00:00
/* Setup new costs */
$this->bucket_cost_new = $this->bucket_cost;
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
Update the annealer to recompute the cost of multiple affected buckets on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
2010-02-22 18:45:58 +00:00
/* Compute new lists with swapped elements */
if($i2 != -1) { /* Swap */
Use array_splice to compute new lists... much shorter code, and probably a lot faster.
2010-02-22 18:13:11 +00:00
array_splice($this->bucket[$b1], $i1, 1, $b2_old[$i2]);
array_splice($this->bucket[$b2], $i2, 1, $b1_old[$i1]);
Update the annealer to recompute the cost of multiple affected buckets on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
2010-02-22 18:45:58 +00:00
} else { /* Move one to other */
Use array_splice to compute new lists... much shorter code, and probably a lot faster.
2010-02-22 18:13:11 +00:00
array_splice($this->bucket[$b1], $i1, 1);
$this->bucket[$b2][] = $b1_old[$i1];
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
}
Update the annealer to recompute the cost of multiple affected buckets on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
2010-02-22 18:45:58 +00:00
/* Get the lists of buckets we need to recompute, by default
* just b1 and b2 */
if(isset ($this->delta_cost_bucket_ids_callback)) {
$cb = $this->delta_cost_bucket_ids_callback;
$ids = $cb($this, $b1);
$ids = array_unique(array_merge($ids, $cb($this, $b2)), SORT_NUMERIC );
} else {
$ids = array($b1, $b2);
}
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
Update the annealer to recompute the cost of multiple affected buckets on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
2010-02-22 18:45:58 +00:00
// TRACE("Recompute IDs:\n");
// TRACE_R($ids);
/* Save that list */
$this->move_bucket_ids = $ids;
/* Compute a delta cost, recompute all costs for all buckets */
foreach($ids as $bucket_id) {
/* Compute costs */
$cost -= $this->bucket_cost[$bucket_id];
$this->bucket_cost_new[$bucket_id] = $this->cost_function($bucket_id);
$cost += $this->bucket_cost_new[$bucket_id];
}
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
Update the annealer to recompute the cost of multiple affected buckets on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
2010-02-22 18:45:58 +00:00
/* Save the new lists */
$b1_new = $this->bucket[$b1];
$b2_new = $this->bucket[$b2];
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
/* Return to the original bucket lists */
$this->bucket[$b1] = $b1_old;
$this->bucket[$b2] = $b2_old;
Update the annealer to recompute the cost of multiple affected buckets on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
2010-02-22 18:45:58 +00:00
return array($cost, array($b1_new, $b2_new));
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
}
Update the annealer to recompute the cost of multiple affected buckets on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
2010-02-22 18:45:58 +00:00
/*
Use the annealer to assign projects and judges to timeslots. This should prevent a project from getting too many judges in a row, and also a judge from judging 2 projects at the same time (which would be more of a problem). Still need to write a verifier to check all the results. But the annealer tests look pretty good. Unfortunately it takes a pretty long time to run. :(
2006-08-08 03:21:08 +00:00
function compute_delta_cost_same_bucket($move)
{
list($b1, $i1, $b2, $i2) = $move;
$cost = 0;
$b_old = $this->bucket[$b1];
$b_new = array();
Update the annealer to recompute the cost of multiple affected buckets on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
2010-02-22 18:45:58 +00:00
/* Make a new bucket list
Use the annealer to assign projects and judges to timeslots. This should prevent a project from getting too many judges in a row, and also a judge from judging 2 projects at the same time (which would be more of a problem). Still need to write a verifier to check all the results. But the annealer tests look pretty good. Unfortunately it takes a pretty long time to run. :(
2006-08-08 03:21:08 +00:00
for($x=0; $x<count($b_old); $x++) {
if($x == $i1) {
Update the annealer to recompute the cost of multiple affected buckets on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
2010-02-22 18:45:58 +00:00
/* Swap or remove this index
Use the annealer to assign projects and judges to timeslots. This should prevent a project from getting too many judges in a row, and also a judge from judging 2 projects at the same time (which would be more of a problem). Still need to write a verifier to check all the results. But the annealer tests look pretty good. Unfortunately it takes a pretty long time to run. :(
2006-08-08 03:21:08 +00:00
if($i2 != -1) $b_new[] = $b_old[$i2];
} else if($x == $i2) {
$b_new[] = $b_old[$i1];
} else {
$b_new[] = $b_old[$x];
}
}
Update the annealer to recompute the cost of multiple affected buckets on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
2010-02-22 18:45:58 +00:00
/* Assign the new item lists to the buckets
Use the annealer to assign projects and judges to timeslots. This should prevent a project from getting too many judges in a row, and also a judge from judging 2 projects at the same time (which would be more of a problem). Still need to write a verifier to check all the results. But the annealer tests look pretty good. Unfortunately it takes a pretty long time to run. :(
2006-08-08 03:21:08 +00:00
$this->bucket[$b1] = $b_new;
Update the annealer to recompute the cost of multiple affected buckets on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
2010-02-22 18:45:58 +00:00
/* Compute costs
Use the annealer to assign projects and judges to timeslots. This should prevent a project from getting too many judges in a row, and also a judge from judging 2 projects at the same time (which would be more of a problem). Still need to write a verifier to check all the results. But the annealer tests look pretty good. Unfortunately it takes a pretty long time to run. :(
2006-08-08 03:21:08 +00:00
$cost -= $this->bucket_cost[$b1];
$c1 = $this->cost_function($b1);
$cost += $c1;
Update the annealer to recompute the cost of multiple affected buckets on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
2010-02-22 18:45:58 +00:00
/* Return to the original bucket lists
Use the annealer to assign projects and judges to timeslots. This should prevent a project from getting too many judges in a row, and also a judge from judging 2 projects at the same time (which would be more of a problem). Still need to write a verifier to check all the results. But the annealer tests look pretty good. Unfortunately it takes a pretty long time to run. :(
2006-08-08 03:21:08 +00:00
$this->bucket[$b1] = $b_old;
return array($cost, array($c1, $b_new, 0, array()));
}
Update the annealer to recompute the cost of multiple affected buckets on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
2010-02-22 18:45:58 +00:00
*/
Use the annealer to assign projects and judges to timeslots. This should prevent a project from getting too many judges in a row, and also a judge from judging 2 projects at the same time (which would be more of a problem). Still need to write a verifier to check all the results. But the annealer tests look pretty good. Unfortunately it takes a pretty long time to run. :(
2006-08-08 03:21:08 +00:00
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
function accept_move($move, $movedata)
{
list($b1, $i1, $b2, $i2) = $move;
Update the annealer to recompute the cost of multiple affected buckets on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
2010-02-22 18:45:58 +00:00
list($b1_new, $b2_new) = $movedata;
Use the annealer to assign projects and judges to timeslots. This should prevent a project from getting too many judges in a row, and also a judge from judging 2 projects at the same time (which would be more of a problem). Still need to write a verifier to check all the results. But the annealer tests look pretty good. Unfortunately it takes a pretty long time to run. :(
2006-08-08 03:21:08 +00:00
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
$this->bucket[$b1] = $b1_new;
Update the annealer to recompute the cost of multiple affected buckets on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
2010-02-22 18:45:58 +00:00
if($b1 != $b2) $this->bucket[$b2] = $b2_new;
$this->bucket_cost = $this->bucket_cost_new;
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
}
function anneal()
{
$temperature = $this->start_temp;
$current_cost = $this->cost;
$last_cost = 0;
$last_cost_count = 0;
Replaced the timeslot scheduler. This one is much faster, but it doens't actually compute cost for the number of judges the student has in a row. But, because it's totally random in layout multiple judges in a row should happen very infrequently.
2006-08-08 06:51:07 +00:00
if($this->num_buckets <= 1) {
TRACE("Only one Bucket, nothing to anneal.\n");
return;
}
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
// $this->print_buckets();
- Add status output to the judge scheduler in the form of 2 variables. Completely untested because I don't have judge data here. Will test when I get home and debug.
2006-10-25 00:53:02 +00:00
$estimated_iterations = ceil(log(0.1 / $this->start_temp, $this->rate));
Update the annealer to recompute the cost of multiple affected buckets on a move if necessary. Add the annealer to compute floor locations (but don't link it to anything yet because there's no editor, we're testing it with GVRSF this year).
2010-02-22 18:45:58 +00:00
// print_r($this);
- Add status output to the judge scheduler in the form of 2 variables. Completely untested because I don't have judge data here. Will test when I get home and debug.
2006-10-25 00:53:02 +00:00
$iterations = 0;
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
while(1) {
$moves = $this->start_moves;
for($m = 0; $m<$moves; $m++) {
// $this->print_buckets();
/* Pick 2 moves at random */
Use the annealer to assign projects and judges to timeslots. This should prevent a project from getting too many judges in a row, and also a judge from judging 2 projects at the same time (which would be more of a problem). Still need to write a verifier to check all the results. But the annealer tests look pretty good. Unfortunately it takes a pretty long time to run. :(
2006-08-08 03:21:08 +00:00
if(isset ($this->pick_move_callback)) {
$cb = $this->pick_move_callback;
$move = $cb($this);
} else {
$move = $this->pick_move();
}
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
/* See what the new cost is compared to the old */
list($delta_c, $movedata) =
$this->compute_delta_cost($move);
$r = floatval(rand()) / floatval(getrandmax());
/* Decide if we want to keep it */
$e = exp(-$delta_c / $temperature);
// TRACE("r=$r, exp=$e, delta=$delta_c\n");
if($r < exp(-$delta_c / $temperature)) {
/* Yes, we do, record the move */
$this->accept_move($move, $movedata);
$current_cost += $delta_c;
$n_accepted++;
Use the annealer to assign projects and judges to timeslots. This should prevent a project from getting too many judges in a row, and also a judge from judging 2 projects at the same time (which would be more of a problem). Still need to write a verifier to check all the results. But the annealer tests look pretty good. Unfortunately it takes a pretty long time to run. :(
2006-08-08 03:21:08 +00:00
// if($current_cost < $this->cost)
If we manage to reach a 0 cost early, stop the annealer, there is no point looking any further. This significantly reduces the timeslot scheduling time. In most cases we reach 0 in a couple thousand iterations, but we need high effort because some timeslot scheduling problems are hard to assign.
2006-08-12 08:07:02 +00:00
$this->cost = $current_cost;
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
// TRACE("Move accepted, cost=$current_cost\n");
} else {
// TRACE("Move rejected\n");
}
$this->iterations++;
- Add status output to the judge scheduler in the form of 2 variables. Completely untested because I don't have judge data here. Will test when I get home and debug.
2006-10-25 00:53:02 +00:00
if($this->iterations % 10000 == 0) {
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
TRACE(" {$this->iterations} iterations, cost={$this->cost}, temperature=$temperature\n");
// $this->print_buckets();
}
If we manage to reach a 0 cost early, stop the annealer, there is no point looking any further. This significantly reduces the timeslot scheduling time. In most cases we reach 0 in a couple thousand iterations, but we need high effort because some timeslot scheduling problems are hard to assign.
2006-08-12 08:07:02 +00:00
if($this->cost == 0) {
/* If we manage to get to a 0 cost
* solution, don't look any more */
break;
}
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
}
- Add status output to the judge scheduler in the form of 2 variables. Completely untested because I don't have judge data here. Will test when I get home and debug.
2006-10-25 00:53:02 +00:00
$iterations++;
If we manage to reach a 0 cost early, stop the annealer, there is no point looking any further. This significantly reduces the timeslot scheduling time. In most cases we reach 0 in a couple thousand iterations, but we need high effort because some timeslot scheduling problems are hard to assign.
2006-08-12 08:07:02 +00:00
- Add status output to the judge scheduler in the form of 2 variables. Completely untested because I don't have judge data here. Will test when I get home and debug.
2006-10-25 00:53:02 +00:00
if(isset ($this->update_callback)) {
$cb = $this->update_callback;
$cb($iterations, $estimated_iterations);
}
If we manage to reach a 0 cost early, stop the annealer, there is no point looking any further. This significantly reduces the timeslot scheduling time. In most cases we reach 0 in a couple thousand iterations, but we need high effort because some timeslot scheduling problems are hard to assign.
2006-08-12 08:07:02 +00:00
if($this->cost == 0) break;
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
if($this->cost == $last_cost) {
$last_cost_count ++;
} else {
$last_cost = $this->cost;
$last_cost_count=0;
}
if($temperature < 0.1 && $last_cost_count > 10)
break;
// TRACE("Cost is {$this->cost}\n");
$temperature *= $this->rate;
Committing a comment to the annealer to look at down the road, ideas from Kris to speed up the scheduler when the cost isnt changing, instead of waiting for the temperature to fall slowly, speed it up when the acceptance rate is really good or really bad
2009-03-24 16:52:10 +00:00
/*
FIXME: README: NOTE: TODO:
From Kris, 2009-03-24
Dave do you think we should consider something like this?
<Kris_School_1> here's the schedule i use in my academic annealer:
if( _params._useVPRTempSchedule ) {
// This is VPR's temperature schedule...
if( successRate > 0.96 ) {
_temp *= 0.5;
} else if( successRate > 0.8 ) {
_temp *= 0.9;
} else if( successRate > 0.15 || !windowsSized ) {
_temp *= 0.95;
} else {
_temp *= 0.8;
}
} else {
// This is identical to Aaarts and Van Laarhaven.
real64 kappa = _params._tempReduction; // 1.0 == slow, 10 = reasonable, 100 == fast
real64 sqrvar = std::sqrt( variance );
if( variance <= EPSNEG || sqrvar <= EPSNEG ) {
_temp = 0.;
} else {
_temp = _temp * ( sqrvar / ( sqrvar + kappa * _temp ) );
}
}
*/
The new judge scheduler. - Missing: Having a project judged more than once by different judging teams is untested, I don't htink it'll work properly, still working on that part. - Missing: Auto updating the configuration if any of the variables are missing. - Missing: A way to preserve judging questions (like willing_chair), so the user doesn't delete them and break the scheduler, OR, notice saying that the question has been deleted and the scheduler won't use the chair calculations, then we need a way to add them back in with the click of a button.
2006-08-01 19:43:15 +00:00
}
TRACE("Annealing complete. {$this->iterations} iterations. Final cost is {$this->cost}\n");
}
function print_bucket($x)
{
$b = $this->bucket[$x];
print("Bucket $x: (cost: {$this->bucket_cost[$x]})\n");
print(" ");
for($y=0;$y<count($b); $y++) {
print("{$b[$y]} ");
}
print("\n");
}
function print_buckets()
{
for($x=0; $x<$this->num_buckets; $x++) {
$this->print_bucket($x);
}
}
}
?>
Copy Permalink