===============
I M P R O V E R
===============

This file is a description of the Improver algorithm, which is a
version of Optimizer for improving the schedule under a tight time
limit. It usually does not have time to re-schedule all events, and
thus it re-schedules only the most important events.

Improver determines the importance of an event by its "improvement
potential," which is the difference between the maximal possible score
and the current score, scaled by the event weight:

improvement-potential[event] = weight[event] * (1.0 - score[event]) 

It arranges events into a priority queue by their improvement
potential. At each step, it extracts the highest-potential event from
the queue and re-schedules it; note that it does not put the
re-scheduled event back into the queue. After re-scheduling an event,
Improver determines the effects on the scores of other events. If the
scores of some events in the queue have changed because of binary
constraints w.r.t. the re-scheduled event, then Improver re-computes
their improvement potential and updates their position in the queue.

If Improver processes all events in the queue before reaching the time
limit, it stops without going second time through the events, which is
different from Optimizer. If it reaches the time limit before
processing all events, it also stops re-scheduling. In this case, it
checks whether any unprocessed events violate hard preferences, and
removes such events from the schedule. Note that an event removal
never causes new violations of hard preferences, and thus Improver
does not need to re-check violations for the already processed events.

The following pseudocode summaries the main steps of Improver:

Create an empty priority queue, 
  which indexes events by their "improvement-potential"
For each event:
  Compute its "score" and "improvement-potential" in the initial schedule
  Insert it into the priority queue, indexed by "improvement-potential"
While the priority queue is nonempty, and the time limit is not reached:
  Extract the event with the highest "improvement-potential" 
    from the priority queue
  Find the best assignment for this event, and re-schedule it
  If this re-scheduling affects the scores of some other events,
    then re-compute their "score"s and "improvement-potential"s,
    and update their position in the priority queue
Sort the events remaining in the priority queue
  in the increasing order of their weights
For each remaining event, in this sorted order:
  Re-check whether it violates hard preferences
  In case of a violation, remove it from the schedule

After we implement the Improver algorithm, we should also add the
procedure that removes hard-preference violations to Optimizer, which
should use this procedure only if it has not completed its first pass
through the main loop.