Subgradient Methods
As mentioned above, the Lagrangian dual function is concave and piece-wise
linear. Existing methods for optimizing the dual function fall roughly into
three classes: subgradient, cutting plane, and bundle methods. Of these,
subgradient methods are commonly used to update the Lagrange multipliers
(i.e., to maximize the dual function) because of their simplicity, the speed
for computing a direction, and the global convergence property. With the
subproblem solutions for given multipliers 
, the subgradient g of
the dual function D is calculated by
where 
is an element of the subgradient. In subgradient
methods, multipliers are updated along the direction of the subgradient
with the step size determined by
where 
is the optimal dual cost, and 
, 
and
are respectively
the step size, dual cost and subgradient at iteration n. As shown in
Tomastik and Luh (1993), subgradient methods often zigzag across a ridge
(intersection of some facets) of the dual function. The slow convergence
rate (less than linear) of the subgradient methods causes these methods
to require many iterations to reach an optimum.
Facet Ascending Algorithm
By recognizing that the Lagrangian dual function is polyhedral concave, and
is made up of many facets, the facet ascending algorithm (FAA) finds the
intersection of adjacent facets (Tomastik and Luh, 1993). A subgradient
of one of the facets is then projected on the intersection to obtain an
ascending direction, and a line search technique is used to determine how
far to move along the direction. The FAA avoids the zigzagging behavior
of subgradient methods, and shows improved convergence. For large problems,
an intersection is usually formed by many facets. Finding such an
intersection is often difficult and requires many dual function
evaluations which are ``computationally expensive." Furthermore, the
ridges are short, causing slow convergence.
Bundle Methods
The bundle method (e.g., Hiriart-Urruty and Lemarechal, 1993) has the
fastest convergence rate among the three classes of methods. It
accumulates and utilizes the subgradients of points within a neighborhood
of the current iterate to find an 
-ascent direction (along which
the function value can increase at least by ), or to detect
within of the dual optimum ( -optimal). Finding such
a direction or detecting -optimal, however, requires solving a
number of quadratic programming problems with considerable complexity.
To reduce the complexity while maintaining the convergence of the bundle
method, the reduced-complexity bundle method (RCBM) finds an
-ascent direction by performing a projection of a subgradient
onto an appropriate subspace formed by the subgradients in the bundle
(Tomastik and Luh, 1996). Along the -ascent direction, a line
search technique is then used to determine the step size for updating
multipliers. Similar to FAA, the large number of dual function evaluations
required to accumulate the subgradients and to perform line search is
very time consuming, and hinders the applicability of the RCBM to very
large problems.
Interleaved Subgradient Method
The iterative resolution of the dual problem requires the dual function
to be evaluated many times, and each function evaluation involves solving
all the subproblems once (called one iteration). These dual function
evaluations are extremely ``expensive" for large problems. For example,
it takes about 
of total CPU time for a case with 82 parts and 14
machines. To efficiently utilize the expensive function evaluations, an
interleaved subgradient (ISG) method has been developed (Kaskavelis and
Caramanis, 1995). Instead of solving all subproblems before updating
multipliers, the ISG method updates multipliers after solving each
subproblem. At the high level, the multipliers are updated along the
direction of the subgradient. Numerical results show that the ISG method
converges much faster than a subgradient method, though algorithm
convergence has not yet been established.
Interleaved Conjugate Gradient Method
As mentioned earlier, the dual function is concave, piece-wise linear, and consists of many facets. Each possible solution of the relaxed problem corresponds to a facet. Because of the combinatorial nature of the original problem, the number of possible solutions of the relaxed problem and therefore the number of facets increases drastically as the problem size increases. The dual function thus approachesa smooth function. This ``smoothness" of the dual function motivates the use of optimization methods for smooth functions.
Among the methods for optimizing smooth functions, conjugate gradient methods have attractive convergence properties and computation efficiency. The conjugate directions are generated by
where 
and are the conjugate direction and gradient at
iteration n. The step size for updating multipliers is determined by
performing a line search along the conjugate direction.
By incorporating the ``interleave" concept with the conjugate gradient method, an interleaved conjugate gradient (ICG) method has been developed that utilizes the ``smooth" property of the dual function and efficiency of the interleaved method for problems of large sizes (e.g., 1000 multipliers or more). In this paper, the ICG method is used to update the multipliers. The ICG algorithm is summarized as follows.
replaced by the lowest feasible
cost obtained up to the current iteration.