"Evaluation of Objective Function Designs Through an Auxiliary Heuristic Scheme"
Li Lei and Raymond Kwan

Exact integer linear programming (ILP) models and their solvers have the advantage of delivering optimal results for complex real-life scheduling problems. However, they are often computationally practical only for relatively small problem instances. Furthermore, it is not easy to establish high confidence in the effectiveness of an objective function design, which is vital for yielding good-quality schedules in practice. For example, suppose a train unit schedule needs 50 train units to cover a timetable. The workings of individual train units cannot be all efficient because of the timing connections of the trips served. The objective function is therefore a tradeoff amongst a number of schedule quality aspects. For train unit scheduling, an exact ILP solver called RS-Opt has been developed based on a multi-commodity network flow model. An iterative heuristic wrapper around RS-Opt called SLIM has also been developed for large problem instances. The SLIM heuristic aims at shrinking the graph size of the network flow model to as small as possible. An optimal graph for SLIM is a sub-graph of the original full graph for RS-Opt in which all the arcs are required in an optimal solution. At convergence, SLIM would have yielded a minimal graph required by RS-Opt to produce the optimal solution. Before convergence, the reduced graph at each iteration is sub-optimal but is of a very small size such that RS-Opt can be executed very quickly. The exact solution of the sub-optimal graph is used as a basis to derive the reduced graph for the next iteration.

In experiments where RS-Opt alone can find the optimal solution S without using SLIM, the percentages of graph arcs in S that are also present in the reduced graphs derived in SLIM iterations have been compared. It was observed that such percentages may not be high even when the iterations were leveling off with objective values quite close to the optimal objective value yielded by RS-Opt. Although the branch-and-price process in the RS-Opt solver may have influenced the graph arc selection, the design of the objective function may have contributed to the observed behavior and alternative designs may have to be considered. This paper reports on further investigations focusing on alternative objective function designs for RS-Opt, the SLIM graph reduction heuristic, and in particular testing the use of the SLIM heuristic scheme as a new methodology for enhancing logical and domain expert reasoning for the evaluation of objective function designs.