The first step is to do as much analysis as possible on earliest and latest takeoff
times. In some cases one aircraft must follow another, in which case the
before variable can be eliminated and the constraints above
simplified to a single linear relationship between the takeoff times. In many cases
there is no possibility of one aircraft interacting with another so both the variable and
the constraints can be eliminated.
Instead of using binary variables, we define a new kind of discrete constraint –
an extension of semicontinuous variables. A standard semicontinuous variable may
take a value of zero or if not zero, then greater than a given conditional minimum.
The extension allows the feasible region to be defined as a series of disjoint ranges.
(The new constraint can be implemented either by modifying the source code of an optimiser
or by defining suitable callback routines to an optimiser used in subroutine library form.)
We define a new variable offset_{AB} as the difference
between the takeoff times of A and B – negative if A follows B and positive if B follows
A, and add a constraint to define its value. Its feasible region is defined to be:
We can eliminate the constraints defined above. The linear relaxation for the new
problem allows the offset variable to take any value and so is as
weak as the original form. However in most cases there will be no need to branch on the
variable – if it takes a value in its feasible region in the relaxed solution, no
branching is required.
This modified problem can be solved to an acceptable solution for a whole day of over
600 takeoffs.
