A Discussion of Mathematical Programming References related to Railroad Freight Car Scheduling

The railroad freight car scheduling problem can be modeled as a multicommodity network flow problem (MCNF). At least five distinct approaches to the general MCNF are reported in the literature: specialized simplex methods, heuristic approaches, interior point methods, nonlinear penalty/barrier function methods, and subgradient optimization. Kennington (1978) and Assad (1978) survey some of the earlier literature on this subject.

It is well known that the "network simplex" algorithm maintains a triangular basis which requires only back substitution, not matrix inversion to solve. The specialized simplex based MCNF algorithms cannot entirely avoid the need to perform matrix inversion, but they try to minimize it by partitioning the matrix into network-structured and non network-structured components.

Hu (1963) gives an adaptation of the Out-of-Kilter algorithm (see Barr, Glover, and Klingman (1974)) to an MCNF. Some examples of specialized simplex algorithms include the approaches of Grigoriadis and White (1972), Elam, Glover and Klingman (1979), Glover and Klingman (1981), Chen and Saigal (1977), Chen and Engquist (1986), Hartman and Lasdon (1972), Brown and McBride (1984), McBride (1985), McBride and Mamer (1993), and Farvolden, Powell and Lustig (1993).

McBride's approach (1985) is generalized to handle any kind of a network subproblem with complicating side constraints. Network data is represented in standard link-node form. His implementation incorporates a network simplex approach for solving subproblems without requiring inversion, carefully linked into a standard simplex algorithm which handles the side constraints. Thus the size of the matrix which must be inverted is limited to the side constraints.

McBride and Mamer (1993) built a primal allocation heuristic to "jump start" the network simplex at a near optimal solution, further reducing execution time. This heuristic creates an allocation of capacity to each link proportional to the resources used by that link in a trial solution with all capacity constraints relaxed. He reports that the "heuristic is not only fast, but obtains very good solutions" and is apparently often used on a stand-alone basis. This heuristic works well for the manufacturing logistics problems McBride has been solving, but it is not clear if it would transfer to the car scheduling problem. Proportional capacity allocation would create many non-integral flows.

Barnhart and Sheffi (1993) propose a heuristic solution to a shipment routing problem in the LTL trucking industry which is very similar to the railroad freight car scheduling problem posed here. Each shipment is a separate commodity, moving over a time space network where the side constraints represent truck capacities. Barnhart's heuristic uses a link-node formulation, like McBride's, but it may terminate without fully solving the problem; also it apparently works best when network capacity far exceeds the amount required.

Farvolden's approach (see Farvolden, Powell and Lustig (1993)) solves the same trucking shipment routing problem as Barnhart's, but using a radically different method. First, Farvolden's approach is a systematic modification of the simplex method designed to produce an optimal linear programming solution, it is not a heuristic. Second, Farvolden reformulates the problem into a path-based formulation. Although Farvolden's algorithm does not incorporate network simplex, partitioning still allows specialization of pivot operations to gain efficiency. In most cases pivots can be completed without matrix inversion.

Farvolden (see Jones, Lustig, Farvolden and Powell (1993)) argues that her path based approach is so efficient that it can be used to solve MCNF problems, not just shipment routing problems. She proposes that general MCNF problems be decomposed into individual O-D pair flows, which are then solved quicker by her algorithm than using Dantzig-Wolfe decomposition with a network simplex algorithm.

Kwon (1994) outlines a railroad freight car scheduling problem similar to the one proposed here, formulated in path variables rather than link-node. He applies a standard column generation approach, similar to but less sophisticated than Farvolden's. Kwon has reported solution times of approximately 20 minutes for a small test problem, which still leaves considerable room for improvement.

Both McBride and Farvolden compare their algorithms' performance with that of the interior point code OB-1 (see Marsten, Subramanian, Lustig and Shanno (1990)). Although OB-1 clearly outperforms the standard simplex algorithm, both McBride and Farvolden argue that their customized codes compare favorably with OB-1 performance. McBride finds that "the purely interior point algorithms are less able to exploit sparsity and therefore take considerably more space." Farvolden's PPLP code "solved problems of the LTL data set up to 50 times faster than the OB-1 solution and problems of the second data set up to 64 times faster."

Nagamochi and Ibaraki (1989) establish sufficient, but not necessary conditions under which MCNF problems will have integral flows. In (1990) they define a class CB (capacity balanced networks) of planar directed networks, where K is the number of commodities and |V| is the number of nodes. A network in CB satisfies the following conditions: (1) The graph is directed, planar and acyclic. (2) All nodes without entering arcs and all nodes without outgoing arcs are located on the boundary of the outer face of the graph. (3) Each commodity has exactly one source and one sink, where the sink is located on the boundary. (4) Each node is capacity balanced. It is shown that this class of networks has the integral flow property. They give an example of a multi-item, multi-stage production scheduling problem which can be easily transformed into a class CB network through addition of some fictitious flows.

Nagamochi and Ibaraki's research does not focus on solution algorithms but rather states some general mathematical conditions under which integral solutions to MCNF problems can be expected. While this research cannot be immediately applied to the dynamic car scheduling problem, future theoretical developments along these lines should be watched closely to see if they might be applicable.

Linear programming (LP) approaches can be used to solve integer programs, particularly where the LP solution is expected to be integral or near integral. If some fractional variable is encountered, branch and bound can be used until an integral solution is obtained. Miliotis (1976) proposes a LP solution to the traveling salesman problem, adding anticycling constraints on an exception basis only when needed and using branch-and-bound to eliminate fractional variables. Schrage (1975) proposes an LP solution to variable upper bound problems such as the P-median, using a specialized simplex approach along with branch-and-bound. Using this type of approach, perhaps the integer MCNF problem (with a linear objective function) could be solved by embedding Farvolden's algorithm inside branch and bound. Many newer branch and bound applications are reported in the literature, but state-of-the-art research is more often based on Lagrangian rather than LP relaxations because these generally give tighter bounds and more rapid convergence.

Pinar and Zenios (1993) use a penalty function to eliminate non-network constraints from the MCNF problem. This approach converts a linear network problem with side constraints into a nonseparable nonlinear network problem without side constraints. This nonlinear problem is solved using a simplical decomposition algorithm which induces separability in the objective function. The penalty function approach has much in common with Lagrangian Relaxation, since both attempt to "price off" excess flows. Penalty functions are clearly the method of choice for MCNF problems with nonlinear costs, although linear costs can be handled as well. In closely related research, Schultz and Meyer (1991) propose a barrier-type algorithm.

Shapiro (1977) compares three methods for solving standard network optimization problems: out-of-kilter, primal-dual and subgradient optimization, but does not discuss the multicommodity case.

There are at least four references in the literature to subgradient methods applied to generalized network problems. Kennington and Shalaby (1977) utilize subgradient search to develop a resource-directive decomposition heuristic technique for obtaining good solutions to large multicommodity network cost minimization problems. The lower bound on optimality is taken from the solution to the unconstrained version of the problem, but apparently there is no attempt to tighten or update this lower bound as the algorithm proceeds. It is not a Lagrangian relaxation based method and does not enforce an integral flow requirement.

Ali, Kennington and Shetty (1988) worked on a single commodity network problem with complicating side constraints requiring equal flows on certain links. Furthermore they required integral flows on all links. By relaxing the side constraints they obtain single commodity network subproblems. The Lagrangian problem is solved using a standard subgradient procedure. They report obtaining tight bounds very quickly in spite of the fact their relaxation has the integrality property. They remark that the subgradient technique "is best suited for a real-world situation in which one must quickly produce near-feasible, near-optimal solutions."

Bertsekas and Tseng (1988) apply Lagrangian relaxation to standard single commodity network flow problems, with and without gains. They dualize the conservation of flow constraints and then use what amounts to a dual adjustment method to find optimal multipliers. Their method includes "Flow Augmentation" and "Price Adjustment" phases which are similar to methods proposed here for the car scheduling problem. The algorithm terminates when complementary slackness conditions are satisfied. Their relaxation obviously possesses the integrality property, but this poses no difficulty, since the solution to network problems with integer demands and capacities is also guaranteed to be integral.

The key to their success is that "the ascent directions used . . . lead to comparable improvement per iteration as the direction of maximal rate of ascent but can be computed with considerably less overhead." They report speedup factors of an order of magnitude over the fastest primal-dual codes available in 1985, this speedup factor increasing with problem size.

Bertsekas and Tseng (1988) (pg. 111) report a practical advantage of using relaxation methods:

For example, suppose we solve a problem and then modify it (by changing a few arc capacities and/or node supplies). To solve the modified problem using the relaxation method, we use as starting node prices the prices obtained from the earlier solution, and change the arc flows that violate the new capacity constraints to their new capacity bounds. Typically, this starting solution is close to optimal, and solution of the modified problem is extremely fast. By contrast, to solve the modified problem using primal simplex, one must provide a starting basis.

The basis obtained from the earlier solution will typically not be a basis for the modified problem. As a result, a new starting basis must be constructed, and there are no simple ways to choose this basis to be nearly optimal.

Thus once an initial solution has been obtained, a relaxation-based algorithm can quickly "bootstrap" itself from one solution to the next as status updates are reported.

Bryson (1991) analyzes the case of a single commodity network flow problem with a complicating "knapsack" side constraint, and the requirement that all flows must be integral. The problem is solved using a subgradient algorithm to obtain a "good" initial solution, then a dual simplex pivoting method is used to reach the final solution. Bryson's algorithm must be embedded into a branch and bound program to ensure optimality since the relaxation used has the integrality property, and the additional side constraint would almost certainly introduce fractional flows into the optimal LP solution.

Held, Wolfe and Crowder (1974) establish a convergence guarantee on the subgradient procedure, so that the subgradient procedure can often find a stronger lower bound than dual adjustment techniques which may not always converge to the optimum. However, the convergence of the subgradient approach can also slow down as the optimum is approached, at this time it may become more beneficial to switch over to another method such as a dual adjustment heuristic.

This is consistent with the findings of Etcheberry (1977) who reports that, in a set covering problem, the subgradient method was faster than linear programming unless a very high accuracy is required. This is compatible with the ultimate requirements for a real time process control system, where it is very important to get a good solution quickly, rather than to solve the problem optimally but outside the required system response time. Etcheberry continues that "the nature of the subgradient optimization algorithm eliminates the necessity of periodic reinversions or similar techniques (no numerical errors, no eta vectors, etc.) Anticycling procedures are not needed either. . . the previous results and considerations lead us to the conclusion that a subgradient iteration takes much less computational effort than a pivot iteration. (A subgradient optimization algorithm should also use less computer memory than an LP algorithm.)"

In some instances, such as Rosenwein (1986), the subgradient method is used first to get an approximate solution quickly, then a customized dual adjustment is used to "fine tune" the subgradient solution. In other cases, such as Kedia (1985), dual adjustment is used first, followed by the subgradient procedure to converge on the optimum. Dual adjustment heuristics tend to modify only one or a few variables at a time so that additional branch-and-bound nodes can be fathomed very quickly; a subgradient iteration may require more time than a dual adjustment procedure, but produce a better bound, and fathom nodes more quickly. The best choice of algorithm is highly problem specific.

Ryu (1993) applied Lagrangian relaxation to produce tight gaps in the Capacitated Plant Location Problem, Multi-Item Capacitated Lot Sizing Problem, Dynamic Production Scheduling Problem and Multilayer Plant Location Problem. Chajakis (1993) worked on a set of related problems in job shop scheduling, vehicle routing and forest management. His research is primarily concerned with the application of Lagrangian Substitution in the case where the integer subproblems have no specific structure but, nonetheless, yield very strong bounds. These subproblems are solved in reasonable time using a variety of standard approaches including "lifting" and double-contracting branching priorities. Ryu and Chajakis establish that Lagrangian relaxation can be successful even if the subproblems do not possess any special structure, provided the subproblem bounds are strong enough. It is then worthwhile to solve the subproblems even if a general purpose branch and bound solver must be used.

In contrast, Kraft’s (1998) Car Scheduling research will show that Lagrangian relaxation can be successful even for relatively weak relaxations possessing the integrality property, provided highly specialized algorithms can solve the subproblems quickly enough, and if the ultimate solution is expected to be integral or near-integral.

A Lagrangian relaxation has Geoffrion 's (1974) "integrality" property if, after the complicating constraints have been relaxed, the subproblems naturally have all integer solutions. This is true in Kraft (1998). Geoffrion showed that if a Lagrangian relaxation has this property, the LR bound can be no better than the linear program (LP) bound.

A number of successful relaxations having the "integrality" property are reported in the literature. These include the classical solution to the Traveling Saleman problem by Held and Karp (1970) (1971), work on the set covering problem by Etcheberry (1977), and the database location problem by Fisher and Hochbaum (1980). The solution to the Traveling Salesman problem by Held and Karp (1970) is successful because the LP solution gives a tight bound on the IP objective function, and the LR is much faster to solve than the LP. In many cases the LP has an exact integer solution, and in these cases the Lagrangian relaxation will converge to the optimum; otherwise, Held and Karp show that any duality gap corresponds to the possible existence of nonintegral extreme points. Held and Karp's second paper (1971) does not change the relaxation but proposes a faster subgradient search procedure for the optimal dual values. Held and Karp show how this relaxation can drastically reduce the size of branch and bound trees.

Fisher (1981) reports that Lagrangian Relaxations with the integrality property can be successful when:

• The LP closely approximates the original integer problem or

• The method used to optimize the dual problem (usually the subgradient method) is more powerful than methods for solving the (generally large) LP relaxation of the original problem.

Fisher and Hochbaum (1980) show that both conditions do not necessarily have to be met if the plan is to embed the Lagrangian Relaxation inside a branch and bound algorithm. While tighter bounds are always desirable in order to fathom branches sooner, a Lagrangian Relaxation may still produce considerable performance improvement if only it runs faster than the original LP. A branch and bound algorithm would still build the same tree as it would using a standard LP approach, only it would do so much faster using Lagrangian relaxation to solve the subproblems. This appears to be the strategy in Fisher and Hochbaum (1980). A Lagrangian relaxation having the integrality property may not initially produce a very tight bound, however that bound will tighten and approach the optimal value as branching proceeds.

Since branch and bound will not be utilized here, a tight bound is necessary, however, Nozick (1992) solved a closely-related network problem as a linear program, and simply by applying a rounding heuristic to generate feasible integer solutions, was able to obtain tight bounds compared to the original LP solution (within approximately 1%) . This result suggests that the LP bound will in fact give a reasonably tight bound on the optimal integer solution. Further, duality gaps of less than 1% have been quickly attained in computational tests of the subgradient algorithm on this problem. Due to complicating side constraints, the LP is very large and difficult to solve, but shortest path subproblems can be solved very quickly. In Kraft’s (1998) Car Scheduling research, both of Fisher's conditions for a successful relaxation are satisfied.

Note: This discussion is excerpted from Kraft (1998) Chapter 3.

Back to Math Programming References

Last Updated January 9, 2001